用图随机特征加速图上高斯过程，百万节点也能跑
Graph Random Features for Scalable Gaussian Processes
- 用图随机特征近似图节点核函数，替代传统计算方式
- 时间复杂度从O(N³)降至O(N^{1.5})，实测提速显著
- 适合需要大规模图上贝叶斯优化的研究者
我们研究将图随机特征（GRFs）——一种近期提出的图节点核函数的随机估计器——应用于离散输入空间上的可扩展高斯过程。在温和假设下，我们证明使用GRFs进行贝叶斯推断的时间复杂度为O(N^{3/2})，相较精确核函数的O(N³)大幅降低。实际运行中实现显著的墙时加速与内存节省，使单芯片上处理超过10⁶个节点的图上贝叶斯优化成为可能，同时保持竞争性性能。
原文摘要 · Abstract (English)
We study the application of graph random features (GRFs) - a recently introduced stochastic estimator of graph node kernels - to scalable Gaussian processes on discrete input spaces. We prove that (under mild assumptions) Bayesian inference with GRFs enjoys $O(N^{3/2})$ time complexity with respect to the number of nodes $N$, compared to $O(N^3)$ for exact kernels. Substantial wall-clock speedups and memory savings unlock Bayesian optimisation on graphs with over $10^6$ nodes on a single computer chip, whilst preserving competitive performance.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。