Abstract
It has become an increasingly common practice for scientists in modern science and engineering to collect samples of multiple network data in which a network serves as a basic data object. The increasing prevalence of multiple network data calls for developments of models and theory that can deal with inference problems for populations of networks. In this work, we propose a general procedure for hypothesis testing of networks and in particular, for differentiating distributions of two samples of networks. We consider a very general framework which allows us to perform tests on large and sparse networks. Our contribution is two-fold: (1) We propose a test statistics based on the singular value of a generalized Wigner matrix. The asymptotic null distribution of the statistics is shown to follow the Tracy–Widom distribution as the number of nodes tends to infinity. The test also yields asymptotic power guarantee with the power tending to one under the alternative; (2) The test procedure is adapted for change-point detection in dynamic networks which is proven to be consistent in detecting the change-points. In addition to theoretical guarantees, another appealing feature of this adapted procedure is that it provides a principled and simple method for selecting the threshold that is also allowed to vary with time. Extensive simulation studies and real data analyses demonstrate the superior performance of our procedure with competitors.
Introduction
In modern data science, we increasingly encounter "populations" of networks—for example, a set of brain connectivity maps from healthy patients versus a set from those with a specific medical condition. While traditional network analysis often focuses on a single, static graph, there is a significant gap in tools that can statistically compare groups of networks. Existing methods often struggle with the inherent sparsity and scale of real-world networks, which violate the assumptions of many classical statistical tests. Furthermore, many change-point detection algorithms require arbitrary "magic numbers" or extensive cross-validation to set thresholds for significance.
This paper introduces a mathematically rigorous yet practical framework for hypothesis testing on network populations, specifically designed to handle the challenges of large and sparse data. By leveraging random matrix theory, the authors provide a principled way to differentiate network distributions and detect change-points in dynamic systems without the need for manual parameter tuning.
Methodology: The TW1-Type Test
The core of the proposed approach is a TW1-type test. The procedure aims to determine if two samples of networks originate from the same underlying distribution of link probabilities.
The Test Statistic
The authors propose a test statistic based on the largest singular value of a standardized matrix, $\hat{Z}$, which represents the difference between the estimated link probabilities of the two populations. A key technical breakthrough is the proof that, under the null hypothesis (where the two samples come from the same distribution), this statistic asymptotically follows the Tracy–Widom distribution (Index 1). This result allows for precise p-value calculation as the number of nodes ($n$) grows toward infinity.
Plugin Estimators
Since the true underlying link probabilities are unknown, the authors evaluate three "plugin" estimators to approximate them:
- Average (AVG): A simple empirical mean of the samples.
- Stochastic Block Model (SBM): Effective if the network follows a clear community structure.
- Modified Neighborhood Smoothing (MNBS): A robust approach that estimates probabilities by comparing node neighborhoods. MNBS is particularly valuable because it does not require prior knowledge of the number of communities and performs well even when the underlying structure is complex or non-block-like.
Dynamic Change-Point Detection
The authors adapt the two-sample test into a "scan statistic" for dynamic networks. By sliding a window across a temporal sequence of networks, they can identify time points where the network structure shifts significantly. Crucially, the threshold for detection is derived directly from Tracy–Widom theory. This provides a principled method for selecting thresholds that can vary over time, making it much easier for practitioners to use reliably compared to heuristic-based methods.
Empirical Validation
The framework was evaluated using both synthetic simulations and real-world datasets.
Synthetic Results
Using various "graphon" models to simulate different network structures and levels of sparsity, the authors found that the TW1-MNBS test maintained stable Type I error rates (around the 0.05 target). As the number of nodes increased, the test achieved near-perfect power, correctly identifying differences that standard $\chi^2$ tests missed or produced unreliable results for.
Real-World Applications
- Brain Functional Networks (COBRE): On a dataset of 72 patients with schizophrenia and 74 healthy controls, the TW1-MNBS test successfully identified structural differences between the groups at thresholds where other methods failed to find a significant signal.
- MIT Reality Mining (RM): In a dynamic dataset of phone call logs and proximity data among 106 students and staff, the change-point detection algorithm accurately identified transitions corresponding to the start of semesters, holidays (like Thanksgiving), and exam periods, outperforming several established competitors.
Discussion and Limitations
While the TW1-type test offers a robust solution for network population inference, the authors acknowledge areas for future exploration. The current framework assumes edge independence (conditional on link probabilities), which may not hold in certain social network contexts. Additionally, while the MNBS estimator is highly robust, the neighborhood smoothing step can be computationally intensive for extremely large, dense populations. Future work will focus on deriving tighter error bounds for the MNBS estimator and extending the framework to models with dependent edges.
Summary updated