TL;DR
This paper addresses a critical flaw in a popular method for comparing random graphs: it fails when the graphs have different numbers of nodes. The authors propose a simple yet effective correction, "Corrected Adjacency Spectral Embeddings" (CASE), which makes the test valid and reliable even for graphs of unequal size. This advancement is crucial for real-world applications like comparing brain connectomes, where graph sizes naturally vary.
What Problem Does This Paper Address?
Comparing complex networks, or graphs, is fundamental in many fields, from neuroscience to social science. A key task is determining if two graphs were generated by the same underlying process (i.e., have the same "generating distribution"). A popular method for this, proposed by Tang et al. (2017), involves embedding graph structures into a lower-dimensional space and then using a kernel-based test to compare these embeddings. However, this method has a critical flaw: it assumes the graphs being compared have the same number of nodes (vertices). When this assumption is violated, the test becomes invalid, leading to incorrect conclusions. This is a significant limitation, as real-world datasets, like brain connectomes, often have varying numbers of nodes.
Methods
The core of the paper's contribution lies in its proposed solution to the invalidity of the existing test. The original test relies on Adjacency Spectral Embeddings (ASE), which estimate the latent positions of graph vertices. The problem arises because the statistical properties of these ASEs, specifically their variance, depend on the number of vertices in the graph. When comparing graphs of different sizes, these differing variances lead to an "incongruity" that makes the subsequent kernel test invalid.
The authors introduce Corrected Adjacency Spectral Embeddings (CASE). The idea is to adjust the ASEs of the larger graph by adding carefully scaled Gaussian noise. This noise effectively inflates the variance of the larger graph's ASEs to match that of the smaller graph. This makes the corrected embeddings (CASE) exchangeable under the null hypothesis, meaning their distributions are similar even if the original graphs had different numbers of vertices. This corrected embedding can then be fed into the original kernel two-sample test, rendering it valid and consistent.
Datasets
The paper uses synthetic datasets generated from Erdös-Rényi (ER) graphs, Stochastic Block Models (SBMs), and Random Dot Product Graphs (RDPGs) for simulation studies.
For the real-world application, the authors utilize a dataset of human connectomes derived from diffusion magnetic resonance imaging (dMRI). This dataset consists of 57 subjects, each with two dMRI scans. Each scan was processed to generate both a 'large' and a 'small' graph, resulting in graphs of different scales (varying numbers of vertices).
Key Insights and Ideas
- The Devil is in the Variance: The fundamental insight is that the variance of the Adjacency Spectral Embedding (ASE) is directly tied to the number of vertices. This seemingly small detail breaks the symmetry required for valid hypothesis testing when comparing graphs of different sizes.
- Noise as a Fix: Injecting scaled Gaussian noise into the ASEs of the larger graph is a surprisingly simple yet effective way to equalize variances and restore the test's validity. It's a clever way to "level the playing field" for statistical comparison.
- Real-World Relevance: The problem isn't just theoretical. Brain connectomes naturally vary in size, making the original test unusable for many important neuroscience applications. The CASE method directly addresses this gap.
- Beyond ER Graphs: The authors demonstrate the validity of their approach not only for simple Erdös-Rényi graphs but also for more complex models like SBMs and general RDPGs, highlighting its broad applicability.
Key Results
- Validity Restored: Simulation studies show that the original test (using ASE) becomes invalid as the difference in graph sizes increases, exhibiting inflated Type I error rates (rejecting the null hypothesis when it's true). In contrast, the proposed CASE method maintains a valid test size close to the nominal significance level (e.g., 0.05) across various graph size ratios and model types.
- Power Maintained: The CASE method not only corrects validity but also retains good statistical power, meaning it can effectively detect differences between graphs when they truly exist. Power generally increases with sample size and is robust across different graph generation models.
- Real-World Impact: Applying the CASE method to dMRI brain connectome data revealed significant differences between graphs of different scales within the same subject and scan. This demonstrates the practical utility of the corrected test in identifying subtle structural variations in brain networks. The corrected test also showed a tendency to reject less often than the uncorrected test, aligning with the intuition that graphs from the same subject/scan should be more similar.
Limitations and Future Work
- Nondeterministic Procedure: The CASE method relies on sampling additive noise, making it nondeterministic. While this is often acceptable in statistical testing, it's a characteristic to be aware of.
- Limit Theory: The authors suggest developing limit theory for the corrected adjacency spectral embeddings and the test statistics that use them. This would provide a stronger theoretical foundation for the method.
- Broader Applicability: The approach of modifying embeddings could potentially be extended to other embedding techniques (like Laplacian spectral embedding) and more general graph models beyond RDPGs, such as Generalized Random Dot Product Graphs.
- Goodness-of-Fit Tests: The paper notes the absence of goodness-of-fit tests for random dot product graphs and suggests that the work presented might facilitate future research in this area.
Summary updated