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

This paper proposes a nonparametric two-sample hypothesis test for low-rank random graphs of differing sizes, utilizing maximum mean discrepancy on optimally transported graph embeddings to determine if the networks originate from the same distribution.

The Gist

Imagine you are a detective trying to solve a mystery: Are two different social networks built on the same "blueprint," or are they fundamentally different?

In the world of data science, these "networks" are just maps of connections—like who follows whom on Twitter, which neurons fire together in a brain, or which people are friends in a group. Usually, statisticians compare two networks by looking at them side-by-side, assuming they have the exact same number of people and that Person A in Network 1 is the same as Person A in Network 2.

But in real life, that's rarely true. One network might have 1,000 people, and the other 5,000. The people are different, and the names don't match up. How do you tell if they are "the same kind of network" without knowing who is who?

This paper by Agterberg, Tang, and Priebe proposes a clever new way to answer that question. Here is the breakdown using simple analogies.

1. The Problem: Comparing Apples to Oranges (That Look Similar)

Imagine you have two jars of marbles.

• Jar A has 100 marbles.
• Jar B has 1,000 marbles.

You want to know: Do these jars contain marbles from the same factory?

If you just look at the colors, you might get confused. Maybe Jar A has mostly red marbles, but Jar B has a mix of red, blue, and green. Is that because they are different factories, or just because Jar B is bigger and has more variety?

In network terms, the "marbles" are the people (vertices), and the "connections" between them are the edges. The authors want to know if the underlying "factory settings" (the probability distribution) that created these connections are the same, even if the networks are different sizes and the people are strangers to each other.

2. The Solution: The "Shadow" Technique (Latent Space)

The authors use a concept called Generalized Random Dot Product Graphs (GRDPG).

Think of every person in a network as having a secret "ID card" hidden in their pocket. This ID card isn't a name; it's a set of coordinates in a hidden, multi-dimensional space (like a secret map).

• If two people have ID cards that are close together on this secret map, they are likely to be friends.
• If they are far apart, they probably won't connect.

The network we see (the web of connections) is just the shadow cast by these hidden ID cards. The paper's method tries to reverse-engineer the shadows to find the hidden ID cards.

3. The Twist: The "Rotating Room" (Indefinite Orthogonal Transformations)

Here is where it gets tricky. The authors discovered that the "secret map" has a weird property: It can be rotated or flipped without changing the shadows.

Imagine you are in a room with a unique pattern on the floor. If you rotate the room 90 degrees, the pattern looks different, but the shape of the room is the same. In math terms, this is called an indefinite orthogonal transformation.

Because of this, you can't just line up the ID cards from Network A and Network B directly. You have to figure out how to rotate the ID cards of Network B so they align perfectly with Network A. If you can rotate them to match, the networks are "twins." If you can't, they are different.

4. The Tool: The "Optimal Transport" Dance

How do you find the right rotation? The authors use a technique called Optimal Transport.

Think of it like a dance floor.

