PaperlayerView exact revision on arXiv

Source-linked AI summary

A Survey on Embedding Dynamic Graphs

Claudio D. T. Barros, Matheus R. F. Mendonça, Alex B. Vieira, Artur Ziviani

arXiv:2101.01229v2cs.LGcs.AI

TL;DR

This survey addresses dynamic graph representation learning across evolving topology, features, and network processes. It formalizes the problem, organizes models and methods into taxonomies, reviews applications, and identifies latency and evaluation theory as open directions.

  • Problem

    Dynamic networks evolve in topology, features, and diffusion, creating challenges in modeling time, capturing temporal features, and choosing temporal granularity for network representations.

  • Method

    The survey formalizes dynamic graph embedding, classifies dynamic graph models and outputs, reviews behaviors and applications, and organizes techniques from factorization and deep learning to random walks and temporal point processes.

  • Results

    The survey synthesizes dynamic graph embedding advances, including temporal random walks that avoid snapshot discretization and are suited to diffusion problems.

  • Takeaways & Limitations

    Dynamic graph embeddings can aggregate temporal information or track representation trajectories, supporting tasks such as graph classification over time and diffusion prediction.

  • Takeaways & Limitations

    Existing methods do not address latency in node and edge creation or removal, while stability metrics require broader real-world testing and mathematical analysis.

Abstract

from arXiv · show

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.

1 Introduction

Dynamic graph embedding addresses network evolution that static or aggregated representations cannot preserve, while organizing the field around temporal problem settings, dynamic behaviors, techniques, applications, and future directions.

  • Motivation: Static or aggregated graph representations lose temporal correlations in networks whose nodes, edges, labels, properties, or diffusion processes evolve over time.These dynamics motivate embedding methods that learn representations for changing networks.
  • Challenges: Dynamic graph embedding must determine how to model time, which dynamic behaviors to capture, and what temporal granularity to represent.Choices include discrete versus continuous time and dataset-level versus coarser temporal representations.
  • Problem settings: The survey formalizes dynamic graph embedding and introduces a taxonomy covering embedding inputs and outputs, including temporal heterogeneity and temporal granularities.The taxonomy broadens static graph embedding settings to handle timestamps, labels, and temporal representations.
  • Dynamic behaviors: It classifies dynamic behaviors as topological evolution, feature evolution, and processes on networks, including diffusion and evolving global node roles.The survey also discusses temporal point processes on networks.
  • Techniques: Its technique taxonomy analyzes algorithmic approaches, compares methods, and extends coverage to graph kernels, temporal point processes, and agnostic methods.The survey presents detailed comparisons of methods and their similarities, differences, and particularities.
  • Applications and future directions: Applications are categorized by topological structure across node-related, edge-related, and joint node-and-edge tasks, alongside proposed future research directions.Future directions include problem settings, solution techniques, applications, and representation learning for generalized graphs such as hypergraphs.

2 Fundamentals Behind the Embedding of Dynamic Graphs

This section establishes graph-embedding fundamentals, dynamic-graph representations, and the input categories and modeling choices that extend static embedding to evolving networks.

  • Static Graph Embedding: Graph embedding maps nodes, edges, subgraphs, or whole graphs into a low-dimensional vector space while preserving graph information.The embedding dimension d is expected to be much smaller than the number of nodes.
  • Static Graph Embedding: Static graph methods represent similarity with matrices, apply matrix factorization, use deep neural architectures, or generate random-walk contexts for representation learning.Random-walk methods use natural-language-processing techniques and neural language models such as SkipGram to preserve higher-order proximity.
  • Dynamic Graphs: A dynamic graph is modeled as G = (V, E, T), with time-varying node sets, edge sets, and graph snapshots whose adjacency, weight, and similarity matrices may also vary over time.Alternative formulations explicitly use node- and edge-presence functions to indicate availability at each time.
  • Dynamic Graph Embedding Input: Dynamic graph inputs can be homogeneous or heterogeneous and may include temporal heterogeneity, node and edge features, or non-relational data.The taxonomy extends static graph-embedding input categories to account for topological and temporal heterogeneity.

2.6 Problem Formulation and Output for Dynamic Graph Embedding

