Towards Real-Time Temporal Graph Learning

Deniz Gurevin, Mohsin Shan, Tong Geng, Weiwen Jiang, Caiwen Ding, Omer Khan

Abstract

Temporal Graph Learning (TGL) is essential for modeling dynamic systems such as social networks and financial transactions. However, existing methods often rely on offline processing, which is unsuitable for real-time applications. This paper introduces an end-to-end pipeline designed for online temporal graph learning. By integrating R-Tree-based graph construction with a highly optimized, fine-grained parallelization strategy for Feed-forward Neural Network (FNN) training, we address the significant computational bottlenecks inherent in dynamic embedding updates. Our approach achieves up to a 13.5x speedup in training time compared to standard baselines while maintaining competitive accuracy across diverse temporal datasets.

1. Introduction

Graph Representation Learning (GRL) has revolutionized the way we analyze complex relational data by mapping nodes and edges into low-dimensional vector spaces. While static GRL has matured, real-world graphs are inherently dynamic—constantly evolving as new interactions occur. Traditional "offline" models require the entire graph history to be available upfront, leading to significant latency and making them impractical for real-time scenarios like fraud detection or live recommendation engines.

This research identifies a critical, often overlooked bottleneck in the temporal graph learning pipeline: the training of the Feed-forward Neural Network (FNN) that follows embedding generation. We propose an online learning framework that processes data in sequential snapshots, optimizing both the graph update mechanism and the underlying matrix operations of the neural network.

2. Problem Statement: The Training Bottleneck

Existing GRL research frequently focuses on accelerating graph traversals or embedding generation. However, in a real-time streaming context, the subsequent step—training an FNN on these embeddings—becomes the primary computational hurdle. Standard deep learning libraries are often optimized for large, square matrices. In contrast, GRL kernels typically involve "skinny" or low-dimensional matrices. This mismatch leads to sub-optimal hardware utilization and increased training times when processing high-frequency temporal updates.

3. Methodology

The proposed pipeline consists of three primary stages designed for an online setting:

3.1 Efficient Graph Construction via R-Trees

To avoid the prohibitive cost of rebuilding the graph from scratch for every update, we employ an R-Tree-based construction method. By clustering nodes into Minimum Bounding Rectangles (MBRs), the system can isolate and update only the specific regions of the tree affected by new interactions. This spatial indexing approach significantly reduces the overhead associated with maintaining a dynamic graph structure.

3.2 Temporal Embedding Generation (EvoNRL)

We utilize temporal random walks to capture the time-dependent relationships within the graph. To maintain real-time performance, we implement an incremental update strategy: only nodes affected by recent changes undergo new simulations. These walks are then processed through a Word2Vec-based model to generate updated embeddings.

3.3 Fine-Grained Parallelization of FNN Training

The core technical contribution lies in the optimization of the FNN training phase. We implemented and evaluated four distinct matrix multiplication (MM) strategies:

  • Inner Product: The standard approach in most libraries.
  • Outer Product: Useful for certain weight update patterns.
  • Row-wise and Column-wise Products: These strategies offer superior data locality and reduced redundant memory reads for the specific "skinny" matrix shapes found in GRL.

Our findings indicate that the optimal strategy is highly dependent on the layer dimensions and batch sizes, necessitating a more granular approach to parallelization than provided by general-purpose frameworks.

4. Experimental Evaluation

The pipeline was evaluated using four real-world temporal datasets: ia-email, wiki-talk, and stackoverflow for link prediction, and a brain connectivity dataset for node classification.

4.1 Performance and Speedups

The fine-grained parallelization strategy yielded significant performance gains:

  • 2-Layer FNNs: Achieved a 2.5x speedup.
  • 3-Layer FNNs: Achieved a 6.6x speedup.
  • Peak Performance: On the brain dataset, the system reached a 13.5x speedup using 40 threads compared to single-threaded execution.

4.2 Accuracy and Batch Size Trade-offs

The online training approach maintained high predictive accuracy, reaching 86.31% on the stackoverflow dataset. A critical insight from our experiments is the "Batch Size Paradox." While larger batches improve hardware throughput and speed, they can "smear" temporal data, causing the model to lose sensitivity to fine-grained timing. We identified a batch size of 1024 as the optimal balance for link prediction tasks.

5. Conclusion and Future Work

This work demonstrates that real-time temporal graph learning is achievable by addressing the specific computational characteristics of GRL kernels. By optimizing the FNN training bottleneck and utilizing efficient graph indexing, we provide a path toward truly online graph analytics. Future research will focus on extending these parallelization techniques to sparse-sparse matrix multiplications (SpGEMM) and exploring adaptive neural architectures that evolve alongside the graph.

Summary updated

BibTeX
@inproceedings{gurevin2022towards,
  author = {Deniz Gurevin and Mohsin Shan and Tong Geng and Weiwen Jiang and Caiwen Ding and Omer Khan},
  title = {{Towards Real-Time Temporal Graph Learning}},
  booktitle = {ICCD},
  year = {2022},
  doi = {10.1109/iccd56317.2022.00047},
}
Figure