Laplacian Change Point Detection for Dynamic Graphs

• URL: http://arxiv.org/abs/2007.01229v1
• Date: Thu, 2 Jul 2020 16:24:24 GMT
• Title: Laplacian Change Point Detection for Dynamic Graphs
• Authors: Shenyang Huang, Yasmeen Hitti, Guillaume Rabusseau, Reihaneh Rabbany
• Abstract summary: 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.
• Score: 10.556288610354997
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Dynamic and temporal 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 two main challenges associated with this problem: I) how to compare graph snapshots across time, II) how to capture temporal dependencies. To solve the above challenges, 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. LAD explicitly models short term and long term dependencies by applying two sliding windows. 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. In all three datasets, we demonstrate that our method can more effectively identify anomalous time points according to significant real world events.

Related papers

• SLADE: Detecting Dynamic Anomalies in Edge Streams without Labels via Self-Supervised Learning [24.41015179377796]
  We propose SLADE (Self-supervised Learning for Anomaly Detection in Edge Streams) for rapid detection of dynamic anomalies in edge streams. In dynamic anomaly detection across four real-world datasets, SLADE outperforms nine competing methods.
  arXiv  Detail & Related papers  (2024-02-19T08:19:26Z)
• GLAD: Content-aware Dynamic Graphs For Log Anomaly Detection [49.9884374409624]
  GLAD is a Graph-based Log Anomaly Detection framework designed to detect anomalies in system logs. We introduce GLAD, a Graph-based Log Anomaly Detection framework designed to detect anomalies in system logs.
  arXiv  Detail & Related papers  (2023-09-12T04:21:30Z)
• Spatial-Temporal Graph Enhanced DETR Towards Multi-Frame 3D Object Detection [54.041049052843604]
  We present STEMD, a novel end-to-end framework that enhances the DETR-like paradigm for multi-frame 3D object detection. First, to model the inter-object spatial interaction and complex temporal dependencies, we introduce the spatial-temporal graph attention network. Finally, it poses a challenge for the network to distinguish between the positive query and other highly similar queries that are not the best match.
  arXiv  Detail & Related papers  (2023-07-01T13:53:14Z)
• 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)
• Temporal Aggregation and Propagation Graph Neural Networks for Dynamic Representation [67.26422477327179]
  Temporal graphs exhibit dynamic interactions between nodes over continuous time. We propose a novel method of temporal graph convolution with the whole neighborhood. Our proposed TAP-GNN outperforms existing temporal graph methods by a large margin in terms of both predictive performance and online inference latency.
  arXiv  Detail & Related papers  (2023-04-15T08:17:18Z)
• Laplacian Change Point Detection for Single and Multi-view Dynamic Graphs [9.663142156296862]
  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.
  arXiv  Detail & Related papers  (2023-02-02T16:30:43Z)
• Evidential Temporal-aware Graph-based Social Event Detection via Dempster-Shafer Theory [76.4580340399321]
  We propose ETGNN, a novel Evidential Temporal-aware Graph Neural Network. We construct view-specific graphs whose nodes are the texts and edges are determined by several types of shared elements respectively. Considering the view-specific uncertainty, the representations of all views are converted into mass functions through evidential deep learning (EDL) neural networks.
  arXiv  Detail & Related papers  (2022-05-24T16:22:40Z)
• Spatio-Temporal Joint Graph Convolutional Networks for Traffic Forecasting [75.10017445699532]
  Recent have shifted their focus towards formulating traffic forecasting as atemporal graph modeling problem. We propose a novel approach for accurate traffic forecasting on road networks over multiple future time steps.
  arXiv  Detail & Related papers  (2021-11-25T08:45:14Z)
• Anomaly Detection in Dynamic Graphs via Transformer [30.926884264054042]
  We present a novel Transformer-based Anomaly Detection framework for DYnamic graph (TADDY) Our framework constructs a comprehensive node encoding strategy to better represent each node's structural and temporal roles in an evolving graphs stream. Our proposed TADDY framework outperforms the state-of-the-art methods by a large margin on four real-world datasets.
  arXiv  Detail & Related papers  (2021-06-18T02:27:19Z)
• Learning Graph Structures with Transformer for Multivariate Time Series Anomaly Detection in IoT [11.480824844205864]
  This work proposed a novel framework, namely GTA, for multivariate time series anomaly detection by automatically learning a graph structure followed by the graph convolution. We also devised a novel graph convolution named Influence propagation convolution to model the anomaly information flow between graph nodes. The experiments on four public anomaly detection benchmarks further demonstrate our approach's superiority over other state-of-the-arts.
  arXiv  Detail & Related papers  (2021-04-08T01:45:28Z)
• 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.