Anomaly and Change Detection in Graph Streams through Constant-Curvature Manifold Embeddings
This addresses the challenge of accurately modeling complex graph data for anomaly detection, though it appears incremental as it adapts existing embedding and change detection methods to non-Euclidean geometries.
The paper tackled the problem of detecting changes and anomalies in sequences of attributed graphs by embedding them into constant-curvature manifolds (hyper-spherical and hyperbolic) instead of Euclidean spaces, with preliminary results showing potential improvements in detection capabilities.
Mapping complex input data into suitable lower dimensional manifolds is a common procedure in machine learning. This step is beneficial mainly for two reasons: (1) it reduces the data dimensionality and (2) it provides a new data representation possibly characterised by convenient geometric properties. Euclidean spaces are by far the most widely used embedding spaces, thanks to their well-understood structure and large availability of consolidated inference methods. However, recent research demonstrated that many types of complex data (e.g., those represented as graphs) are actually better described by non-Euclidean geometries. Here, we investigate how embedding graphs on constant-curvature manifolds (hyper-spherical and hyperbolic manifolds) impacts on the ability to detect changes in sequences of attributed graphs. The proposed methodology consists in embedding graphs into a geometric space and perform change detection there by means of conventional methods for numerical streams. The curvature of the space is a parameter that we learn to reproduce the geometry of the original application-dependent graph space. Preliminary experimental results show the potential capability of representing graphs by means of curved manifold, in particular for change and anomaly detection problems.