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.

Stel je voor dat je twee enorme verzamelingen vrienden hebt: de ene groep uit New York en de andere uit Tokio. Je wilt weten of deze twee groepen op dezelfde manier "sociaal" zijn. Hebben ze dezelfde patronen in wie met wie praat?

In de statistiek noemen we dit een twee-stalen toets. Het probleem is echter: de New Yorkse groep heeft 10.000 mensen, en de Tokio-groep heeft 15.000. Bovendien kennen ze elkaar niet; er is geen lijst die zegt wie in New York "de vriend van" is in Tokio. Ze zijn gewoon twee losse netwerken van verschillende grootte.

Deze paper, geschreven door Joshua Agterberg en collega's, biedt een slimme manier om te testen of deze twee netwerken uit dezelfde "verdeling" komen, zelfs als ze verschillend groot zijn en de mensen erin niet direct met elkaar te vergelijken zijn.

Hier is hoe ze dat doen, vertaald naar alledaagse taal:

1. Het Netwerk als een Landkaart (Latente Ruimte)

Stel je voor dat elke persoon in een netwerk een punt is op een kaart. Maar niet zomaar een kaart: een kaart die de "sociale aard" van die persoon weergeeft.

Als iemand heel populair is, ligt die punt misschien in het centrum.
Als iemand alleen met een specifieke groep praat, ligt die punt in een bepaalde hoek.

De auteurs gebruiken een wiskundige techniek (genaamd Adjacency Spectral Embedding) om deze netwerken om te zetten in zo'n kaart. Ze proberen de complexe web van connecties te "platdrukken" tot een paar dimensies, zodat je de structuur van het netwerk kunt zien als een wolk van punten.

2. Het Rotatie-probleem (De Draaiende Kaart)

Hier komt het lastige deel. Stel je voor dat je de kaart van New York hebt en de kaart van Tokio. Ze zien er misschien precies hetzelfde uit, maar de Tokio-kaart staat misschien 90 graden gedraaid. Of de "Noord"-richting is anders.
In wiskundige termen: de punten kunnen een rotatie ondergaan. Als je de kaarten niet eerst op elkaar afstemt (rotatie), lijkt het alsof ze verschillend zijn, terwijl ze eigenlijk identiek zijn.

De auteurs zeggen: "We moeten eerst de Tokio-kaart zo draaien dat hij perfect op de New Yorkse kaart past." Maar hoe draai je iets als je niet precies weet hoe het eruit moet zien?

3. De Slimme Draaierij (Optimal Transport)

Om deze rotatie te vinden, gebruiken ze een techniek uit de wiskunde die Optimal Transport heet.

De Analogie: Stel je voor dat je een vrachtwagen hebt vol met aardappelen (de New Yorkse punten) en een lege schuur met gaten in de vloer (de Tokio-punten). Je wilt de aardappelen zo in de gaten laten vallen dat je de minste moeite doet (minste afstand).
In dit geval proberen ze de "wolk" van New York-punten zo te draaien en te verschuiven dat deze zo goed mogelijk over de "wolk" van Tokio-punten valt. Als ze perfect passen, is de rotatie gevonden.

4. De Test: Zijn ze hetzelfde?

Zodra ze de kaarten op elkaar hebben gedraaid, kunnen ze ze vergelijken.

Ze gebruiken een maatstaf genaamd Maximum Mean Discrepancy (MMD). Denk hieraan als een "afstandsmeter" tussen twee wolkjes punten.
Als de afstand heel klein is (na het draaien), zeggen ze: "Ja, deze netwerken komen uit dezelfde verdeling. Ze zijn structureel gelijk."
Als de afstand groot blijft, zeggen ze: "Nee, deze netwerken zijn fundamenteel verschillend."

5. Waarom is dit speciaal? (Dunne Netwerken)

De meeste eerdere methoden werkten alleen als de netwerken "dik" waren (iedereen kent bijna iedereen). Maar in het echte leven zijn netwerken vaak "dun" (iedereen kent maar een paar mensen).
De auteurs tonen aan dat hun methode ook werkt voor deze dunne, schaarse netwerken. Ze hebben bewezen dat zelfs als er weinig connecties zijn, je de kaarten nog steeds goed kunt draaien en vergelijken, mits je net groot genoeg zijn.

Samenvatting in één zin

Deze paper geeft ons een wiskundig kompas en een slimme draaierij-techniek om twee verschillende, onbekende sociale netwerken op elkaar te leggen en te zeggen: "Kijk, ondanks dat ze anders groot zijn en andere mensen hebben, zijn ze in feite exact hetzelfde type netwerk."