Dynamic graph embedding maps time-varying network entities or structures into low-dimensional representations while distinguishing what is embedded and how temporal granularity is represented. The survey separates topological outputs from temporal mappings and categorizes dynamic behaviors by topology, features, and network processes.

  • Problem formulation: Dynamic graph embedding maps a dynamic graph into d-dimensional vectors that capture topological information and temporal dependencies.Representations may reconstruct the graph, predict behavior beyond its lifespan, or support task-driven applications.
  • Temporal embedding: Temporal representations may follow each timestamp, move through embedding space as trajectories, or evolve through mappings between consecutive embedding spaces.The network and embedding spaces need not remain identical over time.
  • Output taxonomy: The output taxonomy separates topological embedding from temporal embedding, distinguishing the embedded graph entity from the relationship between input and output time domains.The taxonomy includes node, edge, substructure, and graph snapshot embeddings, alongside temporal categories.
  • Temporal embedding: Embedding over time preserves a representation for each timestamp, whereas time-grouping and whole-time embeddings aggregate timestamps into coarser or single temporal representations.Time-grouping embeddings use sets of timestamps or intervals, while whole-time embeddings use one unitary temporal set.
  • Temporal embedding: Temporal aggregation can occur before embedding or after representation learning through vector-space operations such as weighted averages or nonlinear functions.These operations can produce weekly or monthly representations from daily network data.
  • Topological embedding: Topological outputs include dynamic node, edge, substructure, and snapshot embeddings, each representing the corresponding entity at time t in a low-dimensional space.Node embeddings support time-dependent classification, clustering evolution, and link prediction; substructure embeddings cover induced subgraphs and graphlets.
  • Temporal embedding: The survey’s output taxonomy is illustrated through examples spanning per-timestamp trajectories, grouped timestamps, and whole-time aggregation.Figure 5 groups t0–t3 into T1 and T2, while also showing a single representation across all timestamps.
  • Dynamic behaviors: Dynamic behaviors captured by embeddings fall into topological evolution, feature evolution, and processes on networks.These categories cover changing nodes and edges, changing node or edge features, and time-dependent processes such as diffusion and role evolution.

3 Techniques for the Embedding of Dynamic Graphs

The survey organizes dynamic graph embedding techniques by algorithmic approach, extending static graph classifications to account for temporal dependence. It covers factorization, deep learning, random walks, temporal reconstruction, graph kernels, temporal point processes, and agnostic models.

  • Taxonomy: The proposed taxonomy extends static graph embedding classifications to dynamic graphs and organizes techniques by algorithmic approach.The taxonomy is summarized in Figure 7.
  • Taxonomy: The taxonomy includes matrix and tensor factorization, deep learning, random walks, temporal reconstruction, and graph kernel methods.Temporal reconstruction leverages temporal smoothness alongside edge reconstruction.
  • Novel paradigms: The survey introduces temporal point-process methods that model similarity-matrix changes as stochastic processes.These methods support modeling stochastic events such as the creation or removal of nodes and edges.
  • Novel paradigms: Agnostic models learn embeddings over time independently of the approach used for each graph snapshot.This separates temporal learning from the particular snapshot-level embedding method.
  • Motivation: Earlier methods independently embedded each snapshot with static graph techniques, but network evolution can move vectors and evolve the embedding manifold itself.Incorporating temporal correlations into feature vectors is reported to enhance prediction, classification, and other temporal network analyses.

3.1 Factorization-based methods

