PaperlayerView exact revision on arXiv

Source-linked AI summary

A survey of dynamic graph neural networks

Yanping Zheng, Lu Yi, Zhewei Wei

arXiv:2404.18211v1cs.LGcs.SI

TL;DR

Most graph-learning research focuses on static graphs despite real-world changes in graph structure and attributes. This survey reviews dynamic GNN methods and their applications, synthesizes current challenges, and outlines future directions.

  • Problem

    Most work centers on static graphs, although real-world graph structures and attributes evolve and static GNNs are difficult to apply directly.

    Source: §1 · p. 1

  • Method

    The paper reviews dynamic GNN concepts and models, including large-scale applications and pre-training strategies.

    Source: §1 · p. 2

  • Results

    The survey synthesizes prediction tasks, temporal modeling methods, and large-scale dynamic graph handling, and identifies scalability and theoretical challenges alongside future directions.

    Source: §8 · p. 24

  • Takeaways & Limitations

    Future work should broaden applicability to complex graph structures and evolution patterns and pursue a unified dynamic representation framework with breadth and depth.

    Source: §8 · p. 24

    Real-world datasets containing edge deletions are lacking, limiting assessment of model robustness and performance when handling edge deletion.

    Source: §7.1 · p. 23

Abstract

from arXiv · show

Graph neural networks (GNNs) have emerged as a powerful tool for effectively mining and learning from graph-structured data, with applications spanning numerous domains. However, most research focuses on static graphs, neglecting the dynamic nature of real-world networks where topologies and attributes evolve over time. By integrating sequence modeling modules into traditional GNN architectures, dynamic GNNs aim to bridge this gap, capturing the inherent temporal dependencies of dynamic graphs for a more authentic depiction of complex networks. This paper provides a comprehensive review of the fundamental concepts, key techniques, and state-of-the-art dynamic GNN models. We present the mainstream dynamic GNN models in detail and categorize models based on how temporal information is incorporated. We also discuss large-scale dynamic GNNs and pre-training techniques. Although dynamic GNNs have shown superior performance, challenges remain in scalability, handling heterogeneous information, and lack of diverse graph datasets. The paper also discusses possible future directions, such as adaptive and memory-enhanced models, inductive learning, and theoretical analysis.

1 Introduction

Dynamic graphs model evolving structure and attributes more realistically than static graphs, but existing reviews are outdated amid rapid method and application growth. This survey organizes dynamic GNN concepts, models, and emerging directions.

1 Introduction

  • Dynamic graphs reflect evolving real-world structure and attributes, while static GNNs are difficult to apply directly to such changes.Dynamic GNNs combine graph learning with sequence learning to model structural features and temporal dependencies.Source: §1 · pp. 1–2
  • Existing reviews no longer reflect recent methods and applications, motivating this survey of dynamic graph representation and modeling techniques.It also covers large-scale applications, pre-training strategies, and future trends.Source: §1 · p. 2
  • Node classification and link prediction are widely used evaluation tasks, while spatio-temporal graphs with static structure and changing attributes are outside the survey’s scope.Source: §1 · p. 2
  • The survey reviews fundamental concepts and key techniques, and analyzes mainstream dynamic GNN models, including their advantages and disadvantages.Source: §1 · p. 2
  • The authors identify field challenges and potential future research directions and technological trends.Source: §1 · p. 2

2 Notation and Background

The section establishes graph notation, distinguishes snapshot-based and event-based dynamic graphs, and introduces Hawkes processes as models of event sequences.

2.1 Notation

  • Table 1 notation includes G = (V, E), node features X, adjacency matrix A, degree matrix D, normalized adjacency P, and Laplacian L.The activation function is denoted by σ.Source: §2.1 · p. 3, Table 1 · p. 3

2.2 Dynamic Graphs

  • DTDGs represent equal-interval snapshots, which can lose details between intervals; CTDGs record timestamped events, including node or edge additions and deletions.A quickly disappearing edge can be recorded in the CTDG event history but missed by a DTDG snapshot.Source: §2.2 · pp. 3–4, Figure 2 · p. 4
  • A temporal neighbor of v at time t is an adjacent node paired with an event timestamp earlier than t.Source: §2.2 · p. 4

2.3 Hawkes Processes

  • The Hawkes process models event sequences with background intensity and past-event excitation; HTNE uses historical behaviors to model graph generation.The excitation can decay exponentially over time, and α_i represents the impact weight of an event.Source: §2.3 · pp. 4–5

3 Graph Representation Learning

This section covers graph representation learning, which maps nodes to low-dimensional vectors and updates them over time as graph structure and attributes evolve. It describes methods for representing continuous-time dynamic graphs using temporal constraints, causal patterns, influence decay, or asynchronous event propagation.

3 Graph Representation Learning

  • Dynamic graph representations encode time-dependent node states, while models are grouped by whether they learn from discrete snapshots or timestamped continuous interactions.Discrete-time methods analyze successive snapshots; continuous-time methods use timestamps attached to edges.Source: §3 · p. 6, §3.1 · p. 6

