PaperlayerView exact revision on arXiv

Source-linked AI summary

Representation Learning for Dynamic Graphs: A Survey

Seyed Mehran Kazemi, Rishab Goel, Kshitij Jain, Ivan Kobyzev, Akshay Sethi, Peter Forsyth, Pascal Poupart

arXiv:1905.11485v2cs.LGstat.ML

TL;DR

Graph learning must address applications in which nodes, attributes, and edges evolve over time rather than remain static. The paper surveys dynamic-graph representation learning through encoder-decoder categories, reviews applications and datasets, and identifies future research directions. Its synthesis highlights limited coverage of continuous-time observations and motivates broader dynamic-graph models.

  • Problem

    Many real-world graphs evolve, while traditional graph learning has mostly focused on static graphs, creating a need to study representation learning for dynamic settings.

  • Method

    The paper surveys dynamic-graph representation learning by categorizing encoders and decoders according to how they produce embeddings and predictions.

  • Results

    The survey organizes recent approaches, applications, datasets, and future directions for representation learning over dynamic graphs.

  • Takeaways & Limitations

    Future work should extend dynamic-graph models to richer continuous-time observations and hyperedges.

  • Takeaways & Limitations

    Existing continuous-time dynamic-graph methods are few and mainly handle new-edge additions rather than broader event types.

Abstract

from arXiv · show

Graphs arise naturally in many real-world applications including social networks, recommender systems, ontologies, biology, and computational finance. Traditionally, machine learning models for graphs have been mostly designed for static graphs. However, many applications involve evolving graphs. This introduces important challenges for learning and inference since nodes, attributes, and edges change over time. In this survey, we review the recent advances in representation learning for dynamic graphs, including dynamic knowledge graphs. We describe existing models from an encoder-decoder perspective, categorize these encoders and decoders based on the techniques they employ, and analyze the approaches in each category. We also review several prominent applications and widely used datasets and highlight directions for future research.

1. Introduction

Graphs capture relations in many applications, but traditional graph learning largely assumes static structures. This survey examines representation learning methods for evolving graphs using an encoder-decoder framework.

  • Graphs naturally represent relations among entities in social networks, recommender systems, ontologies, biology, and computational finance.
  • Dynamic graphs evolve as communication events stream and as users, products, ratings, transactions, and supply-chain relations change.
  • Earlier dynamic-graph surveys did not review recent advances in neural representation learning.
  • The survey reviews time-dependent embeddings and embedding-based tasks including node classification, event prediction or interpolation, and link prediction.
  • An encoder-decoder framework organizes methods that encode evolving graph information into embeddings and decode embeddings into predictions.
  • The surveyed techniques address discrete-time and/or continuous-time events, alongside background on graph inference and learning methods.

2. Background and Notation

The survey establishes graph and dynamic-graph notation, distinguishes discrete- from continuous-time evolution, and frames representation learning through encoder-decoder models. It also highlights that indistinguishable node embeddings limit classification expressivity.

  • Static graphs: Graphs consist of vertices and edges, with adjacency, degree, and Laplacian matrices providing standard structural representations.The adjacency matrix stores edge weights, the degree matrix stores row sums, and the Laplacian is L = D − A.
  • Static graphs: Knowledge graphs are directed multigraphs whose labeled edges are triples linking a source, relation type, and target.Unlike heterogeneous information networks, knowledge graphs can allow multiple differently labeled edges between two nodes.
  • Dynamic graphs: Discrete-time dynamic graphs are sequences of regularly sampled snapshots, whereas continuous-time dynamic graphs update an initial graph through timestamped events.Discrete snapshots can lose temporal information, while continuous-time events may include edge or node additions, deletions, splits, and merges.
  • The encoder-decoder framework: The encoder-decoder framework represents models as pairs that encode dynamic graphs into hidden representations and decode them for prediction.Compatible encoders and decoders can be recombined when their hidden representations conform.
  • Expressivity: If two nodes receive identical embeddings, any deterministic decoder assigns them the same class, preventing different labels for those nodes.This limitation illustrates why insufficient model expressivity can lead to underfitting.

