提出可计算的图稀疏化误差估计，提升下游任务可靠性
Empirical Error Estimates for Graph Sparsification
- 基于数据驱动方法，直接估算稀疏化带来的误差
- 在四种任务中验证误差估计有效且稳定
- 计算成本低，适合实际图学习流程使用
图稀疏化是加速图学习算法的常用技术，通过边采样将稠密图近似为稀疏图。由于稀疏化误差具有随机性且未知，用户难以判断下游计算的可靠性。尽管文献中有理论误差界可供参考，但通常在数值上不实用。本文提出一种数据驱动的思路，直接计算经验误差估计，以应对这一问题。所提估计方法高度通用，在四类应用场景中得到验证：拉普拉斯矩阵近似、图割查询、图结构回归和谱聚类。此外，本文还提供了两个理论保证，并说明其计算开销远小于典型稀疏化工作流的总成本，具备实用性。
原文摘要 · Abstract (English)
Graph sparsification is a well-established technique for accelerating graph-based learning algorithms, which uses edge sampling to approximate dense graphs with sparse ones. Because the sparsification error is random and unknown, users must contend with uncertainty about the reliability of downstream computations. Although it is possible for users to obtain conceptual guidance from theoretical error bounds in the literature, such results are typically impractical at a numerical level. Taking an alternative approach, we propose to address these issues from a data-driven perspective by computing empirical error estimates. The proposed error estimates are highly versatile, and we demonstrate this in four use cases: Laplacian matrix approximation, graph cut queries, graph-structured regression, and spectral clustering. Moreover, we provide two theoretical guarantees for the error estimates, and explain why the cost of computing them is manageable in comparison to the overall cost of a typical graph sparsification workflow.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。