📊 statistics

Optimal Time Complexity Algorithms for Computing General Random Walk Graph Kernels on Sparse Graphs

本文介绍了首个针对有标签和无标签稀疏图上的一般随机游走核进行无偏近似的线性时间随机算法，该算法能够在不构建直接积图的情况下实现大规模数据集上的可扩展计算，并比以往的三次时间复杂度方法实现了显著加速。

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

发布于 2026-08-27

📖 1 分钟阅读☕ 轻松阅读

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

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

在计算机科学领域，教机器理解事物的形状一直是一个持久的挑战。虽然我们擅长识别数字列表或图像中的模式，但比较网络（如社交连接、分子键或交通路线）的复杂结构仍然非常困难。为了实现这一点，研究人员使用了一种被称为“图核”（graph kernels）的数学工具。可以将它们想象成一种为一对网络分配单一评分的方法，告诉我们它们之间的相似程度。高分意味着这两个网络共享相似的连接模式；低分则意味着它们在本质上是不同的。这种相似性评分是许多机器学习任务的基础，例如预测一种新的化合物是否有效，或将相似的社交网络归为一类。

然而，计算这种评分在历史上一直是一场计算噩梦。对于复杂的网络，标准方法所需的时间和内存之多，使得一旦网络规模超过一定大小，它们就变得无法使用。这就像试图通过绘制每条连接的地图，来计算城市中每对人之间所有可能的路径；这张地图大到无法放在一个房间里，而且计数所需的时间比人类的一生还要长。这种瓶颈使得强大的数学技术无法应用于大规模的现实世界数据集，迫使科学家要么忽略数据的完整复杂性，要么退而求其次，使用粗略且不太准确的近似值。

一组研究人员现在为这类广泛的相似性工具解决了这个问题。他们开发了一种新方法，可以以随网络规模线性增长的时间来计算这些复杂的网络比较。这意味着，如果一个网络的大小增加一倍，计算相似性评分所需的时间也仅增加一倍，而不是爆炸式地增长到一个无法处理的数字。他们的方法被称为“图旅者”（Graph Voyagers），既适用于简单网络，也适用于那些单个点具有特定标签（例如分子中不同类型的原子）的网络。该方法非常高效，可以处理拥有超过一万六千个节点的网络，而这种规模在以前是无法使用精确方法进行分析的。

他们的核心创新在于如何模拟在这些网络中的移动。传统上，为了比较两个网络，计算机必须同时构建两个网络的巨大组合地图，这一步会消耗大量的内存。新方法完全避免了构建这个巨型地图的过程。相反，它派出成对的虚拟行走者，一个在每个网络上，并引导它们逐步移动。这些行走者由一组共享的随机信号引导。如果两个网络上的行走者走了相同步数的路，并且落在具有匹配标签的点上，它们就会对最终的相似性评分做出贡献。如果它们走的步数不同，或者落在不匹配的点上，它们的贡献就会相互抵消。通过重复这个过程数千次并取平均值，该算法可以在无需在内存中存储组合地图的情况下，构建出对真实相似性的高度准确的估计。

这项技术不仅仅是一个理论上的技巧；它产生了一种将整个网络表示为多维空间中点的新方法。在这个空间中，两点之间的距离反映了网络之间的相似程度。由于该方法速度极快，它允许研究人员一次处理包含数千个图的整个数据集，而不是一对一对地进行比较。在针对化学和生物分析的标准数据集进行的测试中，这种新方法达到甚至超过了精确、缓慢计算的准确度。它还被证明比现有的最高效方法更快，处理大型图的速度比现有最佳替代方案快了多达 27 倍。

或许最重要的一点是，这种速度为自动学习衡量相似性的最佳方式打开了大门。过去，科学家必须手动选择如何计算相似性评分的规则，通常只能采用可能并不适合其特定数据的标准公式。有了这种线性时间的新方法，计算机现在可以直接从数据中学习最优规则，调整计算方式以找到对特定任务最有用的模式。在实验中，这种学习规则的能力显著提高了分类化合物的准确度。研究人员已经表明，通过消除计算障碍，我们可以释放出更强大、更具适应性的方式，让机器去理解构成我们世界的复杂结构。

技术摘要：计算稀疏图上通用随机游走核（RWK）的最优时间复杂度算法

问题陈述

本文解决了计算稀疏图上**通用随机游走核（General Random Walk Kernels, RWKs）**时存在的计算瓶颈。RWK 是一类著名的正定对称函数，通过在直接积图 $G_1 \times G_2$ 上对不同长度的游走进行加权求和，为图对分配相似度分数。

虽然 RWKs 涵盖了流行的核函数（如边际核、几何核和指数核），但其精确计算的成本极高。对于具有 $N$ 个顶点的图，通过直接积图进行暴力评估会产生 $O(N^6)$ 的复杂度。即使是优化后的方法（例如求解 Sylvester 方程或使用谱分解），通常也需要 $O(N^3)$ 的时间，并且往往无法处理**有标签图（labelled graphs）**或扩展到大规模数据集。此外，现有的亚立方阶（sub-cubic）方法通常无法处理学习核参数所需的任意系数序列 $(\mu_i)$ 。值得注意的是，虽然 Kang 等人 (2012) 曾提供过一种 $O(N)$ 算法，但该算法仅限于无标签图上特定几何 RWK 的情况。

核心问题在于：是否可能在 $O(N)$ 的线性时间复杂度内，为稀疏的有标签图计算通用 RWK 的无偏估计？

方法论：图航行者 (Graph Voyagers, GVoys)

