Change Point Methods on a Sequence of Graphs
This addresses the need for robust change detection in dynamic networks across technological, biological, and social domains, though it is incremental as it adapts existing CPMs to graph data.
The paper tackles the problem of detecting changes in stationarity within sequences of attributed graphs, proposing novel Change Point Methods (CPMs) that map graphs to vectors and apply statistical tests to identify shifts with confidence levels. Results demonstrate effectiveness in real-world applications like epileptic-seizure detection and graph classification.
Given a finite sequence of graphs, e.g., coming from technological, biological, and social networks, the paper proposes a methodology to identify possible changes in stationarity in the stochastic process generating the graphs. In order to cover a large class of applications, we consider the general family of attributed graphs where both topology (number of vertexes and edge configuration) and related attributes are allowed to change also in the stationary case. Novel Change Point Methods (CPMs) are proposed, that (i) map graphs into a vector domain; (ii) apply a suitable statistical test in the vector space; (iii) detect the change --if any-- according to a confidence level and provide an estimate for its time occurrence. Two specific multivariate CPMs have been designed: one that detects shifts in the distribution mean, the other addressing generic changes affecting the distribution. We ground our proposal with theoretical results showing how to relate the inference attained in the numerical vector space to the graph domain, and vice versa. We also show how to extend the methodology for handling multiple change points in the same sequence. Finally, the proposed CPMs have been validated on real data sets coming from epileptic-seizure detection problems and on labeled data sets for graph classification. Results show the effectiveness of what proposed in relevant application scenarios.