• You have a group of dancers (Network A's ID cards) on the left.
• You have another group (Network B's ID cards) on the right.
• You want to pair them up so that the total distance they have to walk to meet is minimized.

The authors developed an algorithm (using something called the Sinkhorn algorithm) that efficiently figures out the best rotation and pairing. It's like a super-smart matchmaker that says, "Okay, if we spin Network B this way, these two people are a perfect match."

5. The Test: The "Maximum Mean Discrepancy" (MMD)

Once the networks are rotated and aligned, the authors use a statistical test called Maximum Mean Discrepancy (MMD).

Imagine you have two bags of marbles again. You want to know if they are from the same factory. You take a handful from each bag and ask a very sensitive detector: "How different do these handfuls look?"

• If the detector says "Zero difference," the networks are likely the same.
• If it says "Huge difference," they are different.

The paper proves that this detector works even when:

1. The networks are sparse (very few connections, like a ghost town).
2. The networks have negative eigenvalues (a mathematical quirk that happens in complex networks, like a "negative" connection).
3. The networks are different sizes.

6. Why This Matters

Previous methods were like trying to compare two puzzles where you knew exactly which piece went where. This new method works even if:

• The puzzles have different numbers of pieces.
• The pieces are scrambled.
• The puzzles are made of "fuzzy" or "negative" pieces.

In summary:
The authors built a mathematical "universal translator." They take two messy, different-sized networks, extract their hidden "DNA" (latent positions), rotate them until they align, and then check if their DNA matches. If it does, the networks are statistically identical, regardless of their size or how the people are named.

This is a huge step forward for analyzing real-world data, where we rarely have perfect, matched datasets. It allows scientists to compare a small brain network to a large social network and ask: "Are they built on the same fundamental rules?"

Technical Summary

Here is a detailed technical summary of the paper "Nonparametric two-sample hypothesis testing for low-rank random graphs of differing sizes" by Agterberg, Tang, and Priebe.

1. Problem Statement

The paper addresses the fundamental statistical problem of testing whether two networks (graphs) of differing sizes ($n$ and $m$ vertices) are drawn from the same underlying distribution.

• Challenge: Unlike classical two-sample tests for Euclidean data where observations are vectors, network data involves complex structures. Furthermore, existing methods often assume the graphs share the same vertex set (matched pairs) or rely on specific parametric models (e.g., Stochastic Blockmodels) that cannot handle negative eigenvalues or repeated eigenvalues in the expected adjacency matrix.
• Goal: Develop a nonparametric, model-agnostic test statistic that can determine if two graphs $A^{(1)}$ and $A^{(2)}$ have "equal distributions," even when they have different numbers of vertices and no known vertex correspondence.

2. Methodology

2.1 Theoretical Framework: Generalized Random Dot Product Graph (GRDPG)

The authors formalize the problem using the GRDPG framework (Rubin-Delanchy et al., 2022).

• Model: A graph $A$ is generated such that $P(A_{ij}=1 | X) = \alpha_n X_i^\top I_{p,q} X_j$, where $X_i$ are latent vectors in $\mathbb{R}^d$, $\alpha_n$ is a sparsity parameter, and $I_{p,q} = \text{diag}(I_p, -I_q)$.
• Significance: The matrix $I_{p,q}$ allows for indefinite geometry (negative eigenvalues), covering models like the Stochastic Blockmodel (SBM) with $K \ge 3$ blocks, which previous methods (like Tang et al., 2017b) could not handle.
• Null Hypothesis ($H_0$): The distributions of the latent positions, $F_X$ and $F_Y$, are equivalent up to an indefinite orthogonal transformation ($Q \in O(p,q)$). That is, $F_X = F_Y \circ Q$. This accounts for the non-identifiability of the latent space in GRDPG.

2.2 Test Statistic: Maximum Mean Discrepancy (MMD)

The proposed test statistic is based on the Maximum Mean Discrepancy (MMD) applied to the rows of the Adjacency Spectral Embedding (ASE).

1. Embedding: Compute the ASE ($\hat{X}$ and $\hat{Y}$) for both graphs by taking the top $d$ eigenvectors of the adjacency matrices, scaled by the square root of the absolute eigenvalues.
2. Alignment: Because the ASE is only unique up to an orthogonal transformation, the rows of $\hat{X}$ and $\hat{Y}$ must be aligned before comparison.
3. Optimal Transport Alignment: The authors propose estimating the optimal orthogonal rotation matrix $\hat{W}$ using Optimal Transport (Wasserstein distance). Specifically, they solve a Procrustes-like problem to minimize the Wasserstein distance between the empirical distributions of the embedded rows.
   • They utilize Sinkhorn regularization to make the optimal transport computation efficient and stable.
   • The alignment is performed separately on the positive ($p$) and negative ($q$) eigenspaces to handle the indefinite metric.
4. U-Statistic: The test statistic is a two-sample U-statistic:
   $$U_{n,m}(\hat{X}\hat{W}, \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)$$
   where $\kappa$ is a characteristic, radial kernel (e.g., Gaussian).

2.3 Inference Procedure

Since the limiting distribution of the U-statistic under the null is complex and depends on the unknown underlying distribution, the authors propose a bootstrap permutation test:

1. Estimate $\hat{W}$ using the observed graphs.
2. Compute the observed test statistic.
3. Resample from the empirical distributions of the aligned embeddings to generate a null distribution.
4. Calculate the p-value.

3. Key Contributions

1. Handling Indefinite Geometry: The paper extends previous work (Tang et al., 2017b) to handle negative eigenvalues and repeated eigenvalues. This allows the test to be valid for a broader class of models, including balanced $K$-block SBMs where $K \ge 3$.
2. Differing Sizes: The methodology explicitly handles graphs with different numbers of vertices ($n \neq m$), a scenario where standard "matched pairs" approaches fail.
3. Sparse Regime Consistency: The authors prove consistency in sparse regimes where the average degree grows as $n^\alpha$ with $\alpha > 0$ (specifically requiring $n\alpha_n \gg \log^4 n$). This is a significant improvement over dense-graph assumptions in prior literature.
4. Optimal Transport for Alignment: They introduce a rigorous algorithm using Optimal Transport to estimate the rotation matrix $\hat{W}$, proving its convergence to the global optimum under specific initialization conditions.
5. Uniform Consistency: The test is shown to be consistent against a wide range of fixed alternatives, not just local ones.

4. Key Theoretical Results

• Theorem 3.1 (Sparse Regime): Under the null hypothesis, the scaled test statistic $(m\beta_m + n\alpha_n) U_{n,m}$ converges to the population MMD. Crucially, the difference between the statistic computed on estimated embeddings ($\hat{X}$) and true latent positions ($X$) vanishes almost surely, even in sparse settings.
• Theorem 3.2 (Convergence Rate): Quantifies the error between the estimated U-statistic and the population MMD, showing it is $O(\sqrt{\frac{\log(n+m)}{n}} + \sqrt{\frac{\log(n+m)}{m}})$.
• Corollary 3.3 (Dense Regime): For sufficiently dense graphs (average degree $> \sqrt{n} \log n$), the standard scaling $(m+n)$ applies, recovering results similar to Gretton et al. (2012) for Euclidean data.
• Proposition 3.5: Establishes the convergence rate of the Optimal Transport estimator $\hat{W}$ to the true alignment matrix, showing it depends on the eigengap and sparsity.
• Theorem 3.6: Proves that the alternating minimization algorithm (Sinkhorn + Procrustes) converges to a fixed point if initialized sufficiently close to the global optimum.

5. Significance and Impact

• Universality: The proposed test is universally consistent for the entire class of rank-$d$ network models (GRDPG), making it a powerful tool for general network analysis without needing to specify the exact generative model (e.g., SBM, DCSBM, Mixed-Membership).
• Robustness to Sparsity: By addressing the challenges of sparse graphs (where estimation error is high), the method is applicable to real-world networks (social, biological) which are typically sparse.
• Handling Non-Identifiability: The paper provides a rigorous mathematical framework for dealing with the non-identifiability of latent positions in indefinite inner product spaces, a common issue in spectral graph theory that was previously a barrier to nonparametric testing.
• Practical Utility: Numerical simulations demonstrate that the test maintains correct Type I error rates and achieves high power even for small sample sizes and varying degrees of sparsity, outperforming or extending the capabilities of existing methods.

In summary, this work bridges the gap between nonparametric statistics and network science, providing a theoretically grounded, flexible, and computationally feasible method for comparing networks of different sizes and structures.