作者提出了 Graph Voyagers (GVoys)，这是第一个能够在 $O(N)$ 时间内实现通用 RWK 对有标签和无标签稀疏图进行无偏近似的算法。该方法推广了图随机特征 (Graph Random Features, GRFs)，但引入了特定的机制以避免在内存中实例化直接积图 $G_1 \times G_2$ 。

核心机制

依赖性随机游走 (Dependent Random Walks)： 该算法不是在巨大的积图上采样游走，而是在 $G_1$ 和 $G_2$ 上独立地采样随机游走。为了模拟积图上的游走，这些独立的游走通过共享随机变量进行耦合。
通过随机变量进行过滤：
- 长度匹配 ( $g$ -变量)： 为了确保只有相同长度的游走才会对核函数产生贡献（正如积图游走的定义所要求的那样），算法在每一步 $l$ 将游走贡献乘以共享的 Rademacher 随机变量 $g(l)$ 。由于 $E[g(l_1)g(l_2)] = \mathbb{I}(l_1 = l_2)$ ，长度不同的游走项在期望下会消失。
- 标签匹配 ( $z$ -变量)： 对于有标签图，算法引入了与顶点标签对应的额外共享随机变量 $z(l, i)$ 。这过滤掉了顶点标签序列不匹配的游走贡献，有效地处理了积图中边仅存在于具有相同标签的顶点之间的约束。
图级嵌入 (Graph-Level Embeddings)： 算法为每个图构建低维特征向量。对于任何一对图 $(G_i, G_j)$ ，其嵌入的 dot product（点积）提供了真实 RWK $K_{RWK}(G_i, G_j)$ 的无偏估计。
内存效率： 该方法不存储积图的邻接矩阵。它利用稀疏表示和锚点（anchor points）来降低维度，确保空间复杂度与节点数量保持线性关系。

算法细节

输入： 图 $G_i$ 、调制函数 $f_\mu$ （由系数 $\mu_i$ 导出）、终止概率 $p_{halt}$ 以及游走数量 $m$ 。
过程：
1. 初始化共享随机序列 $g$ 和 $z$ 。
2. 对于每个图，从各种顶点开始模拟 $m$ 次随机游走。
3. 将“沉积”（deposits）累积到锚点顶点，权重由调制函数、随机变量和游走概率决定。
4. 构建特征矩阵 $C_i$ 和 $D_i$ 。
输出： 特征向量 $\phi(G_i)$ ，使得 $K_{RWK}(G_i, G_j) = \mathbb{E}[\phi(G_i)^\top \phi(G_j)]$ 。

主要贡献

线性时间复杂度： 本文提出了第一个针对通用 RWKs（涵盖任意系数序列 $(\mu_i)$ ）的有标签和无标签稀疏图的 $O(N)$ 无偏近似算法。这超越了以往仅限于无标签图上特定情况（如几何 RWK）的 $O(N)$ 方法。
大规模数据集的可扩展性： 通过避免实例化直接积图，该方法能够处理拥有 $>2^{14}$ 个节点的图以及包含数千个图的数据集，而此前的方法会因内存溢出 (OOM) 或时间限制而失败。
理论保证：
- 无偏性： 定理 4.1 证明了该估计量是无偏的。
- 集中性： 定理 4.2 提供了指数级的集中界限，表明估计量会精确收敛到真实的核值。
- 最优性： 定理 4.3 表明，使用 Rademacher 分布的随机变量可以最小化估计量的方差。
隐式核学习 (Implicit Kernel Learning)： 能够近似通用 RWKs（而非固定的特例）的能力，使得端到端学习系数序列 $(\mu_i)$ 成为可能，从而开启了可扩展的隐式图核学习。

实验结果

作者在 TUDataset 和合成的 Erdős-Rényi 图上对 GVoys 进行了评估：

准确性： 随着随机游走数量的增加，GVoys 收敛至精确的 RWK 值。在图分类任务（如 MUTAG, ENZYMES, NCI1）中，GVoys 的表现达到或超过了精确 RWK 基准线。
速度：
- 对于具有 $>2^{10}$ 个节点的图，GVoys 的表现优于谱分解、共轭梯度法和不动点迭代法。
- 对于具有 $2^{13}$ 个节点的图，GVoys 比不动点迭代法快 27 倍。
- 对于具有 $2^{14}$ 个节点的图，GVoys 比共轭梯度法快 8 倍，而其他基准方法则会出现内存溢出或耗时过长的问题。
核学习： 使用 GVoys 在 MUTAG 数据集上学习系数 $(\mu_i)$ 得到了 $88.3\%$ 的准确率，比标准的几何 RWK 基准线（ $81.4\%$ ）提高了 $8.5\%$ 。

重要性与主张

本文声称解决了图核方法中长期存在的计算障碍。通过实现线性时间和空间复杂度，GVoys 使将通用随机游走核应用于此前难以处理的大规模真实世界数据集变得可行。

作者强调，其方法是第一个实现通用 RWKs（针对有标签和无标签图）无偏近似的亚立方阶算法。虽然之前存在针对特定实例（如无标签图上的几何 RWK）的 $O(N)$ 算法，但 GVoys 是首个能处理具有任意系数和有标签顶点的通用情况的算法。引入新型图嵌入（随机特征）并保留核结构的方法，使其在缩放方面与节点数及数据集中图的数量保持线性关系。这种能力被强调为实现可扩展隐式图核学习的前提，因为在隐式学习中，核参数本身也是从数据中学习得到的。

论文总结道，虽然该方法对于无权无向图是无偏的，但估计器的随机性质可能会为下游任务提供鲁棒性，在分类场景中甚至可能优于精确的核计算。