Dit is handig voor alles, van het vergelijken van hersenconnecties van twee patiënten tot het analyseren van sociale media-groepen van verschillende landen, zonder dat we hoeven te weten wie precies wie is.

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

Hier is een gedetailleerde technische samenvatting van het paper "Nonparametric two-sample hypothesis testing for low-rank random graphs of differing sizes" in het Nederlands.

Titel

Niet-parametrische tweestalen hypothesetoetsing voor laag-rangige willekeurige grafen van verschillende groottes.

1. Probleemstelling

Het paper adresseert een fundamenteel probleem in de netwerkanalyse: hoe test men of twee netwerken (grafische structuren) uit dezelfde kansverdeling komen, wanneer deze netwerken verschillende aantallen knopen hebben?

Traditionele methoden voor tweestalen toetsing op grafen gaan vaak uit van een bekende overeenkomst tussen de knopen (bijv. "matched pairs") of vereisen dat beide grafen op dezelfde verzameling knopen zijn gedefinieerd. In veel praktische scenario's (zoals sociale netwerken of neurale connectomics) is er echter geen vooraf bekende knopen-mapping, en kunnen knopen worden toegevoegd of verwijderd zonder de fundamentele structuur te veranderen.

De auteurs willen een model-agnostische (niet-parametrische) toets ontwikkelen die:

Werkt voor grafen met verschillende aantallen knopen ( $n$ en $m$ ).
Geldt voor een breed scala aan laag-rangige netwerkmomenten (waaronder Stochastic Blockmodels, Random Dot Product Graphs, en Graphons).
Robuust is tegen sparsiteit (dunne netwerken) en indefinite geometrie (negatieve eigenwaarden in de verwachtingsmatrix).

2. Methodologie en Kader

Het Generalized Random Dot Product Graph (GRDPG) Model

De auteurs gebruiken het GRDPG-raamwerk (Rubin-Delanchy et al., 2022) als onderliggend model.

Elke knoop $i$ heeft een latente vector $X_i$ in een $d$ -dimensionale Euclidische ruimte.
De kans op een rand tussen knoop $i$ en $j$ wordt gegeven door $P(A_{ij}=1) = \alpha_n X_i^\top I_{p,q} X_j$ , waarbij $I_{p,q} = \text{diag}(I_p, -I_q)$ .
De matrix $I_{p,q}$ introduceert indefinite orthogonaliteit, wat toelaat dat de verwachtingsmatrix van de graaf negatieve eigenwaarden heeft (essentieel voor modellen zoals het Stochastic Blockmodel met meer dan 2 blokken).

Definitie van "Gelijke Verdeling"

Vanwege de niet-identificeerbaarheid van het GRDPG-model (de latente posities zijn alleen gedefinieerd tot op een indefinite orthogonale transformatie $Q \in O(p,q)$ ), definiëren de auteurs gelijkheid als volgt:
Twee verdelingen $F_X$ en $F_Y$ zijn equivalent ( $F_X \simeq F_Y$ ) als er een matrix $Q \in O(p,q)$ bestaat zodat $F_X = F_Y \circ Q$ . De nulhypothese ( $H_0$ ) is dat de twee netwerken uit equivalente verdelingen komen.

De Teststatistiek

De kern van de methode is een niet-parametrische tweestalen U-statistiek gebaseerd op de Maximum Mean Discrepancy (MMD):

Spectral Embedding: Men berekent de Adjacency Spectral Embedding (ASE) voor beide grafen, wat resulteert in matrices $\hat{X}$ en $\hat{Y}$ (de geschatte latente posities).
Rotatie (Optimal Transport): Omdat de ASE's willekeurig kunnen zijn georiënteerd (door de niet-identificeerbaarheid), moet men de rijen van $\hat{X}$ $\hat{X}$ en $\hat{Y}$ $\hat{Y}$ op elkaar afstemmen. Dit wordt gedaan door een orthogonale matrix $\hat{W}_n$ $\hat{W}_{n}$ te vinden die de afstand tussen de verdelingen minimaliseert.
- De auteurs gebruiken Optimal Transport (specifiek de Wasserstein-afstand) om deze rotatie te schatten.
- Om de indefinite structuur ( $p$ positieve en $q$ negatieve componenten) correct te behandelen, wordt de optimalisatie gesplitst in twee blokken: één voor de positieve en één voor de negatieve eigenwaarden.
- Een Sinkhorn-regularisatie wordt toegepast om het optimal transport-probleem computationeel efficiënt op te lossen.
MMD Berekening: Na rotatie wordt de MMD berekend tussen de geschatte latente posities:
$U_{n,m}(\hat{X}, \hat{Y}) = \text{MMD}(\hat{X}\hat{W}_n, \hat{Y})$
Een bootstrapped permutatietest wordt gebruikt om de $p$ -waarde te bepalen, aangezien de exacte asymptotische verdeling onder $H_0$ complex is en afhankelijk van de onderliggende verdeling.

