🤖 machine learning

Computationally-efficient Graph Modeling with Refined Graph Random Features

本文介绍了 GRFs++，这是一类改进的图随机特征（Graph Random Features），它通过利用一种用于并行化短路径行走的新型缝合技术（walk-stitching technique），并将路径长度终止策略扩展到固定伯努利方案之外，从而提升了图核（graph kernels）的计算效率和近似精度。

原作者： Krzysztof Choromanski, Avinava Dubey, Arijit Sehanobish, Isaac Reid

发布于 2026-06-26

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Krzysztof Choromanski, Avinava Dubey, Arijit Sehanobish, Isaac Reid

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你拥有一张巨大的、复杂的城市地图（一个图/Graph），其中每个交叉口都是一个“节点”，每条街道都是一条连接。在机器学习中，我们经常需要根据连接程度来判断两个交叉口之间的相似度。它们是邻居吗？是通过短路径连接的吗？还是处于城市的另一端，只能通过一条漫长且曲折的路线相连？

计算每一对交叉点的这种“相似度”，就像是试图走遍城市中所有可能的路径来观察两点是否接触。对于一个小城镇，这很容易；但对于一个巨大的大都市，这会耗费极长时间并导致你的计算机崩溃。

这篇论文介绍了一种更聪明的新型计算方法，称为 GRFs++（改进型图随机特征）。以下是它的工作原理，我们使用简单的类比来解释：

1. 旧方法：“长途跋涉”问题

之前的方法（常规 GRFs）试图通过从每个交叉口派出“探险家”（随机游走）来解决这个问题。

问题所在： 为了理解两个遥远的交叉口之间有什么关系，探险家必须进行一次非常漫长的、一步一脚印的旅行，直到到达另一端。
瓶颈： 这是一个串行过程。在完成第 9 步之前，你无法进行第 10 步。这就像是在过河时必须踩在石头上一步步跳跃，每跳一步都要等待前一步完成后才能开始下一步。这很慢，且难以利用现代计算机进行加速。
局限性： 如果城市规模巨大，探险家往往在到达遥远的街区之前就“放弃”（停止行走）了，这意味着计算机认为这些遥远的区域之间没有任何联系。

2. 新方法：“路径缝合”（乐高类比）

作者提出了 GRFs++，它彻底改变了策略。与其派出一名进行漫长且精疲力竭旅程的探险家，不如派出许多短程探险家，然后将他们的路径缝合在一起。

类比： 想象你需要建造一座 100 英尺长的桥。
- 旧方法： 一个人尝试一次铺设一块木板，如此循环，一次铺一块。如果他们累了，桥的建设就会停止。
- GRFs++ 方法： 你雇佣了 10 支团队。每支团队同时建造 10 英尺长的路段（并行工作）。然后，你使用一种特殊的胶水（“缝合”技术）将这些 10 个路段拼接成一座长桥。
优势： 因为大家都在同时工作，任务完成得更快。更棒的是，由于每个路段都很短，这种“胶水”能确保最终生成的桥梁与一个人从头到尾亲手建造的桥一样坚固且精确。这使得计算机能够理解远程节点之间的连接，而无需经历那种缓慢的、步步等待的过程。

3. “停止信号”升级

在旧方法中，探险家遵循一个简单的规则：“每走一步，抛一次硬币。如果是正面，就停止行走。”这类似于伯努利试验（简单的硬币投掷）。

升级版： GRFs++ 允许使用更复杂的“停止信号”。探险家不再仅仅依赖简单的硬币投掷，而是可以根据更复杂的、预先计划好的方案（如泊松分布）来停止。
结果： 这不会增加任何额外的时间成本，但它能让“探险家”在正确的时机停止，从而在不减慢速度的前提下，绘制出更精确的城市地图。

4. 这篇论文实际证明了什么

作者不仅猜测这行得通，还进行了数学证明和测试：

准确性： 他们证明了将短路径缝合在一起，在数学上（平均而言）能得到与进行一次长路径行走完全相同的答案。
速度： 他们展示了 GRFs++ 比旧方法快得多，尤其是在处理大型复杂图（如物体的 3D 模型或大规模社交网络）时。
现实世界测试： 他们在以下领域进行了测试：
- 3D 网格（Meshes）： 预测 3D 打印物体的形状。
- 图像分类： 帮助计算机识别图像（例如在 Vision Transformers 中）。
- 图分类： 对不同类型的网络进行分类（如化学分子或社交群体）。
- 聚类： 将相似的节点分组在一起（如寻找社交网络中的社群）。

总结

GRFs++ 就像是从一名独自奔跑马拉松的慢速信使，升级到了由短跑选手组成的接力赛队。通过并行运行短距离冲刺并将结果拼接在一起，该系统比以前更快速、更高效地构建出了整个网络的完整且准确的图像。它解决了旧方法难以察觉的“远程”连接问题，同时更有效地利用了计算机的性能。

技术摘要：基于改进型图随机特征（Refined Graph Random Features）的高效图建模

1. 问题陈述

图建模是机器学习应用中的基础，涵盖了从异常检测、推荐系统到计算生物学的广泛领域。其中的一个核心挑战在于计算图核（graph kernels），这些核定义了基于节点连通性（例如扩散过程、随机游走或正则化拉普拉斯矩阵）的相似度。计算这些核的精确 Gram 矩阵通常需要相对于节点数 $N$ 具有三次时间复杂度（ $N^3$ ）的操作，这使得在大规模图上进行计算变得难以实现。

虽然低秩分解策略（ $K \approx \Phi \Phi^\top$ ）为实现亚二次复杂度提供了路径，但现有的**图随机特征（Graph Random Features, GRFs）**方法存在特定的局限性：

