通过连续空间游走，高效计算隐式图的随机特征。
SWING: Unlocking Implicit Graph Representations for Graph Random Features
- 在连续空间中进行游走，避免显式构建图结构。
- 结合重要性采样与线性化核函数，提升计算精度与效率。
- 适用于ε-邻近图等隐式图，适合加速器部署。
我们提出SWING：用于隐式网络图（i-graphs）的空闲游走算法，针对由节点特征向量定义边权重的图结构进行随机特征计算。这类图包括机器学习中常用的ε-邻近图。不同于传统基于节点的游走，SWING在嵌入图的连续空间中进行游走。为准确高效地逼近原始组合计算，SWING采用定制化的Gumbel-softmax采样机制，结合通过随机特征获得的线性化核函数与重要性采样技术。该方法建立在隐式图与傅里叶分析之间的深层联系之上。SWING具备加速器友好特性，无需显式构造输入图。论文提供了详细的理论分析，并在多种i-graph上进行了全面实验。
原文摘要 · Abstract (English)
We propose SWING: Space Walks for Implicit Network Graphs, a new class of algorithms for computations involving Graph Random Features on graphs given by implicit representations (i-graphs), where edge-weights are defined as bi-variate functions of feature vectors in the corresponding nodes. Those classes of graphs include several prominent examples, such as: $ε$-neighborhood graphs, used on regular basis in machine learning. Rather than conducting walks on graphs' nodes, those methods rely on walks in continuous spaces, in which those graphs are embedded. To accurately and efficiently approximate original combinatorial calculations, SWING applies customized Gumbel-softmax sampling mechanism with linearized kernels, obtained via random features coupled with importance sampling techniques. This algorithm is of its own interest. SWING relies on the deep connection between implicitly defined graphs and Fourier analysis, presented in this paper. SWING is accelerator-friendly and does not require input graph materialization. We provide detailed analysis of SWING and complement it with thorough experiments on different classes of i-graphs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。