通过随机丢弃消息加速大规模图的在线节点标注。
Fast online node labeling with graph subsampling
- 在图采样中随机丢弃消息，实现高效在线计算。
- 仅需 $O(1/ε^2)$ 条边即可保持谱特性近似，分类误差增加 $O(nε)$。
- 适合处理百万至万亿节点的大规模稀疏图，性能稳定。
大型数据应用依赖于存储在数百万至数万亿节点的稀疏图中。基于图的方法（如节点预测）需在图规模变化时仍保持计算效率。局部近似个性化页面排名（APPR）等技术可解决稀疏线性系统，其复杂度与图大小无关，但依赖最大节点度，而真实图中最大度远高于平均度。本文提出一种在线采样APPR方法，随机丢弃消息。利用图稀疏化工具和矩阵线性代数，给出图谱性质的近似边界（$O(1/ε^2)$条边），以及节点分类性能的额外开销（$O(nε)$）。
原文摘要 · Abstract (English)
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).
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。