# Fast Online Node Labeling for Very Large Graphs

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 78 references that are in the map.
- First posted on arXiv 25 May 2023.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Scaling Graph Neural Networks with Approximate PageRank](https://mlsanity.com/paper/2007.01570/) (2020)
- [p-Laplacian Based Graph Neural Networks](https://mlsanity.com/paper/2111.07337/) (2021)
- [BISTRO: An Efficient Relaxation-Based Method for Contextual Bandits](https://mlsanity.com/paper/1602.02196/) (2016)
- [Variational Perspective on Local Graph Clustering](https://mlsanity.com/paper/1602.01886/) (2016)
- [Differentially Private Graph Learning via Sensitivity-Bounded Personalized PageRank](https://mlsanity.com/paper/2207.06944/) (2022)
- [Approximate Personalized PageRank on Dynamic Graphs](https://mlsanity.com/paper/1603.07796/) (2016)
- [Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push](https://mlsanity.com/paper/2101.03652/) (2021)
- [Worst-case Complexity of Cyclic Coordinate Descent: O(n2) Gap with Randomized Version](https://mlsanity.com/paper/1604.07130/) (2016)
- [Online Similarity Prediction of Networked Data from Known and Unknown Graphs](https://mlsanity.com/paper/1302.7263/) (2013)
- [Hierarchies of Relaxations for Online Prediction Problems with Evolving Constraints](https://mlsanity.com/paper/1503.01212/) (2015)
- [A Tutorial on Online Supervised Learning with Applications to Node Classification in Social Networks](https://mlsanity.com/paper/1608.09014/) (2016)
- [See the Tree Through the Lines: The Shazoo Algorithm -- Full Version --](https://mlsanity.com/paper/1301.5160/) (2013)

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

- [Faster Local Solvers for Graph Diffusion Equations](https://mlsanity.com/paper/2410.21634/) (2024)
- [Fast online node labeling with graph subsampling](https://mlsanity.com/paper/2503.16755/) (2025)

## Abstract (arXiv)

This paper studies the online node classification problem under a transductive learning setting. Current methods either invert a graph kernel matrix with O(n3) runtime and O(n2) space complexity or sample a large volume of random spanning trees, thus are difficult to scale to large graphs. In this work, we propose an improvement based on the textitonline relaxation technique introduced by a series of works (Rakhlin et al.,2012; Rakhlin and Sridharan, 2015; 2017). We first prove an effective regret O(√n1+γ) when suitable parameterized graph kernels are chosen, then propose an approximate algorithm FastONL enjoying O(k√n1+γ) regret based on this relaxation. The key of FastONL is a textitgeneralized local push method that effectively approximates inverse matrix columns and applies to a series of popular kernels. Furthermore, the per-prediction cost is O(vol(S)log 1/ε) locally dependent on the graph with linear memory cost. Experiments show that our scalable method enjoys a better tradeoff between local and global consistency.