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

---

1. Problématique et Contexte

L'inférence statistique sur les Modèles de Blocs Stochastiques (SBM) repose souvent sur le spectre de la matrice d'adjacence normalisée, notée $A^*$. Dans la pratique, la matrice de probabilité vraie $B$ est inconnue et doit être remplacée par un estimateur « plug-in », noté $\hat{B}$.

Ce remplacement introduit deux types distincts d'erreurs de perturbation dans la matrice d'adjacence normalisée estimée :

1. Perturbation simple ($\Delta$) : Se produit lorsque $\hat{B}$ remplace $B$ uniquement au numérateur de la normalisation.
2. Perturbation composite ($\tilde{\Delta}$) : Se produit lorsque $\hat{B}$ remplace $B$ à la fois au numérateur et au dénominateur.

Le défi central réside dans le fait que la perturbation simple possède une structure de rang faible, tandis que la perturbation composite présente généralement une structure de rang plein. Cette différence structurelle fondamentale rend l'analyse asymptotique des statistiques de test (comme les plus grandes valeurs propres ou les statistiques spectrales linéaires) beaucoup plus complexe dans le cas composite, car les termes d'erreur ne s'annulent pas de la même manière.

2. Méthodologie : Le Cadre de Décomposition Unifié

Les auteurs proposent un cadre théorique novateur pour analyser et contrôler ces erreurs. La méthodologie repose sur trois piliers :

A. Analyse de la Somme des Carrés Totale

Les auteurs décomposent la somme des carrés totale de la matrice estimée ($\text{tr}(\hat{A}^2)$) en trois composantes :

1. La somme des carrés due à la matrice d'adjacence normalisée théorique ($\text{tr}(A^{*2})$).
2. Le terme croisé entre la matrice théorique et la perturbation ($\text{tr}(A^*\Delta)$ ou $\text{tr}(A^*\tilde{\Delta})$).
3. La somme des carrés due à la perturbation elle-même ($\text{tr}(\Delta^2)$ ou $\text{tr}(\tilde{\Delta}^2)$).

Découverte clé : Ils démontrent que pour la perturbation simple, le terme croisé $\text{tr}(A^*\Delta)$ est asymptotiquement négligeable ($o_p(1)$). En revanche, pour la perturbation composite, le terme croisé $\text{tr}(A^*\tilde{\Delta})$ n'est pas négligeable et converge vers une distribution normale.

B. La Décomposition Unifiée de la Perturbation Composite

Pour expliquer et maîtriser le comportement non négligeable de $\tilde{\Delta}$, les auteurs proposent une décomposition structurée de la matrice de perturbation composite :
$$\tilde{\Delta} = \check{A} + \Delta + \check{\Delta}$$
Où :

• $\Delta$ est la perturbation simple (rang faible).
• $\check{A}$ est une matrice de biais de rang plein introduite par le facteur de redimensionnement (le dénominateur). C'est ce terme qui couple l'erreur d'estimation avec les fluctuations aléatoires de $A^*$.
• $\check{\Delta}$ est une matrice de biais de la perturbation simple (rang faible).

Cette décomposition permet d'isoler le terme dominant ($\check{A}$) responsable de la non-négligeabilité du terme croisé.

C. Application aux Statistiques de Test

Ce cadre est appliqué à deux classes majeures de statistiques de test :

1. La statistique de la plus grande valeur propre ($\lambda_1$).
2. La statistique spectrale linéaire (basée sur la trace, ex: $\text{tr}(\hat{A}^3)$).

3. Résultats Principaux

A. Amélioration des Conditions de Convergence pour $\lambda_1$

• Contexte : La loi de Tracy-Widom régit la distribution de la plus grande valeur propre.
• Résultat : Les auteurs améliorent la condition existante de convergence de $K = O(n^{1/6-\tau})$ (où $K$ est le nombre de communautés et $n$ la taille du réseau) vers le taux optimal $K = o(n^{1/6})$.
• Distinction :
  • Pour la perturbation simple, ce taux optimal est atteint sans condition supplémentaire.
  • Pour la perturbation composite, un hypothèse d'équilibre des communautés (Assomption 3) est requise pour contrôler la norme spectrale de la matrice de biais $\check{A}$. Cela souligne la sensibilité accrue des valeurs extrêmes aux perturbations de rang plein.

B. Preuve Rigoureuse de la Normalité Asymptotique pour les Statistiques Linéaires

• Défi : Prouver que tous les termes d'erreur induits par l'estimation de $B$ sont asymptotiquement négligeables pour la statistique spectrale linéaire.
• Résultat : En utilisant la décomposition unifiée, les auteurs contrôlent systématiquement chaque terme d'erreur (y compris ceux impliquant $\check{A}$). Ils démontrent que, sous la condition $K = o(n^{1/2})$, la statistique spectrale linéaire estimée conserve sa distribution normale asymptotique, même lorsque $B$ est estimé. Cela valide théoriquement l'utilisation pratique de ces tests dans des scénarios réalistes où les paramètres sont inconnus.

C. Comportement Asymptotique des Termes d'Erreur

• Termes croisés : $\text{tr}(A^*\Delta) \to 0$ (négligeable) vs $\text{tr}(A^*\tilde{\Delta}) \to N(0,1)$ (dominant).
• Termes de somme des carrés : Bien que $\text{tr}(\Delta^2)$ et $\text{tr}(\tilde{\Delta}^2)$ soient du même ordre de grandeur, ils convergent vers des distributions limites différentes (la première suit une loi du Chi-deux, la seconde non).

4. Contributions Clés

1. Révélation d'une distinction fondamentale : Mise en évidence que la transition d'une perturbation simple à une perturbation composite change radicalement la nature asymptotique des termes croisés (négligeable vs non négligeable) en raison de l'apparition d'une matrice de biais de rang plein.
2. Développement d'un cadre unifié : Création d'une décomposition mathématique ($\tilde{\Delta} = \check{A} + \Delta + \check{\Delta}$) qui permet d'isoler et de contrôler les sources d'erreur de manière structurée.
3. Optimisation des bornes théoriques : Amélioration de la condition de croissance du nombre de communautés $K$ pour la convergence de Tracy-Widom, passant d'un taux sous-optimal au taux optimal $o(n^{1/6})$.
4. Justification théorique complète : Fourniture d'une preuve rigoureuse de la normalité asymptotique pour les statistiques spectrales linéaires avec estimateurs plug-in, comblant un vide théorique majeur dans la littérature.

5. Signification et Impact

Ce travail est significatif car il fournit des garanties théoriques plus précises pour l'inférence sur les réseaux réels, où les paramètres du modèle sont toujours inconnus et doivent être estimés.

• Pratique : Il justifie l'utilisation de tests d'hypothèse basés sur le spectre (comme les tests de qualité d'ajustement ou de détection de communautés) même lorsque la matrice de probabilité est estimée, à condition que les conditions d'équilibre soient respectées.
• Généralité : Le cadre de décomposition proposé n'est pas limité aux SBM unidirectionnels. Il offre un principe général pour traiter les erreurs d'estimation dans d'autres modèles à variables latentes, les problèmes de tests à deux échantillons, les réseaux dirigés et l'estimation de covariance en haute dimension reposant sur des matrices normalisées.

En résumé, l'article transforme la compréhension des erreurs d'estimation dans les modèles de réseaux en passant d'une approche heuristique à une analyse structurelle rigoureuse, distinguant clairement les effets des perturbations de rang faible et de rang plein.