PaperlayerView exact revision on arXiv

Source-linked AI summary

Towards Better Dynamic Graph Learning: New Architecture and Unified Library

Le Yu, Leilei Sun, Bowen Du, Weifeng Lv

arXiv:2303.13047v3cs.LG

TL;DR

Dynamic graph learning methods may miss node correlations and long-term temporal dependencies, and inconsistent training pipelines limit reproducibility. The paper introduces DyGFormer, which uses neighbor co-occurrence encoding and patch-based Transformer processing, alongside DyGLib, a unified evaluation library. Across dynamic link prediction and node classification, DyGFormer outperforms most existing methods, while baseline inconsistencies underscore the value of standardized pipelines.

  • Problem

    Existing methods often fail to capture node correlations or long-term temporal dependencies, while diverse training pipelines make results difficult to reproduce.

  • Method

    DyGFormer learns from historical first-hop interactions using neighbor co-occurrence encoding and patch-based Transformer processing, while DyGLib standardizes training and evaluation.

  • Results

    DyGFormer outperforms existing methods on most datasets for dynamic link prediction and performs better than most baselines in dynamic node classification.

  • Takeaways & Limitations

    DyGLib supports reproducible, scalable, and credible comparisons, and DyGFormer provides a strong approach for modeling node correlations and long-term temporal dependencies.

  • Takeaways & Limitations

    DyGFormer may be suboptimal when high-order node relationships are essential because it learns only from first-hop interactions.

Abstract

from arXiv · show

We propose DyGFormer, a new Transformer-based architecture for dynamic graph learning. DyGFormer is conceptually simple and only needs to learn from nodes' historical first-hop interactions by: (1) a neighbor co-occurrence encoding scheme that explores the correlations of the source node and destination node based on their historical sequences; (2) a patching technique that divides each sequence into multiple patches and feeds them to Transformer, allowing the model to effectively and efficiently benefit from longer histories. We also introduce DyGLib, a unified library with standard training pipelines, extensible coding interfaces, and comprehensive evaluating protocols to promote reproducible, scalable, and credible dynamic graph learning research. By performing exhaustive experiments on thirteen datasets for dynamic link prediction and dynamic node classification tasks, we find that DyGFormer achieves state-of-the-art performance on most of the datasets, demonstrating its effectiveness in capturing nodes' correlations and long-term temporal dependencies. Moreover, some results of baselines are inconsistent with previous reports, which may be caused by their diverse but less rigorous implementations, showing the importance of DyGLib. All the used resources are publicly available at https://github.com/yule-BUAA/DyGLib.

1 Introduction

Dynamic graph learning methods often miss correlations between interacting nodes and long-term temporal dependencies, while inconsistent implementations hinder reproducibility. The paper addresses these issues with DyGFormer and DyGLib, then evaluates them across dynamic graph tasks.

  • Existing methods often compute node representations independently, failing to exploit correlations that can indicate future interactions.
  • Long interaction histories force many methods to truncate sequences or rely on computationally constrained sequential processing.
  • DyGFormer combines neighbor co-occurrence encoding with sequence patching to model node correlations and long-term temporal dependencies.The model uses historical first-hop interactions and feeds multiple patches to a Transformer.
  • DyGLib provides standard training pipelines, extensible interfaces, and comprehensive evaluation for continuous-time dynamic graph learning.It supports dynamic link prediction and dynamic node classification across integrated methods and datasets.
  • Experiments show DyGFormer outperforms existing methods on most datasets, while baseline inconsistencies highlight the importance of standardized implementations.

2 Related Work

Prior work applies discrete-time or continuous-time approaches to dynamic graphs, while Transformers have been adapted broadly to sequential and patched inputs. Existing dynamic graph libraries remain limited in scope and applicability.

  • Dynamic Graph Learning: Discrete-time methods process manually constructed snapshots, whereas continuous-time methods learn directly from temporally ordered interactions.
  • Dynamic Graph Learning: Continuous-time dynamic graph methods use temporal graph neural networks, memory networks, temporal random walks, or sequential models.
  • Transformer-based Applications in Various Fields: Transformers use self-attention for sequential data and have been applied in natural language processing, computer vision, and time-series forecasting.
  • Transformer-based Applications in Various Fields: Prior patching methods divide images or time series into patches before Transformer processing; this work extends patching to dynamic graph sequences.
  • Graph Learning Library: Existing dynamic graph libraries focus on narrower settings, such as dynamic embeddings, discrete-time algorithms, or large-scale training techniques.

3 Preliminaries