Factorization-based methods represent dynamic graphs through low-rank decompositions of time-dependent similarity measures. Their main paradigms differ in how they impose temporal dependence: smoothing, incremental perturbation updates, or explicit constant and time-varying factors.

  • Overview: Factorization-based methods generate time-indexed node embeddings by applying low-rank decompositions to temporal similarity measures represented as matrices or tensors.Matrix sequences model temporal evolution between adjacent timestamps, whereas tensors couple topology and time in one factorization.
  • Temporal dependence: Three paradigms connect representations across timestamps: temporal smoothing, perturbation-based updates, and temporal matrix factorization.These respectively stabilize trajectories, assume slight topological changes, or decompose similarity into constant and time-dependent terms.
  • Temporal smoothing: Temporal smoothing jointly reconstructs each snapshot’s similarity matrix and constrains consecutive embeddings to remain similar.A parameter τ regulates the contribution of the smoothness term, while extensions can weight recent timestamps or account for unequal time intervals.
  • Incremental updates: Incremental update methods iteratively revise embeddings under the assumption that each later similarity matrix is a small perturbation of the initial matrix.They can reduce computation for sparse evolution but accumulate errors and may be ineffective when networks evolve intensely; restart times can mitigate accumulation.
  • Temporal matrix factorization: Temporal matrix factorization separates persistent node properties from topology changes using a constant matrix U and a time-dependent matrix V(t).The rows of U encode persistent properties, while rows of V(t) represent changes over time; describing V(t) remains the main challenge.

3.2 Approaches based on Deep Learning

Deep-learning methods extract graph structure and temporal dependencies with architectures including recurrent and convolutional networks, autoencoders, and generative models. The survey organizes them into encoder-decoder and generative architectures according to their network design.

  • Architectures: Dynamic graph neural architectures combine topology extraction with temporal modeling using RNNs, LSTMs, GRUs, CNNs, and attention mechanisms.RNN-based models process graph snapshots or representations, while CNNs can capture temporal dependencies and attention can identify relevant time points.
  • Generative models: Generative models such as VAEs and GANs learn time-evolving data distributions through latent representations and generative or recognition/discriminator networks.Dynamic graph variants apply these models to distributions that change over time.
  • Taxonomy: The survey’s taxonomy distinguishes encoder-decoder methods from encoder-sampling-decoder methods that represent data as probability distributions.The former supports reconstruction or application-driven prediction, while the latter contains generative models.
  • Encoder-decoder methods: An encoder-decoder maps data to low-dimensional representations, then reconstructs the data or solves tasks such as link prediction and node or graph classification.Autoencoders aim for lossless reconstruction, whereas application-driven encodings may be lossy.
  • Dynamic autoencoders: Dynamic autoencoders use historical network records to reconstruct a graph at a future timestamp, thereby predicting a future network state.Examples include autoencoder, recurrent, and combined strategies such as dyngraph2vecAE, dyngraph2vecRNN, and dyngraph2vecAERNN.

3.3 Random Walk Approaches

Random-walk methods create node contexts from sequences and learn embeddings that preserve proximity or higher-order dependencies. Dynamic variants differ in whether time is handled after snapshot walks, through incremental updates, or directly within temporally ordered walks.

  • Core approach: Random-walk approaches treat fixed-length walks as sentences, use them to capture higher-order dependencies, and commonly learn embeddings with Skip-Gram.The resulting vectors preserve node proximity in the embedded space without directly using adjacency matrices.
  • Temporal random walks: Temporal random walks incorporate time-dependent contexts directly by allowing walks across consecutive timestamps under time-ordering restrictions.Continuous-time methods such as CTDNE select subsequent nodes with unbiased or temporally weighted rules, avoiding snapshot discretization.
  • Random walks on snapshots: Snapshot-based methods generate embeddings independently at each time and later combine or align them using smoothing, concatenation, or orthogonal transformations.These methods do not model temporal connections during random-walk generation itself.
  • Efficiency trade-off: Generating random walks for every timestamp is computationally expensive, while update-based methods trade some accuracy for substantial computational efficiency.The cited comparison states that a full walk in every snapshot is more precise, but the efficiency gain compensates for the small accuracy loss.
  • Evolving random walks: Evolving random walks update representations incrementally by resampling walks for nodes affected by topological changes rather than recomputing all walks.Dynnode2vec and EvoNRL use dynamic Skip-Gram models with initialization or stored walks carried across timestamps.

3.4 Edge Reconstruction based Optimization with Temporal Smoothing

