用准蒙特卡洛方法降低图核估计方差，尤其在梯形图上效果显著。
Heating Up Quasi-Monte Carlo Graph Random Features: A Diffusion Kernel Perspective
- 基于扩散核视角改进图随机特征，提升估计精度。
- 在梯形图上验证了更低方差，但节数影响性能表现。
- 适合做图学习与核方法研究的学者参考。
我们基于近期提出的准图随机特征（q-GRFs），研究其在扩散（或热）核、Matérn核和反余弦核上的适用性。发现扩散核与2-正则化拉普拉斯核表现最相近。进一步探索了埃多斯-雷尼、巴尔巴西-阿尔伯特随机图、二叉树及梯形图等图结构，旨在识别哪些组合能从反向终止技术中获益。结果表明，q-GRFs在梯形图上可实现扩散核的低方差估计，但梯形图的节数会影响算法表现；相关理论支持正在完善。本工作拓展了最早期针对组合对象定义核的准蒙特卡洛方法，为基于核的学习算法及未来实际应用奠定基础。
原文摘要 · Abstract (English)
We build upon a recently introduced class of quasi-graph random features (q-GRFs), which have demonstrated the ability to yield lower variance estimators of the 2-regularized Laplacian kernel (Choromanski 2023). Our research investigates whether similar results can be achieved with alternative kernel functions, specifically the Diffusion (or Heat), Matérn, and Inverse Cosine kernels. We find that the Diffusion kernel performs most similarly to the 2-regularized Laplacian, and we further explore graph types that benefit from the previously established antithetic termination procedure. Specifically, we explore Erdős-Rényi and Barabási-Albert random graph models, Binary Trees, and Ladder graphs, with the goal of identifying combinations of specific kernel and graph type that benefit from antithetic termination. We assert that q-GRFs achieve lower variance estimators of the Diffusion (or Heat) kernel on Ladder graphs. However, the number of rungs on the Ladder graphs impacts the algorithm's performance; further theoretical results supporting our experimentation are forthcoming. This work builds upon some of the earliest Quasi-Monte Carlo methods for kernels defined on combinatorial objects, paving the way for kernel-based learning algorithms and future real-world applications in various domains.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。