3. Belangrijkste Bijdragen en Resultaten

Theoretische Consistentie

De auteurs bewijzen dat hun test consistent is (d.w.z. de kans op het correct verwerpen van $H_0$ gaat naar 1 als $n, m \to \infty$ ) onder twee verschillende regimes:

Sparsere Regimes: Voor grafen met een gemiddelde verwachte graad van orde $n\alpha_n \gg \log^4(n)$ . In dit regime moet de teststatistiek worden geschaald met $(m\beta_m + n\alpha_n)$ . De auteurs tonen aan dat zelfs bij negatieve eigenwaarden en herhaalde eigenwaarden, de test consistent blijft.
Dichtere Regimes: Voor grafen met een gemiddelde graad groter dan $\sqrt{n}\log(n)$ . Hier geldt de schaling $(n+m)$ , analoog aan klassieke MMD-resultaten voor dichte data.

Omgaan met Indefinite Orthogonaliteit

Een cruciale theoretische doorbraak is het bewijs dat men, ondanks de aanwezigheid van indefinite orthogonaliteit ( $O(p,q)$ ), in de limiet alleen rekening hoeft te houden met blok-orthogonale transformaties ( $O(d) \cap O(p,q)$ ). Dit betekent dat de instabiliteit van indefinite matrices in de praktijk kan worden omzeild door zorgvuldige analyse van de convergentie van de spectrale embedding.

Algoritme voor Rotatie

Het paper introduceert een efficiënt algoritme (Algorithm 1) dat afwisselend optimal transport (via Sinkhorn) en Procrustes-analyse gebruikt om de rotatiematrix $\hat{W}_n$ te schatten. Ze bewijzen convergentie van dit algoritme als het wordt geïnitieerd dicht bij het globale optimum.

Robuustheid

In tegenstelling tot eerdere werken (zoals Tang et al., 2017b), is deze methode niet beperkt tot modellen met alleen positieve eigenwaarden of unieke eigenwaarden. Het werkt dus ook voor het Stochastic Blockmodel met $K \ge 3$ blokken, wat vaak leidt tot negatieve eigenwaarden in de verwachtingsmatrix.

4. Simulaties en Validatie

De auteurs testen hun methode op gesimuleerde data:

Stochastic Blockmodels (SBM): Ze testen op verschillen in connectiviteitsmatrices.
Degree-Corrected SBM: Ze testen op verschillen in de heterogeniteit van de graadverdeling.
Resultaten: De test toont een stijgende power naarmate het aantal knopen toeneemt. Voor dunnere netwerken is de power lager en groeit deze trager, wat overeenkomt met de theoretische voorspellingen. De test is in staat om lokale afwijkingen van de nulhypothese te detecteren, zelfs wanneer de netwerken verschillende groottes hebben.

5. Betekenis en Impact

Universele Toepasbaarheid: De methode is de eerste die een universeel consistente tweestalen toets biedt voor een breed scala aan laag-rangige netwerkmomenten, inclusief die met negatieve eigenwaarden en verschillende knopenaantallen.
Praktische Relevantie: Het elimineert de noodzaak voor vooraf bekende knopen-mapping, wat essentieel is voor het vergelijken van dynamische netwerken of netwerken uit verschillende bronnen.
Theoretische Vooruitgang: Het paper lost de theoretische uitdagingen op die voortkomen uit de indefinite geometrie van GRDPG-modellen, en toont aan dat deze complexiteit kan worden gereduceerd tot een probleem van blok-orthogonale alignering.
Computationele Efficiëntie: Door het gebruik van Sinkhorn-regularisatie voor optimal transport, wordt een computationeel zwaar probleem (assignment problem) oplosbaar gemaakt voor grote netwerken.

Kortom, dit paper biedt een robuust, theoretisch onderbouwd en praktisch toepasbaar raamwerk om te bepalen of twee complexe netwerken fundamenteel dezelfde structuur delen, ongeacht hun grootte of specifieke netwerkmoment.