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

Dieses Paper stellt einen nichtparametrischen Zweistichproben-Test vor, der unter Verwendung von Graph-Embeddings, optimaler Transporttheorie und der Maximum Mean Discrepanz prüft, ob zwei Netzwerke unterschiedlicher Größe aus derselben Verteilung stammen, wobei die Konsistenz des Tests für dichte Graphen bewiesen und in verschiedenen Sparsity-Regimen untersucht wird.

Das Wesentliche

Stellen Sie sich vor, Sie sind ein Detektiv, der zwei völlig verschiedene Städte untersucht. Die eine Stadt hat 1.000 Einwohner, die andere 5.000. In beiden Städten gibt es ein soziales Netzwerk: Wer kennt wen?

Die große Frage lautet: Sind diese beiden Städte im Grunde genommen gleich aufgebaut? Haben die Menschen dort ähnliche Freundschaftsmuster, auch wenn die Städte unterschiedlich groß sind und die Namen der Einwohner völlig anders lauten?

Das ist genau das Problem, das diese wissenschaftliche Arbeit löst. Die Autoren (Joshua Agterberg, Minh Tang und Carey Priebe) haben einen neuen, cleveren Weg entwickelt, um zwei unterschiedlich große Netzwerke zu vergleichen, ohne dabei starr auf die genauen Namen der Knotenpunkte zu achten.

Hier ist die Erklärung der Methode, aufgeteilt in einfache Bilder:

1. Das Problem: Äpfel mit Birnen vergleichen?

Normalerweise ist es schwer, zwei Netzwerke zu vergleichen, wenn sie unterschiedlich groß sind.

• Stellen Sie sich vor: Sie haben ein Foto von einem kleinen Dorf und eines von einer riesigen Metropole. Wenn Sie versuchen, die Häuser direkt nebeneinander zu legen, passen sie nicht zusammen.
• Das alte Problem: Bisherige Methoden sagten oft: "Oh, die Städte haben unterschiedliche Namen für ihre Straßen, also sind sie unterschiedlich!" oder sie funktionierten nur, wenn die Netzwerke sehr dicht vernetzt waren (wie eine überfüllte Party).

2. Die Lösung: Der "Geist" der Stadt (Latente Räume)

Die Autoren sagen: "Vergessen wir die Namen der Häuser. Schauen wir uns den Charakter der Stadt an."
Sie nutzen eine Technik namens Adjacency Spectral Embedding.

• Die Analogie: Stellen Sie sich vor, Sie nehmen jede Person in der Stadt und geben ihr einen unsichtbaren "Charakter-Raum" (eine Art GPS-Koordinate in einem mehrdimensionalen Raum).
  • Ein sehr beliebter Mensch hat Koordinaten an einem Ort.
  • Ein Einsiedler hat Koordinaten an einem anderen Ort.
  • Die Gesamtheit aller Koordinaten bildet eine Wolke.
• Wenn zwei Städte denselben "Charakter" haben, dann sehen diese Wolken von Koordinaten ähnlich aus – egal, ob die eine Stadt 100 Punkte hat und die andere 10.000.

3. Das Drehen des Bildes (Optimal Transport)

Hier wird es knifflig. Selbst wenn die Wolken ähnlich sind, könnten sie im Raum "verdreht" sein.

• Die Analogie: Stellen Sie sich vor, Sie haben zwei Fotos desselben Objekts. Auf dem einen Foto ist das Objekt gerade, auf dem anderen ist es um 45 Grad gedreht und gespiegelt. Wenn Sie die Fotos direkt vergleichen, sehen sie unterschiedlich aus, obwohl es dasselbe Objekt ist.
• Die Methode: Die Autoren verwenden einen Algorithmus namens Optimal Transport (Optimaler Transport).
  • Stellen Sie sich vor, Sie haben zwei Haufen Sand (die Koordinatenwolken). Der Algorithmus fragt: "Wie viel Arbeit (Transportkosten) kostet es, den Sandhaufen A so zu verschieben und zu drehen, dass er genau auf Sandhaufen B passt?"
  • Sie drehen und verschieben die Koordinaten der kleineren Stadt so lange, bis sie perfekt mit der größeren Stadt übereinstimmen. Erst dann vergleichen sie sie.

4. Das "Geister-Problem" (Negative Eigenwerte)

Ein besonders cleverer Teil der Arbeit ist der Umgang mit "negativen Eigenwerten".

• Die Analogie: In manchen Netzwerken gibt es nicht nur "Freunde" (positive Verbindungen), sondern auch "Feinde" oder "Rivalitäten" (negative Verbindungen). In der Mathematik führt das dazu, dass die Koordinatenwolke sich in eine seltsame, hyperbolische Form verzieht (wie ein Sattel statt einer Kugel).
• Frühere Methoden scheiterten oft an diesen "negativen" Formen. Die Autoren haben jedoch gezeigt, dass man diese seltsamen Formen trotzdem sicher drehen und vergleichen kann, ohne dass das Ergebnis verrückt wird. Sie haben einen Weg gefunden, die "Geometrie der Feindschaft" in den Vergleich einzubeziehen.