3. Representation Learning for Static Graphs

The survey introduces static-graph representation learning as background, covering proximity-based, shallow, decomposition, spectral, and graph-convolutional encoders alongside expressivity results.

  • Static-graph methods provide background for the survey’s later discussion of dynamic-graph representation learning.
  • High-Order Proximity Matrices: High-order proximity encoders represent each node with a row or column of a proximity matrix and are typically parameter-free.Examples include common neighbors, Jaccard’s coefficient, Adamic-Adar, Katz, and preferential attachment.
  • Shallow Encoders: Shallow encoders directly learn node and relation vectors or matrices as lookup representations indexed by entity identifiers.
  • Decomposition Approaches: Decomposition methods learn embeddings that place connected nodes close together, using constrained eigenvalue or singular-value decompositions.Constraints remove scaling and trivial single-vector solutions; spectral embeddings can use top generalized eigenvectors or adjacency eigenvectors.
  • Graph Convolutional Network Approaches: GCN layers aggregate representations from a node and its neighbors through an order-invariant transform that handles variable neighborhood sizes.Attributed graphs can initialize node representations with attribute vectors.
  • Graph Convolutional Network Approaches: GCN expressivity is studied through graph-isomorphism tests and universal approximation, with certain models matching Weisfeiler-Lehman power and G-invariant networks acting as universal approximators.

4. Encoders for Dynamic Graphs

Dynamic-graph encoders address evolving graphs and differ according to whether reasoning targets extrapolation or interpolation. The survey categorizes these approaches within an encoder-decoder framework.

  • Dynamic-graph reasoning includes extrapolation and interpolation, which typically require different encoder types.
  • The survey organizes dynamic-graph representation-learning techniques by how encoders produce embeddings for downstream decoders.

4.1 Aggregating Temporal Observations

Temporal aggregation simplifies dynamic graphs by combining observations into a static graph, enabling static encoders but discarding temporal detail. Weighted aggregation can emphasize recent snapshots, yet aggregation may hinder accurate prediction when timing matters.

  • Aggregation collapses temporal observations or adjacency matrices into a static graph, after which a static encoder can generate embeddings.
  • Uniform and weighted aggregation schemes combine snapshots, with θ controlling the emphasis placed on recent observations.Larger θ values assign greater importance to more recent adjacency matrices.
  • Aggregation can assign identical values to pairs with different interaction histories, such as newly formed versus recently dissolved connections.
  • Aggregation methods offer simplicity, scalability, and reuse of static-graph learning methods, and can support extrapolation or interpolation with suitable weighting.For interpolation, weights can depend on distance from the prediction timestamp.
  • Aggregation may lose useful timing information and hinder accurate predictions when the timing of events is important.Formation and dissolution aggregation specifically loses timing information.

4.2 Aggregating Static Features

These approaches compute static node features independently at each snapshot and aggregate them into a single representation for decoding. Aggregation can use fixed temporal weights or learned time-series models, balancing simplicity and scalability against repeated per-snapshot computation.

  • Static feature aggregation: Static encoders first compute node features independently for each snapshot, then aggregate them into a single vector supplied to a decoder.The framework can use any suitable static encoder at each timestamp.
  • Temporal weighting: Exponential-decay aggregation assigns greater weight to recent snapshots and can support extrapolation or interpolation with a modified time weighting.For interpolation, weights can depend on distance from the queried timestamp rather than distance from the latest snapshot.
  • Temporal weighting: Time-series models such as ARIMA and moving averages predict future feature values instead of using explicitly fixed snapshot weights.The surveyed works fit these models to features from previous snapshots.
  • Example: A common-neighbor encoder illustrates the procedure by producing embeddings separately from each adjacency snapshot before combining them with temporal weights.The example notes that other static encoders could be substituted.
  • Trade-offs: The approach can reuse static-graph literature and offers simplicity, scalability, and flexibility for interpolation and extrapolation.Its computational cost can nevertheless become high when many snapshots or expensive static encoders are used.

