# Fast online node labeling with graph subsampling

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 32 references that are in the map.
- First posted on arXiv 21 Mar 2025.

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

- [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)
- [Scaling Graph Neural Networks with Approximate PageRank](https://mlsanity.com/paper/2007.01570/) (2020)
- [Graph Meta Learning via Local Subgraphs](https://mlsanity.com/paper/2006.07889/) (2020)
- [Learning Graph Representations with Embedding Propagation](https://mlsanity.com/paper/1710.03059/) (2017)
- [Optimizing Generalized PageRank Methods for Seed-Expansion Community Detection](https://mlsanity.com/paper/1905.10881/) (2019)
- [Variational Perspective on Local Graph Clustering](https://mlsanity.com/paper/1602.01886/) (2016)
- [Fast Online Node Labeling for Very Large Graphs](https://mlsanity.com/paper/2305.16257/) (2023)
- [Multi-class Graph Clustering via Approximated Effective p-Resistance](https://mlsanity.com/paper/2306.08617/) (2023)
- [Fast and Robust Contextual Node Representation Learning over Dynamic Graphs](https://mlsanity.com/paper/2411.07123/) (2024)

## Abstract (arXiv)

Large data applications rely on storing data in massive, sparse graphs with millions to trillions of nodes. Graph-based methods, such as node prediction, aim for computational efficiency regardless of graph size. Techniques like localized approximate personalized page rank (APPR) solve sparse linear systems with complexity independent of graph size, but is in terms of the maximum node degree, which can be much larger in practice than the average node degree for real-world large graphs. In this paper, we consider an online subsampled APPR method, where messages are intentionally dropped at random. We use tools from graph sparsifiers and matrix linear algebra to give approximation bounds on the graph's spectral properties (O(1/ε2) edges), and node classification performance (added O(nε) overhead).