PaperlayerView exact revision on arXiv

Source-linked AI summary

Foundations and modelling of dynamic networks using Dynamic Graph Neural Networks: A survey

Joakim Skarding, Bogdan Gabrys, Katarzyna Musial

arXiv:2005.07496v2cs.SIcs.LGstat.ML

TL;DR

Dynamic-network research is difficult to navigate because it spans disciplines with inconsistent terminology, while graph neural networks have received limited attention for dynamic networks. The paper establishes a detailed terminology and foundation, then surveys dynamic graph neural network models and their prediction uses. It also identifies current boundaries: prediction remains concentrated on unattributed, time-conditioned discrete link appearance, while continuous-time encoders and broader prediction tasks remain relatively open.

  • Problem

    Dynamic-network research uses inconsistent terminology across disciplines, and graph neural networks for dynamic networks have received limited attention.

  • Method

    The paper establishes a comprehensive dynamic-network terminology and taxonomy, then surveys dynamic graph neural network models and their prediction applications.

  • Results

    The survey provides foundations and context for dynamic-network modelling and a comprehensive overview of dynamic graph neural networks and dynamic link prediction.

  • Takeaways & Limitations

    Dynamic graph neural networks form a broad research direction, with applications spanning prediction tasks and opportunities for further work.

  • Takeaways & Limitations

    Current prediction research is largely limited to unattributed, time-conditioned discrete link-appearance prediction, with continuous-time encoders still sparsely studied.

Abstract

from arXiv · show

Dynamic networks are used in a wide range of fields, including social network analysis, recommender systems, and epidemiology. Representing complex networks as structures changing over time allow network models to leverage not only structural but also temporal patterns. However, as dynamic network literature stems from diverse fields and makes use of inconsistent terminology, it is challenging to navigate. Meanwhile, graph neural networks (GNNs) have gained a lot of attention in recent years for their ability to perform well on a range of network science tasks, such as link prediction and node classification. Despite the popularity of graph neural networks and the proven benefits of dynamic network models, there has been little focus on graph neural networks for dynamic networks. To address the challenges resulting from the fact that this research crosses diverse fields as well as to survey dynamic graph neural networks, this work is split into two main parts. First, to address the ambiguity of the dynamic network terminology we establish a foundation of dynamic networks with consistent, detailed terminology and notation. Second, we present a comprehensive survey of dynamic graph neural network models using the proposed terminology

I. INTRODUCTION

The survey addresses inconsistent terminology and fragmented coverage in dynamic-network research by establishing foundations, taxonomy, and context before surveying dynamic graph neural networks. It defines dynamic networks as structures whose nodes and edges can appear or disappear over time, capturing both temporal and structural patterns.

  • Motivation: Dynamic networks are important because real-world networks change over time, and temporal structure can affect network properties and predictive capabilities.The survey frames dynamic-network analysis as relevant across fields that use network representations of complex systems.
  • Scope and contributions: Its scope is broader than related surveys for dynamic-network foundations but narrower and more detailed for dynamic graph neural networks.The dynamic graph neural network coverage focuses on models encoding dynamic-network topology and their use in prediction.
  • Foundations: The paper establishes a comprehensive dynamic-network terminology and taxonomy to address inconsistent naming across interdisciplinary research.It defines a dynamic network as a graph whose nodes and edges have start and end timestamps.
  • Foundations: The survey provides a crossdisciplinary overview of dynamic-network models as context for understanding dynamic graph neural networks.The overview is intended as a reference point for further exploration rather than as a standalone dynamic-models survey.
  • Dynamic graph neural networks: The paper surveys dynamic graph neural networks, which combine graph-based aggregation for structural patterns with temporal modules such as recurrent networks or positional attention.These models support tasks including node classification and link prediction through task-specific decoders and data.
  • Organization: The survey is organized into foundations and dynamic-network models, dynamic-topology encoders, and prediction using dynamic graph neural networks.It follows an encoder-decoder framework and divides the work into sections that build upon one another.

1) Discrete Representation

