# Fast and Robust Contextual Node Representation Learning over Dynamic Graphs

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 52 references that are in the map.
- First posted on arXiv 11 Nov 2024.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [Temporal Graph Networks for Deep Learning on Dynamic Graphs](https://mlsanity.com/paper/2006.10637/) (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)
- [Scaling Graph Neural Networks with Approximate PageRank](https://mlsanity.com/paper/2007.01570/) (2020)
- [How to Find Your Friendly Neighborhood: Graph Attention Design with Self-Supervision](https://mlsanity.com/paper/2204.04879/) (2022)
- [Variational Graph Recurrent Neural Networks](https://mlsanity.com/paper/1908.09710/) (2019)
- [Approximate Graph Propagation](https://mlsanity.com/paper/2106.03058/) (2021)
- [Instant Graph Neural Networks for Dynamic Graphs](https://mlsanity.com/paper/2206.01379/) (2022)
- [Variational Perspective on Local Graph Clustering](https://mlsanity.com/paper/1602.01886/) (2016)
- [Subset Node Anomaly Tracking over Large Dynamic Graphs](https://mlsanity.com/paper/2205.09786/) (2022)
- [Approximate Personalized PageRank on Dynamic Graphs](https://mlsanity.com/paper/1603.07796/) (2016)
- [InstantEmbedding: Efficient Local Node Representations](https://mlsanity.com/paper/2010.06992/) (2020)
- [Subset Node Representation Learning over Large Dynamic Graphs](https://mlsanity.com/paper/2106.01570/) (2021)
- [Hierarchies over Vector Space: Orienting Word and Graph Embeddings](https://mlsanity.com/paper/2211.01430/) (2022)
- [COMET: Convolutional Dimension Interaction for Collaborative Filtering](https://mlsanity.com/paper/2007.14129/) (2020)
- [Edge-based Local Push for Personalized PageRank](https://mlsanity.com/paper/2203.07937/) (2022)
- [Knowledge Authoring for Rules and Actions](https://mlsanity.com/paper/2305.07763/) (2023)
- [SubAnom: Efficient Subgraph Anomaly Detection Framework over Dynamic Graphs](https://mlsanity.com/paper/2312.10504/) (2023)
- [Faster Local Solvers for Graph Diffusion Equations](https://mlsanity.com/paper/2410.21634/) (2024)
- [Dual Averaging Method for Online Graph-structured Sparsity](https://mlsanity.com/paper/1905.10714/) (2019)
- [Knowledge Authoring with Factual English, Rules, and Actions](https://mlsanity.com/paper/2411.06253/) (2024)

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

- [Fast online node labeling with graph subsampling](https://mlsanity.com/paper/2503.16755/) (2025)

## Abstract (arXiv)

Real-world graphs grow rapidly with edge and vertex insertions over time, motivating the problem of efficiently maintaining robust node representation over evolving graphs. Recent efficient GNNs are designed to decouple recursive message passing from the learning process, and favor Personalized PageRank (PPR) as the underlying feature propagation mechanism. However, most PPR-based GNNs are designed for static graphs, and efficient PPR maintenance remains as an open problem. Further, there is surprisingly little theoretical justification for the choice of PPR, despite its impressive empirical performance. In this paper, we are inspired by the recent PPR formulation as an explicit ℓ1-regularized optimization problem and propose a unified dynamic graph learning framework based on sparse node-wise attention. We also present a set of desired properties to justify the choice of PPR in STOA GNNs, and serves as the guideline for future node attention designs. Meanwhile, we take advantage of the PPR-equivalent optimization formulation and employ the proximal gradient method (ISTA) to improve the efficiency of PPR-based GNNs upto 6 times. Finally, we instantiate a simple-yet-effective model (textscGoPPE) with robust positional encodings by maximizing PPR previously used as attention. The model performs comparably to or better than the STOA baselines and greatly outperforms when the initial node attributes are noisy during graph evolution, demonstrating the effectiveness and robustness of textscGoPPE.