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

Daniele Zambon, Lorenzo Livi, Cesare Alippi

TL;DR

This paper demonstrates that the "shape" of your embedding space matters: when monitoring streams of complex graphs for anomalies, embedding them into curved manifolds (spherical or hyperbolic) often preserves structural information much better than standard Euclidean space. By learning the optimal curvature of the manifold, the authors achieve faster and more accurate change detection in graph sequences.

What Problem Does This Paper Address?

Detecting changes or anomalies in a stream of graphs (like social networks, chemical structures, or communication logs) is notoriously difficult. The "gold standard" involves calculating the Graph Edit Distance (GED)—a measure of how many changes are needed to turn one graph into another. However, GED is computationally expensive and doesn't scale well to high-speed data streams.

To solve this, researchers often "embed" graphs into a simpler numeric space (like Euclidean $d$-dimensional space) where they can use standard statistical tests. The problem? Euclidean geometry is "flat," while many real-world graphs have inherent "curved" structures (e.g., hierarchical or cluster-heavy). Forcing these graphs into a flat space introduces distortion, which masks subtle anomalies and leads to false alarms or missed detections.

Methods

The authors propose a framework to embed graphs into constant-curvature manifolds. They consider three types of geometry:

  1. Euclidean ($\kappa = 0$): The standard "flat" space.
  2. Spherical ($\kappa > 0$): A "positively curved" space, like the surface of a globe.
  3. Hyperbolic ($\kappa < 0$): A "negatively curved" space, often described as having a "saddle" shape, which is mathematically ideal for representing hierarchical data.

The Workflow: * Learning Curvature: Instead of picking a space at random, they treat the curvature ($\kappa$) as a learnable parameter. They find the $\kappa$ that minimizes the "distortion" between the original graph distances and the distances in the embedded manifold. * Dissimilarity-Based Embedding: They map graphs to points on the manifold such that the distance between points closely approximates the Graph Edit Distance between the original graphs. * Out-of-Sample Mapping: To handle new graphs in a stream without re-calculating everything, they use a "prototype-based" approach. They select a few landmark graphs (prototypes) and position new graphs relative to these landmarks on the manifold. * Detection Test: Once the graphs are points on a manifold, they use a CUSUM-inspired (Cumulative Sum) test. This involves calculating the Fréchet mean (the generalization of an average for curved surfaces) of nominal data and flagging when new data points drift too far from that mean.

Datasets

The study uses the Delaunay graph dataset.

  • Structure: Nodes represent points in a 2D plane, and edges are determined by Delaunay triangulation.
  • Complexity: The dataset is organized into classes of increasing difficulty. "Difficulty" here refers to how hard it is to distinguish a "changed" distribution of graphs from the "nominal" (reference) distribution.
  • Purpose: This dataset provides a controlled environment to test how well different geometries capture subtle structural shifts.

Key Insights and Ideas

  • Euclidean is often the worst choice: Figure 1 in the paper is a "smoking gun"—it shows that the distortion is often at a local maximum when curvature is zero (Euclidean). By moving even slightly into spherical or hyperbolic territory, the representation becomes significantly more faithful to the original data.
  • Hyperbolic Geometry for Networks: The authors confirm a growing trend in network science: complex networks often have an underlying hyperbolic nature. Their results show that hyperbolic embeddings frequently outperform spherical ones for graph data.
  • Curvature as a Diagnostic: The ability to "learn" the curvature provides a hint about the data's nature. If the system learns a negative $\kappa$, it suggests the graph stream has a hierarchical or tree-like structure.

Key Results

The authors compared their manifold embeddings against a "Graph Domain" baseline (using raw GED) and a standard "Dissimilarity Representation."

  • Accuracy (DCR): The Detected Change Rate (DCR) for Hyperbolic and Spherical manifolds was consistently higher than for Euclidean embeddings. In one test case (Difficulty 2), the Euclidean method had a DCR of only 0.04, while the Hyperbolic method reached 0.96.
  • Speed of Detection ($ARL_1$): This measures the "Average Run Length" until a change is detected. Lower is better. In many cases, the Hyperbolic manifold detected changes significantly faster (fewer time steps) than the Euclidean one.
  • Competitive with Ground Truth: Remarkably, the curved manifold embeddings performed nearly as well as the "Graph Domain" method, which uses the full, computationally heavy GED calculations directly. This suggests that the embedding captures almost all the relevant "signal" while being much faster to process in a live stream.

Limitations and Future Work

  • Dataset Diversity: The results are based on Delaunay graphs. While these are a good benchmark, the authors acknowledge that more diverse real-world datasets (social networks, bio-informatics) are needed to confirm if hyperbolic geometry is universally superior for all graph streams.
  • Scalar vs. Multivariate: The current detection test relies on a single scalar score (distance from the mean). The authors suggest that a multivariate approach—monitoring multiple geometric features simultaneously—would likely be even more effective, though more complex to implement.
  • Optimization: Finding the optimal curvature and embedding is currently a multi-step optimization problem. Future work could involve more streamlined, analytical solutions to make the setup phase even faster.

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},
}

Loading related content...

Figure