Abstract
Dataset shift refers to the problem where the input data distribution may change over time (e.g., between training and test stages). Since this can be a critical bottleneck in several safety-critical applications such as healthcare, drug-discovery, etc., dataset shift detection has become an important research issue in machine learning. Though several existing efforts have focused on image/video data, applications with graph-structured data have not received sufficient attention. Therefore, in this paper, we investigate the problem of detecting shifts in graph structured data through the lens of statistical hypothesis testing. Specifically, we propose a practical two-sample test based approach for shift detection in large-scale graph structured data. Our approach is very flexible in that it is suitable for both undirected and directed graphs, and eliminates the need for equal sample sizes. Using empirical studies, we demonstrate the effectiveness of the proposed test in detecting dataset shifts. We also corroborate these findings using real-world datasets, characterized by directed graphs and a large number of nodes.
Introduction
Machine learning models often fail silently when the real-world data they process differs from their training data. This phenomenon, known as dataset shift, is a primary culprit behind the failure of machine learning systems in the wild. While established methods exist for detecting shifts in Euclidean data (like images or audio), detecting shifts in graph-structured data—such as brain connectivity networks, social graphs, or molecular structures—remains severely under-explored.
Existing statistical tests for graphs are often highly restrictive, typically requiring equal sample sizes and only supporting undirected, unweighted graphs. This paper introduces a highly flexible, statistical two-sample testing method designed to overcome these limitations, providing a practical safeguard for safety-critical applications like healthcare and network analysis.
Methodology
The authors propose a novel two-sample hypothesis test based on the Frobenius distance between the population adjacency matrices of two graph datasets.
- Test Statistic: A new test statistic ($T_{new}$) is formulated using U-statistics, providing a minimum-variance unbiased estimator for the distance between graph populations.
- Flexibility: The mathematical framework accommodates directed and weighted edges and explicitly removes the requirement for equal sample sizes ($m \neq n$).
- Implementation: Due to the analytical complexity of the asymptotic null distribution, the authors employ a permutation-based approach. By pooling and shuffling datasets, they estimate $p$-values to determine if a statistically significant shift has occurred.
Experimental Setup
The proposed method was evaluated using both simulated and real-world datasets:
- Simulated Data: Sparse graphs generated via stochastic block models under the Inhomogeneous Erdős-Rényi (IER) model were used to test varying sparsity, graph sizes, and sample imbalances.
- MIT Phone-Call Network: A dataset of 299 directed, unweighted networks tracking communication patterns, featuring imbalanced sample sizes (weekdays vs. weekends).
- ABIDE fMRI Dataset: A healthcare dataset comprising 871 undirected, weighted brain functional connectivity graphs, stratified by demographics and Autism Spectrum Disorder (ASD) diagnosis.
Results and Discussion
Empirical results demonstrate that the proposed test consistently achieves higher statistical power compared to state-of-the-art baselines, such as $T_{fro}$ and $T_{asymp}$. This advantage is particularly pronounced as graph size and sparsity increase. Notably, the test maintains high power even with very small sample sizes (e.g., $m=n=10$) on large graphs.
In real-world scenarios, the test successfully detected behavioral shifts in the MIT Phone dataset ($p < 0.001$) and uncovered hidden stratification in the ABIDE dataset. For instance, it identified significant distribution shifts based on age within both healthy and ASD populations—shifts that baseline methods either failed to detect or could not process due to sample imbalance. These findings highlight the importance of shift detection as a necessary audit before trusting model predictions in clinical settings.
Conclusion
While the theoretical guarantees rely on the assumption of edge independence (IER model), the proposed method offers a robust and flexible framework for detecting dataset shifts in complex graph data. Future work involves integrating these detection mechanisms directly into automated MLOps pipelines to trigger real-time warnings or model retraining, ensuring the reliability of graph-based applications in safety-critical domains.
Summary updated