Nonparametric two-sample hypothesis testing for low-rank random graphs of differing sizes

Each language version is independently generated for its own context, not a direct translation.

🕵️‍♂️ Le Détective des Réseaux : Comment comparer deux mondes différents ?

Imaginez que vous êtes un détective chargé de comparer deux grandes villes, disons Paris et Tokyo.

Paris a 2 millions d'habitants.
Tokyo en a 37 millions.

Vous ne pouvez pas comparer personne par personne (il n'y a pas de correspondance parfaite entre un Parisien et un Tokyoïte). Pourtant, vous voulez savoir : « Est-ce que la façon dont les gens se connectent dans ces deux villes est fondamentalement la même ? »

Peut-être que dans les deux villes, les gens aiment se regrouper par quartier, ou peut-être que dans l'une, les gens sont très connectés entre eux, tandis que dans l'autre, ils sont isolés.

C'est exactement le problème que résolvent les auteurs de cet article (Joshua Agterberg, Minh Tang et Carey Priebe). Ils ont créé un outil mathématique pour comparer deux réseaux (comme des cartes de relations) de tailles différentes, même si ces réseaux sont très "vides" (peu de connexions) ou très complexes.

🧩 1. Le Problème : Des cartes de tailles différentes

Dans le monde réel, les données en réseau (amis sur Facebook, neurones dans le cerveau, citations entre scientifiques) sont souvent de tailles différentes.

Le défi : Comment dire que deux réseaux sont "pareils" quand l'un a 100 nœuds et l'autre 10 000 ?
L'obstacle : Souvent, les mathématiciens supposent que les réseaux sont denses (pleins de liens). Mais dans la réalité, la plupart des réseaux sont rares (sparse) : un individu n'a que quelques amis parmi des milliers de possibilités. De plus, certains réseaux ont des structures "négatives" ou complexes que les anciennes méthodes ne pouvaient pas gérer.

🔍 2. La Solution : La "Carte de l'Âme" (Embedding)

Pour comparer ces deux villes, les auteurs utilisent une technique géniale appelée l'incorporation spectrale (ou spectral embedding).

L'analogie de la carte de l'âme :
Imaginez que vous prenez chaque ville et que vous la transformez en une carte simplifiée où chaque habitant est un point dans un espace à 3 dimensions (comme une carte géographique).

Dans cette carte, les gens qui se ressemblent (qui ont les mêmes types d'amis) sont proches les uns des autres.
Les gens qui sont différents sont loin.

Même si Paris a 2 millions de points et Tokyo 37 millions, la forme globale de la carte (la distribution des points) peut être identique. Si la forme est la même, alors les deux réseaux viennent de la même "distribution" (même modèle de comportement).

🔄 3. Le Tour de Magie : L'Alignement (Optimal Transport)

Il y a un petit problème : même si les deux cartes ont la même forme, elles peuvent être tournées différemment dans l'espace.

La carte de Paris pourrait être tournée de 90 degrés par rapport à celle de Tokyo.
Si vous les superposez sans les redresser, elles sembleront différentes, alors qu'elles sont identiques !

C'est là que les auteurs introduisent leur innovation majeure : l'Optimal Transport (Transport Optimal).

L'analogie du déménagement :
Imaginez que vous devez déménager les meubles d'un appartement (Paris) pour qu'ils correspondent exactement à la disposition d'un autre appartement (Tokyo).

Vous ne voulez pas juste déplacer les meubles au hasard.
Vous voulez trouver le chemin le plus court et le plus efficace pour tourner et déplacer les meubles afin qu'ils s'alignent parfaitement.

Les auteurs ont créé un algorithme qui fait exactement cela : il trouve la meilleure rotation pour aligner la "carte de l'âme" de Paris sur celle de Tokyo. Une fois alignées, on peut comparer les deux cartes point par point.

📊 4. Le Test Statistique : La "Distance de Goût"

Une fois les cartes alignées, comment savoir si elles sont vraiment identiques ?
Les auteurs utilisent une mesure appelée Maximum Mean Discrepancy (MMD).

L'analogie du test de dégustation :
Imaginez que vous avez deux grands bols de soupe.

Vous prenez une cuillère de soupe dans le bol A (Paris) et une dans le bol B (Tokyo).
Vous goûtez des milliers de cuillères.
Si les saveurs (la distribution des points) sont identiques, les cuillères se ressembleront toujours.
Si les soupes sont différentes (l'une est salée, l'autre sucrée), vous le remarquerez rapidement.

Leur test mathématique fait la même chose : il compare des milliers de "cuillères" (des points sur les cartes) pour voir si les deux réseaux proviennent de la même "recette".

🚀 5. Pourquoi c'est important ?

Avant cet article, les méthodes existantes échouaient dans deux cas :

Quand les réseaux sont très vides (peu de liens) : C'est le cas de la plupart des réseaux réels (comme les interactions neuronales ou les réseaux sociaux où la plupart des gens ne se connaissent pas).
Quand les structures sont complexes : Certaines mathématiques "négatives" (des eigenvalues négatifs) faisaient planter les anciens algorithmes.

Leur résultat :

Ils ont prouvé que leur méthode fonctionne même pour des réseaux très vides.
Ils ont prouvé que leur méthode fonctionne même si les réseaux ont des structures mathématiques complexes (négatives).
Ils ont montré que leur algorithme converge rapidement (il trouve la bonne réponse en peu de temps).

🎯 En résumé

Cet article nous donne un nouvel outil de comparaison universel.
Imaginez que vous avez deux puzzles de tailles différentes, avec des pièces de formes différentes. Cet article vous dit :

Comment transformer ces puzzles en une image lisse (l'embedding).
Comment tourner cette image pour qu'elle soit bien alignée (l'Optimal Transport).
Comment vérifier avec certitude si les deux puzzles représentent le même paysage, même si l'un est beaucoup plus petit ou plus vide que l'autre.

C'est une avancée majeure pour les neurosciences (comparer des cerveaux de tailles différentes), les réseaux sociaux, et toute science qui utilise des données en réseau.

Each language version is independently generated for its own context, not a direct translation.

1. Problématique et Contexte

L'article aborde le problème fondamental de la statistique des réseaux : déterminer si deux graphes observés, notés $A^{(1)}$ (de taille $n \times n$ ) et $A^{(2)}$ (de taille $m \times m$ ), proviennent de la même distribution sous-jacente.

Défis majeurs :

Tailles différentes : Contrairement aux travaux antérieurs qui supposent souvent que les graphes partagent le même ensemble de sommets (paradigme des "paires appariées"), cet article traite le cas où $n \neq m$ et où il n'existe pas d'alignement a priori entre les sommets.
Modèles de rang faible : Les graphes sont générés selon des modèles à rang faible (matrices de probabilité d'arêtes de rang $d \ll n$ ), incluant les modèles de blocs stochastiques (SBM), les graphons de rang fini et les graphes à produit scalaire aléatoire (RDPG).
Non-identifiabilité et géométrie indéfinie : Dans le cadre des Generalized Random Dot Product Graphs (GRDPG), les positions latentes ne sont identifiables qu'à une transformation près par un groupe orthogonal indéfini $O(p, q)$ (où $p+q=d$ ). La présence de valeurs propres négatives dans la matrice de probabilité complique l'alignement des embeddings spectraux, car les transformations orthogonales standards ne suffisent pas.
Régimes de parcimonie : Les graphes réels sont souvent parcimonieux (le degré moyen croît plus lentement que $n$ ). La plupart des méthodes existantes échouent ou nécessitent des hypothèses trop restrictives (valeurs propres distinctes, graphes denses) pour ces régimes.

2. Méthodologie

Les auteurs proposent un test d'hypothèse non paramétrique basé sur la Discrépance Maximale de Moyenne (MMD) appliquée aux embeddings spectraux des graphes.

A. Cadre Théorique : GRDPG

Le modèle utilisé est le GRDPG. Une matrice d'adjacence $A$ est générée conditionnellement à des positions latentes $X \in \mathbb{R}^d$ i.i.d. selon une distribution $F_X$ :
$P(A_{ij}=1 | X) = \alpha_n X_i^\top I_{p,q} X_j$
où $I_{p,q} = \text{diag}(I_p, -I_q)$ et $\alpha_n$ est un facteur de parcimonie. Ce cadre englobe les SBM, les DCSBM (Degree-Corrected SBM) et les graphons de rang fini.

B. Statistique de Test

La procédure se déroule en plusieurs étapes :

Embedding Spectral (ASE) : On calcule la décomposition spectrale des matrices d'adjacence $A^{(1)}$ et $A^{(2)}$ . On obtient les matrices d'embeddings $\hat{X}$ et $\hat{Y}$ (les $d$ vecteurs propres normalisés par les valeurs propres).
Estimation de l'Alignement (Optimal Transport) : En raison de la non-identifiabilité (rotation et signe des vecteurs propres), les embeddings $\hat{X}$ $\hat{X}$ et $\hat{Y}$ $\hat{Y}$ ne sont pas directement comparables. Les auteurs proposent d'estimer une matrice de rotation orthogonale $\hat{W}$ $\hat{W}$ qui aligne les distributions des lignes de $\hat{X}$ $\hat{X}$ et $\hat{Y}$ $\hat{Y}$ .
- Ce problème est formulé comme un problème de Transport Optimal (distance de Wasserstein) entre les distributions empiriques des lignes, restreint aux matrices orthogonales (Problème Procrustéen).
- Une version régularisée par entropie (algorithme de Sinkhorn) est utilisée pour résoudre efficacement ce problème itérativement.
Calcul de la Statistique U : Une fois alignés, on calcule une statistique U à deux échantillons utilisant un noyau caractéristique $\kappa$ (ex: noyau gaussien) sur les lignes des embeddings alignés :
$U_{n,m}(\hat{X}, \hat{Y}\hat{W}) = \frac{1}{n(n-1)}\sum_{i \neq j} \kappa(\hat{X}_i, \hat{X}_j) - \frac{2}{nm}\sum_{i,k} \kappa(\hat{X}_i, \hat{Y}_k \hat{W}) + \dots$
Décision : La distribution nulle de la statistique est approximée par un test de permutation (bootstrap) sur les distributions empiriques alignées.

3. Contributions Clés

Formalisation de l'égalité de distribution : Définition rigoureuse de l'égalité de distribution pour des graphes de tailles différentes sous le cadre GRDPG, tenant compte de l'invariance par transformation orthogonale indéfinie ( $O(p, q)$ ).
Extension aux graphes parcimonieux et indéfinis : Contrairement à l'article de référence Tang et al. (2017b), cette méthode fonctionne pour des graphes parcimonieux (degré moyen $\gg \log^4(n)$ ) et accepte des matrices de probabilité avec des valeurs propres négatives et répétées.
Consistance uniforme : Démonstration que le test est consistant (puissance tend vers 1) sous des alternatives fixes et locales, même lorsque les graphes sont de tailles différentes et de régimes de parcimonie variés.
Algorithme d'alignement : Proposition d'un algorithme basé sur le transport optimal régularisé pour estimer la matrice de rotation $\hat{W}$ , avec des garanties de convergence prouvées lorsque l'initialisation est proche de l'optimum global.
Gestion de la non-identifiabilité : Preuve que, bien que le modèle GRDPG implique des transformations orthogonales indéfinies, l'utilisation des embeddings spectraux et de l'alignement optimal permet de se ramener à des transformations orthogonales standards ( $O(d)$ ) pour la limite asymptotique, simplifiant ainsi l'analyse théorique.

4. Résultats Théoriques et Asymptotiques

Les auteurs établissent deux régimes de convergence principaux :

Régime de parcimonie (Théorème 3.1) :
- Hypothèse : $\min(n\alpha_n, m\beta_m) \gg \log^4(\max(n, m))$ .
- Résultat : La statistique, correctement normalisée par $(m\beta_m + n\alpha_n)$ , converge presque sûrement vers 0 sous l'hypothèse nulle ( $H_0: F_X \simeq F_Y$ ) et vers une constante positive sous l'alternative.
- La normalisation est plus lente que dans le cas dense en raison de la difficulté d'estimer les positions latentes dans les graphes clairsemés.
Régime dense (Corollaire 3.3) :
- Hypothèse : Le degré moyen croît plus vite que $\sqrt{n}\log(n)$ .
- Résultat : La statistique converge avec la normalisation classique $(n+m)$ , similaire aux résultats pour les données euclidiennes (Gretton et al., 2012).
Estimation des paramètres : Le test reste consistant même si les facteurs de parcimonie $\alpha_n$ et $\beta_m$ sont estimés à partir des données (Corollaire 3.4).

5. Signification et Impact

Cet article représente une avancée significative dans la statistique des réseaux pour plusieurs raisons :

Universalité : C'est l'un des premiers tests non paramétriques universellement consistants pour une large classe de modèles de graphes de rang faible, sans exiger que les graphes aient le même nombre de sommets ou la même structure de communauté.
Robustesse aux valeurs propres négatives : En traitant explicitement les géométries indéfinies (via $I_{p,q}$ ), le modèle devient applicable à des structures de communautés complexes (ex: SBM équilibré avec $K \ge 3$ blocs) qui échouent avec les méthodes RDPG classiques ( $q=0$ ).
Praticabilité : La combinaison de l'embedding spectral, du transport optimal et du bootstrap rend la méthode applicable aux données réelles, comme le montrent les simulations sur des modèles de blocs stochastiques et des graphes à correction de degré.
Théorie des statistiques U dégénérées : L'article fournit une analyse fine de la convergence des statistiques U dégénérées dans un contexte de graphes aléatoires, comblant un vide théorique entre la théorie des graphons et l'inférence sur les réseaux réels.

En résumé, cette méthode offre un outil robuste et théoriquement fondé pour comparer des réseaux de nature différente et de tailles variées, ouvrant la voie à des applications en neurosciences (comparaison de connectomes de sujets différents) et en sciences sociales.