Dynamic networks can be represented discretely as ordered graph snapshots or continuously through time-precise event, contact-sequence, and graph-stream representations. The suitable representation depends on link duration, which spans instantaneous interactions to persistent evolving relations.

  • Discrete representations: Discrete representations model a dynamic graph as an ordered set of graph snapshots.These snapshots allow static network methods to be applied repeatedly and collectively reveal network dynamics.
  • Discrete representations: Overlapping time-windows, multilayer networks, and tensors provide alternative snapshot-based representations.Sliding windows reduce abrupt changes between consecutive snapshots.
  • Continuous representations: Continuous representations preserve exact temporal information through event-based, contact-sequence, and graph-stream formats.Event-based and contact-sequence representations suit links that do not persist long, whereas graph streams suit longer-persisting edges.
  • Continuous representations: Event-based representations record node pairs, event start times, and durations, while contact sequences simplify events to instantaneous timestamps.Contact sequences are suitable for message networks such as text-message and email networks.
  • Continuous representations: Graph streams encode edge additions and removals as separate timestamped events, but are mainly used to address hardware limitations and are not surveyed in detail.The event indicator uses −1 for removal and 1 for addition.
  • Link duration spectrum: The link-duration spectrum distinguishes temporal networks with short-lived links from evolving networks whose persistent links establish a network structure.The spectrum ranges from zero-duration interactions to infinite-duration links that never disappear.

C. NODE DYNAMICS

Node dynamics distinguishes networks with a fixed node set from networks in which nodes may appear or disappear. Growing networks are a special case, and node dynamics can combine with any link-duration category.

  • Node dynamics: Static networks keep the number of nodes constant over time, whereas dynamic networks allow nodes to appear and disappear.This distinction is separate from how long links persist.
  • Node dynamics: Growing networks are node-dynamic networks in which nodes may only appear.The paper describes node-growing networks as common, while noting node-only-disappearing networks as a theoretical special case.
  • Node dynamics: Any node-dynamics category can be combined with any link-duration category, producing combinations such as growing evolving or node-static temporal networks.The authors keep node dynamics discrete rather than introducing a node-duration spectrum.
  • Node dynamics: Node dynamics is an important modelling consideration because some network models support it and others do not.Table 1 organizes dynamic network types by node dynamics and link duration, excluding special cases.

D. THE DYNAMIC NETWORK CUBE

The dynamic network cube organizes network types across temporal granularity, link duration, and node dynamics, while situating them within broader dynamic-network modelling approaches.

  • The dynamic network cube: The resulting network types can generally be combined, yielding domain-independent terminology for different dynamic-network configurations.The suggested terminology is presented in Table 2, while Table 3 lists types along the three dimensions.
  • Dynamic network models: Network models may serve as reference models or realistic models for tasks such as prediction, community detection, and network simulation.Reference models preserve selected characteristics while realistic models aim to replicate network change.
  • The dynamic network cube: The cube classifies dynamic networks along temporal granularity, link duration, and node dynamics.Its dimensions distinguish discrete versus continuous time, temporal versus evolving links, and node-static versus node-dynamic networks.
  • Dynamic network models: The survey establishes a typology of dynamic-network topology models based on the method used to model the network.This overview provides context for navigating dynamic graph neural networks.
  • Dynamic network models: Dynamic-network models include statistical, agent-based, and representation-learning approaches.Representation learning methods include tensor decomposition, random walks, and deep learning.

F. DISCUSSION AND SUMMARY

The survey combines a foundation and taxonomy of dynamic networks with a detailed review of dynamic graph neural networks. It highlights representation choices, model organization, and practical modelling constraints.

  • Discussion and summary: The survey provides a comprehensive dynamic-network foundation and uses it to organize the dynamic graph neural-network literature.Section II defines representations, link-duration categories, node dynamics, and their combined taxonomy; later sections examine DGNNs in detail.
  • Discussion and summary: Discrete representations suit snapshot-based modelling, whereas graph streams represent evolving networks whose updates are too frequent for snapshots.Both discrete and continuous representations can represent temporal networks.
  • Discussion and summary: Snapshot-based models process the graph at each time step, so runtime increases linearly with the number of snapshots and becomes costly for huge graphs.The per-snapshot cost is significant on large real-world networks.
  • Discussion and summary: Continuous-time representations offer finer temporal granularity but generally require more complex or substantially redesigned models.Continuous models are less common than discrete-time models, partly because they are more difficult to develop.
  • Dynamic graph neural networks: DGNNs encode dynamic graphs by combining graph-structure aggregation with temporal modelling, commonly using GNNs alongside RNNs or self-attention.Discrete DGNNs process snapshots, while continuous DGNNs iterate over the network.