4.3 Time as a Regularizer

Time-regularized encoders impose temporal coherence by encouraging a node’s embeddings to remain similar across consecutive snapshots. Alternative initialization strategies preserve this continuity while allowing sharp changes when graph events require them.

  • Smoothness constraints: Smoothness constraints penalize distances between a node’s embeddings at consecutive snapshots to discourage abrupt representation changes.Euclidean distance is a common choice, although other distances are also used.
  • Distance functions: Rotation projections or angular distances provide alternatives to direct Euclidean comparison when aligning embeddings across snapshots.The angular formulation restricts embedding vectors to unit norm.
  • Online updates: Some methods update representations incrementally, support streaming observations, and can handle newly added nodes.One LINE extension recomputes embeddings only for nodes strongly affected since the previous snapshot.
  • Autoencoder integration: Time regularization can be combined with static autoencoders by adding a penalty based on the distance between current and previous latent representations.The example applies reconstruction and temporal-consistency objectives across successive timestamps.
  • Trade-offs: Penalizing temporal distance can suppress genuine abrupt changes, whereas initializing each snapshot from the previous model allows sharp changes when necessary.This trade-off is illustrated by events such as a company acquisition.

4.4 Decomposition-based Encoders

Decomposition-based encoders represent dynamic graphs by decomposing temporal adjacency data into components whose factors provide node embeddings and temporal patterns. Incremental matrix updates improve efficiency, but accumulated approximation error requires periodic recalculation.

  • Tensor decomposition: Stacking adjacency matrices across timestamps yields an order-3 tensor that can be decomposed to obtain dynamic node representations.The row factors can be interpreted as node embeddings, while temporal factors encode evolution.
  • Temporal prediction: Tensor factors capture temporal patterns and support interpolation, while Holt-Winters forecasting extends temporal factors for extrapolation.The forecasted factors reconstruct adjacency tensors for future snapshots.
  • Temporal factorization: A factorized prediction model separates static node features from time-dependent features and predicts future adjacency with ˆAT+l = U(VT+l)′.The time-dependent factor is modeled as a polynomial in time in the described approach.
  • Temporal knowledge graphs: Temporal knowledge graphs can be modeled as order-4 tensors and decomposed with CP, Tucker, or related methods to obtain entity, relation, and timestamp embeddings.Some surveyed work connects these decompositions with cognitive memory functions.
  • Streaming updates: Incremental eigenvalue and singular-value updates efficiently adapt decompositions after small graph changes, including new edges or nodes.Perturbation methods approximate updated eigenpairs, while likelihood estimation can embed an added node.
  • Limitations: Incremental updates accumulate approximation error, so models must be recalculated periodically when the error exceeds an acceptable threshold.A proposed method can signal the timestamp at which a specified tolerance is exceeded.

4.5 Random Walk Encoders

Random-walk encoders learn unsupervised node embeddings and can reuse prior walks to reduce computation in evolving graphs. Time-respecting walks capture temporal order, but updating walks and embeddings remains costly in streaming settings.

  • Snapshot updates: Dynamic-graph methods reuse valid walks from previous snapshots and generate new walks from affected nodes to update embeddings efficiently.The procedure can initialize the current embedding model with parameters learned at the preceding snapshot.
  • Update bias: Naively retaining prior walks while adding walks from affected nodes can bias the resulting walk distribution relative to generating walks from scratch.The bias occurs because earlier walks could not traverse edges that did not yet exist.
  • Update bias: Unbiased update algorithms reuse valid previous walks while generating new walks for the new snapshot.NetWalk instead combines dynamic walks with a customized autoencoder for node representations.
  • Temporal walks: Time-respecting walks constrain successive edges to move forward in time, with transition distributions that may depend on the current timestamp.In the example, only transitions using edges added after the walk’s previous edge are valid.
  • Temporal walks: Combining static walks on older observations with temporal walks on recent observations uses topology from the past and temporal information from the recent interval.The resulting walks are jointly used to learn node embeddings.
  • Core approach: Random-walk approaches learn embeddings without requiring a decoder and can support unsupervised tasks such as clustering and community detection.They may also capture longer-term dependencies than decomposition approaches.
  • Limitations: Random-walk updates require new walks and gradient optimization after incoming observations, making them less suitable for fast streaming scenarios.The required update can be time-consuming for large dynamic graphs.
  • Limitations: Most surveyed random-walk representation learning methods target non-attributed graphs, leaving extension to attributed graphs as a future direction.

