From Simple to Composite Perturbations: A Unified Decomposition Framework for Stochastic Block Models

Titel: Van Simpel tot Samengestelde Perturbaties: Een Unificerend Decompositieframe voor Stochastische Blokmodellen

1. Probleemstelling

In de statistische inferentie voor stochastische blokmodellen (SBM) is de spectrum van de genormaliseerde adjacentiematrix $A^*$ cruciaal voor hypothesetoetsing en community-detectie. In de theorie wordt vaak aangenomen dat de ware waarschijnlijkheidsmatrix $B$ bekend is. In de praktijk is $B$ echter onbekend en moet deze worden vervangen door een schatter $\hat{B}$ (een "plug-in" schatter).

Deze vervanging introduceert twee fundamenteel verschillende soorten schattingsfouten (perturbaties) in de genormaliseerde adjacentiematrix:

1. Simpel perturbatie ($\Delta$): Ontstaat wanneer $\hat{B}$ alleen in de teller van de normalisatie wordt gebruikt.
2. Samengestelde perturbatie ($\tilde{\Delta}$): Ontstaat wanneer $\hat{B}$ zowel in de teller als de noemer wordt gebruikt.

De bestaande literatuur heeft vaak moeite om de asymptotische eigenschappen van deze perturbaties nauwkeurig te analyseren, vooral omdat de samengestelde perturbatie een complexere structuur heeft dan de simpele variant. Het doel van dit artikel is om deze verschillen te kwantificeren en een unificerend raamwerk te ontwikkelen om de inferentie onder beide regimes te verbeteren.

2. Methodologie

De auteurs ontwikkelen een nieuw analytisch raamwerk gebaseerd op de decompositie van de totale som van kwadraten ($\text{tr}(M^2)$) en de spectrale eigenschappen van de matrices.

• Decompositie van de Samengestelde Perturbatie:
  De kern van de methode is het inzien dat de samengestelde perturbatiematrix $\tilde{\Delta}$ niet zomaar een schaling is van de simpele perturbatie $\Delta$. De auteurs ontleden $\tilde{\Delta}$ in drie componenten:
  $$\tilde{\Delta} = \check{A} + \Delta + \check{\Delta}$$
  Waarbij:

  • $\Delta$: De simpele perturbatie (laag-rang).
  • $\check{A}$: Een bias-matrix van de genormaliseerde adjacentiematrix $A^*$, veroorzaakt door de schaling in de noemer. Deze matrix is vol-rang (full-rank).
  • $\check{\Delta}$: Een bias-matrix van $\Delta$.

• Analyse van Kruistermen:
  Een cruciale stap is het analyseren van de kruisterm $\text{tr}(A^* \tilde{\Delta})$. De auteurs tonen aan dat bij simpele perturbaties deze term asymptotisch verwaarloosbaar is, maar bij samengestelde perturbaties niet verwaarloosbaar is. Dit komt doordat de vol-rang component $\check{A}$ koppelt met de willekeurige fluctuaties van $A^*$, wat leidt tot een dominante term die convergeert naar een normale verdeling.

• Technische Benadering:
  Door deze gestructureerde decompositie kunnen de auteurs elke bron van fout (bias, variatie, schaling) term-voor-term controleren. Dit stelt hen in staat om de spectrale normen van de perturbatiematrices nauwkeurig te begrenzen en de asymptotische verdelingen van teststatistieken af te leiden.

3. Belangrijkste Bijdragen

Het artikel levert vier hoofdcontributies:

1. Onderscheid tussen Simpele en Samengestelde Perturbaties:
   De auteurs onthullen een fundamenteel verschil: terwijl de kruisterm $\text{tr}(A^* \Delta)$ asymptotisch verwaarloosbaar is ($o_p(1)$), is de samengestelde kruisterm $\text{tr}(A^* \tilde{\Delta})$ van orde $O_p(1)$ en niet verwaarloosbaar. Bovendien convergeren de som-van-kwadraten termen $\text{tr}(\Delta^2)$ en $\text{tr}(\tilde{\Delta}^2)$, hoewel ze van dezelfde orde zijn, naar verschillende limietverdelingen.