Edge-reconstruction methods optimize objectives that preserve temporal smoothness while modeling network connections or temporal relationships. DynamicTriad additionally represents structural information and evolution patterns through open-to-closed triad transitions.

  • Objective functions: Edge-reconstruction approaches optimize objectives based on edge reconstruction while preserving temporal smoothness.The survey separates them by algorithmic properties even though network embedding, matrix factorization, and Skip-Gram objectives are theoretically connected.
  • Temporal interpretation: Temporal smoothness can be interpreted as reconstructing temporal edges between a node at one time and the same node at a subsequent timestamp.This interpretation supports the category’s inclusion among embedding methods.
  • DynamicTriad: DynamicTriad preserves structural information and network evolution patterns by modeling whether open triads develop into closed triads.It combines triad-transition probabilities with distance-based and margin-based ranking losses, while also enforcing smoothness across consecutive timestamps.

3.5 Methods based on Graph Kernel

Graph-kernel-based methods model dynamic graphs through elementary substructures and evolving neighborhood similarities. They extend static structural representations by tracking transitions or updates caused by new edges.

  • Elementary substructures such as graphlet transitions, graphlet frequencies, and adjacency-matrix summaries provide topological building blocks for dynamic representations.These attributes are reconstructed using shallow autoencoder approaches.
  • Dynamic graph embedding tracks transitions between different elementary structures rather than only representing a static network structure.
  • SecondOrder uses Min-Hash fingerprinting to learn neighborhood similarity and update embeddings after new edges alter node relationships.The approach modifies a node’s embedding when a neighbor becomes more similar after edge addition.
  • SecondOrder can be viewed as a graph-kernel-based approach to dynamic graph embedding.

3.6 Methods based on Temporal Point Process

Temporal-point-process methods treat node interactions or propagation events as stochastic processes whose probabilities depend on topology, features, and network history. They update node and edge representations as events occur and use conditional intensities or related counting mechanisms to model temporal behavior.

  • Temporal-point-process methods model interactions as stochastic processes conditioned on network topology, node features, and network history.Their event-driven procedure computes current node representations and edge embeddings before updating affected representations.
  • Other methods apply temporal point processes to events including interactions, knowledge-graph facts, edge evolution, linking rates, and neighborhood formation sequences.Examples include DyRep, DeepCoEvolve, KnowEvolve, M2DNE, and HTNE; Knyazev et al. extend DyRep by replacing its original encoder.
  • Event processing updates the embedding of the influenced node using its connected edges and then updates the embedding of the event’s edge.
  • MHDNE represents edge formation through historical-edge and network-evolution sequences, with new-edge intensity modeled by a Hawkes process.Its intensity uses node embeddings, exponential time decay, and neighborhood distance, while network evolution incorporates open triangles and triadic closure.
  • GBTPP estimates the probability that an event propagates to a neighboring node at the next timestamp from propagation history and the currently influenced node.Propagation depends on whether neighboring nodes are susceptible to the current node’s influence and is expressed through conditional intensity.

3.7 Agnostic Models

Agnostic models separate dynamic evolution from the static embedding algorithm used at each timestamp. They either retrofit prior embeddings using local temporal smoothness or learn transformations that map representations between successive snapshots.

  • Agnostic approaches connect representations across time using state-of-the-art static embeddings, then capture dynamics through retrofitting or embedding-space transformations.
  • Retrofitting: Retrofitting initializes embeddings with a static method and locally updates later vectors using neighborhood information from each new snapshot.Each updated vector balances similarity to its previous value and to adjacent nodes at the current timestamp until convergence.
  • Retrofitting: After the first timestamp, retrofitting does not learn embeddings directly from data but relies on a temporal-smoothing criterion.
  • Transformation models: Transformation models treat network evolution as mappings between node-embedding vectors at successive timestamps and can map a known snapshot to an unobserved next snapshot.
  • Transformation models: Homogeneous transformation shares one mapping across successive timestamps, whereas heterogeneous transformation learns a distinct procedure for each timestamp pair.The described mappings use linear transformations or projection matrices.

3.8 Other Dynamic Graph Embedding Approaches

Some dynamic graph embedding methods fall outside the main algorithmic categories because they use distinctive methodologies or combine techniques. Another strategy aggregates all temporal interactions and vertices into a static graph before applying static embedding methods.

  • Some approaches use specific methodologies or combine multiple techniques without one algorithmic paradigm serving as the main category.
  • Temporal information can be aggregated into a static graph containing all interactions and vertices observed from the beginning through the final analysis timestamp.
  • These aggregation-based methods then apply static graph embedding to the network containing the stored temporal information.