4.6 Sequence-Model Encoders

Sequence-model encoders represent dynamic graphs by combining graph-structural information with temporal evolution. They include snapshot-based RNN pipelines, graph-aware recurrent models, attention mechanisms, and continuous-time event updates.

  • RNN-based encoders for DTDGs: Snapshot-based pipelines apply a graph encoder to each snapshot, then use an RNN to aggregate each node’s representation across its history.The graph encoder captures structural information, while the RNN captures temporal information before decoding predictions.
  • RNN-based encoders for DTDGs: Embedded approaches replace standard recurrent gate computations with graph-convolution operations that incorporate neighborhood structure and recurrent memory.Chen et al. combine GCNs with LSTMs, embedding separate GCN models into the LSTM gates and initializing them from hidden or memory states.
  • Other sequence models: Other DTDG sequence encoders use Kalman filters or self-attention to track node embeddings across graph snapshots.DySAT applies attention-based GCNs per snapshot, adds positional embeddings, and then uses multi-head self-attention over the temporal sequence.
  • RNN-based encoders for CTDGs: Continuous-time RNN models mainly process new-edge events by updating source and target node representations, and relation representations for dynamic knowledge graphs.JODIE uses separate source and target RNNs, while Know-Evolve updates entities and relations through custom recurrent mechanisms.

4.7 Autoencoder-based Encoders

Autoencoder-based encoders learn dynamic node or node-pair representations from current and previous graph snapshots. They can transfer parameters between snapshots for faster learning and smoothness, but may not fully capture node evolution.

  • Node-based autoencoders: Dynamic autoencoders encode node histories from adjacency rows and reconstruct the current snapshot’s adjacency information.Goyal et al. use feed-forward networks or LSTMs for the encoder, with analogous architectures for reconstruction.
  • Model transfer across snapshots: Each snapshot’s autoencoder can inherit the preceding model’s weights, with architecture changes supported by network widening and deepening transformations.The model size is selected heuristically using the previous autoencoder and graph differences.
  • Discussion and analysis: Parameter initialization across snapshots accelerates current-snapshot learning and implicitly imposes a smoothness constraint, but the learned embeddings may not capture node evolution.Bonner et al. propose alternative autoencoders to better represent that evolution.
  • Pairwise autoencoders: Autoencoders can instead map node pairs to hidden representations for predicting edge additions or deletions in the next snapshot.The pairwise features are computed from graphlet transitions and concatenated across previous snapshots.

4.8 Diachronic Encoders

Diachronic encoders map nodes, relations, or timestamps to representations that vary with time. Different designs model temporal trends, seasonality, timestamp structure, or explicit time-dependent feature components.

  • Definition and scope: Diachronic encoders represent node–timestamp or relation–timestamp pairs, unlike encoders that map each node or relation independently of time.They are useful for interpolation because they can provide embeddings at arbitrary time points.
  • Explicit temporal functions: A node-specific diachronic encoder makes a selected percentage of embedding features explicit functions of time while leaving the remaining features constant.A node embedding at a specific time is obtained by substituting that time into the learned function.
  • Time-dependent embeddings: Some models make embeddings direct functions of time by combining shallow embeddings with trend and seasonal components and Gaussian uncertainty.The resulting distribution has mean zv + αvwvt + βvsin(2πωvt) and covariance matrix Σv.
  • Timestamp embeddings: Other models learn timestamp embeddings and project entity and relation embeddings into the timestamp-specific space.This design provides embeddings only for a pre-defined set of timestamps.
  • Timestamp structure: Character-level timestamp encoders feed relation embeddings and timestamp-character embeddings into an LSTM, allowing missing date values to be handled naturally.The approach can also be applied to node embeddings and optionally includes time-modifier embeddings.