A. PSEUDO-DYNAMIC MODELS

Pseudo-dynamic models represent changing topology or dynamic processes without fitting the model’s dynamic properties to dynamic data. The section also positions discrete DGNNs as GNN–time-series combinations.

  • Pseudo-dynamic models: Pseudo-dynamic models contain dynamic processes, but their dynamic properties are not fitted to dynamic data.The Barabási–Albert model is given as a non-DGNN example.
  • Pseudo-dynamic models: G-GCN extends VGAE for predicting links involving nodes with no prior connections, addressing the cold-start problem.It uses a GCN encoder and an inner-product decoder.
  • Discrete dynamic graph neural networks: Dynamic graphs can be modelled by applying static graph methods to snapshots, with temporal information handled separately.Discrete DGNNs use a GNN for each graph snapshot and a temporal component across snapshots.
  • Discrete dynamic graph neural networks: A discrete DGNN combines deep time-series modelling with a GNN, using RNNs most often and self-attention in some models.The GNN produces node representations at each time, while the temporal model produces representations across time.

1) Stacked Dynamic Graph Neural Networks

Stacked DGNNs separately encode graph structure at each snapshot and temporal patterns across snapshots. The architecture is flexible in its choice of GNN and temporal model, with node-specific variants also available.

  • Stacked Dynamic Graph Neural Networks: A stacked DGNN applies a separate GNN to each graph snapshot and feeds the outputs into a temporal model such as an RNN.This separates structural encoding from temporal encoding.
  • Stacked Dynamic Graph Neural Networks: GCRN-M1 exemplifies stacking a spectral GCN with a standard peephole LSTM.The architecture reshapes GNN outputs into vectors so a one-dimensional LSTM can encode the entire dynamic network.
  • Stacked Dynamic Graph Neural Networks: The stacked architecture is not tied to one GNN or RNN, and later examples combine spatial GCNs, PATCHY-SAN, or GGNNs with LSTMs.Other stacked models use self-attention, including GAT for spatial patterns and transformers for temporal patterns.
  • Stacked Dynamic Graph Neural Networks: WD-GCN and CD-GCN use a separate, weight-shared LSTM for each node after GCN processing.CD-GCN differs from WD-GCN by adding skip-connections past the GCN.
  • Stacked Dynamic Graph Neural Networks: Stacked DGNNs have been adapted to heterogeneous networks, knowledge networks, and snapshot-level subgraph anomaly detection.These variants preserve the stacked structural-and-temporal encoding pattern for specialized settings.

2) Integrated Dynamic Graph Neural Networks

Integrated DGNNs combine graph neural networks and recurrent neural networks within one layer to model spatial and temporal patterns jointly. Surveyed examples vary in their graph, recurrent, and application components, while preserving this integrated structure.

  • Integrated DGNNs combine GNNs and RNNs in one layer to model spatial and temporal domains jointly.
  • GCRN-M2: GCRN-M2 replaces ConvLSTM convolutions with graph convolutions for node-level two-dimensional signals.Its graph convolutions operate on both the input and hidden layer.
  • EvolveGCN: EvolveGCN integrates an RNN into a GCN to update its weights through matrix-based EGCU-H or EGCU-O layers.In EGCU-H, weights are the RNN hidden layer; in EGCU-O, they are the RNN input and output.
  • Other integrated models: Integrated approaches differ in their GNN or RNN, target use case, and graph type, including path-failure, knowledge-graph, and link-prediction applications.Examples include GC-LSTM, LRGCN, RE-Net, and TNA.
  • Autoencoder-based models: DynGEM and dyngraph2vec use autoencoder-based encoders to incorporate information across graph snapshots for dynamic representation or prediction.DynGEM initializes each snapshot from the previous snapshot, while dyngraph2vec uses a sliding window of past snapshots.
  • Generative models: VGRNN and SI-VGRNN integrate GCNs into RNN encoders to track temporal graph evolution, while GCN-GAN and DynGraphGAN target dynamic link prediction with adversarial architectures.

