Résumé technique : Test d'hypothèse à deux échantillons pour l'égalité de sous-espaces dans les données de réseaux

Formulation du problème

L'article traite du défi fondamental consistant à déterminer si deux ensembles de données de type réseau indépendantes partagent les mêmes structures de connectivité latentes sous-jacentes, spécifiquement leurs structures de communautés, même lorsque leurs probabilités d'arêtes diffèrent de manière significative. Dans de nombreuses applications, comme la comparaison de réseaux sociaux entre différentes plateformes ou l'analyse de la connectivité aéroportuaire au fil du temps, les « communautés » (groupes latents) peuvent rester stables tandis que la densité ou les probabilités de connexion spécifiques fluctuent.

Formellement, soient $A^{(1)}$ et $A^{(2)}$ deux matrices d'adjacence indépendantes de taille $n \times n$, générées par des matrices de probabilité symétriques de rang faible $P^{(1)}$ et $P^{(2)}$ de rang $k$. Les auteurs proposent de tester l'hypothèse nulle selon laquelle les espaces colonnes (sous-espaces) engendrés par les vecteurs propres principaux de ces matrices de probabilité sont identiques :
$$H_0: V^{(1)}(V^{(1)})^\top = V^{(2)}(V^{(2)})^\top$$
versus l'hypothèse alternative $H_1$ où les sous-espaces diffèrent. Ici, $V^{(i)} \in \mathbb{R}^{n \times k}$ contient les vecteurs propres orthonormés correspondant aux valeurs propres non nulles de $P^{(i)}$.

Cette hypothèse est démontrée comme étant équivalente au test de l'égalité des structures de communauté dans les modèles de blocs stochastiques (SBM) et les modèles de blocs stochastiques à appartenance mixte (MMSBM), à permutation et mise à l'échelle près, ainsi qu'à l'égalité des espaces de caractéristiques latentes dans les graphes de produit scalaire aléatoire généralisés (GRDPG).

Méthodologie

Statistique de test

La statistique de test proposée est basée sur la norme de Frobenius de la différence entre les matrices de projection spectrale empiriques des deux réseaux. Soit $\hat{V}^{(i)}$ la matrice des $k$ vecteurs propres empiriques principaux de $A^{(i)}$. La statistique est définie par :
$$T_n := \| \hat{V}^{(1)}(\hat{V}^{(1)})^\top - \hat{V}^{(2)}(\hat{V}^{(2)})^\top \|_F^2$$

Théorie asymptotique

La principale contribution théorique est un théorème limite établissant que, sous un centrage et une mise à l'échelle appropriés, $T_n$ converge en distribution vers une variable aléatoire gaussienne standard. Ce résultat est valable sous les conditions suivantes :

1. Parcimonie (Sparsity) : Le degré attendu moyen croît au moins logarithmiquement avec le nombre de sommets ($n\rho_n \gg \log n$).
2. Échelle des valeurs propres : Les valeurs propres non nulles des matrices de probabilité évoluent linéairement avec $n\rho_n$.
3. Incohérence : Les lignes des vecteurs propres de la population sont uniformément réparties (une condition satisfaite par les tailles de communautés équilibrées dans les modèles de blocs).

La moyenne asymptotique ($\mu_2$) et la variance ($\sigma_2^2$) de la statistique sont dérivées explicitement en termes de paramètres de la population. La dérivation repose sur une nouvelle expansion en série matricielle de la différence de projection, décomposant la statistique en un terme de second ordre dominant et des termes de reste d'ordre supérieur. La preuve utilise un théorème de limite centrale de type martingale pour établir la limite gaussienne pour le terme de second ordre, tout en démontrant que les termes d'ordre supérieur sont asymptotiquement négligeables.

Estimation pilotée par les données

Pour rendre ce test opérationnel, les auteurs proposent des estimateurs cohérents par substitution (plug-in) pour la moyenne et la variance asymptotiques. Ces estimateurs remplacent les vecteurs propres et les valeurs propres de la population inconnus par leurs contreparties empiriques. La cohérence de ces estimateurs est prouvée sous une hypothèse de « régime dense » légèrement plus forte ($n\rho_n \gg \sqrt{n}$), qui garantit que l'erreur d'estimation ne distord pas la distribution limite.

Analogue à un échantillon

L'article établit également un théorème limite correspondant pour un test à un échantillon, qui évalue la distance entre un sous-espace empirique et un sous-espace de référence connu. Ce résultat sert de fondement technique à la preuve pour deux échantillons et est présenté comme un résultat d'intérêt indépendant, fournissant une base pour les intervalles de confiance sur la distance de projection.