5. Der Test: Ist es Zufall oder Absicht?

Nachdem sie die beiden Koordinatenwolken perfekt ausgerichtet haben, wenden sie einen statistischen Test an (Maximum Mean Discrepancy).

• Das Ergebnis:
  • Wenn die Wolken nach dem Ausrichten identisch aussehen, dann stammen die beiden Netzwerke aus derselben Verteilung (die Städte haben denselben "Charakter").
  • Wenn sie sich unterscheiden, dann sind die Netzwerke fundamental anders.

Warum ist das wichtig?

Diese Methode ist wie ein universeller Übersetzer für Netzwerke:

1. Sie funktioniert für kleine und große Netzwerke.
2. Sie funktioniert für dichte (viele Freunde) und spärliche (wenige Freunde) Netzwerke.
3. Sie ignoriert die spezifischen Namen der Knoten (wer ist wer) und konzentriert sich nur auf die Struktur.

Zusammenfassend:
Die Autoren haben einen Weg gefunden, zwei völlig unterschiedliche soziale Netzwerke (wie ein kleines Dorf und eine Großstadt) zu vergleichen, indem sie die Menschen in ihre "Charakter-Koordinaten" übersetzen, diese Koordinaten wie Puzzleteile so lange drehen, bis sie passen, und dann prüfen, ob die beiden Bilder am Ende gleich aussehen. Das ist ein großer Schritt für die Statistik, um Netzwerke in der realen Welt (von sozialen Medien bis zu Gehirnverbindungen) besser zu verstehen.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des Papers „Nonparametric two-sample hypothesis testing for low-rank random graphs of differing sizes" von Agterberg, Tang und Priebe auf Deutsch.

1. Problemstellung

Das Papier adressiert das Problem des zweistichprobenbasierten Hypothesentests für Netzwerkdaten (Graphen) unterschiedlicher Größe.

• Ziel: Zu testen, ob zwei beobachtete Adjazenzmatrizen $A^{(1)} \in \{0,1\}^{n \times n}$ und $A^{(2)} \in \{0,1\}^{m \times m}$ aus derselben Verteilung stammen.
• Herausforderungen:
  • Die Graphen haben unterschiedliche Anzahlen von Knoten ($n \neq m$).
  • Es gibt keine vorab bekannte Zuordnung (Matching) zwischen den Knoten der beiden Graphen.
  • Die Graphen sind oft spärlich (sparse), d.h. die durchschnittliche erwartete Gradzahl wächst langsamer als die Anzahl der Knoten.
  • Die zugrunde liegenden Modelle können negativen Eigenwerte in der Erwartungsmatrix der Kantenwahrscheinlichkeiten aufweisen (indefinite Geometrie).
• Rahmenwerk: Die Autoren nutzen das Framework des verallgemeinerten Random Dot Product Graph (GRDPG). Dies verallgemeinert populäre Modelle wie Stochastic Blockmodels (SBM), degree-corrected SBMs und Random Dot Product Graphs (RDPG).
• Definition der Gleichheit: Zwei Verteilungen $F_X$ und $F_Y$ latenten Positionen gelten als gleich ($F_X \simeq F_Y$), wenn sie sich nur durch eine indefinite orthogonale Transformation $Q \in O(p,q)$ unterscheiden, wobei $Q I_{p,q} Q^\top = I_{p,q}$ gilt. Dies berücksichtigt die Nicht-Identifizierbarkeit des GRDPG-Modells.

2. Methodik

Die vorgeschlagene Methode ist ein nichtparametrischer Test, der auf der Maximum Mean Discrepancy (MMD) basiert, angewendet auf eingebettete Knotenvektoren.

A. Adjacency Spectral Embedding (ASE)

Zunächst werden die latenten Positionen der Knoten geschätzt. Dazu wird die Adjacency Spectral Embedding (ASE) verwendet:

• Die Adjazenzmatrix wird einer Spektralzerlegung unterzogen.
• Die $d$ größten Eigenwerte (nach Betrag) und die zugehörigen Eigenvektoren werden extrahiert.
• Die geschätzte Matrix der latenten Positionen ist $\hat{X} = U_A |\Lambda_A|^{1/2}$.

B. Optimal Transport zur Ausrichtung (Alignment)

Da die latenten Positionen nur bis auf eine orthogonale Transformation identifizierbar sind, müssen die Embeddings $\hat{X}$ und $\hat{Y}$ vor dem Vergleich ausgerichtet werden.

• Das Problem wird als Optimal Transport (Wasserstein-Distanz) unter der Nebenbedingung orthogonaler Matrizen formuliert.
• Um die indefiniten Eigenwerte zu handhaben, wird die Optimierung getrennt für die positiven ($p$) und negativen ($q$) Teile der Eigenwerte durchgeführt.
• Es wird ein block-orthogonaler Matrix $\hat{W}_n$ gesucht, der die Distanz zwischen den empirischen Verteilungen der skalierten Embeddings minimiert:
  $$\inf_{W \in O(d) \cap O(p,q)} d_2(\hat{F}_{\hat{X}}, \hat{F}_{\hat{Y}} \circ W)$$
