Online non-parametric change-point detection for heterogeneous data streams observed over graph nodes
This work addresses change-point detection for heterogeneous data streams in graph-based systems, which is an incremental improvement over existing methods.
The paper tackles the problem of detecting change-points in heterogeneous data streams from graph nodes, proposing an online non-parametric method that estimates likelihood-ratios using kernels and graph connectivity. It demonstrates the method's quality on synthetic and real-world applications, though no concrete numbers are provided.
Consider a heterogeneous data stream being generated by the nodes of a graph. The data stream is in essence composed by multiple streams, possibly of different nature that depends on each node. At a given moment $τ$, a change-point occurs for a subset of nodes $C$, signifying the change in the probability distribution of their associated streams. In this paper we propose an online non-parametric method to infer $τ$ based on the direct estimation of the likelihood-ratio between the post-change and the pre-change distribution associated with the data stream of each node. We propose a kernel-based method, under the hypothesis that connected nodes of the graph are expected to have similar likelihood-ratio estimates when there is no change-point. We demonstrate the quality of our method on synthetic experiments and real-world applications.