Anomaly and Change Detection in Graph Streams through Constant-Curvature Manifold Embeddings

Daniele Zambon, Lorenzo Livi, Cesare Alippi

Abstract

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.

Introduction

Detecting changes or anomalies in a stream of graphs—such as social networks, chemical structures, or communication logs—is a critical but computationally demanding task. The traditional approach relies on the Graph Edit Distance (GED), which measures the minimum number of operations required to transform one graph into another. While accurate, GED is NP-hard and does not scale to high-velocity data streams.

To address this, researchers typically embed graphs into a lower-dimensional numeric space where standard statistical tests can be applied. However, the choice of embedding space is often restricted to Euclidean geometry. This "flat" representation frequently fails to capture the inherent hierarchical or clustered structures of real-world graphs, introducing significant distortion that can mask subtle anomalies.

Methodology

This paper proposes a framework to embed graphs into constant-curvature manifolds, where the curvature ($\kappa$) is treated as a learnable parameter. Three geometric types are considered:

  1. Euclidean ($\kappa = 0$): Standard flat space.
  2. Spherical ($\kappa > 0$): Positively curved space.
  3. Hyperbolic ($\kappa < 0$): Negatively curved space, ideal for hierarchical data.

Learning Optimal Curvature

Instead of assuming a geometry, the authors optimize $\kappa$ to minimize the distortion between the original graph distances and the distances in the manifold. As shown in the figure below, Euclidean space often represents a local maximum for distortion, suggesting that even slight curvature can significantly improve representation fidelity.

Log-distortion as a function of curvature. The peak at zero curvature highlights the limitations of Euclidean embeddings for graph data.

Detection Framework

Once the graphs are mapped to the manifold, the system employs a CUSUM-inspired (Cumulative Sum) test. This involves calculating the Fréchet mean—a generalization of the average for curved surfaces—of nominal data and flagging instances where new data points drift beyond a statistical threshold.

Experimental Results

The methodology was evaluated using the Delaunay graph dataset across varying levels of "difficulty" (the subtlety of the distribution shift). The performance was measured using the Detected Change Rate (DCR) and the Average Run Length ($ARL_1$), which indicates detection speed.

Experimental results comparing different embedding manifolds. Curved manifolds (Spherical and Hyperbolic) consistently outperform Euclidean embeddings in both accuracy (DCR) and detection speed ($ARL_1$).

Key findings include:

  • Euclidean Underperformance: In many scenarios, Euclidean embeddings yielded the lowest DCR. For instance, at Difficulty 2, the Euclidean method achieved a DCR of only 0.04, whereas the Hyperbolic method reached 0.96.
  • Hyperbolic Superiority: Hyperbolic manifolds frequently outperformed spherical ones, confirming that many graph structures possess an underlying negative curvature.
  • Efficiency: The curved manifold embeddings performed nearly as well as the "Graph Domain" baseline (raw GED) while offering the computational efficiency required for real-time stream processing.

Conclusion

The "shape" of the embedding space is a critical factor in graph stream analysis. By moving beyond flat Euclidean representations and learning the intrinsic curvature of the data, researchers can achieve faster and more reliable anomaly detection. Future work will focus on expanding these tests to more diverse real-world datasets and exploring multivariate detection features.

Summary updated

Abstract

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.
BibTeX
@inproceedings{zambon2018anomaly,
  author = {Daniele Zambon and Lorenzo Livi and Cesare Alippi},
  title = {{Anomaly and Change Detection in Graph Streams through Constant-Curvature Manifold Embeddings}},
  booktitle = {IJCNN},
  year = {2018},
  url = {https://openreview.net/forum?id=PucPPLWATw4},
}
Figure