2. Unificerend Decompositieframe:
   Ze introduceren de decompositie $\tilde{\Delta} = \check{A} + \Delta + \check{\Delta}$. Dit raamwerk onthult dat de schaling in de noemer een nieuwe, vol-rang bias-matrix ($\check{A}$) introduceert. Dit verklaart waarom de samengestelde perturbatie een fundamenteel andere asymptotische impact heeft dan de simpele variant.

3. Verbeterde Rate voor de Grootste Eigenwaarde:
   Voor de teststatistiek gebaseerd op de grootste eigenwaarde ($\lambda_1$), verbeteren ze de bestaande voorwaarde voor de convergentie naar de Tracy-Widom-verdeling.

   • Van $K = O(n^{1/6-\tau})$ naar de optimale rate $K = o(n^{1/6})$.
   • Voor het samengestelde geval is een extra balansvoorwaarde voor de community-groottes nodig (Assumptie 3) om de invloed van de vol-rang bias-matrix $\check{A}$ te beheersen.

4. Rigoureuze Asymptotische Normaliteit voor Lineaire Spectrale Statistieken:
   Ze leveren een volledig bewijs voor de asymptotische normaliteit van de lineaire spectrale statistiek (zoals voorgesteld door Wu en Hu) wanneer $B$ wordt geschat. Het grootste technische obstakel was het systematisch controleren van alle fouttermen veroorzaakt door de perturbatie. Het unificerend raamwerk maakt het mogelijk om aan te tonen dat alle perturbatie-geïnduceerde fouten asymptotisch verwaarloosbaar zijn, zelfs in het samengestelde geval.

4. Resultaten

• Grootste Eigenwaarde ($\lambda_1$):
  • Onder simpele perturbatie convergeert $n^{2/3}(\lambda_1(\bar{A}) - 2)$ naar de Tracy-Widom verdeling ($TW_1$) onder de voorwaarde $K = o(n^{1/6})$.
  • Onder samengestelde perturbatie geldt hetzelfde resultaat, mits de community-groottes gebalanceerd zijn (geen enkele community is te groot, specifiek $n_k \leq c_2 n / \log K$). Zonder deze balans zou de vol-rang bias de limietverdeling verstoren.
• Lineaire Spectrale Statistiek ($\text{tr}(A^3)$):
  • Voor zowel simpele als samengestelde perturbaties geldt dat de gestandaardiseerde statistiek convergeert naar een standaardnormale verdeling $N(0,1)$ onder de voorwaarde $K = o(n^{1/2})$.
  • In tegenstelling tot de grootste eigenwaarde, vereist de lineaire statistiek voor het samengestelde geval geen extra balansvoorwaarde; de fouttermen zijn hier van nature verwaarloosbaar.
• Simulaties:
  De simulaties bevestigen de theoretische bevindingen: de kruisterm bij samengestelde perturbatie volgt een normale verdeling (niet verwaarloosbaar), terwijl deze bij simpele perturbatie een chi-kwadraat verdeling volgt die verwaarloosbaar wordt bij grotere $n$.

5. Betekenis en Impact

Dit artikel biedt een nieuw theoretisch fundament voor de analyse van netwerkmodellen waarbij parameters worden geschat.

• Praktische Relevantie: Het rechtvaardigt het gebruik van plug-in schatters in hypothesetoetsing voor netwerken, aangezien het aantoont dat onder specifieke voorwaarden de inferentie robuust blijft.
• Theoretische Vooruitgang: Het raamwerk lost het probleem op dat de "naive" behandeling van schattingsfouten in genormaliseerde matrices (waarbij teller en noemer beide worden geschat) leidt tot onjuiste asymptotische conclusies.
• Generaliseerbaarheid: De auteurs suggereren dat hun aanpak (het isoleren van specifieke bias-termen veroorzaakt door normalisatie) toepasbaar is op bredere problemen, zoals tweestalen toetsing, gerichte netwerken, en andere latent variable modellen die afhankelijk zijn van genormaliseerde matrices.

Kortom, dit werk verduidelijkt de complexe interactie tussen schattingsfouten en spectrale eigenschappen in netwerken en biedt een gestructureerde methode om deze fouten te beheersen, wat leidt tot scherpere en betrouwbaardere theoretische garanties.