Title: 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.