Abstract
Sequential change-point detection for graphs is a fundamental problem for streaming network data types and has wide applications in social networks and power systems. Given fixed vertices and a sequence of random graphs, the objective is to detect the change-point where the underlying distribution of the random graph changes. In particular, we focus on the local change that only affects a subgraph. We adopt the classical Erdős-Rényi model and revisit the generalized likelihood ratio (GLR) detection procedure. The scan statistic is computed by sequentially estimating the most-likely subgraph where the change happens. We provide theoretical analysis for the asymptotic optimality of the proposed procedure based on the GLR framework and demonstrate the efficiency of our detection algorithm using simulations.
Introduction
In many real-world systems—like social networks, power grids, or seismic sensor arrays—data arrives as a continuous stream of graphs. A critical task in these environments is sequential change-point detection: identifying the exact moment the underlying structure of the network changes. This is challenging because changes are often local, affecting only a small subset of nodes, and we typically do not know when the change will occur or which specific nodes will be involved.
Problem Formulation
The authors model the network using the Erdős-Rényi (ER) model, where edges between nodes exist with a certain probability. They focus on a scenario where a network starts in a homogeneous state (probability $p_0$) and, at an unknown time $\tau$, a subset of nodes of size $n$ suddenly increases its internal connection probability to $p_1$.
Methodology
To address the uncertainty of the affected subgraph, the paper utilizes a Generalized Likelihood Ratio (GLR) Test. Since the specific subgraph is unknown, the algorithm "scans" through possible subgraphs to find the one that most likely represents a change. To maintain computational feasibility, the authors implement:
- Window-Limiting: The algorithm only looks back at a specific "window" of recent history to prevent computational costs from exploding over time.
- Greedy Approximation: Because finding the "densest $n$ subgraph" is NP-hard, a greedy heuristic is used to approximate the maximum likelihood estimate of the affected subgraph.
Key Insights and Theoretical Optimality
The core contribution of this work is the proof of first-order asymptotic optimality. The authors demonstrate that even without prior knowledge of which subgraph is changing, their GLR procedure achieves the same detection delay "slope" as an ideal CUSUM test that knows the subgraph in advance.
This detection speed is fundamentally limited by the Kullback–Leibler (KL) divergence between the pre-change and post-change distributions. The GLR statistic effectively recovers this information-theoretic bound, matching the lower bound $(I^{-1} \log \gamma)$ as the allowed false-alarm rate ($\gamma$) goes to infinity.
Key Results
Numerical simulations were conducted with networks of $N=20$ and $N=50$ nodes, where a small subgraph of $n=5$ nodes underwent a change from $p_0 = 0.2$ to $p_1 = 0.5$.
As shown in the performance plots, the GLR approach's detection delay closely follows the slope of the "ideal" CUSUM test. The results also highlight scaling effects: as the total network size ($N$) increases, the detection delay also increases. This confirms that as the "haystack" grows, finding the changing "needle" (the subgraph) requires more observations to maintain statistical confidence.
Limitations and Future Work
While the detection is mathematically optimal, the current model assumes the size of the affected subgraph ($n$) is known. Future research could extend this to scenarios where the community size is unknown, or to more complex graphical models that account for edge dependencies (like transitivity) and temporal dependencies where the network state at time $t$ depends on time $t-1$.
Summary updated