A dynamic graph is modeled as chronologically ordered timestamped interactions between nodes, optionally carrying node and link features. Dynamic graph representation learning uses historical interactions to produce time-aware node representations for link prediction and node classification.

  • Dynamic Graph: A dynamic graph is a chronological sequence of timestamped interactions, with each interaction identifying source and destination nodes.
  • Dynamic Graph: Nodes may have feature vectors and interactions may have link-feature vectors; non-attributed graphs use zero vectors for these features.
  • Problem Formalization: Given nodes, a timestamp, and prior interactions, dynamic graph learning seeks time-aware representations for the nodes.
  • Problem Formalization: Dynamic link prediction estimates whether two nodes connect at a specified time, while dynamic node classification infers a node’s state at that time.

4 New Architecture and Unified Library

DyGFormer models dynamic interactions from first-hop histories using neighbor co-occurrence features, temporal encodings, patching, and a Transformer to capture correlations and long-term dependencies. DyGLib standardizes training, coding, and evaluation to support reproducible continuous-time dynamic graph learning.

  • DyGFormer architecture: A Transformer processes concatenated source and destination sequence representations to capture temporal dependencies within and across sequences, then averages outputs into time-aware node representations.The resulting representations support dynamic link prediction and dynamic node classification.
  • DyGFormer architecture: DyGFormer extracts source and destination nodes’ historical first-hop interaction sequences before the target timestamp.
  • DyGFormer architecture: The model encodes neighbors, links, and time intervals, including periodic temporal patterns from intervals between historical and target interactions.Time intervals are encoded with trainable sinusoidal functions.
  • DyGFormer architecture: Neighbor co-occurrence encoding represents neighbor appearance frequencies across both sequences to model correlations between the source and destination nodes.The frequency vectors are transformed into co-occurrence features and can be integrated into other dynamic graph learning methods.
  • DyGFormer architecture: Patching groups temporally adjacent interaction encodings into non-overlapping patches, preserving local temporal proximities while reducing the number of Transformer inputs for longer histories.Sequences that are not divisible by the patch size are padded; the patch size can increase with sequence length to keep patch counts approximately constant.
  • DyGLib unified library: DyGLib provides standardized training, extensible PyTorch interfaces, thirteen datasets, and evaluation protocols spanning transductive and inductive link prediction and node classification.Its protocols use random, historical, and inductive negative sampling to support more reliable comparisons.

5 Experiments

Experiments across thirteen datasets evaluate DyGFormer and baselines for dynamic link prediction and node classification using unified protocols. DyGFormer generally performs strongly, while analyses connect its behavior to neighbor correlations, longer histories, and evaluation choices.

  • Performance Comparisons and Discussions: DyGFormer usually outperforms baselines, with average ranks of 2.49/2.69 for transductive and 2.69/2.56 for inductive link prediction on AP/AUC-ROC.These averages span three negative sampling strategies.
  • Performance Comparisons and Discussions: DyGFormer achieves an average rank of 2.50 in dynamic node classification, outperforming most baselines.
  • Generalizability of Neighbor Co-occurrence Encoding Scheme: NCoE improves TCL and GraphMixer by average gains of 5.36% and 1.86%, respectively, across all datasets.TCL with NCoE can approach DyGFormer on datasets with shorter input sequences.
  • Advantages of Patching Technique: DyGFormer consistently gains from longer sequences, whereas most baselines degrade or incur expensive computation on longer histories.Memory-network methods handle longer histories affordably but do not benefit from them, while patching reduces DyGFormer’s training time and memory costs as sequence length increases.
  • Verification of the Motivation of Neighbor Co-occurrence Encoding Scheme: NCoE more often corrects wrong predictions when positive links have higher common-neighbor ratios than negative links; on Flights, it revises 83.66% and 83.83% of selected errors.The cited correction rates concern positive links in FN and negative links in FP, respectively.
  • When Will DyGFormer Be a Good Choice?: DyGFormer performs worse on US Legis. and UN Vote, where TP and TN common-neighbor ratios are less distinguishable or reversed and longer histories provide little benefit.The paper concludes that other methods may be preferable under these dataset characteristics.

6 Conclusion

The paper presents DyGFormer and DyGLib as complementary contributions to dynamic graph learning: a model for node correlations and long-term dependencies, and a toolkit for reproducible research.

  • DyGFormer uses neighbor co-occurrence encoding to exploit correlations between nodes in each interaction.
  • DyGFormer uses patching to help capture long-term temporal dependencies.
  • DyGLib provides standard training pipelines, extensible coding interfaces, and comprehensive evaluation protocols for continuous-time dynamic graph learning.
  • The paper aims to foster reproducible, scalable, and credible dynamic graph learning research.

