PaperlayerView exact revision on arXiv

Source-linked AI summary

ROLAND: Graph Learning Framework for Dynamic Graphs

Jiaxuan You, Tianyu Du, Jure Leskovec

arXiv:2208.07239v1cs.LGcs.AIcs.SI

TL;DR

Dynamic GNNs lack effective transfer of static-GNN designs, realistic evolving-data evaluation, and scalable training. ROLAND adapts static GNNs through recurrent hierarchical states, live-update evaluation, and incremental/meta-learning training, improving MRR while scaling to large dynamic graphs.

  • Problem

    Dynamic GNN research is limited by model designs that do not incorporate successful static-GNN architectures, evaluation settings that miss evolving data, and training methods that do not scale.

  • Method

    ROLAND repurposes static GNNs by recurrently updating layer-wise hierarchical node states and combines live-update evaluation with incremental training and meta-learning.

  • Results

    ROLAND achieves a 62.7% average MRR improvement over state-of-the-art baselines under standard evaluation and scales to dynamic graphs with 56 million edges.

  • Takeaways & Limitations

    ROLAND provides a framework for building, training, and evaluating dynamic GNNs while retaining effective static-GNN designs and supporting large datasets.

  • Takeaways & Limitations

    The BSI-ZK dataset uses only 100 sampled negative edges because of memory constraints.

Abstract

from arXiv · show

Graph Neural Networks (GNNs) have been successfully applied to many real-world static graphs. However, the success of static graphs has not fully translated to dynamic graphs due to the limitations in model design, evaluation settings, and training strategies. Concretely, existing dynamic GNNs do not incorporate state-of-the-art designs from static GNNs, which limits their performance. Current evaluation settings for dynamic GNNs do not fully reflect the evolving nature of dynamic graphs. Finally, commonly used training methods for dynamic GNNs are not scalable. Here we propose ROLAND, an effective graph representation learning framework for real-world dynamic graphs. At its core, the ROLAND framework can help researchers easily repurpose any static GNN to dynamic graphs. Our insight is to view the node embeddings at different GNN layers as hierarchical node states and then recurrently update them over time. We then introduce a live-update evaluation setting for dynamic graphs that mimics real-world use cases, where GNNs are making predictions and being updated on a rolling basis. Finally, we propose a scalable and efficient training approach for dynamic GNNs via incremental training and meta-learning. We conduct experiments over eight different dynamic graph datasets on future link prediction tasks. Models built using the ROLAND framework achieve on average 62.7% relative mean reciprocal rank (MRR) improvement over state-of-the-art baselines under the standard evaluation settings on three datasets. We find state-of-the-art baselines experience out-of-memory errors for larger datasets, while ROLAND can easily scale to dynamic graphs with 56 million edges. After re-implementing these baselines using the ROLAND training strategy, ROLAND models still achieve on average 15.5% relative MRR improvement over the baselines.

1 INTRODUCTION AND RELATED WORK

Dynamic GNNs face gaps in model design, evaluation, and scalability. ROLAND addresses these gaps by adapting static GNNs, introducing live-update evaluation, and proposing scalable training strategies.

  • Motivation: Dynamic GNNs have limitations in model design, evaluation settings, and training strategies that matter for real-world applications.Existing approaches do not fully transfer successful static GNN architectures, reflect evolving data, or scale to large graphs.
  • Model design: ROLAND repurposes static GNNs for dynamic graphs by treating layer-wise node embeddings as hierarchical states updated over time.The framework is designed to preserve effective static-GNN architectural choices while extending them to dynamic settings.
  • Results: 62.7% average performance gain over the best baseline was achieved on three datasets under the existing standard evaluation setting.The experiments cover eight dynamic graph datasets with up to 56 million edges and 733 graph snapshots.
  • Training: ROLAND scales to dynamic graphs with 56 million edges, at least 13 times larger than existing benchmarks, while supporting fast adaptation through meta-learning.The framework treats predictions in different periods as sequential tasks and learns a meta-model for future tasks.
  • Evaluation: ROLAND’s live-update evaluation uses predictions and model updates on a rolling basis to better reflect evolving data and model behavior.This contrasts with common deterministic dataset splits.

2 PRELIMINARIES

Dynamic graphs are represented as sequences of timestamped static snapshots. GNNs iteratively aggregate neighborhood messages to produce node embeddings, while ROLAND extends this structure with time-varying hierarchical states.

  • Dynamic graphs: A dynamic graph is represented as a sequence of graph snapshots, each containing timestamp-matched nodes and edges.Snapshot-based modeling allows different snapshots to contain different node sets, supporting node addition and deletion.
  • Graph representation: A static graph is represented by nodes, edges, optional node features, and optional edge features.Dynamic graphs additionally associate timestamps with nodes and edges.
  • ROLAND: ROLAND extends static GNNs by treating layer-wise embeddings as hierarchical node states that can be updated over time.Its design inserts embedding-update modules into static GNN architectures for dynamic graphs.
  • Graph Neural Networks: A GNN learns node embeddings by iteratively aggregating messages from each node’s local neighborhood across multiple layers.Message-passing and aggregation functions can vary across GNN architectures.

