Calibrated Nonparametric Scan Statistics for Anomalous Pattern Detection in Graphs
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.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Lineage
Builds on1
Related papers
- Normality Calibration in Semi-supervised Graph Anomaly DetectionGuolei Zeng, Hezhe Qiao, Guoguo Ai, Jinsong Guo et al.ICML 2026 · 1 citation
- Mining Top-k Pairs of Correlated Subgraphs in a Large NetworkArneish Prateek, Arijit Khan, Akshit Goyal, Sayan RanuVLDB 2020 · 13 citations
- Mitigating Homophily Disparity in Graph Anomaly Detection: A Scalable and Adaptive ApproachYunhui Liu, Qizhuo Xie, Yinfeng Chen, Xudong Jin et al.WWW 2026
- HOPS: Probabilistic Subtree Mining for Small and Large GraphsPascal Welke, Florian Seiffarth, Michael Kamp, Stefan WrobelKDD 2020 · 5 citations
- Decoupling Representation Learning and Classification for GNN-based Anomaly DetectionYanling Wang, Jing Zhang, Shasha Guo, Hongzhi Yin et al.SIGIR 2021 · 120 citations
