Online non-parametric change-point detection for heterogeneous data streams observed over graph nodes

• URL: http://arxiv.org/abs/2110.10518v1
• Date: Wed, 20 Oct 2021 12:10:15 GMT
• Title: Online non-parametric change-point detection for heterogeneous data streams observed over graph nodes
• Authors: Alejandro de la Concha and Argyris Kalogeratos and Nicolas Vayatis
• Abstract summary: We propose an online non-parametric method to infer $tau$ 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 demonstrate the quality of our method on synthetic experiments and real-world applications.
• Score: 79.94639436527454
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 $\tau$, 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 $\tau$ 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.

Related papers

• Leveraging Invariant Principle for Heterophilic Graph Structure Distribution Shifts [42.77503881972965]
  Heterophilic Graph Neural Networks (HGNNs) have shown promising results for semi-supervised learning tasks on graphs. How to learn invariant node representations on heterophilic graphs to handle this structure difference or distribution shifts remains unexplored. We propose textbfHEI, a framework capable of generating invariant node representations through incorporating heterophily information.
  arXiv  Detail & Related papers  (2024-08-18T14:10:34Z)
• Online Centralized Non-parametric Change-point Detection via Graph-based Likelihood-ratio Estimation [77.81487285123147]
  Consider each node of a graph to be generating a data stream that is synchronized and observed at near real-time. At a change-point $tau$, a change occurs at a subset of nodes $C$, which affects the probability distribution of their associated node streams. We propose a novel kernel-based method to both detect $tau$ and localize $C$, based on the direct estimation of the likelihood-ratio between the post-change and the pre-change distributions of the node streams.
  arXiv  Detail & Related papers  (2023-01-08T10:15:24Z)
• Graph Convolutional Neural Networks with Diverse Negative Samples via Decomposed Determinant Point Processes [21.792376993468064]
  Graph convolutional networks (GCNs) have achieved great success in graph representation learning. In this paper, we use quality-diversity decomposition in determinant point processes to obtain diverse negative samples. We propose a new shortest-path-base method to improve computational efficiency.
  arXiv  Detail & Related papers  (2022-12-05T06:31:31Z)
• Collaborative likelihood-ratio estimation over graphs [55.98760097296213]
  Graph-based Relative Unconstrained Least-squares Importance Fitting (GRULSIF) We develop this idea in a concrete non-parametric method that we call Graph-based Relative Unconstrained Least-squares Importance Fitting (GRULSIF) We derive convergence rates for our collaborative approach that highlights the role played by variables such as the number of available observations per node, the size of the graph, and how accurately the graph structure encodes the similarity between tasks.
  arXiv  Detail & Related papers  (2022-05-28T15:37:03Z)
• Data-heterogeneity-aware Mixing for Decentralized Learning [63.83913592085953]
  We characterize the dependence of convergence on the relationship between the mixing weights of the graph and the data heterogeneity across nodes. We propose a metric that quantifies the ability of a graph to mix the current gradients. Motivated by our analysis, we propose an approach that periodically and efficiently optimize the metric.
  arXiv  Detail & Related papers  (2022-04-13T15:54:35Z)
• Gransformer: Transformer-based Graph Generation [14.161975556325796]
  Gransformer is an algorithm based on Transformer for generating graphs. We modify the Transformer encoder to exploit the structural information of the given graph. We also introduce a graph-based familiarity measure between node pairs.
  arXiv  Detail & Related papers  (2022-03-25T14:05:12Z)
• Score-based Generative Modeling of Graphs via the System of Stochastic Differential Equations [57.15855198512551]
  We propose a novel score-based generative model for graphs with a continuous-time framework. We show that our method is able to generate molecules that lie close to the training distribution yet do not violate the chemical valency rule.
  arXiv  Detail & Related papers  (2022-02-05T08:21:04Z)
• Learning Representations using Spectral-Biased Random Walks on Graphs [18.369974607582584]
  We study how much a probabilistic bias in this process affects the quality of the nodes picked by the process. We succinctly capture this neighborhood as a probability measure based on the spectrum of the node's neighborhood subgraph represented as a normalized laplacian matrix. We empirically evaluate our approach against several state-of-the-art node embedding techniques on a wide variety of real-world datasets.
  arXiv  Detail & Related papers  (2020-05-19T20:42:43Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.