Abstract
We propose a new approach, the calibrated nonparametric scan statistic (CNSS), for more accurate detection of anomalous patterns in large-scale, real-world graphs. Scan statistics identify connected subgraphs that are interesting or unexpected through maximization of a likelihood ratio statistic; in particular, nonparametric scan statistics (NPSSs) identify subgraphs with a higher than expected proportion of individually significant nodes. However, we show that recently proposed NPSS methods are miscalibrated, failing to account for the maximization of the statistic over the multiplicity of subgraphs. This results in both reduced detection power for subtle signals, and low precision of the detected subgraph even for stronger signals. Thus we develop a new statistical approach to recalibrate NPSSs, correctly adjusting for multiple hypothesis testing and taking the underlying graph structure into account. While the recalibration, based on randomization testing, is computationally expensive, we propose both an efficient (approximate) algorithm and new, closed-form lower bounds. These advances, along with the integration of recent core-tree decomposition methods, enable CNSS to scale to large real-world graphs, with substantial improvement in the accuracy of detected subgraphs. Extensive experiments on both semi-synthetic and real-world datasets are demonstrated to validate the effectiveness of our proposed methods, in comparison with state-of-the-art counterparts.
Introduction
In domains ranging from epidemiology to financial fraud detection, identifying "hotspots"—connected subgraphs where activity deviates significantly from the norm—is a critical task. Scan statistics serve as the primary tool for this purpose, searching for subgraphs that maximize a likelihood ratio statistic. Nonparametric scan statistics (NPSS) have gained popularity because they do not require rigid assumptions about the underlying data distribution. Instead, they identify subgraphs containing a higher-than-expected proportion of "significant" nodes (nodes with low p-values).
However, existing NPSS methods suffer from a fundamental flaw: miscalibration. When searching through millions of potential connected subgraphs, the likelihood of finding an anomalous-looking cluster by pure chance increases dramatically. Current methods fail to account for this "multiplicity of subgraphs," leading to a bias where the algorithm selects overly large, noisy clusters that obscure the actual signal.
The Problem: Multiplicity and Miscalibration
The core issue identified in this research is that uncalibrated NPSS methods do not adjust for the scale of the search space. In a large graph, the probability of finding a subgraph with a high proportion of significant nodes under the null hypothesis (where no true anomaly exists) is much higher than the theoretical expectation for a single node. This results in low precision; the algorithm "cheats" by picking up random noise that accumulates over the search space, often resulting in the selection of the largest possible significance threshold and dispersed, low-quality detections.
Proposed Method: Calibrated Nonparametric Scan Statistics (CNSS)
To address this, we introduce Calibrated Nonparametric Scan Statistics (CNSS). The framework replaces the standard expected proportion of significant nodes ($\alpha$) with a calibrated value ($\alpha'$) representing the expected maximum proportion of significant nodes one would find by searching over all subgraphs of a given size under the null hypothesis.
To make this approach computationally viable for massive real-world networks, we developed three key innovations:
- Efficient Approximation: Finding the maximum number of significant nodes in a connected subgraph is an NP-hard problem. We utilize a greedy merging heuristic that approximates this value rapidly, ensuring the calibration remains feasible.
- Closed-Form Lower Bounds: To bypass the need for thousands of time-consuming randomization tests, we derived mathematical lower bounds for the calibrated threshold using Network Neighborhood Analysis and Percolation Theory. This allows for a "warm start" or a purely analytical approximation of the calibration.
- Core-Tree Decomposition: Real-world networks often feature a "core-periphery" structure. By compressing the tree-like "whiskers" of the graph into a dense core, we can perform optimization on a significantly reduced graph without sacrificing detection accuracy.
Experimental Evaluation
We evaluated CNSS against six state-of-the-art baselines (including LTSS and EventTree) using both synthetic and real-world data.
Semi-synthetic Benchmarks
Using five SNAP networks (WikiVote, CondMat, Twitter, Slashdot, and DBLP), we injected synthetic anomalous signals into real graph structures. CNSS consistently outperformed all baselines. In terms of F-score—a metric balancing precision and recall—CNSS achieved an average of 0.603, significantly higher than the best-performing baseline, DFGS, which averaged 0.451.
Real-World Case Studies
- COVID-19 Spatio-temporal Analysis: We analyzed daily confirmed cases across 3,234 U.S. counties. CNSS identified subgraphs with a 42% higher death rate than those found by other methods. While baselines produced dispersed, fragmented patterns, CNSS pinpointed cohesive geographic regions with high severity.
- Twitter Event Detection: In a graph of over 100,000 hashtags related to #BlackLivesMatter, CNSS successfully localized specific social events with higher precision than uncalibrated methods.
Key Insights and Conclusion
The research demonstrates that the degree of miscalibration in graph scans is not constant; it depends heavily on the graph's size, density, and connectivity. By accounting for this structure, CNSS provides a much-needed correction to the multiplicity bias. Furthermore, the use of derived lower bounds resulted in a 400x to 2200x speedup over full randomization testing, making high-precision anomaly detection practical for large-scale networks.
While the current search algorithm is heuristic, the results show that as long as the same approximation is used for both the data and the calibration step, the resulting statistic remains well-calibrated. Future work will explore adapting this calibration framework to other families of scan statistics and investigating its performance across diverse graph topologies.
Summary updated