Calibrated Nonparametric Scan Statistics for Anomalous Pattern Detection in Graphs

Chunpai Wang, Daniel B. Neill, Feng Chen

Abstract

Detecting anomalous clusters or "hotspots" in complex networks is a critical task in graph mining, with applications ranging from public health to social media monitoring. Traditional Nonparametric Scan Statistics (NPSS) often suffer from miscalibration due to the multiple hypothesis testing problem—the "look-everywhere" effect—where searching over millions of subgraphs inevitably leads to false positives. This paper introduces Calibrated Nonparametric Scan Statistics (CNSS), a framework that recalibrates statistical thresholds to account for this bias. By combining randomization tests with efficient closed-form lower bounds derived from percolation theory, CNSS achieves significant improvements in precision and scalability.

The Challenge of Miscalibration in Graph Scanning

Graph anomaly detection often involves searching for connected subgraphs where node attributes deviate significantly from the norm. NPSS typically identifies subgraphs with an unusually high proportion of nodes having low p-values (significant nodes). However, in large graphs, the sheer number of possible connected subgraphs makes it highly likely to find clusters that appear anomalous purely by chance.

Existing methods fail to account for this statistical inflation, leading to "bloated" detections that include many normal nodes. This miscalibration results in low precision, as the algorithms become over-sensitive to random noise.

Calibrated Nonparametric Scan Statistics (CNSS)

To address these issues, the authors propose CNSS, which recalibrates the objective function used for subgraph selection.

1. The Calibration Step

Instead of using a fixed expected proportion of significant nodes ($\alpha$), CNSS uses a size-dependent threshold $\alpha'(N, \alpha)$. This threshold represents the expected maximum proportion of significant nodes one would find in any connected subgraph of size $N$ under the null hypothesis.

Calibration threshold alpha'(N, alpha) vs. subgraph size N across different graph types.

Calculating $\alpha'$ exactly is computationally prohibitive. The authors employ two main strategies:

  • Randomization Tests: Shuffling node p-values to empirically determine the distribution of the maximum proportion of significant nodes.
  • Theoretical Lower Bounds: To avoid the cost of repeated simulations, the authors derived closed-form lower bounds for $\alpha'$ using Percolation Theory and neighborhood analysis. These bounds allow for near-instantaneous threshold estimation.
Comparison of randomization tests and theoretical lower bounds for threshold estimation.

3. Scalable Search Algorithm

Finding the optimal subgraph is NP-hard. CNSS utilizes a greedy merging algorithm that starts from significant nodes and iteratively expands to maximize the significance ratio. To handle massive networks, a core-tree decomposition is applied, focusing the search on the graph's dense core while simplifying the periphery.

Experimental Evaluation

The authors tested CNSS on several real-world graph structures from the SNAP repository, including WikiVote, CondMat, and Twitter, using injected Gaussian signals. They also conducted a case study on COVID-19 spatial-temporal data across 3,234 U.S. counties.

Key Results

  • Improved Accuracy: CNSS significantly outperformed baselines, achieving an average F-score of 0.603 compared to 0.451 for the next best method (DFGS).
  • Computational Efficiency: The theoretical bounds provided a speedup of 400x to 2200x over randomization-based estimation, enabling the analysis of very large graphs.
  • Real-World Impact: In the COVID-19 study, CNSS identified hotspots with a 42% higher death rate than those found by uncalibrated methods, demonstrating its ability to pinpoint the most clinically relevant clusters.

Conclusion and Future Work

CNSS provides a robust solution to the miscalibration problem in graph anomaly detection. By shifting the focus from the search algorithm to the objective function's statistical validity, the authors have created a tool that is both more precise and more scalable. Future work may involve refining the heuristic search to provide stronger theoretical guarantees and exploring detection in scenarios with extremely low signal-to-noise ratios.

Summary updated

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 (on the expected maximum proportion of significant nodes for subgraphs of a given size, under the null hypothesis of no anomalous patterns). 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.
BibTeX
@inproceedings{wang2022calibrated,
  author = {Chunpai Wang and Daniel B. Neill and Feng Chen},
  title = {{Calibrated Nonparametric Scan Statistics for Anomalous Pattern Detection in Graphs}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i4.20339},
}
Figure