Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2503.16755 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909676428328960 |
|---|---|
| author | Huang, Yushen Luo, Ertai Babenezhad, Reza Sun, Yifan |
| author_facet | Huang, Yushen Luo, Ertai Babenezhad, Reza Sun, Yifan |
| contents | 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 \emph{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). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_16755 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Fast online node labeling with graph subsampling Huang, Yushen Luo, Ertai Babenezhad, Reza Sun, Yifan Data Structures and Algorithms Machine Learning 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 \emph{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). |
| title | Fast online node labeling with graph subsampling |
| topic | Data Structures and Algorithms Machine Learning |
| url | https://arxiv.org/abs/2503.16755 |