SWING: Unlocking Implicit Graph Representations for Graph Random Features

📄 arXiv: 2602.12703v1 📥 PDF

作者: Alessandro Manenti, Avinava Dubey, Arijit Sehanobish, Cesare Alippi, Krzysztof Choromanski

分类: cs.LG

发布日期: 2026-02-13

💡 一句话要点

SWING：解锁隐式图表示的图随机特征计算方法

🎯 匹配领域: 支柱三：空间感知与语义 (Perception & Semantics)

关键词: 图神经网络 随机特征 隐式图 空间游走 Gumbel-softmax 重要性采样 傅里叶分析

📋 核心要点

  1. 现有图神经网络方法在处理大规模图时面临挑战，尤其是在图结构隐式定义的情况下，需要显式地构建图结构。
  2. SWING通过在连续空间中进行游走，避免了显式图结构的构建，并利用Gumbel-softmax采样和随机特征来近似图上的计算。
  3. SWING算法在不同类型的隐式图上进行了实验验证，展示了其在近似图计算方面的有效性和效率。

📝 摘要（中文）

我们提出了SWING：隐式网络图的空间游走算法，这是一类新的算法，用于在由隐式表示（i-graphs）给出的图上进行涉及图随机特征的计算，其中边权重被定义为相应节点中特征向量的双变量函数。这些图的类别包括几个突出的例子，例如：机器学习中经常使用的$ε$-邻域图。这些方法不是在图的节点上进行游走，而是依赖于在嵌入这些图的连续空间中进行游走。为了准确有效地近似原始组合计算，SWING应用了定制的Gumbel-softmax采样机制，该机制具有通过随机特征和重要性采样技术获得的线性化核。该算法本身就很有意义。SWING依赖于本文提出的隐式定义图和傅里叶分析之间的深刻联系。SWING对加速器友好，不需要输入图的物化。我们提供了SWING的详细分析，并用对不同类别的i-graph的全面实验对其进行补充。

🔬 方法详解

问题定义：论文旨在解决隐式图上的图随机特征计算问题。传统的图神经网络方法需要显式地构建图结构，这在大规模图或者图结构隐式定义的情况下变得非常困难和耗时。现有方法在处理这类问题时，计算复杂度高，难以扩展到大规模图。

核心思路：SWING的核心思路是避免显式地构建图结构，而是在图嵌入的连续空间中进行游走。通过将图上的计算转化为连续空间中的积分，并利用随机特征和重要性采样来近似计算，从而降低计算复杂度。

技术框架：SWING算法主要包含以下几个阶段：1）将图嵌入到连续空间中；2）定义连续空间中的游走策略；3）利用Gumbel-softmax采样机制生成游走路径；4）使用随机特征和重要性采样来近似图上的计算。整个框架无需显式地构建图结构，可以直接在连续空间中进行计算。

关键创新：SWING的关键创新在于它将图上的计算问题转化为了连续空间中的积分问题，并利用随机特征和重要性采样来近似计算。这种方法避免了显式地构建图结构，从而降低了计算复杂度，并且可以处理隐式定义的图结构。此外，定制的Gumbel-softmax采样机制也是一个重要的创新点，它能够有效地生成游走路径。

关键设计：SWING的关键设计包括：1）使用随机特征来近似图核函数，从而降低计算复杂度；2）使用重要性采样来提高采样的效率；3）定制的Gumbel-softmax采样机制，用于生成游走路径。此外，论文还详细分析了算法的收敛性和复杂度，并给出了参数设置的建议。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

论文通过在不同类型的隐式图上进行实验，验证了SWING算法的有效性。实验结果表明，SWING算法能够在保证计算精度的前提下，显著降低计算复杂度，并且在某些情况下，性能优于传统的图神经网络方法。具体的性能数据和对比基线在论文中进行了详细的展示。

🎯 应用场景

SWING算法可应用于各种需要处理大规模图数据的场景，例如社交网络分析、推荐系统、分子性质预测等。尤其是在图结构隐式定义的情况下，SWING算法能够有效地进行图计算，具有重要的实际应用价值和潜力。未来，该算法可以进一步扩展到处理动态图和异构图等更复杂的情况。

📄 摘要（原文）

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.