串行效率低下： 标准 GRFs 依赖于顺序采样长随机游走来捕捉远距离节点之间的关系。这一过程本质上是串行的，且无法得到现代并行加速器的良好支持。
难以建模远距离关系： 通过增加停止概率来缩短游走长度以提高速度，会降低建模远距离节点关系的能力，如果游走不相交，往往会将它们的核值近似为零。
终止机制僵化： 标准 GRFs 使用固定的伯努利试验方案进行游走终止，这对于给定的计算预算而言可能并非最优。

2. 方法论：改进型图随机特征 (GRFs++)

作者提出了 GRFs++，这是一类改进型的图随机特征，通过以下三个主要技术创新解决了上述局限性：

A. 游走拼接机制 (Walk-Stitching Mechanism)

GRFs++ 不再顺序采样单个长随机游走，而是将过程分解为 $l$ 个独立的、较短的随机游走。随后，这些较短的游走通过矩阵乘法被“拼接”在一起，以模拟长游走的统计特性。

数学公式： 核矩阵 $K_\alpha(W)$ 被近似为 $l$ 对矩阵乘积的期望：
$K_\alpha(W) \approx \mathbb{E}\left[ \prod_{i=1}^l K_1^{(i)} (K_2^{(i)})^\top \right]$
调制函数调整： 为了保持无偏性，用于游走更新的调制函数 $f$ 必须满足更高阶的卷积条件。具体而言，核的泰勒级数系数 $\alpha_k$ 必须是 $f$ 与自身进行 $2l$ 层离散卷积的结果。这使得该方法能够在实现并行计算短游走的同时，恢复长游走的近似质量。

B. 通用游走终止策略

GRFs++ 将游走终止机制从标准的伯努利分布（固定停止概率 $p_{halt}$ ）进行了扩展。

灵活采样： 该方法允许从任何离散概率分布 $P$ 中采样游走长度，前提是采样自 $P$ 以及计算累积概率 $P(X \ge k)$ 是高效的。
无偏估计： 通过调整包含基于所选分布生存函数的归一化因子的负载更新规则，作者证明了无论采用何种终止策略，估计量始终保持无偏。这使得诸如（泊松分布长度）等策略能够更好地适应特定的计算约束或图拓扑结构。

C. 实现选项

该框架提供三种实现模式，以平衡稀疏性与维度：

选项 I（稀疏型）： 通过矩阵乘法链直接构建稀疏矩阵 $X$ 和 $Y$ 。
选项 II（降维型）： 应用 Johnson-Lindenstrauss 变换 (JLT) 来降低维度，以牺牲稀疏性为代价换取更低维度的嵌入。
选项 III（隐式型）： 通过直接计算矩阵-向量乘积来避免显式矩阵构建，利用矩阵乘法的结合律实现每步 $O(N)$ 的复杂度。

3. 核心贡献

游走拼接技术： 一种创新的方法，用并行短游走采样和矩阵-矩阵乘法取代了顺序长游走采样，显著提升了在现代硬件上的计算效率。
理论无偏性： 本文提供了严格的证明（引理 3.1，定理 3.3），证明了 GRFs++ 提供了图核的无偏近似。此外，研究进一步确立了增加游走拼接度 $l$ （特别是对于 2 的幂次时）会单调降低近似的均方误差 (MSE)。
泛化的终止机制： 将其扩展到任意游走长度分布，表明非伯努利策略可以在不增加额外计算成本的情况下提高精度。
与去卷积的联系： 作者建立了寻找 GRFs++ 的调制函数 $f$ 与对核生成函数进行高阶去卷积之间的理论联系。

4. 实验结果

作者在各种数据集和任务上将 GRFs++ 与常规 GRFs 及暴力基准方法进行了评估：

核近似精度： 在具有大直径（高达 159）的图上，GRFs++ 始终比常规 GRFs 获得更低的 Frobenius 范数误差，特别是在处理距离较远的节点对时。
计算速度： GRFs++ 展示了显著的加速。对于规模在 11,700 到 35,300 个节点之间的网格，GRFs++ 仅需数秒或数分钟即可运行完成，而暴力方法通常会超出时间限制（超时）或耗时显著更长。
下游任务：
- 图分类： GRFs++ 在 12 个数据集（如 MUTAG、ENZYMES、COLLAB）上实现了与精确扩散核相当的性能，并优于常规 GRFs。
- 节点聚类： 在 Karate 和 Dolphins 等标准数据集上，GRFs++ 的聚类误差率低于常规 GRFs 及其他基准方法（如 Louvain、Spectral）。
- 网格法线预测： 在预测 3D 网格的顶点法线时，GRFs++ 的准确度与基准暴力核匹配，同时显著优于常规 GRFs。
- 视觉 Transformer (ViT)： 将 GRFs++ 作为归纳偏置集成到 ImageNet 和 Places365 上的视觉 Transformer 中，带来了持续的准确度提升。
- 图 Transformer： 在 GraphGPS 框架中，基于 GRF++ 的位置编码在 Peptides-func 和 CIFAR-10 等基准测试上的表现优于标准基准。

5. 重要性与主张

本文声称 GRFs++ 成功解决了图核中计算效率与建模长程依赖能力之间的长期权衡问题。通过从顺序随机游走采样转向并行矩阵运算，GRFs++ 使得在不牺牲精度的情况下，在大规模图上近似复杂的图核成为可能。

作者强调，其方法不仅是一种启发式方法，而且具有理论保证的无偏性和集中性。他们将 GRFs++ 定位为一个通用的工具，可以应用于各种类型的核（扩散核、逆核、指数核），并能集成到多样化的机器学习流水线中，从传统的核方法到现代的 Transformer 架构。这项工作表明，“游走拼接”范式提供了一种高效的图建模通用方法，克服了以往随机特征方法的顺序瓶颈。