用随机小波特征加速图核计算，提升大规模图表示学习效率
Random Wavelet Features for Graph Kernel Machines
- 基于随机小波构造谱嵌入，通过点积近似图核的低秩形式
- 在谱局部化图核上比现有方法更精确，误差更低
- 适合需要高效、可扩展图表示的大规模网络分析任务
节点嵌入将图顶点映射到低维欧氏空间，同时保留结构信息，是节点分类、链接预测和信号重构等任务的核心。关键目标是设计使点积能捕捉图诱导节点相似性的嵌入。图核为定义此类相似性提供了严谨方法，但大规模网络上的直接计算往往不可行。受欧氏空间中核近似随机特征方法的启发，我们提出随机谱节点嵌入，其点积可估计任意特定图核的低秩近似。理论与实证结果表明，该方法在谱局部化图核上比现有方法更准确，验证了随机谱构造在可扩展且原则化图表示学习中的有效性。
原文摘要 · Abstract (English)
Node embeddings map graph vertices into low-dimensional Euclidean spaces while preserving structural information. They are central to tasks such as node classification, link prediction, and signal reconstruction. A key goal is to design node embeddings whose dot products capture meaningful notions of node similarity induced by the graph. Graph kernels offer a principled way to define such similarities, but their direct computation is often prohibitive for large networks. Inspired by random feature methods for kernel approximation in Euclidean spaces, we introduce randomized spectral node embeddings whose dot products estimate a low-rank approximation of any specific graph kernel. We provide theoretical and empirical results showing that our embeddings achieve more accurate kernel approximations than existing methods, particularly for spectrally localized kernels. These results demonstrate the effectiveness of randomized spectral constructions for scalable and principled graph representation learning.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。