3.1 Models for Dynamic graphs

  • Dynamic GNNs use deep-learning graph models to capture complex temporal evolution, with distinct approaches for discrete-time and continuous-time graphs.The survey compares their base models, supported graph types, and handled graph events.Source: §3.1 · p. 7

3.2 Dynamic GNNs for DTDGs

  • For discrete-time dynamic graphs, stacked models encode each snapshot with a GNN and model the resulting sequence, while integrated models combine spatial and temporal operations within a layer.Examples include DySAT, which uses spatial GAT and temporal Transformers [14], and GC-LSTM, which applies graph convolution to LSTM states.Source: §3.2 · pp. 7–8
  • Other discrete-time approaches evolve GNN parameters, aggregate gradients across snapshot windows, or use autoencoders initialized or conditioned by earlier snapshots.EvolveGCN updates GCN weights with RNNs, while WinGNN aggregates gradients over sliding windows and DynGEM [64] initializes each snapshot’s autoencoder from its predecessor.Source: §3.2 · p. 10

3.3 Dynamic GNNs for CTDGs

  • Continuous-time methods are organized as temporal point-process, RNN-based, or temporal random-walk approaches, using timestamped events to preserve event order and asynchronous intervals.DyRep uses a pairwise intensity function and self-attention to prioritize relevant information when modeling multiple graph types.Source: §3.3 · p. 11
  • Continuous-time RNN methods update affected nodes as events occur; JODIE updates user and item embeddings and projects future trajectories, while TGAT encodes time and attends to historical neighbors.TGN [3] combines memory, message, aggregation, update, and embedding modules to maintain event-responsive node representations.Source: §3.3 · pp. 12–13
  • APAN propagates messages asynchronously in a specified number of steps to keep events ordered by timestamp during online training.Timestamp-order disruptions can make RNN-based embedding generation unstable.Source: §3.3 · p. 13
  • Temporal random walks follow sequences of edges with non-decreasing timestamps, constraining movement by both graph adjacency and time.The approach adapts random-walk methods such as DeepWalk and Node2vec to dynamic graphs.Source: §3.3 · p. 13
  • CAW anonymizes nodes using relative-identity frequencies in sampled walks, while CAW-N predicts temporal links by encoding and pooling sampled walks with RNNs.Removing node identities supports inductive learning while preserving pattern structures and correlations.Source: §3.3 · p. 13
  • Zebra uses exponential decay in its T-PPR metric to rank temporal neighbors by influence, then directly aggregates the top-k neighbors into an embedding.Recent neighbors receive higher traversal probability; direct aggregation avoids recursive temporal-neighbor aggregation.Source: §3.3 · pp. 13–14

4 Processing and Learning on Large-scale Dynamic Graphs

Large-scale dynamic graphs add memory, synchronization, and temporal-ordering demands to scalability challenges. The section reviews scalable algorithms and training frameworks for discrete- and continuous-time graphs.

4 Processing and Learning on Large-scale Dynamic Graphs

  • Mini-batch learning on dynamic graphs requires sufficient history, optimized node-memory updates, memory synchronization across partitions, and chronologically ordered temporal batches.Time encoding and sequential data traversal are among the approaches used to meet these demands.Source: §4 · p. 14

4.1 Scalable GNNs for Dynamic Graphs

  • SEIGN improves scalability with parameter-free message preprocessing, multi-scale representations, convolution-kernel updates, and graph mini-batch training.It updates convolution-kernel weights with GRUs for each snapshot rather than evolving the entire GNN, and also evolves node representations.Source: §4.1 · p. 15
  • EARLY lowers computational costs on continuously changing graphs by updating only the top-k nodes selected using local and global scores integrated as information gain.Local scores reflect convolution effects and random-walk changes; global scores reflect node influence.Source: §4.1 · p. 15
  • Decoupled propagation and training support incremental updates, while SDG uses a dynamic personalized-PageRank propagation matrix to avoid redundant graph propagation.The decoupled approach locates affected nodes after graph changes; SDG updates random-walk distributions with push-out and add-back operations.Source: §4.1 · p. 15

4.2 Scalable Training Frameworks for Dynamic GNNs

  • For discrete-time graphs, PiPAD pipelines multiple snapshots, while Chakaravarthy et al. use gradient checkpointing, graph-difference transfers, and snapshot partitioning.The latter method is reported to improve on traditional methods.Source: §4.2 · pp. 15–16
  • TGL supports several dynamic GNN types with temporal-edge access, parallel sampling, random chunk scheduling, and a mailbox for node-memory messages.The mailbox aggregates recent messages before sequentially updating node memory, avoiding direct mail generation from the most recent memory state.Source: §4.2 · p. 16
  • DistTGL [75] improves convergence speed and training throughput over TGL, with near-linear speedups on distributed GPU clusters.It adds static node memory, time-period and memory parallelism, and uses prefetching and pipelining to overlap batch formation with GPU training.Source: §4.2 · p. 16
  • Other frameworks use streaming edge partitioning and pipelining, hierarchical parallelism, or STEP’s significance-based edge sampling and pruning during training and inference.SPEED [76] also reduces memory use on a single GPU, while STEP [78] focuses particularly on newly added edges.Source: §4.2 · pp. 16–17