D. CONTINUOUS DYNAMIC GRAPH NEURAL NETWORKS

Continuous DGNNs model graph changes as event streams rather than snapshots, using RNNs, temporal point processes, or time embeddings. The surveyed approaches update embeddings or event intensities to represent evolving network structure and interactions.

  • Continuous DGNNs comprise RNN-based, temporal-point-process, and time-embedding approaches.
  • RNN-based approaches: RNN-based models update interacting nodes’ embeddings whenever network events occur, keeping representations continuously current.The category includes SGNN for directed strictly evolving networks and JODIE for interaction networks.
  • Streaming graph neural networks: SGNN separates node-state updating from neighborhood propagation, using interaction, update or propagate, and merge units.The update component runs first, followed by propagation to local neighbors.
  • JODIE: JODIE maintains separate user and item RNNs that update embeddings using prior embeddings, interaction features, and elapsed time.Its projection component predicts future embedding trajectories and is trained for that prediction.
  • Related temporal-point-process models: Know-Evolve, LDG, and GHN extend temporal point-process modelling to interaction or temporal knowledge networks through recurrent or attention-based architectures.
  • Temporal point processes: DyREP parameterizes a temporal point process to jointly model structural network evolution and node communication.Its intensity function can predict link appearance and the time of link appearance.

3) Time embedding based models

Time-embedding DGNNs represent temporal information as vectors and combine those features with neighborhood information through attention. TGAT uses learned time features in masked attention, while TGN adds memory of node history.

  • Time-embedding methods represent temporal patterns with positional or functional time vectors, including time2vec and functional time embeddings.
  • TGAT: TGAT’s time embedding uses learned frequencies and phases to encode time relative to a neighboring event.The embedding size is d.
  • TGAT architecture: A TGAT layer concatenates target, neighbor, optional edge, and time features before applying masked graph attention.Each additional layer adds one more neighborhood hop.
  • TGAT architecture: 2 layers (2 hops) were found optimal for TGAT because additional hops exponentially increase run-time.
  • TGN: TGN extends TGAT with a memory module that embeds each node’s history and adds the memory vector to the temporal feature representation.

E. DISCUSSION AND SUMMARY

The survey finds promising but uneven coverage of dynamic graph topology: discrete DGNNs are broader and snapshot-based, whereas continuous models remain specialized. Model choice therefore depends on network type, temporal detail, node dynamics, and computational constraints.

  • Deep learning methods for dynamic graphs already show capacity to encode dynamic topology, although the field remains new.
  • Expressivity limitations: Models that cannot represent link deletion or duration are limited to strictly evolving or interaction networks, although deletion events can represent disappearing persistent links.
  • Expressivity limitations: The survey states that deletion-event and node-removal mechanisms have not been implemented in practice to the authors’ knowledge.
  • Model comparison: Discrete model complexity depends on graph size per snapshot and snapshot count, while time-window construction trades temporal granularity for faster computation.
  • Coverage limitations: Continuous DGNNs currently target specialized network types, leaving no general-purpose continuous encoder for dynamic networks.
  • Model selection: Practitioners should consider static GNNs first when a discrete representation is sufficient because they train faster and are generally simpler.
  • Model comparison: Discrete DGNNs iterate over snapshots, while continuous DGNNs iterate edge-by-edge and generally take longer to train, especially on dense networks.
  • Model selection: For detailed interaction timestamps, TGAT or TGN are suggested, whereas node-dynamic settings favor DySAT, EvolveGCN, or HDGNN.

A. DECODERS