4.9 Staleness

Staleness arises in continuous-time dynamic graphs when a node’s embedding is not updated after its last observation. Time-aware updates can estimate the node’s current representation during inactive intervals.

  • Problem: A node representation may become stale when time passes after its last update without a new observation involving that node or its influencers.This issue is especially relevant to extrapolation over continuous-time dynamic graphs.
  • Time-based updates: Kumar et al. model representation evolution during inactivity by encoding the elapsed time since the node’s previous interaction.The elapsed-time vector is learned from time-dependent parameters.
  • Prediction: The resulting time-adjusted representation replaces the potentially stale embedding when making predictions at the current time.Diachronic encoders can similarly update embeddings without new observations when adapted for extrapolation.

5. Decoders for Dynamic Graphs

The survey organizes dynamic-graph decoders into time-predicting and time-conditioned categories, covering temporal event prediction, interpolation, and timestamp-specific graph queries.

  • Time-predicting decoders: Time-predicting decoders estimate when an event will occur or infer a missing timestamp, supporting extrapolation and interpolation.Examples include predicting a future visit and recovering the missing time of a knowledge-graph relation.
  • Time-predicting decoders: Early approaches count relation-specific paths and use generalized linear models with exponential, Weibull, or geometric time distributions.The model score parameterizes a density, whose expected time predicts when the relation will form.
  • Time-predicting decoders: Neural time-predicting methods use node and relation embeddings to parameterize temporal point-process intensities and derive event-time predictions from conditional densities.The intensity uses the graph history, the latest involvement time, and an exponential transform to remain positive; survival integrals may require approximation.
  • Time-predicting decoders: Equation (55)’s intensity can fail for concurrent events because t may equal the most recent event time, making the intensity zero.This caveat limits the suitability of that formulation when events occur simultaneously.
  • Time-predicting decoders: Relation-specific temporal point processes distinguish faster-changing communications from slower-changing associations, with sampling used to approximate survival-function computations.This models interactions and topological evolution using separate rates of change.
  • Time-conditioned decoders: Time-conditioned decoders predict graph facts at a specified timestamp rather than predicting the time of an event.They support both future queries and interpolation of missing historical facts.
  • Time-conditioned decoders: Timestamp embeddings can be incorporated into TransE, DistMult, ComplEx, RESCAL, and related scores, but shallow timestamp encoders generalize poorly beyond observed times.Such models may not support future timestamps effectively and can overfit when training contains many distinct timestamps; character-level timestamp embeddings offer a potential alternative.
  • Time-conditioned decoders: Static node representations may lose information needed for timestamp-specific predictions, motivating representations that vary with time.The issue arises when a node’s relevant facts differ across timestamps.

6. Other Relevant Models and Problems

Beyond encoder-decoder models, the survey reviews probabilistic relational reasoning, spatiotemporal graph formulations, and dynamic knowledge-graph construction from text.

  • Statistical relational models: Statistical relational models combine logic and probability through soft rules, enabling probabilistic inference over graph facts.Examples include Markov logic networks, Problog, probabilistic soft logic, and relational logistic regression.
  • Statistical relational models: These models naturally represent uncertainty and support joint, interpretable inference over an entire graph, but require additional computation.Their uncertainty handling is relevant when relations come from noisy measurements or ambiguous language.
  • Statistical relational models: Dynamic statistical relational models add time as an argument to soft rules, allowing rules to increase the probability of likely transitions between snapshots.A triadic-closure rule raises the probability that friends of friends become friends in the next snapshot.
  • Probabilistic walks: Probabilistic-walk approaches learn walks that probabilistically reach nodes having a desired relation to a starting node.They are distinguished from the random-walk encoders discussed elsewhere in the survey.
  • Spatiotemporal graphs: Spatiotemporal graph methods connect nodes across snapshots with temporal links and learn on the resulting static graph.They are applied to structured time-series tasks including video activity recognition and traffic-flow prediction.
  • Spatiotemporal graphs: Other approaches reason directly over evolving graphs, including temporal and spatial graph convolutions for human-skeleton action recognition.These methods avoid the heuristics used by approaches that first combine frame-level graphs into spatiotemporal graphs.
  • Dynamic knowledge-graph construction: Dynamic knowledge-graph construction from text extracts probabilistic facts and adds those exceeding a confidence threshold.Some systems also use graph-based predictive models to supply prior probabilities independent of textual evidence.

