改进图随机特征，让远距离节点关系建模更高效准确
Computationally-efficient Graph Modeling with Refined Graph Random Features
- 用拼接短路径替代长路径采样，实现并行计算
- 保持长路径逼近精度，计算效率显著提升
- 支持更灵活的路径终止策略，无额外开销
我们提出一种新型图随机特征（GRFs++），用于高效且精确地计算基于图节点的核函数。GRFs++ 解决了传统GRFs在建模远距离节点关系上的长期难题，通过创新的路径拼接技术，将多个短路径串联起来，无需依赖长随机游走的采样，同时保持无偏性。该方法将原本串行、低效的长路径采样，转化为可并行的短路径计算与矩阵-矩阵乘法，大幅提高效率。此外，GRFs++ 将简单的伯努利终止机制扩展为更广泛的路径长度分布策略，提升了图核的近似精度，且不增加计算成本。我们通过实证评估验证了所有主张，并提供了理论分析作为补充。
原文摘要 · Abstract (English)
We propose refined GRFs (GRFs++), a new class of Graph Random Features (GRFs) for efficient and accurate computations involving kernels defined on the nodes of a graph. GRFs++ resolve some of the long-standing limitations of regular GRFs, including difficulty modeling relationships between more distant nodes. They reduce dependence on sampling long graph random walks via a novel walk-stitching technique, concatenating several shorter walks without breaking unbiasedness. By applying these techniques, GRFs++ inherit the approximation quality provided by longer walks but with greater efficiency, trading sequential, inefficient sampling of a long walk for parallel computation of short walks and matrix-matrix multiplication. Furthermore, GRFs++ extend the simplistic GRFs walk termination mechanism (Bernoulli schemes with fixed halting probabilities) to a broader class of strategies, applying general distributions on the walks' lengths. This improves the approximation accuracy of graph kernels, without incurring extra computational cost. We provide empirical evaluations to showcase all our claims and complement our results with theoretical analysis.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。