Dynamic-network decoders transform dynamic graph embeddings into edge or adjacency predictions, most often for time-conditioned link prediction. The survey contrasts simple embedding aggregation, feed-forward, generative, and downstream-decoding strategies with their associated losses.

  • Most surveyed predicting decoders are time-conditioned and output an adjacency matrix representing edge probabilities, often for time τ = t + 1.
  • Decoders produce predicted adjacency matrices from dynamic graph embeddings, typically combining the embeddings of two nodes to estimate link probability.
  • Inner products, concatenation, means, and Hadamard products provide simple link decoders when likely connected nodes are suitably embedded.
  • Feed-forward decoders add parameters but can represent nonlinear relationships between node embeddings for link prediction.
  • Generative decoders such as GraphRNN, GCN-GAN, and DynGraphGAN generate graph structures or adjacency matrices for dynamic-network prediction.
  • Downstream decoding reuses embeddings learned for one task, such as node classification, for another task, such as link prediction.
  • Deep prediction methods use losses for direct link prediction or dynamic-graph reconstruction, with binary cross-entropy common for edge prediction and negative sampling addressing imbalance.

2) Autoencoders

The survey distinguishes reconstruction-based autoencoders from temporal-point-process objectives and reviews evaluation metrics for highly imbalanced dynamic link prediction. It emphasizes that metric choice must reflect whether links are new, recurring, appearing, or disappearing.

  • 2) Autoencoders: Autoencoder approaches reconstruct discrete dynamic networks snapshot by snapshot, while variational autoencoders additionally support generative latent-space interpolation.
  • 2) Autoencoders: E-LSTM-D weights reconstruction loss toward existing links through a matrix that increases their contribution.
  • 2) Autoencoders: DyRep optimizes a temporal point process whose loss rewards high intensity for observed events and high survival probability for events that do not occur.
  • 2) Autoencoders: DyRep estimates an intractable intensity integral by sampling non-events and applying Monte Carlo estimation within each mini-batch.
  • 2) Autoencoders: Regularization may combine reconstruction loss with a weighted penalty, commonly using L2 norms or variational distributions conditioned on previous observations.
  • C. EVALUATION METRICS: Dynamic link prediction is difficult to evaluate because actual links can comprise less than 1% of all possible links, making class imbalance substantial.
  • C. EVALUATION METRICS: Fixed-threshold metrics are discouraged without a natural threshold, while PRAUC and error rate are presented as alternatives for imbalanced prediction.
  • C. EVALUATION METRICS: GMAUC separates newly appearing links from previously observed links, but its use assumes recurring-link prediction is sufficiently balanced.

D. DISCUSSION AND SUMMARY

The survey frames dynamic graph prediction as a pipeline from network definition through encoding and decoding, while finding that current work remains concentrated in discrete, unattributed link prediction. It identifies evaluation, temporal resolution, scalability, and network diversity as open challenges.

  • D. DISCUSSION AND SUMMARY: Dynamic-network prediction combines encoders, decoders, and losses that capture temporal and structural information, with most surveyed models using downstream embeddings for link prediction.
  • D. DISCUSSION AND SUMMARY: Direct prediction architectures are expected to optimize more fully for the prediction task than two-step embedding-and-decoding architectures.
  • D. DISCUSSION AND SUMMARY: Dynamic link-prediction evaluation is non-trivial because massive class imbalance affects metric suitability and recurring links may not be balanced.
  • D. DISCUSSION AND SUMMARY: Current deep models largely focus on unattributed, time-conditioned, discrete link-appearance prediction, leaving other prediction settings relatively unexplored.
  • V. CHALLENGES AND FUTURE WORK: Future models should cover dynamic attributes, directed or signed edges, heterogeneous and multilayer networks, and predictions beyond topology.
  • V. CHALLENGES AND FUTURE WORK: Continuous-time modelling could provide finer temporal representations than snapshot-based methods, but further work is needed.
  • V. CHALLENGES AND FUTURE WORK: Scalability is constrained by snapshot-processing bottlenecks and interaction-driven costs, while frequent snapshots can undermine temporal-network modelling.
Loading 2005.07496v2…