# From random-walks to graph-sprints: a low-latency node embedding framework on continuous-time dynamic graphs

arXiv: https://arxiv.org/abs/2307.08433 · HTML: https://mlsanity.com/paper/2307.08433/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 38 references that are in the map.
- First posted on arXiv 17 Jul 2023.

## Builds on (most cited first, 26 of 26)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Efficient Estimation of Word Representations in Vector Space](https://mlsanity.com/paper/1301.3781/) (2013)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Optuna: A Next-generation Hyperparameter Optimization Framework](https://mlsanity.com/paper/1907.10902/) (2019)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [Temporal Graph Networks for Deep Learning on Dynamic Graphs](https://mlsanity.com/paper/2006.10637/) (2020)
- [Principal Neighbourhood Aggregation for Graph Nets](https://mlsanity.com/paper/2004.05718/) (2020)
- [Inductive Representation Learning on Temporal Graphs](https://mlsanity.com/paper/2002.07962/) (2020)
- [Predicting Dynamic Embedding Trajectory in Temporal Interaction Networks](https://mlsanity.com/paper/1908.01207/) (2019)
- [Inductive Representation Learning in Temporal Networks via Causal Anonymous Walks](https://mlsanity.com/paper/2101.05974/) (2021)
- [ROLAND: Graph Learning Framework for Dynamic Graphs](https://mlsanity.com/paper/2208.07239/) (2022)
- [DynGEM: Deep Embedding Method for Dynamic Graphs](https://mlsanity.com/paper/1805.11273/) (2018)
- [APAN: Asynchronous Propagation Attention Network for Real-time Temporal Graph Embedding](https://mlsanity.com/paper/2011.11545/) (2020)
- [A Review on Graph Neural Network Methods in Financial Applications](https://mlsanity.com/paper/2111.15367/) (2021)
- [Provably expressive temporal graph networks](https://mlsanity.com/paper/2209.15059/) (2022)
- [Deep Coevolutionary Network: Embedding User and Item Features for Recommendation](https://mlsanity.com/paper/1609.03675/) (2016)
- [Hashing-Accelerated Graph Neural Networks for Link Prediction](https://mlsanity.com/paper/2105.14280/) (2021)
- [Efficient Representation Learning Using Random Walks for Dynamic Graphs](https://mlsanity.com/paper/1901.01346/) (2019)
- [node2bits: Compact Time- and Attribute-aware Node Representations for User Stitching](https://mlsanity.com/paper/1904.08572/) (2019)
- [Continuous Temporal Graph Networks for Event-Based Graph Data](https://mlsanity.com/paper/2205.15924/) (2022)
- [From Static to Dynamic Node Embeddings](https://mlsanity.com/paper/2009.10017/) (2020)

## Built on by (most cited first, 1 of 1)

- [Deep-Graph-Sprints: Accelerated Representation Learning in Continuous-Time Dynamic Graphs](https://mlsanity.com/paper/2407.07712/) (2024)

## Abstract (arXiv)

Many real-world datasets have an underlying dynamic graph structure, where entities and their interactions evolve over time. Machine learning models should consider these dynamics in order to harness their full potential in downstream tasks. Previous approaches for graph representation learning have focused on either sampling k-hop neighborhoods, akin to breadth-first search, or random walks, akin to depth-first search. However, these methods are computationally expensive and unsuitable for real-time, low-latency inference on dynamic graphs. To overcome these limitations, we propose graph-sprints a general purpose feature extraction framework for continuous-time-dynamic-graphs (CTDGs) that has low latency and is competitive with state-of-the-art, higher latency models. To achieve this, a streaming, low latency approximation to the random-walk based features is proposed. In our framework, time-aware node embeddings summarizing multi-hop information are computed using only single-hop operations on the incoming edges. We evaluate our proposed approach on three open-source datasets and two in-house datasets, and compare with three state-of-the-art algorithms (TGN-attn, TGN-ID, Jodie). We demonstrate that our graph-sprints features, combined with a machine learning classifier, achieve competitive performance (outperforming all baselines for the node classification tasks in five datasets). Simultaneously, graph-sprints significantly reduce inference latencies, achieving close to an order of magnitude speed-up in our experimental setting.