Technical Summary: Two-Sample Hypothesis Testing for Subspace Equality in Network Data

Problem Formulation

The paper addresses the fundamental challenge of determining whether two independent network-valued data sets share the same underlying structural connectivity patterns, specifically their latent community structures, even when their edge probabilities differ significantly. In many applications, such as comparing social networks across platforms or analyzing airport connectivity over time, the "communities" (latent groups) may remain stable while the density or specific connection probabilities fluctuate.

Formally, let $A^{(1)}$ and $A^{(2)}$ be two independent adjacency matrices of size $n \times n$, generated from symmetric, low-rank probability matrices $P^{(1)}$ and $P^{(2)}$ of rank $k$. The authors propose testing the null hypothesis that the column spaces (subspaces) spanned by the leading eigenvectors of these probability matrices are identical:
$$H_0: V^{(1)}(V^{(1)})^\top = V^{(2)}(V^{(2)})^\top$$
versus the alternative $H_1$ where the subspaces differ. Here, $V^{(i)} \in \mathbb{R}^{n \times k}$ contains the orthonormal eigenvectors corresponding to the non-zero eigenvalues of $P^{(i)}$.

This hypothesis is shown to be equivalent to testing for equality of community structures in Stochastic Blockmodels (SBM) and Mixed-Membership Stochastic Blockmodels (MMSBM), up to permutation and scaling, and equality of latent feature spaces in Generalized Random Dot Product Graphs (GRDPG).

Methodology

Test Statistic

The proposed test statistic is based on the Frobenius norm of the difference between the empirical spectral projection matrices of the two networks. Let $\hat{V}^{(i)}$ denote the matrix of the leading $k$ empirical eigenvectors of $A^{(i)}$. The statistic is defined as:
$$T_n := \| \hat{V}^{(1)}(\hat{V}^{(1)})^\top - \hat{V}^{(2)}(\hat{V}^{(2)})^\top \|_F^2$$

Asymptotic Theory

The core theoretical contribution is a limit theorem establishing that, under appropriate centering and scaling, $T_n$ converges in distribution to a standard Gaussian random variable. This result holds under the following conditions:

1. Sparsity: The average expected degree grows at least logarithmically with the number of vertices ($n\rho_n \gg \log n$).
2. Eigenvalue Scaling: The non-zero eigenvalues of the probability matrices scale linearly with $n\rho_n$.
3. Incoherence: The rows of the population eigenvectors are uniformly spread (a condition satisfied by balanced community sizes in blockmodels).

The asymptotic mean ($\mu_2$) and variance ($\sigma_2^2$) of the statistic are derived explicitly in terms of the population parameters. The derivation relies on a novel matrix series expansion of the projection difference, decomposing the statistic into a dominant second-order term and higher-order remainder terms. The proof utilizes a martingale central limit theorem to establish the Gaussian limit for the second-order term, while demonstrating that higher-order terms are asymptotically negligible.

Data-Driven Estimation

To make the test operational, the authors propose consistent plug-in estimators for the asymptotic mean and variance. These estimators replace the unknown population eigenvectors and eigenvalues with their empirical counterparts. The consistency of these estimators is proven under a slightly stronger "dense regime" assumption ($n\rho_n \gg \sqrt{n}$), which ensures that the estimation error does not distort the limiting distribution.

One-Sample Analogue

The paper also establishes a corresponding limit theorem for a one-sample test, which assesses the distance between an empirical subspace and a known reference subspace. This result serves as the technical foundation for the two-sample proof and is presented as a result of independent interest, providing a basis for confidence intervals on the projection distance.

Key Contributions

1. A Two-Sample Test for Common Subspaces: The authors propose a spectral test statistic for the equality of column spaces of low-rank probability matrices. They prove its asymptotic normality and provide consistent estimators for its parameters, enabling rigorous Type I error control without computationally intensive resampling methods like bootstrapping.
2. Application to Blockmodel Families: The framework is shown to be applicable to both SBMs and MMSBMs. The test effectively detects changes in community structure (membership assignments) even when edge probabilities vary, distinguishing between structural shifts and mere density fluctuations.
3. Limit Theorem for Projection Distances: The paper derives a limit theorem for the projection distance between empirical and true eigenspaces under Bernoulli noise. This generalizes previous results that often assumed Gaussian noise or focused on individual eigenvectors, providing a global distributional theory for subspace estimation errors.

Results

Numerical Simulations

The authors validate the method through extensive simulations on synthetic data:

• Stochastic Blockmodels (SBM): The test demonstrates strong power in distinguishing networks with different community structures. Even small perturbations (reassigning a small number of nodes) are detected with high probability as the network density increases.
• Mixed-Membership SBMs (MMSBM): The test successfully detects shifts in mixed-membership profiles. The simulations indicate that while the test is effective, detecting changes in soft-assignment regimes (MMSBM) requires slightly larger perturbations or denser networks compared to hard-assignment regimes (SBM).
• Size Control: The empirical size of the test remains close to the nominal significance level ($\alpha = 0.05$) and improves as the network density increases.

Real-World Application

The methodology is applied to US domestic flight data (January 2016 – September 2021) to analyze the airport network.

• Stable Periods: Comparisons of flight networks in January and November across different years show no statistically significant structural differences, indicating stable community structures.
• Structural Disruption: Comparisons involving June 2020 (the peak of the COVID-19 pandemic disruption) reveal statistically significant differences in the network's subspace structure compared to other years. This confirms the test's ability to detect major structural disruptions in real-world network data.

Significance and Claims

The paper claims to provide a rigorous, computationally efficient framework for network hypothesis testing that moves beyond testing specific parameter equality (e.g., exact edge probabilities) to testing the stability of the underlying geometric structure (the subspace).

• Robustness: Unlike methods that rely on exact parameter matching or assume specific noise structures (like Gaussian), this approach is robust to nuisance fluctuations in edge density and is tailored to the heteroskedastic Bernoulli noise inherent in network data.
• Theoretical Novelty: The derivation of the Gaussian limit for the projection distance under Bernoulli noise is presented as a significant theoretical advancement, filling a gap in the literature where such distributional results were previously unavailable for this specific setting.
• Practical Utility: By providing closed-form limiting distributions and consistent estimators, the method avoids the computational burden of permutation tests or bootstrap procedures, making it scalable for large network datasets.

The authors note that while their results are established under bounded, independent Bernoulli noise, future work could extend these limit theorems to heavy-tailed distributions or dependent edge structures. Additionally, the current analysis assumes the rank $k$ is known, and incorporating rank selection uncertainty remains an open challenge.