Fast online node labeling with graph subsampling
Not on the map. Why?
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).
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
10 of 32 references.
References · 10
- 2016node2vec: Scalable Feature Learning for Networkscited by 1,918
- 2014DeepWalk: Online Learning of Social Representationscited by 1,547
- 2020Scaling Graph Neural Networks with Approximate PageRankcited by 174
- 2020Graph Meta Learning via Local Subgraphscited by 89
- 2017Learning Graph Representations with Embedding Propagationcited by 38
- 2019Optimizing Generalized PageRank Methods for Seed-Expansion Community Detectioncited by 35
- 2016Variational Perspective on Local Graph Clusteringcited by 14
- 2023Fast Online Node Labeling for Very Large Graphscited by 2
- 2023Multi-class Graph Clustering via Approximated Effective p-Resistancecited by 2
- 2024Fast and Robust Contextual Node Representation Learning over Dynamic Graphscited by 1
Built on by
Not cited yet.