4 Dynamic Graph Embedding Applications

Dynamic graph embeddings support applications focused on nodes, edges, or whole graphs, extending familiar network-analysis tasks to evolving settings and adding temporal prediction problems.

  • Application taxonomy: Dynamic graph embedding applications are organized into node-related, edge-related, and graph-related tasks.Node tasks include classification, recommendation, and trajectory analysis; edge tasks include link and event-time prediction; graph tasks include classification, visualization, and diffusion prediction.
  • Node-related applications: Node classification assigns labels at a timestamp or predicts future labels using dynamic node behavior and labels.Classifiers are trained on labeled node embeddings using linear layers, SVMs, logistic regression, or boosting techniques.
  • Node-related applications: Node embeddings also support recommendations, attribute prediction, clustering, and trajectory tracking over time.Embeddings can provide inputs to time-series models for attribute prediction, while trajectories capture transitions and ideological shifts rather than only stable groups.
  • Edge-related applications: Dynamic link prediction covers both forecasting new edges at a future snapshot and completing previously observed but missing links.It is commonly formulated as classifying edge existence or non-existence, and can be generalized to weighted links or predictions at t_NS + α.
  • Edge-related applications: Event-time prediction estimates when an interaction will occur from a node pair and network history, often using temporal point processes.DyRep and DeepCoevolve are cited as examples of methods predicting the next event time.
  • Edge-related applications: Edge classification predicts time-varying edge labels by combining or operating on node embeddings to form edge embeddings.Examples include trust ratings and sentiment associated with interactions.
  • Node- and edge-related applications: Anomaly detection and diffusion prediction can target either nodes or edges, identifying unusual behavior or likely diffusion sources and links.Diffusion prediction may identify affected nodes or edges most likely to transmit information.
  • Graph-related applications: Whole-graph embeddings enable graph classification at observed timestamps or in the future, using aggregated node embeddings or graph kernels.The resulting representations can be passed to classifiers similar to those used for node classification.

5 Conclusion and Future Directions

The survey formalizes dynamic graph embedding, organizes problem settings and techniques, and reviews applications while identifying open directions for broader models, temporal scales, theory, and tooling. Future work includes handling hypergraphs, latency, spatial-temporal patterns, property-preserving evolution, and unified evaluation frameworks.

  • Contributions: The survey defines dynamic graph embedding problem settings and outputs, including temporal aggregation and representation trajectories.Its taxonomy incorporates dynamic graph models and fundamental time aspects in embeddings.
  • Contributions: It classifies dynamic graph embedding paradigms by algorithmic approach and extends prior taxonomies with graph kernels, temporal point processes, and agnostic methods.The survey also reviews embedding techniques according to their topological-temporal properties and assumptions.
  • Future directions: Unified libraries, algorithms, applications, and benchmark datasets could support reproducible evaluation and incremental integration of new techniques.DynamicGEM is cited as an open-source template covering reconstruction, link prediction, node classification, and temporal visualization.
  • Future directions: Future work should develop stability metrics validated on real networks and deepen mathematical analysis of representations and graph evolution.The survey notes that a proposed adjacency-matrix and snapshot-based metric requires more detailed exploration across methods and problems.
  • Future directions: A future direction is temporal multiscale embedding that captures network phenomena occurring at daily, weekly, monthly, and yearly scales.Existing work has considered separate timescales for dynamics on the network and dynamics of the network.
  • Future directions: Dynamic hypergraph embedding remains underdeveloped because existing dynamic graph models generally represent only pairwise node connections.The survey identifies methods for dynamic hypergraphs as a promising research area.
  • Future directions: Current methods do not model latency, while spatial-temporal edges create correlations between non-consecutive timestamps that complicate embedding.Latency represents finite creation or removal intervals, and spatial-temporal edges connect nodes across different timestamps.
  • Future directions: Further research may generate network evolutions in low-dimensional spaces while preserving selected properties such as pathways, degree distributions, and scale invariance.The survey suggests exploring variational autoencoders and GANs for generating networks similar to training data.
Loading 2101.01229v2…