Change Detection in Graph Streams by Learning Graph Embeddings on Constant-Curvature Manifolds

Area of Science:

• Graph theory
• Machine learning
• Non-Euclidean geometry

Background:

• Graph data presents complex geometry, challenging traditional machine learning.
• Euclidean embeddings are limited for capturing graph structures.
• Non-Euclidean spaces, like constant-curvature Riemannian manifolds (CCMs), offer better graph representation.

Purpose of the Study:

• To develop a novel framework for detecting changes in stationarity within attributed graph streams.
• To leverage the geometric properties of CCMs for improved graph analysis.
• To address the limitations of Euclidean embeddings in graph learning.

Main Methods:

• Utilized adversarial learning to train an autoencoder for graph embeddings on CCMs.
• Developed two novel change detection tests specifically designed for CCMs.
• Applied the framework to synthetic data and real-world applications (epileptic seizure detection, hostility detection).

Main Results:

• The proposed framework successfully detects subtle changes in graph-generating processes.
• Methods based on CCMs consistently outperform those using Euclidean embeddings.
• Demonstrated effectiveness in both synthetic and real-world graph data.

Conclusions:

• Constant-curvature Riemannian manifolds provide a powerful tool for graph embedding and change detection.
• The novel framework offers a significant advancement in analyzing dynamic graph data.
• This approach enhances the accuracy and sensitivity of change detection in graph streams.