A.1 Limitations

DyGFormer is limited by its reliance on first-hop interactions and sensitivity to negative sampling, while DyGLib provides a broader evaluation toolkit.

  • DyGFormer ignores high-order relationships because it learns solely from nodes’ first-hop interactions.
  • Modeling multi-hop neighbors directly could impose expensive computational costs.
  • The neighbor co-occurrence encoding scheme is sensitive to different negative sampling strategies.
  • Figure 3 depicts DyGLib’s standard training pipelines, extensible coding interfaces, and comprehensive evaluation protocols.

B.1 Descriptions of Datasets

The experiments use thirteen public dynamic-graph datasets and compare DyGFormer with eight baseline methods spanning recurrent, attention, memory, walk-based, and mixer architectures.

  • Datasets: The study uses thirteen publicly available datasets collected by prior work.
  • Datasets: The datasets cover interaction domains including Wikipedia edits, Reddit posts, corporate emails, mobile proximity, university messaging, and flights.
  • Datasets: Dataset statistics include node and link counts and feature dimensions, with the paper reporting its own Contact calculations.
  • Baselines: The comparison includes eight baselines: JODIE, DyRep, TGAT, TGN, CAWN, EdgeBank, TCL, and GraphMixer.
  • Implementation: DyGLib fixes model-saving issues for memory-based baselines by preserving their raw messages.

B.4 Some Inconsistent Observations with Previous Reports

The paper attributes inconsistencies with earlier baseline reports to hyperparameter choices, problematic implementations, and evaluation adaptations, using standardized experimental settings to compare methods.

  • Inconsistent observations: Baseline behavior differs from previous reports in some cases because of varied pipelines and problematic implementations.
  • Hyperparameters: Grid search over critical hyperparameters can significantly improve many baselines’ performance.
  • Implementations: Fixing implementation problems can worsen some reported results, as illustrated by CAWN’s transductive AP performance under random negative sampling.
  • Evaluation adaptations: GraphMixer results differ partly because its implementation was adapted for inductive evaluation by removing one-hot node encoding.
  • Experimental settings: DyGFormer handles shorter sequences directly and uses the most recent interactions when sequences exceed the defined length.

C.2 Additional Results for Inductive Dynamic Link Prediction

This section documents the evaluation configurations and supplementary analyses for inductive dynamic link prediction, including negative sampling, hyperparameters, and computational comparisons.

  • Inductive dynamic link prediction is evaluated with AP and AUC-ROC under three negative sampling strategies.
  • The supplementary materials report searched hyperparameter ranges and configurations for neighbor sampling, dropout, input sequences, and patch sizes.
  • Additional comparisons cover sampling configurations, EdgeBank variants, dynamic node classification, neighbor co-occurrence encoding, and patching-related training costs.

C.6 Results and Discussions of Ablation Study

The ablation study evaluates neighbor co-occurrence encoding, time encoding, sequence mixing, and separate neighbor-occurrence encoding in DyGFormer.

  • DyGFormer achieves optimal performance when all evaluated components are retained.
  • Removing Neighbor Co-occurrence Encoding, Time Encoding, or sequence mixing worsens results, while separately encoding neighbor occurrences forms another evaluated variant.
  • Neighbor co-occurrence encoding has the largest performance impact because it effectively captures correlations between nodes.
  • Time encoding and separate neighbor-occurrence encoding also improve performance, whereas mixing source and destination sequences yields relatively minor gains.

C.7 Results on Temporal Graph Benchmark

On the Temporal Graph Benchmark, DyGFormer shows strong link-prediction performance and scalability, while its node-property results motivate task-specific models.

  • Superiority of DyGFormer: DyGFormer ranks first on tgbl-wiki-v2, second or third on tgbl-coin-v2 and tgbl-comment, and performs moderately on tgbl-review-v2 for dynamic link property prediction.
  • Superiority of DyGFormer: Its neighbor co-occurrence encoding may suit datasets with repeated interactions but may be mismatched to datasets containing many new links.
  • Superiority of DyGFormer: For dynamic node property prediction, DyGFormer outperforms trainable methods but remains below Persistent Forecast and Moving Average.
  • Scalability of DyGFormer: DyGFormer scales to datasets with hundreds of thousands of nodes and tens of millions of links, while several baselines fail.
Loading 2303.13047v3…