• Algorithmus: Zur Lösung dieses Problems wird ein alternierender Minimierungsansatz verwendet, der den Sinkhorn-Algorithmus (für regularisierten Optimal Transport) mit einem Procrustes-Schritt (für die orthogonale Matrix) kombiniert.

C. Teststatistik

Die Teststatistik ist eine U-Statistik, die die MMD zwischen den ausgerichteten Embeddings misst:
$$U_{n,m}(\hat{X}, \hat{Y}) = \frac{1}{n(n-1)}\sum_{i \neq j} \kappa(\hat{X}_i, \hat{X}_j) - \frac{2}{mn}\sum_{i,k} \kappa(\hat{X}_i, \hat{Y}_k) + \frac{1}{m(m-1)}\sum_{k \neq l} \kappa(\hat{Y}_k, \hat{Y}_l)$$
Dabei ist $\kappa$ ein charakteristischer, radialer Kernel (z.B. Gauß-Kernel).

D. Signifikanztest

Da die asymptotische Verteilung der Teststatistik unter der Nullhypothese komplex ist und von den zugrunde liegenden Verteilungen abhängt, wird die Nullverteilung durch Bootstrapping (Permutationstest) approximiert.

3. Wichtige Beiträge und Ergebnisse

A. Konsistenz unter Sparsity und Indefinitheit

• Erweiterung bestehender Literatur: Im Gegensatz zu früheren Arbeiten (z.B. Tang et al., 2017b), die nur dichte Graphen oder Graphen mit positiven Eigenwerten (RDPG) behandeln, ist dieser Test konsistent für spärliche Graphen und solche mit negativen Eigenwerten (indefinite Geometrie).
• Sparsity-Regime:
  • Für spärliche Graphen (mittlerer Grad $\gg \log^4(n)$) wird die Statistik mit dem Faktor $(m\beta_m + n\alpha_n)$ skaliert.
  • Für dichte Graphen (mittlerer Grad $\gg \sqrt{n} \log(n)$) wird die Standard-Skalierung $(m+n)$ verwendet.
• Theoretische Garantie: Es wird bewiesen, dass die Teststatistik unter der Nullhypothese gegen 0 konvergiert und unter der Alternativhypothese (bei festen Alternativen) gegen eine positive Konstante konvergiert, was eine konsistente Testentscheidung garantiert.

B. Behandlung der Nicht-Identifizierbarkeit

Ein zentrales theoretisches Ergebnis ist, dass trotz der Notwendigkeit, indefinite orthogonale Transformationen ($O(p,q)$) zu berücksichtigen, die asymptotischen Ergebnisse durch block-orthogonale Matrizen ($O(d) \cap O(p,q)$) beschrieben werden können. Dies ermöglicht die Verwendung stabiler numerischer Algorithmen (wie Procrustes) statt instabiler Optimierung über die gesamte indefinite Gruppe.

C. Schätzung der Sparsity-Parameter

Das Papier zeigt, dass die unbekannten Sparsity-Parameter $\alpha_n$ und $\beta_m$ konsistent geschätzt werden können (durch den Anteil der Kanten in den Graphen), ohne dass die Konsistenz des Tests beeinträchtigt wird.

D. Numerische Simulationen

Die Autoren demonstrieren die Leistungsfähigkeit des Tests an simulierten Daten:

• Stochastic Blockmodels (SBM): Der Test erkennt Unterschiede in den Verbindungsstärken.
• Degree-Corrected SBMs: Der Test erkennt Unterschiede in der Heterogenität der Knotengrade.
• Die Ergebnisse zeigen, dass die Teststärke (Power) mit zunehmender Graphgröße steigt, jedoch bei sehr spärlichen Graphen langsamer konvergiert, was den theoretischen Vorhersagen entspricht.

4. Signifikanz und Bedeutung

• Universalität: Der Test ist universell konsistent für die gesamte Klasse von Netzwerkmodellen mit Rang $d$, einschließlich komplexer Modelle wie gemischte Mitgliedschafts-Blockmodelle (Mixed-Membership SBM) und Graphons mit endlichem Rang.
• Praktische Anwendbarkeit: Die Methode erfordert keine Kenntnis der Knotenkorrespondenz und funktioniert auch, wenn die Graphen unterschiedliche Größen haben. Dies ist in vielen realen Anwendungen (z.B. Neurobiologie, soziale Netzwerke) essenziell.
• Theoretische Durchbrüche: Die Arbeit löst das Problem der Behandlung negativer Eigenwerte in der spektralen Einbettung für Hypothesentests, was bisher ein offenes Problem war. Sie verbindet Konzepte aus der spektralen Graphentheorie, Optimal Transport und der Theorie degenerierter U-Statistiken.
• Robustheit: Durch die Verwendung von Bootstrapping wird die Abhängigkeit von der genauen asymptotischen Verteilung umgangen, was den Test in der Praxis robust macht.

Zusammenfassend bietet dieses Papier einen rigorosen, nichtparametrischen Rahmen zum Vergleich beliebiger niedrigrangiger Zufallsgraphen unterschiedlicher Größe und Sparsity, der theoretisch fundiert und praktisch implementierbar ist.