Source-linked AI summary
dyngraph2vec: Capturing Network Dynamics using Dynamic Graph Representation Learning
Palash Goyal, Sujit Rokka Chhetri, Arquimedes Canedo
TL;DR
Static graph embeddings do not adequately represent evolving networks with varied temporal dynamics, limiting their use for future-link prediction. dyngraph2vec combines dense and recurrent layers to learn structural patterns and temporal transitions, and the paper reports improved link-prediction performance over state-of-the-art methods. The approach captures temporal patterns on synthetic and real datasets, while community growth or shrinkage remains future work.
Problem
Existing graph representation methods primarily focus on static aggregated or snapshot graphs, although real networks evolve through complex temporal dynamics relevant to predicting future links.
Method
dyngraph2vec uses multiple nonlinear layers for graph structure and recurrent layers to learn temporal transitions from graph snapshots, with lookback controlling temporal-history length.
Results
dyngraph2vec captures temporal patterns on synthetic and real datasets and outperforms state-of-the-art methods in link prediction.
Takeaways & Limitations
Learning network dynamics can improve embedding quality and link-prediction performance, including for temporal patterns that span multiple time steps.
Takeaways & Limitations
Handling evolving communities whose sizes or total number change is identified as future work requiring inductive methods.
Abstract
from arXiv · showhide
Learning graph representations is a fundamental task aimed at capturing various properties of graphs in vector space. The most recent methods learn such representations for static networks. However, real world networks evolve over time and have varying dynamics. Capturing such evolution is key to predicting the properties of unseen networks. To understand how the network dynamics affect the prediction performance, we propose an embedding approach which learns the structure of evolution in dynamic graphs and can predict unseen links with higher precision. Our model, dyngraph2vec, learns the temporal transitions in the network using a deep architecture composed of dense and recurrent layers. We motivate the need of capturing dynamics for prediction on a toy data set created using stochastic block models. We then demonstrate the efficacy of dyngraph2vec over existing state-of-the-art methods on two real world data sets. We observe that learning dynamics can improve the quality of embedding and yield better performance in link prediction.
1. Introduction
Graph representation learning has largely modeled static networks, while real networks evolve through temporal patterns that affect link prediction. dyngraph2vec learns structural and temporal dynamics from graph snapshots to predict future connections.
- Graph representation learning maps nodes to fixed-dimensional vectors, enabling link prediction as nearest-neighbor search in embedding space.
- Static methods use aggregated or snapshot graphs, but cannot capture complex dynamics governing network evolution.
- Multiple snapshots can reveal temporal patterns that let models predict a user’s next connection more accurately than a single snapshot.
- Temporal patterns vary in duration and across vertices, challenging methods that assume short, two-step patterns or smooth changes.
- dyngraph2vec combines nonlinear layers for structural patterns with recurrent layers for temporal transitions, using a lookback parameter to control learned history.
- The model targets link prediction, evaluates collaboration and social networks, supports aggregated and snapshot graphs, and reports improved performance over state-of-the-art methods.
2. Related Work
Related work spans static embeddings, dynamic extensions, and direct dynamic link-prediction models. Existing dynamic embedding methods commonly rely on smoothness, incremental updates, short temporal patterns, or link-level representations.
- Static graph embedding represents each node with one vector, whereas dynamic graph embedding produces time-indexed vectors from multiple graph snapshots.
- Distance-preserving methods match node distances between graph and embedding spaces, while structure-preserving methods retain node roles.
- DynGEM initializes each embedding from the previous timestep, implicitly encouraging temporal smoothness without explicit regularization.
- DynamicTriad relaxes smoothness but models only patterns spanning two timesteps, while TIMERS updates embeddings with incremental SVD and threshold-triggered reruns.
- DYLINK2VEC embeds links rather than nodes and learns temporal patterns, but link embedding is non-scalable for dense graphs.
- Other dynamic link-prediction approaches use probabilistic non-parametric models, matrix or tensor factorizations, or application-specific designs.
3. Motivating Example
The motivating example constructs a stochastic-block-model graph whose communities evolve as selected nodes shift membership. Embeddings that capture dynamics move those nodes toward their future community, unlike several static or short-history baselines.
- The toy graph begins with two 500-node communities generated by a stochastic block model, using in-block probability 0.1 and cross-block probability 0.01.
- Community evolution repeatedly increases selected nodes’ cross-community connections before changing their membership and rewiring edges.
- The task is to learn embeddings predictive of community changes for 10 selected nodes.
- DynGEM moves selected nodes only toward the yellow-community boundary, DynamicTriad shifts 1 to 4 nodes, and optimalSVD shifts none.
- The three dyngraph2vec variations move most selected nodes into the indigo community while keeping other nodes intact.
4. Methodology
The methodology defines dynamic graph embedding as learning low-dimensional node representations from graph histories to predict future links. dyngraph2vec combines dense and recurrent architectures, with variants that trade temporal modeling against parameter efficiency.
- Optimization: Training minimizes weighted reconstruction error for future edges, emphasizing observed edges, and updates all layers using backpropagation or backpropagation through time with Adam.The LSTM-based variants use backpropagation through time to update recurrent weights.
- Architecture variations: The three architectures are dyngraph2vecAE, dyngraph2vecRNN, and dyngraph2vecAERNN, differing in how they formulate the temporal mapping function.The AE variant extends autoencoders, while the RNN and AERNN variants address temporal information and parameter-count limitations.
- Problem formulation: dyngraph2vec maps graph evolution to time-indexed node embeddings that capture temporal patterns needed to predict future representations and links.The embedding at each time step uses graph history, while the model predicts the graph at a subsequent time step.
- Problem formulation: The model takes previous graph snapshots as input and generates the graph at the next time step, modeling nonlinear interactions within and across time.This forecasting setup is trained to capture evolving relations between nodes.
- Architecture variations: dyngraph2vecAE uses fully connected layers over a look-back window, but its parameter count is O(nld^(1)), making learning challenging for sparse graphs.The look-back window supplies neighborhood vectors from multiple graph snapshots.
- Architecture variations: dyngraph2vecRNN uses sparsely connected LSTM networks to model long-term dependencies and reduce parameters relative to fully connected temporal processing.Multiple LSTMs can pass cell states and hidden representations across the look-back sequence.
- Architecture variations: dyngraph2vecAERNN first encodes sparse neighborhood vectors into low-dimensional representations, passes them through LSTMs, and then decodes the resulting hidden representation.The encoder reduces the dimensionality presented to the LSTM, addressing the large parameter requirements of sparse neighborhood inputs.
5. Experiments
The experiments evaluate dyngraph2vec on synthetic and real-world dynamic graphs using link prediction at the next time step. They compare the model with established static and dynamic embedding baselines using MAP and precision@k.
- Datasets: The evaluation uses one synthetic stochastic block model dataset and two real-world datasets to test dynamic graph embedding.The real-world datasets are Hep-th author collaboration and Autonomous Systems communication networks.
- Datasets: The synthetic SBM contains 1000 nodes in two communities, with one community diminished by migrating 10–20 nodes across 10 generated dynamic graphs.Cross-block connectivity is 0.01 and in-block connectivity is 0.1.
- Datasets: Hep-th is an author collaboration graph aggregated monthly from January 1993 to April 2003, evaluated on its last 50 snapshots with 2000 sampled nodes.The dataset represents collaboration among authors in High Energy Physics Theory.
- Datasets: Autonomous Systems is a monthly snapshot communication network derived from BGP logs, evaluated on its last 50 snapshots with 2000 sampled nodes.The dataset contains 733 instances spanning November 8, 1997, to January 2, 2000.
- Baselines: The comparison includes static SVD methods, incremental and rerun SVD, dynamicTriad, and dynGEM as state-of-the-art static and dynamic baselines.These methods differ in whether they model graph structure, perturbations, triadic closure, or incremental snapshot reconstruction.
- Evaluation: Link prediction at time t+1 uses all graphs through time t, with MAP and precision@k measuring prediction quality.precision@k evaluates the fraction of correct predictions among the top k, while MAP averages precision across nodes.
6. Results and Analysis
Across synthetic and real-world datasets, dyngraph2vec variants generally achieve strong link-prediction performance by modeling temporal graph dynamics, with performance depending on dataset and lookback. Longer training sequences help AS more than Hep-th.
- SBM Dataset: On the SBM dataset, dynGEM achieves the highest MAP values, while dyngraph2vec variants remain within ±1.5% of dynGEM.The synthetic change occurs only one time step earlier, matching dynGEM’s update mechanism.
- dyngraph2vec variants generally outperform static and dynamic state-of-the-art algorithms on the Hep-th and AS datasets.
- Hep-th Dataset: For Hep-th, dyngraph2vecAERNN, dyngraph2vecRNN, and dyngraph2vecAE obtain approximately 105%, 102%, and 42% higher average MAP than dynamicTriad.The reported lookback values are 8, 8, and 5, respectively.
- AS Dataset: For AS, dyngraph2vecAERNN, dyngraph2vecRNN, and dyngraph2vecAE obtain approximately 137%, 95%, and 74% higher average MAP than rerunSVD.The reported lookback values are 10, 10, and 5, respectively.
- Lookback Analysis: Increasing lookback generally raises average MAP, with dyngraph2vecAERNN reaching 0.739 at lookback 8 on Hep-th and 0.3801 at lookback 10 on AS.dyngraph2vecAE declines at lookback 10 on Hep-th, unlike the recurrent variants.
- Training Sequence Length: More training graph sequences produce little MAP increase for Hep-th RNN and AERNN, but AS improves gradually before converging after 80% of the sequence.For AS, convergence begins after a total of 40 graph sequences.
7. Discussion
The recurrent model variation achieves higher average MAP values by learning short- and long-term temporal patterns, but performance depends on dataset-specific tuning and resource limits constrain larger lookbacks.
- Model Variation: Recurrent variations achieve higher average MAP values than fully connected architectures without recurrent units.The paper attributes this advantage to learning short- and long-term temporal patterns and temporal graph evolution.
- Dataset: The same model architecture can perform differently across datasets because their temporal patterns may be periodic, semi-periodic, or stationary.The authors therefore tune models specifically to each dataset.
- Sampling: Model size increases with the number of nodes used during training, so the proposed algorithms use uniform node sampling to mitigate this weakness.The paper suggests graph-property-aware sampling as a possible improvement.
- Large Lookbacks: Lookback values greater than 10 repeatedly caused resource-exhaustion errors with the available hardware.
8. Future Work
Future work extends evaluation beyond the tested datasets and next-step link prediction, while addressing hyperparameter coverage and evolving community structure.
- Other Datasets: Further datasets beyond synthetic dynamic SBM, Hep-th, and AS remain to be tested.
- Hyper-parameters: Exhaustive evaluation across broader embedding-size and lookback-size ranges remains future work.
- Evaluation: Dynamic graph evaluation could extend beyond next-step link prediction to tasks such as node classification.
- Evolving communities: Inductive methods for communities that grow or shrink in node count or number remain an interesting future direction.
9. Conclusion
The paper introduces dyngraph2vec to capture temporal patterns in dynamic networks and predict future links. Its experiments show stronger link-prediction performance than state-of-the-art methods, while future work targets interpretability, hyperparameter optimization, and graph convolutions.
- dyngraph2vec captures temporal patterns in dynamic networks and produces embeddings for predicting future links.
- The model has three architectural variations with different capabilities for learning dynamic network behavior.
- Experiments on synthetic and real datasets show that dyngraph2vec outperforms state-of-the-art methods in link prediction.
- Future work includes interpretability, automatic hyperparameter optimization, and graph convolutions using node attributes.