  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.