Principales contributions

1. Un test à deux échantillons pour les sous-espaces communs : Les auteurs proposent un test spectral pour l'égalité des espaces colonnes de matrices de probabilité de rang faible. Ils prouvent sa normalité asymptotique et fournissent des estimateurs cohérents pour ses paramètres, permettant un contrôle rigoureux de l'erreur de Type I sans recourir à des méthodes de rééchantillonnage coûteuses en calcul comme le bootstrap.
2. Application aux familles de modèles de blocs : Le cadre s'avère applicable tant aux SBM qu'aux MMSBM. Le test détecte efficacement les changements de structure de communauté (assignations de membres), même lorsque les probabilités d'arêtes varient, distinguant ainsi les changements structurels des simples fluctuations de densité.
3. Théorème limite pour les distances de projection : L'article dérive un théorème limite pour la distance de projection entre les sous-espaces propres empiriques et réels sous un bruit de Bernoulli. Cela généralise les résultats précédents qui supposaient souvent un bruit gaussien ou se concentraient sur des vecteurs propres individuels, fournissant une théorie de distribution globale pour les erreurs d'estimation de sous-espaces.

Résultats

Simulations numériques

Les auteurs valident la méthode par des simulations approfondies sur des données synthétiques :

• Modèles de blocs stochastiques (SBM) : Le test démontre une forte puissance pour distinguer les réseaux ayant des structures de communauté différentes. Même de petites perturbations (réassignation d'un petit nombre de nœuds) sont détectées avec une haute probabilité à mesure que la densité du réseau augmente.
• Modèles de blocs stochastiques à appartenance mixte (MMSBM) : Le test détecte avec succès les changements dans les profils d'appartenance mixte. Les simulations indiquent que, bien que le test soit efficace, la détection des changements dans les régimes d'assignation souple (MMSBM) nécessite des perturbations légèrement plus importantes ou des réseaux plus denses par rapport aux régimes d'assignation stricte (SBM).
• Contrôle de la taille : La taille empirique du test reste proche du niveau de signification nominal ($\alpha = 0,05$) et s'améliore à mesure que la densité du réseau augmente.

Application au monde réel

La méthodologie est appliquée aux données de vols domestiques américains (janvier 2016 – septembre 2021) pour analyser le réseau aéroportuaire.

• Périodes stables : Les comparaisons des réseaux de vols en janvier et en novembre pour différentes années ne montrent aucune différence structurelle statistiquement significative, indiquant des structures de communauté stables.
• Disruption structurelle : Les comparaisons impliquant juin 2020 (le pic de la perturbation due à la pandémie de COVID-19) révèlent des différences statistiquement significatives dans la structure du sous-espace du réseau par rapport aux autres années. Cela confirme la capacité du test à détecter des ruptures structurelles majeures dans les données de réseaux réels.

Signification et affirmations

L'article affirme fournir un cadre rigoureux et efficace sur le plan computationnel pour le test d'hypothèses sur les réseaux, qui dépasse le test de l'égalité de paramètres spécifiques (par exemple, les probabilités d'arêtes exactes) pour tester la stabilité de la structure géométrique sous-jacente (le sous-espace).

• Robustesse : Contrairement aux méthodes qui reposent sur l'appariement de paramètres exacts ou supposent des structures de bruit spécifiques (comme le bruit gaussien), cette approche est robuste aux fluctuations de densité d'arêtes et est adaptée au bruit de Bernoulli hétéroscédastique inhérent aux données de réseaux.
• Nouveauté théorique : La dérivation de la limite gaussienne pour la distance de projection sous un bruit de Bernoulli est présentée comme une avancée théorique significative, comblant une lacune dans la littérature où de tels résultats de distribution n'étaient auparavant pas disponibles pour ce contexte spécifique.
• Utilité pratique : En fournissant des distributions limites à forme fermée et des estimateurs cohérents, la méthode évite la charge de calcul des tests de permutation ou des procédures de bootstrap, ce qui la rend scalable pour les grands ensembles de données de réseaux.

Les auteurs notent que, bien que leurs résultats soient établis sous un bruit de Bernoulli indépendant et borné, les travaux futurs pourraient étendre ces théorèmes limites à des distributions à queue lourde ou à des structures d'arêtes dépendantes. De plus, l'analyse actuelle suppose que le rang $k$ est connu, et l'intégration de l'incertitude de la sélection du rang demeure un défi ouvert.