提出新算法在流式分布式场景下高效稀疏化图拉普拉斯矩阵
Improved large-scale graph learning through ridge spectral sparsification
- 基于有效电阻维护小规模子集实现图拉普拉斯稀疏化
- 单次遍历完成处理，保持强谱逼近精度
- 适合大规模实时图学习场景，尤其分布式系统
基于图的技术和谱图理论为机器学习带来了诸多重要进展。分析中的核心对象是图拉普拉斯矩阵L，它编码了图的结构。本文研究在分布式流式设置下对拉普拉斯矩阵进行学习的问题，即网络中多个工作节点实时观测图的新边。在此场景下，快速或近似地学习并保持L的分布式表示极具挑战。为此，我们提出一种新算法GSQUEAK，通过维护一小部分有效电阻，高效稀疏化拉普拉斯矩阵。我们证明该算法能生成具有强谱逼近保证的稀疏近似矩阵，同时以单次遍历方式在分布式环境中处理边数据。
原文摘要 · Abstract (English)
Graph-based techniques and spectral graph theory have enriched the field of machine learning with a variety of critical advances. A central object in the analysis is the graph Laplacian L, which encodes the structure of the graph. We consider the problem of learning over this Laplacian in a distributed streaming setting, where new edges of the graph are observed in real time by a network of workers. In this setting, it is hard to learn quickly or approximately while keeping a distributed representation of L. To address this challenge, we present a novel algorithm, GSQUEAK, which efficiently sparsifies the Laplacian by maintaining a small subset of effective resistances. We show that our algorithm produces sparsifiers with strong spectral approximation guarantees, all while processing edges in a single pass and in a distributed fashion.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。