Technisches Resümee: Zwei-Stichproben-Hypothesentest auf Subraum-Gleichheit in Netzwerkdaten

Problemformulierung

Die Arbeit befasst sich mit der grundlegenden Herausforderung, zu bestimmen, ob zwei unabhängige netzwerkbasierte Datensätze dieselben zugrunde liegenden strukturellen Konnektivitätsmuster teilen – insbesondere deren latente Gemeinschaftsstrukturen –, selbst wenn sich deren Kantenwahrscheinlichkeiten signifikant unterscheiden. In vielen Anwendungen, wie etwa dem Vergleich sozialer Netzwerke über verschiedene Plattformen hinweg oder der Analyse der Flughafenkonnektivität über die Zeit, können die „Communities“ (latente Gruppen) stabil bleiben, während die Dichte oder die spezifischen Verbindungswahrscheinlichkeitenen fluktuieren.

Formal sei $A^{(1)}$ und $A^{(2)}$ zwei unabhängige Adjazenzmatrizen der Größe $n \times n$, die aus symmetrischen, niedrigrangigen Wahrscheinlichkeitsmatrizen $P^{(1)}$ und $P^{(2)}$ des Rangs $k$ generiert wurden. Die Autoren schlagen vor, die Nullhypothese zu testen, dass die Spaltenräume (Subräume) der führenden Eigenvektoren dieser Wahrscheinlichkeitsmatrizen identisch sind:
$$H_0: V^{(1)}(V^{(1)})^\top = V^{(2)}(V^{(2)})^\top$$
gegenüber der Alternativhypothese $H_1$, bei der die Subräume verschieden sind. Hierbei enthält $V^{(i)} \in \mathbb{R}^{n \times k}$ die orthonormalen Eigenvektoren der nicht-nullen Eigenwerte von $P^{(i)}$.

Diese Hypothese wird als äquivalent zum Test auf Gleichheit der Gemeinschaftsstrukturen in Stochastic Blockmodels (SBM) und Mixed-Membership Stochastic Blockmodels (MMSBM) (bis auf Permutation und Skalierung) sowie zur Gleichheit der latenten Merkmalsräume in Generalized Random Dot Product Graphs (GRDPG) nachgewiesen.

Methodik

Teststatistik

Die vorgeschlagene Teststatistik basiert auf der Frobeniusnorm der Differenz zwischen den empirischen spektralen Projektionsmatrizen der beiden Netzwerke. Sei $\hat{V}^{(i)}$ die Matrix der führenden $k$ empirischen Eigenvektoren von $A^{(i)}$. Die Statistik ist definiert als:
$$T_n := \| \hat{V}^{(1)}(\hat{V}^{(1)})^\top - \hat{V}^{(2)}(\hat{V}^{(2)})^\top \|_F^2$$

Asymptotische Theorie

Der zentrale theoretische Beitrag ist ein Grenzwertsatz, der etabliert, dass $T_n$ unter angemessener Zentrierung und Skalierung gegen eine Standard-Normalverteilung konvergiert. Dieses Ergebnis gilt unter folgenden Bedingungen:

1. Sparsity (Dünnbesetztheit): Der durchschnittliche erwartete Grad wächst mindestens logarithmisch mit der Anzahl der Knoten ($n\rho_n \gg \log n$).
2. Eigenwert-Skalierung: Die nicht-nullen Eigenwerte der Wahrscheinlichkeitsmatrizen skalieren linear mit $n\rho_n$.
3. Inkohärenz: Die Zeilen der Populations-Eigenvektoren sind gleichmäßig verteilt (eine Bedingung, die durch ausgewogene Community-Größen in Blockmodellen erfüllt wird).

Der asymptotische Mittelwert ($\mu_2$) und die Varianz ($\sigma_2^2$) der Statistik werden explizit in Abhängigkeit von den Populationsparametern hergeleitet. Die Herleitung stützt sich auf eine neuartige Matrix-Reihenentwicklung der Projektionsdifferenz, welche die Statistik in einen dominanten Term zweiter Ordnung und höhere Ordnung restliche Terme zerlegt. Der Beweis nutzt einen Martingal-Zentralen-Limit-Theorem, um die Gaußsche Limitierung für den Term zweiter Ordnung zu etablieren, während gleichzeitig gezeigt wird, dass Terme höherer Ordnung asymptotisch vernachlässigbar sind.

Datengesteuerte Schätzung

Um den Test operabel zu machen, schlagen die Autoren konsistente Plug-in-Schätzer für den asymptotischen Mittelwert und die Varianz vor. Diese Schätzer ersetzen die unbekannten Populations-Eigenvektoren und Eigenwerte durch deren empirische Gegenstücke. Die Konsistenz dieser Schätzer wird unter einer etwas stärkeren „dichten Regime“-Annahme ($n\rho_n \gg \sqrt{n}$) bewiesen, die sicherstellt, dass der Schätzfehler die Grenzverteilung nicht verzerrt.

Einsample-Analogon

Das Paper etabliert zudem einen entsprechenden Grenzwertsatz für einen Einsample-Test, der den Abstand zwischen einem empirischen Subraum und einem bekannten Referenzsubraum bewertet. Dieses Resultat dient als technisches Fundament für den Zwei-Sample-Beweis und wird als Ergebnis von eigenem Interesse präsentiert, da es eine Basis für Konfidenzintervalle auf den Projektionsabstand bietet.