5 Datasets and Benchmarks Overview

The section surveys public dynamic-graph datasets, prediction settings, and benchmarks. It describes variation in dataset domains, scales, structures, and features, alongside task definitions and efforts to standardize model evaluation.

5.1 Datasets

  • Public datasets span varied domains and scales, from thousands of nodes and edges in UCI and Contact to millions or billions in Taobao and MAG, with both bipartite and general graphs.Datasets are categorized as continuous-time or discrete-time, though processing can transform one type into the other.Source: §5.1 · pp. 17–18
  • Many dynamic-graph datasets lack node or edge features, and datasets with node features are especially rare.The paper notes that collecting real-world features can be costly; learning from structural change alone may improve generalization.Source: §5.1 · pp. 18–19

5.2 Prediction Problems

  • Dynamic-graph prediction includes node-, edge-, and graph-level tasks, with link prediction, anomaly detection, and community discovery illustrating temporally changing targets and structures.Evaluation settings also distinguish generalization to unseen evolving graphs (inductive) from prediction on a trained graph (transductive), and future prediction (extrapolation) from missing-value imputation (interpolation).Source: §5.2 · pp. 19–20

5.3 Benchmarks

  • Unified benchmark frameworks standardize datasets, preprocessing, and training strategies so models can be compared under shared evaluation conditions.Table 5 provides links to these benchmarks.Source: §5.3 · p. 21, Table 5 · p. 21

6 Advanced Techniques in Graph Processing

The section reviews dynamic transfer learning and pretraining for dynamic graphs. It describes early-stage graph transfer research, current pretraining approaches, and unresolved requirements for scalable, temporally and structurally informed pretraining.

6.1 Dynamic Transfer Learning

  • Graph dynamic transfer learning must adapt as both source and target domains evolve, accounting for historical target states, shifting distributions, and temporal interdependencies.Graph-specific research remains early-stage and has largely borrowed LSTM or attention approaches from other fields.Source: §6.1 · p. 21

6.2 Pretraining Techniques for Dynamic GNNs

  • Dynamic-graph pretraining includes PT-DGNN’s time-based masking of recent edges or attributes and CPDG’s temporal-structural contrastive learning with memory states.These approaches seek to capture temporal evolution or preserve longer-term information for downstream tasks.Source: §6.2 · p. 22
  • Large-scale dynamic-graph pretraining remains challenging: models must handle different temporal granularities and downstream tasks while preserving structural neighbors and long- and short-term patterns.Efficient sampling and training are also required, and learned temporal patterns should be incorporated promptly into downstream tasks.Source: §6.2 · p. 22

7 Future Trends and Challenges

The paper identifies dataset complexity and diversity gaps, early-stage interpretability research, and unresolved challenges for applying LLMs to dynamic graph learning.

7.1 More Complex Dynamic Graphs

  • EdgeBank results suggest current datasets may not distinguish models well, motivating richer structural information and temporal evolution patterns for evaluation.The paper also notes that dynamic graph datasets remain less diverse than static graph datasets.Source: §7.1 · pp. 22–23
  • Real-world datasets with edge-deletion events are lacking, limiting assessment of model robustness and performance on such dynamics.The paper names user unfollowing as an example and proposes collecting real edge-deletion data.Source: §7.1 · p. 23
  • Dynamic signed networks and dynamic heterophilic graphs receive little attention, motivating datasets with varied topologies and more complex structures.The paper calls for larger-scale, richer-content datasets to support real-world complex-network learning.Source: §7.1 · p. 23

7.2 Interpretability of Dynamic GNNs

  • Dynamic GNN interpretability remains early-stage, with DGExplainer [110] and DynBrainGNN representing attempts to explain predictions or build in interpretability.DGExplainer redistributes output activation scores to identify important nodes for link prediction and node regression.Source: §7.2 · p. 23

7.3 LLMs for dynamic graph learning

  • LLMs show promise on dynamic graph tasks, but large-scale performance, computational efficiency, and explicit graph-structure modeling remain challenges.The paper reports that one example can improve LLM accuracy on multiple tasks, while performance declines as graph size grows [116].Source: §7.3 · pp. 23–24

8 Conclusion

The paper surveys dynamic GNN research across tasks, temporal modeling, and large-scale graph handling, then identifies challenges and future directions. It calls for broader applicability to complex graph structures and evolution patterns.

8 Conclusion

  • The survey covers dynamic GNN prediction tasks, temporal modeling methods, and approaches for handling large-scale dynamic graphs.It summarizes current research advances and points to expanding model scope and studying expressive capability.Source: §8 · p. 24
  • Scalability, theoretical guidance, and dataset construction remain challenges for dynamic GNNs.Source: §8 · p. 24
  • Future work should address more diverse graph structures and evolution patterns and pursue a unified representation-learning framework with breadth and depth.The paper notes that practical applications increasingly involve dynamic graph analysis.Source: §8 · p. 24
Loading 2404.18211v1…