Anomaly and Change Detection in Graph Streams through Constant-Curvature
  Manifold Embeddings
  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.