Zentrale Beiträge

1. Ein Zwei-Stichproben-Test für gemeinsame Subräume: Die Autoren schlagen einen spektralen Test auf die Gleichheit der Spaltenräume niedrigrangiger Wahrscheinlichkeitsmatrizen vor. Sie beweisen dessen asymptotische Normalität und liefern konsistente Schätzer für dessen Parameter, was eine rigorose Kontrolle der Typ-I-Fehlerrate ohne rechenintensive Resampling-Methoden wie Bootstrapping ermöglicht.
2. Anwendung auf Blockmodell-Familien: Es wird gezeigt, dass das Framework sowohl für SBMs als auch für MMSBMs anwendbar ist. Der Test erkennt effektiv Änderungen in der Gemeinschaftsstruktur (Mitgliedschaftszuweisungen), selbst wenn die Kantenwahrscheinlichkeiten variieren, und unterscheidet somit zwischen strukturellen Verschiebungen und bloßen Dichtefluktuationen.
3. Grenzwertsatz für Projektionsabstände: Das Paper leitet einen Grenzwertsatz für den Projektionsabstand zwischen empirischen und wahren Eigenräumen unter Bernoulli-Rauschen ab. Dies generalisiert bisherige Ergebnisse, die oft Gaußsches Rauschen annahmen oder sich auf einzelne Eigenvektoren konzentrierten, und liefert eine globale Verteilungstheorie für Fehler der Subraum-Schätzung.

Ergebnisse

Numerische Simulationen

Die Autoren validieren die Methode durch umfangreiche Simulationen auf synthetischen Daten:

• Stochastic Blockmodels (SBM): Der Test zeigt eine starke Power bei der Unterscheidung von Netzwerken mit unterschiedlichen Gemeinschaftsstrukturen. Selbst kleine Perturbationen (die Neuzuweisung einer kleinen Anzahl von Knoten) werden mit hoher Wahrscheinlichkeit detektiert, wenn die Netzwerkdichte steigt.
• Mixed-Membership SBMs (MMSBM): Der Test erkennt erfolgreich Verschiebungen in den Mixed-Membership-Profilen. Die Simulationen deuten darauf hin, dass die Detektion von Änderungen in Soft-Assignment-Regimen (MMSBM) im Vergleich zu Hard-Assignment-Regimen (SBM) etwas größere Perturbationen oder dichtere Netzwerke erfordert.
• Größenkontrolle: Die empirische Größe des Tests bleibt nahe am nominalen Signifikanzniveau ($\alpha = 0,05$) und verbessert sich mit zunehmender Netzwerkdichte.

Anwendung in der realen Welt

Die Methodik wird auf US-Inlandsflugdaten (Januar 2016 – September 2021) angewendet, um das Flughafennetz zu analysieren.

• Stabile Perioden: Vergleiche der Flugnetzwerke im Januar und November über verschiedene Jahre hinweg zeigen keine statistisch signifikanten strukturellen Unterschiede, was auf stabile Gemeinschaftsstrukturen hindeutet.
• Strukturelle Disruption: Vergleiche, die den Juni 2020 (den Höhepunkt der COVID-19-bedingten Störungen) beinhalten, offenbaren statistisch signifikante Unterschiede in der Subraumstruktur des Netzwerks im Vergleich zu anderen Jahren. Dies bestätigt die Fähigkeit des Tests, große strukturelle Brüche in realen Netzwerkdaten zu detektieren.

Bedeutung und Ansprüche

Das Paper beansprucht, einen rigorosen, recheneffizienten Rahmen für die Netzwerkhypothesentests bereitzustellen, der über das Testen spezifischer Parametergleichheiten (z. B. exakte Kantenwahrscheinlichkeiten) hinausgeht und statlich auf die Stabilität der zugrunde liegenden geometrischen Struktur (den Subraum) abzielt.

• Robustheit: Im Gegensatz zu Methoden, die auf exaktes Parameter-Matching angewiesen sind oder spezifische Rauschstrukturen (wie Gaußsches Rauschen) voraussetzen, ist dieser Ansatz robust gegenüber störenden Fluktuationen in der Kanten-Dichte und auf das heteroskedastische Bernoulli-Rauschen zugeschnitten, das in Netzwerkdaten inhärent ist.
• Theoretische Neuheit: Die Ableitung der Gaußschen Limitierung für den Projektionsabstand unter Bernoulli-Rauschen wird als bedeutender theoretischer Fortschritt präsentiert, der eine Lücke in der Literatur schließt, in der solche Verteilungsergebnisse für diesen spezifischen Kontext zuvor nicht verfügbar waren.
• Praktischer Nutzen: Durch die Bereitstellung geschlossener Grenzwertverteilungen und konsistenter Schätzer vermeidet die Methode die Rechenlast von Permutationstests oder Bootstrap-Verfahren, was sie skalierbar für große Datensätze macht.

Die Autoren merken an, dass ihre Ergebnisse zwar unter beschränkten, unabhängigen Bernoulli-Rauschen etabliert sind, zukünftige Arbeiten diese Grenzwertsätze jedoch auf schwerfällige (heavy-tailed) Verteilungen oder abhängige Kantenstrukturen ausweiten könnten. Zudem setzt die aktuelle Analyse voraus, dass der Rang $k$ bekannt ist; die Einbeziehung der Unsicherheit bei der Rangwahl bleibt eine offene Herausforderung.