A Survey on Embedding Dynamic Graphs

Embedding static graphs in low-dimensional vector spaces plays a key role in network analytics and inference, supporting applications like node classification, link prediction, and graph visualization. However, many real-world networks present dynamic behavior, including topological evolution, featu...

Full description

Saved in:
Bibliographic Details
Published in:ACM computing surveys 2023-01, Vol.55 (1), p.1-37
Main Authors: Barros, Claudio D. T., Mendonça, Matheus R. F., Vieira, Alex B., Ziviani, Artur
Format: Article
Language:English
Subjects:
Anomalies
Classification
Computer science
Diffusion
Embedding
Evolution
Graphs
Machine learning
Network analysis
Random walk
Taxonomy
Tensors
Topology
Vector spaces
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Embedding static graphs in low-dimensional vector spaces plays a key role in network analytics and inference, supporting applications like node classification, link prediction, and graph visualization. However, many real-world networks present dynamic behavior, including topological evolution, feature evolution, and diffusion. Therefore, several methods for embedding dynamic graphs have been proposed to learn network representations over time, facing novel challenges, such as time-domain modeling, temporal features to be captured, and the temporal granularity to be embedded. In this survey, we overview dynamic graph embedding, discussing its fundamentals and the recent advances developed so far. We introduce the formal definition of dynamic graph embedding, focusing on the problem setting and introducing a novel taxonomy for dynamic graph embedding input and output. We further explore different dynamic behaviors that may be encompassed by embeddings, classifying by topological evolution, feature evolution, and processes on networks. Afterward, we describe existing techniques and propose a taxonomy for dynamic graph embedding techniques based on algorithmic approaches, from matrix and tensor factorization to deep learning, random walks, and temporal point processes. We also elucidate main applications, including dynamic link prediction, anomaly detection, and diffusion prediction, and we further state some promising research directions in the area.
ISSN:0360-0300
1557-7341
DOI:10.1145/3483595