首次实现稀疏图随机游走核的线性时间无偏近似，速度快27倍。
Optimal Time Complexity Algorithms for Computing General Random Walk Graph Kernels on Sparse Graphs
- 通过依赖随机游走采样，直接在嵌入空间计算核值。
- 在128倍更大图上运行，比暴力法快27倍，保持精度。
- 适合大规模图学习，尤其擅长标签图的高效建模。
我们提出首个针对稀疏图的通用随机游走核（RWKs）的线性时间随机算法，实现无偏近似，涵盖有标签与无标签情形。此前最快方法为三次方时间复杂度，且不适用于有标签图。我们的方法通过采样依赖随机游走，在ℝᵈ中生成新型图嵌入，其点积期望等于真实RWK，无需在内存中构建直接乘积图，可扩展至单机无法存储的大规模数据集。我们推导出指数集中界，证明估计器精度高，并表明对通用RWK的近似能力能解锁高效隐式图核学习。实验显示，本方法比现有高效方法快达27倍，可处理比暴力法最大可处理图大128倍的图。
原文摘要 · Abstract (English)
We present the first linear time complexity randomized algorithms for unbiased approximation of the celebrated family of general random walk kernels (RWKs) for sparse graphs. This includes both labelled and unlabelled instances. The previous fastest methods for general RWKs were of cubic time complexity and not applicable to labelled graphs. Our method samples dependent random walks to compute novel graph embeddings in $\mathbb{R}^d$ whose dot product is equal to the true RWK in expectation. It does so without instantiating the direct product graph in memory, meaning we can scale to massive datasets that cannot be stored on a single machine. We derive exponential concentration bounds to prove that our estimator is sharp, and show that the ability to approximate general RWKs (rather than just special cases) unlocks efficient implicit graph kernel learning. Our method is up to $\mathbf{27\times}$ faster than its counterparts for efficient computation on large graphs and scales to graphs $\mathbf{128 \times}$ bigger than largest examples amenable to brute-force computation.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。