3 PROPOSED ROLAND FRAMEWORK

ROLAND generalizes static GNNs to dynamic graphs by maintaining hierarchical node states and updating them over time. It combines live-update evaluation with incremental and meta-training strategies for evolving graph data.

  • From Static GNNs to Dynamic GNNs: ROLAND repurposes static GNN architectures for dynamic graphs by treating embeddings from all GNN layers as hierarchical node states.Each layer captures neighborhood information at a different hop distance, and the full hierarchy is maintained over time.
  • From Static GNNs to Dynamic GNNs: The hierarchical update module preserves and dynamically updates node states at every level instead of recomputing embeddings from each new snapshot alone.The update module can be inserted into any static GNN.
  • From Static GNNs to Dynamic GNNs: ROLAND incorporates edge features, bidirectional message passing, selectable aggregation functions, and skip-connections into its dynamic GNN architecture.The explored aggregation functions are summation, maximum, and average; the paper reports that these designs improve performance.
  • Live-update Evaluation: ROLAND’s live-update evaluation fine-tunes on newly observed labels, evaluates predictions on new data, and uses historical states with the current snapshot.The procedure is designed to avoid future-information leakage while reflecting evolving data distributions.
  • Training Strategies: Incremental training keeps only the model, incoming snapshot, and historical node states in GPU memory, enabling training on graphs with 56 million edges and 733 snapshots.The approach borrows truncated back-propagation-through-time and avoids retaining the entire historical graph in GPU memory.
  • Training Strategies: ROLAND formulates predictions in different periods as sequential tasks and uses a meta-model initialization to adapt quickly to future unseen tasks.The framework follows the Reptile algorithm for meta-learning updates.

4 EXPERIMENTS

Experiments evaluate ROLAND on eight dynamic-graph datasets using future link prediction, standard fixed-split comparisons, live-update training, and ablations of architecture, meta-learning, and retraining.

  • 4.2 Results in the Standard Evaluation Settings: 62.69% average performance gain is achieved by ROLAND with a GRU update-module over baselines under the standard fixed-split setting.The comparison follows EvolveGCN’s snapshot frequency, test snapshots, and MRR computation for fairness.
  • 4.3 Results in the Live-update Settings: BPTT fails to scale to large datasets and models, whereas all re-implemented baselines train successfully with ROLAND incremental training.BPTT stores historical node embeddings in GPU memory; even when it works on smaller datasets, its best model underperforms ROLAND-trained baselines by almost 10%.
  • 4.3 Results in the Live-update Settings: 15.48% average performance improvement is achieved by ROLAND with a GRU update-module over the best baseline when both use ROLAND training.Except on AS-733, ROLAND consistently outperforms the re-implemented baselines, with gains ranging from 2.40% on BSI-ZK to 44.22% on Reddit-Body.
  • 4.4 Ablation Study: Batch normalization, skip-connections, and max aggregation are desirable architectural choices, with skip-connections producing more than 20% performance gain.The architectural ablation is conducted on BSI-SVT under the live-update setting and reports MRR distributions across design options.
  • 4.4 Ablation Study: Meta-learning provides dataset- and update-design-dependent MRR gains, while periodic retraining adapts to changing transaction patterns and outperforms stopping after the first 25% of snapshots.Meta-learning uses α values from 0.1 to 1.0, where α=1 is the non-meta-learning baseline; retraining generally requires only a few epochs per update.

5 ADDITIONAL RELATED WORK

Related work contrasts ROLAND with recurrent dynamic GNNs and other dynamic-graph methods, while Table 4 characterizes meta-learning gains.

  • Dynamic GNNs: Existing recurrent dynamic GNNs either replace feature encoders with GNNs or replace recurrent-cell linear layers with GNN layers.The first approach ignores lower-level node-embedding evolution, while the second has undesirable performance when snapshot counts are large.
  • Effectiveness of meta-learning: Table 4 defines meta-learning gain as the MRR improvement from the best meta-learning setting over the non-meta-learning setting, with results averaged over three seeds except for BSI-ZK.The study varies α across update methods and datasets to assess performance effects.
  • Dynamic GNNs: Few prior dynamic GNNs explore static-graph designs such as edge features, batch normalization, and skip-connections.ROLAND addresses this design gap by incorporating mature static GNN designs into dynamic graph learning.
  • Other learning methods for dynamic graphs: Researchers also study matrix factorization, random-walk, and point-process methods for dynamic graphs, but this paper focuses on GNNs because of their performance and inductive learning capabilities.The related-work comparison therefore spans multiple methodological families while retaining a GNN-based scope.

6 CONCLUSION

ROLAND is a system for building, training, and evaluating dynamic GNNs that repurposes static GNNs and supports live model updates. Experiments show that ROLAND-based dynamic GNNs scale to large datasets and outperform existing state-of-the-art models.

  • ROLAND helps researchers repurpose any static GNN for dynamic graphs while retaining effective static-GNN designs.
  • Its live-update pipeline dynamically updates models during evaluation to mimic real-world usage.
  • ROLAND-based dynamic GNNs successfully scale to large datasets and outperform existing state-of-the-art models.
Loading 2208.07239v1…