7. Applications, Datasets & Codes

The survey covers dynamic-graph applications, evaluation tasks, representative temporal datasets, and open-source implementations for graph and knowledge-graph models.

  • Applications: Dynamic-graph applications include link prediction, entity or relation prediction, recommender systems, temporal reasoning, graph classification, and community detection.The survey also discusses datasets and software resources supporting representation-learning research.
  • Applications: Dynamic link prediction asks whether a labeled or unlabeled link existed in the past or will appear in the future.Applications include temporal knowledge-graph completion, friend recommendation, biological-connection discovery, and obsolete-fact prediction.
  • Applications: Dynamic recommender systems use timestamped user-item interactions to recommend items according to evolving tastes, including cyclic or trending behavior.Unlike basic link prediction, the output is a sequence of recommendation slates.
  • Applications: Temporal reasoning includes predicting event times, missing timestamps, and epidemic states, while graph classification and community detection use classification accuracy or cluster-overlap measures.Multi-class epidemic settings may also report micro-F1 and macro-F1.
  • Datasets: Table 2 summarizes dataset type, node and edge counts, and temporal granularity for datasets used in dynamic knowledge-graph publications.The survey provides a representative sample and points readers to network repositories for additional datasets.
  • Datasets: The Social Evolution and Github datasets distinguish associative or topological events from communicative interactions.Social Evolution contains 83 nodes; Github contains 12,328 nodes and 604,649 communication events.
  • Datasets: HEP-TH is an evolving citation network, whereas Autonomous Systems provides 733 daily snapshots with both node and edge additions and deletions.HEP-TH grows from 1424 to 7980 nodes and from 2,556 to 21,036 edges; Autonomous Systems grows from 103 to 6,474 nodes.

8. Future Directions & Conclusion

The survey organizes recent dynamic-graph representation-learning research through an encoder-decoder framework and identifies open directions spanning graph types, temporal observations, classification, expressiveness, hyperedges, and benchmarking.

  • Conclusion: The survey reviews dynamic-graph representation learning through an encoder-decoder framework and highlights directions for improving learning and reasoning.The framework categorizes techniques that encode graph information into embeddings and decode embeddings into predictions.
  • Continuous-time dynamic graphs: Continuous-time dynamic-graph models should handle edge deletion, node addition and deletion, node splitting, node merging, and other observations beyond edge addition.Existing continuous-time work is limited, and one node-addition method uses only the graph’s current state rather than its evolution.
  • Generalizing graph encoders: Extending encoders across graph types remains difficult, including random walks for attributed graphs and autoencoders for knowledge graphs.The survey identifies broader applicability to more graph types as a future research direction.
  • Sequence modeling: Streaming continuous-time models could replace recurrent architectures with self-attention, while simultaneous observations require order-robust processing.Current RNN-based encoders use random orderings for observations occurring at the same time, which may hinder generalization to other orderings.
  • Dynamic-graph classification: Dynamic-graph classification remains understudied, with current approaches often converting dynamic graphs into static graphs before classification.The survey calls for models designed specifically to classify dynamic graphs.
  • Representation scope and evaluation: Future models should address hyperedges and standardized benchmarks, because binary reification can leave no test-time embedding and differing datasets hinder comparison.The survey recommends dynamic models capable of handling hyperedges and benchmarks with common train, validation, and test splits.
Loading 1905.11485v2…