Concept Drift and Anomaly Detection in Graph Streams

Abstract

Graph representations offer powerful and intuitive ways to describe data in a multitude of application domains. Here, we consider stochastic processes generating graphs and propose a methodology for detecting changes in stationarity of such processes. The methodology is general and considers a process generating attributed graphs with a variable number of vertices/edges, without the need to assume one-to-one correspondence between vertices at different time steps. The methodology acts by embedding every graph of the stream into a vector domain, where a conventional multivariate change detection procedure can be easily applied. We ground the soundness of our proposal by proving several theoretical results. In addition, we provide a specific implementation of the methodology and evaluate its effectiveness on several detection problems involving attributed graphs representing biological molecules and drawings. Experimental results are contrasted with respect to suitable baseline methods, demonstrating the effectiveness of our approach.

References in corpus (1)

• Quantifying sudden changes in dynamical systems using symbolic networks

Cited by in corpus (13)

• A Gentle Introduction to Deep Learning for Graphs
• Learning Backtrackless Aligned-Spatial Graph Convolutional Networks for Graph Classification
• Detecting sequences of system states in temporal networks
• Change Detection in Graph Streams by Learning Graph Embeddings on Constant-Curvature Manifolds
• Graph Deep Learning for Time Series Forecasting
• Sequential Change-point Detection for High-dimensional and non-Euclidean Data
• DyEdgeGAT: Dynamic Edge via Graph Attention for Early Fault Detection in IIoT Systems
• Embedding and trajectories of temporal networks
• Change Point Methods on a Sequence of Graphs
• Counterfactual Explanations of Concept Drift
• Incremental Learning with Concept Drift Detection and Prototype-based Embeddings for Graph Stream Classification
• Learning Vertex Convolutional Networks for Graph Classification
• Online Graph Dictionary Learning