Laplacian Change Point Detection for Single and Multi-view Dynamic Graphs

• URL: http://arxiv.org/abs/2302.01204v1
• Date: Thu, 2 Feb 2023 16:30:43 GMT
• Title: Laplacian Change Point Detection for Single and Multi-view Dynamic Graphs
• Authors: Shenyang Huang, Samy Coulombe, Yasmeen Hitti, Reihaneh Rabbany, Guillaume Rabusseau
• Abstract summary: We focus on change point detection in dynamic graphs and address three main challenges associated with this problem. We first propose Laplacian Anomaly Detection (LAD) which uses the spectrum of graph Laplacian as the low dimensional embedding of the graph structure at each snapshot. Next, we propose MultiLAD, a simple and effective generalization of LAD to multi-view graphs.
• Score: 9.663142156296862
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Dynamic graphs are rich data structures that are used to model complex relationships between entities over time. In particular, anomaly detection in temporal graphs is crucial for many real world applications such as intrusion identification in network systems, detection of ecosystem disturbances and detection of epidemic outbreaks. In this paper, we focus on change point detection in dynamic graphs and address three main challenges associated with this problem: i). how to compare graph snapshots across time, ii). how to capture temporal dependencies, and iii). how to combine different views of a temporal graph. To solve the above challenges, we first propose Laplacian Anomaly Detection (LAD) which uses the spectrum of graph Laplacian as the low dimensional embedding of the graph structure at each snapshot. LAD explicitly models short term and long term dependencies by applying two sliding windows. Next, we propose MultiLAD, a simple and effective generalization of LAD to multi-view graphs. MultiLAD provides the first change point detection method for multi-view dynamic graphs. It aggregates the singular values of the normalized graph Laplacian from different views through the scalar power mean operation. Through extensive synthetic experiments, we show that i). LAD and MultiLAD are accurate and outperforms state-of-the-art baselines and their multi-view extensions by a large margin, ii). MultiLAD's advantage over contenders significantly increases when additional views are available, and iii). MultiLAD is highly robust to noise from individual views. In five real world dynamic graphs, we demonstrate that LAD and MultiLAD identify significant events as top anomalies such as the implementation of government COVID-19 interventions which impacted the population mobility in multi-view traffic networks.

Related papers

• InstructG2I: Synthesizing Images from Multimodal Attributed Graphs [50.852150521561676]
  We propose a graph context-conditioned diffusion model called InstructG2I. InstructG2I first exploits the graph structure and multimodal information to conduct informative neighbor sampling. A Graph-QFormer encoder adaptively encodes the graph nodes into an auxiliary set of graph prompts to guide the denoising process.
  arXiv  Detail & Related papers  (2024-10-09T17:56:15Z)
• Multivariate Time-Series Anomaly Detection based on Enhancing Graph Attention Networks with Topological Analysis [31.43159668073136]
  Unsupervised anomaly detection in time series is essential in industrial applications, as it significantly reduces the need for manual intervention. Traditional methods use Graph Neural Networks (GNNs) or Transformers to analyze spatial while RNNs to model temporal dependencies. This paper introduces a novel temporal model built on an enhanced Graph Attention Network (GAT) for multivariate time series anomaly detection called TopoGDN.
  arXiv  Detail & Related papers  (2024-08-23T14:06:30Z)
• Entropy Causal Graphs for Multivariate Time Series Anomaly Detection [7.402342914903391]
  This work proposes a novel framework called CGAD, an entropy Causal Graph for multivariate time series Anomaly Detection. CGAD utilizes transfer entropy to construct graph structures that unveil the underlying causal relationships among time series data. CGAD outperforms state-of-the-art methods on real-world datasets with a 15% average improvement.
  arXiv  Detail & Related papers  (2023-12-15T01:35:00Z)
• Hierarchical Joint Graph Learning and Multivariate Time Series Forecasting [0.16492989697868887]
  We introduce a method of representing multivariate signals as nodes in a graph with edges indicating interdependency between them. We leverage graph neural networks (GNN) and attention mechanisms to efficiently learn the underlying relationships within the time series data. The effectiveness of our proposed model is evaluated across various real-world benchmark datasets designed for long-term forecasting tasks.
  arXiv  Detail & Related papers  (2023-11-21T14:24:21Z)
• Coupled Attention Networks for Multivariate Time Series Anomaly Detection [10.620044922371177]
  We propose a coupled attention-based neural network framework (CAN) for anomaly detection in multivariate time series data. To capture inter-sensor relationships and temporal dependencies, a convolutional neural network based on the global-local graph is integrated with a temporal self-attention module.
  arXiv  Detail & Related papers  (2023-06-12T13:42:56Z)
• EasyDGL: Encode, Train and Interpret for Continuous-time Dynamic Graph Learning [92.71579608528907]
  This paper aims to design an easy-to-use pipeline (termed as EasyDGL) composed of three key modules with both strong ability fitting and interpretability. EasyDGL can effectively quantify the predictive power of frequency content that a model learn from the evolving graph data.
  arXiv  Detail & Related papers  (2023-03-22T06:35:08Z)
• DAGAD: Data Augmentation for Graph Anomaly Detection [57.92471847260541]
  This paper devises a novel Data Augmentation-based Graph Anomaly Detection (DAGAD) framework for attributed graphs. A series of experiments on three datasets prove that DAGAD outperforms ten state-of-the-art baseline detectors concerning various mostly-used metrics.
  arXiv  Detail & Related papers  (2022-10-18T11:28:21Z)
• Multivariate Time Series Forecasting with Dynamic Graph Neural ODEs [65.18780403244178]
  We propose a continuous model to forecast Multivariate Time series with dynamic Graph neural Ordinary Differential Equations (MTGODE) Specifically, we first abstract multivariate time series into dynamic graphs with time-evolving node features and unknown graph structures. Then, we design and solve a neural ODE to complement missing graph topologies and unify both spatial and temporal message passing.
  arXiv  Detail & Related papers  (2022-02-17T02:17:31Z)
• Learning Multi-Granular Hypergraphs for Video-Based Person Re-Identification [110.52328716130022]
  Video-based person re-identification (re-ID) is an important research topic in computer vision. We propose a novel graph-based framework, namely Multi-Granular Hypergraph (MGH) to better representational capabilities. 90.0% top-1 accuracy on MARS is achieved using MGH, outperforming the state-of-the-arts schemes.
  arXiv  Detail & Related papers  (2021-04-30T11:20:02Z)
• Laplacian Change Point Detection for Dynamic Graphs [10.556288610354997]
  We propose Laplacian Anomaly Detection (LAD) which uses the spectrum of the Laplacian matrix of the graph structure at each snapshot to obtain low dimensional embeddings. In synthetic experiments, LAD outperforms the state-of-the-art method. We also evaluate our method on three real dynamic networks: UCI message network, US senate co-sponsorship network and Canadian bill voting network.
  arXiv  Detail & Related papers  (2020-07-02T16:24:24Z)
• Structural Temporal Graph Neural Networks for Anomaly Detection in Dynamic Graphs [54.13919050090926]
  We propose an end-to-end structural temporal Graph Neural Network model for detecting anomalous edges in dynamic graphs. In particular, we first extract the $h$-hop enclosing subgraph centered on the target edge and propose the node labeling function to identify the role of each node in the subgraph. Based on the extracted features, we utilize Gated recurrent units (GRUs) to capture the temporal information for anomaly detection.
  arXiv  Detail & Related papers  (2020-05-15T09:17:08Z)

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.