随机游走核

玻尔百科

核心要点

随机游走核通过对两个图之间同步的“匹配游走”进行计数来衡量图的相似性，这一过程通过在其直积图上计数游走来实现形式化。
它通过创建一个包含所有长度匹配游走的加权和来计算单一的相似性得分，其中使用阻尼因子来控制局部与全局结构的影响力。
虽然功能强大，但随机游走核并非通用核，因为它可能无法区分那些碰巧具有相同数量各长度游走的不同图。
该核在生物信息学和神经科学中具有重要应用，用于比较复杂网络，如脑连接组、蛋白质相互作用网络，以及模拟药物-靶点效应。

引言

在一个日益互联的世界里，从社交网络到生物通路，能够定量地比较复杂网络的结构是一项根本性的挑战。像计算节点和边数这样的简单度量仅仅触及了皮毛，未能捕捉到定义网络功能和特性的复杂拓扑结构。这一差距催生了对更精密工具的需求，这些工具能够感知并比较连通性的本质。我们如何确定健康大脑的布线结构与患病大脑的结构有何不同，或者一个蛋白质的相互作用邻域在不同物种间是否保守？

本文介绍了随机游走核，这是一种为回答此类问题而设计的强大数学模型。它通过比较图中所有可能的路径（或“游走”）的集合，提供了一种衡量图相似性的原则性方法。我们将首先深入探讨“原理与机制”，通过探索如何将比较两个图的问题转化为在单个更大的图上计数游走的问题，从而从头开始构建这一概念。随后，“应用与跨学科联系”部分将展示这个抽象概念如何成为解决神经科学、系统生物学乃至药物发现领域现实问题的多功能工具，彰显其作为理解复杂系统的统一语言的角色。

原理与机制

要真正掌握随机游走核，我们必须踏上一段旅程，从一个简单的问题开始，逐步构建起层层优美的数学机制。我们的目标不仅仅是找到一个公式，而是理解其背后的物理直觉和思想的优雅统一性。

如何比较不可比较之物？

想象一下，你是一位数字社会学家，拥有两个大型社交网络。你想要回答一个看似简单的问题：“它们有多相似？”这个问题出奇地深刻。对于一个网络来说，“相似”究竟意味着什么？这当然不仅仅是关于人数（节点）或友谊关系（边）的数量。网络的真正特性在于其错综复杂的连接之网——即其结构。

我们可以尝试将它们分解成小的、可管理的部分来进行比较。例如，我们可以计算每个网络中三角形的数量。如果两者都有很多三角形，也许它们代表了紧密结合的社区。这是一个好的开始，但三角形只是一个小模式。那么正方形、五边形或更复杂的结构呢？

网络结构中一个更基本的“部分”是游走（walk）：一个由相连节点组成的序列，就像你可以在网络中进行的一次旅行。一次游走可以很短，探索局部邻域，也可以很长，揭示全局景观。一个图中所有可能游走的集合，是对其结构的丰富描述。因此，我们的问题“两个图有多相似？”可以被提炼为“它们的游走集合有多相似？”

同步之舞：匹配游走与直积图

这时，一个绝妙的想法应运而生。为了比较两个图（比如 $G$ 和 $H$ ）中的游走，我们可以想象尝试在两个图中同时进行一次游走。把它想象成一场同步舞蹈。我们有两个舞者，一个在舞厅 $G$ 中，另一个在舞厅 $H$ 中。只有当第一个舞者能够从其当前位置 $u$ 移动到舞厅 $G$ 中的新位置 $v$ ，并且同时，第二个舞者能够从其位置 $x$ 移动到舞厅 $H$ 中的新位置 $y$ 时，一次“匹配的舞步”才会发生。

这些匹配舞步的序列构成了一次匹配游走（matched walk）。两个图共享的各种长度的匹配游走越多，它们的连接结构就必定越相似。

这种同步舞蹈的直观想法可以通过一个优美的数学构造来形式化：图的直积（direct product graph）。让我们构建一个新的、更大的图，称之为 $G \times H$ 。在这个新的“元图”中，一个节点不再是单个点，而是一个节点对 $(u, x)$ ，其中 $u$ 是来自 $G$ 的节点， $x$ 是来自 $H$ 的节点。在这类成对的节点之间，比如从 $(u, x)$ 到 $(v, y)$ ，存在一条边的充分必要条件是：在 $G$ 中存在一条从 $u$ 到 $v$ 的边，并且在 $H$ 中存在一条从 $x$ 到 $y$ 的边。

根据这个定义，直积图 $G \times H$ 中的一次游走，就其构造而言，正是 $G$ 和 $H$ 之间的一次匹配游走。我们已经将比较两个图的问题转化为了在单个更大的图中计数游走的问题。这是科学中的一个经典策略：将一个困难的比较问题转化为一个更直接的计数问题。

用线性代数计数舞蹈

我们如何计算一个图中的游走次数？这里，我们求助于线性代数的威力。图论中最优雅的结论之一指出，如果一个图的邻接矩阵为 $A$ ，那么从节点 $i$ 到节点 $j$ 的长度为 $t$ 的游走数量，恰好是矩阵 $A$ 的 $t$ 次幂中第 $i$ 行第 $j$ 列的元素，记为 $(A^t)_{ij}$ 。

那么，我们的直积图的邻接矩阵 $A_{G \times H}$ 是什么呢？它原来是各个邻接矩阵的克罗内克积（Kronecker product），写作 $A_G \otimes A_H$ 。因此，长度为 $t$ 的匹配游走数量被编码在这个新矩阵的幂次中： $(A_G \otimes A_H)^t$ 。

克罗内克积的性质给了我们一个惊人简单的结果。直积图中长度为 $t$ 的总游走数，我们称之为 $N_t(G \times H)$ ，恰好是每个独立图中长度为 $t$ 的总游走数的乘积。 $N_t(G \times H) = N_t(G) \times N_t(H)$ 让我们用一个简单的例子来看这一点。取一个由一条边连接两个节点的图 $G$ ，和一个作为三角形的图 $H$ 。在 $G$ 中，任何长度为 $t$ 的游走数量总是 2。对于三角形 $H$ ，它是一个 2-正则图，长度为 $t$ 的游走数量是 $3 \times 2^t$ 。因此，它们之间长度为 $t$ 的匹配游走总数就是 $(2) \times (3 \times 2^t) = 6 \times 2^t$ 。“同步舞蹈”的复杂度仅仅是各个独立舞蹈复杂度的乘积！

从无限游走中得到单一评分

我们现在可以计算任何长度 $t$ 的匹配游走。为了得到一个单一的相似性得分，我们需要将这些计数结合起来。我们不能简单地将它们相加，因为更长的游走数量要多得多，会主导总和。解决方案是计算一个加权和，其中较长的游走被赋予逐渐减小的权重。我们使用一个阻尼因子（damping factor） $\lambda$ ，一个介于 0 和 1 之间的数字。长度为 $t$ 的游走的贡献由 $\lambda^t$ 加权。

这就给出了随机游走核（random walk kernel）的定义： $k_{\mathrm{RW}}(G, H) = \sum_{t=0}^{\infty} \lambda^t (\text{长度为 } t \text{ 的匹配游走计数})$ 参数 $\lambda$ 就像一个旋钮。一个非常小的 $\lambda$ 意味着我们主要关注短的游走，捕捉局部的结构相似性。随着我们增加 $\lambda$ ，我们允许更长的、更全局的游走对我们的相似性得分做出贡献。

为了让这个无穷级数有意义，它必须收敛到一个有限的数。这要求我们的阻尼因子 $\lambda$ 足够小，以抵消游走数量的增长。精确的条件涉及到矩阵的谱半径（spectral radius） $\rho(A)$ ，你可以把它看作是矩阵对游走的内在“放大系数”。如果 $|\lambda| 1 / \rho(A_G \otimes A_H)$ ，该级数就会收敛，这可以简化为 $|\lambda| 1 / (\rho(A_G)\rho(A_H))$ 。

当它收敛时，这个无穷和有一个优美而紧凑的形式。就像几何级数 $1 + r + r^2 + \dots$ 的和是 $\frac{1}{1-r}$ 一样，矩阵几何级数 $\sum_{t=0}^\infty (\lambda A_{G \times H})^t$ 的和是 $(I - \lambda A_{G \times H})^{-1}$ 。这个矩阵被称为预解式（resolvent），它出现在物理和工程的许多领域。它优雅地捕捉了两个图之间所有可能匹配游走的总和，每个游走都根据其长度进行了适当的加权。

宏伟的配方：作为卷积的核

你可能想知道，这整个过程——分解为游走、计数它们、然后求和——是否只是一个聪明的一次性技巧。美妙的答案是否定的。它是比较结构化对象的一个深刻而普遍的原则的典范，即Haussler 的 R-卷积框架（Haussler's R-convolution framework）。

这个框架为构建相似性度量提供了一个通用的配方：

分解：定义一个关系 $R$ ，将你的复杂对象（这里是图）分解成一系列更简单的“部分”（这里是游走）。
比较部分：定义一个“基核”，用于计算任意两个部分之间的相似性。在我们简单的随机游走核中，我们隐式地在比较来自两个图的游走。
聚合：两个复杂对象的最终核（或相似性得分），是所有可能的部分对（每对中一个部分来自一个对象）之间相似性的总和。

随机游走核正是从这个配方中自然产生的。这表明我们的方法并非随意的，而是在各种离散结构（从生物序列和分子到自然语言文本）上创建核的一个强大思想的实例。这种统一性是深刻科学思想的标志。

视觉的极限：核所不能见的

我们构建了一个强大的显微镜来检查网络结构。但像任何仪器一样，它也有其局限性。随机游走核是否提供了对图的完美、全能的视角？坦率地说，答案是否定的。

一个理想的核应该是特征核（characteristic）或通用核（universal）。这意味着它应该足够强大，能够区分任何两个不完全相同的图。如果图 $G$ 和图 $H$ 具有不同的结构，一个通用核应该总能将它们区分开来。

然而，随机游走核可能会被欺骗。它的整个“世界观”都基于对游走的计数。如果两个不同的图碰巧每种长度的游走数量都完全相同，该核就会认为它们是相同的。这样的图是存在的！例如，某些同谱图（cospectral graphs）对，它们非同构但共享相同的特征值，简单的随机游走核就无法区分。

发生这种情况是因为特征映射——将图转化为一组游走计数的过程——不是单射（injective）的。这是一个多对一的映射，不同的图可以被映射到相同的特征表示。因为核只能看到这个特征表示，它就对原始图之间的差异视而不见。RKHS，即核可以表示的函数空间，不够丰富以至于无法分离所有可能的图，因此该核不是通用的。

这并非核的“失败”，而是一种根本性的权衡。在科学和工程中，我们不断地用表达能力换取计算效率。随机游走核之所以在计算上可行，正是因为它依赖于一种简化的、基于游走的图视角。这种效率的代价是它的视觉存在盲点。认识到这些盲点的性质和范围，与欣赏该工具本身的力量同样重要。

应用与跨学科联系

在理解了随机游走核的原理之后，我们可能仍然会有一种“那又怎样？”的感觉。诚然，它是一个优美的数学构造，但它究竟有何用途？这种比较图上无限游走的抽象概念，在何处与现实世界相遇？答案是，无处不在。这个思想真正的力量和美感在于其非凡的能力，它为理解复杂、相互关联的系统提供了一种统一的语言，从我们大脑的布线到拯救生命的药物设计。它让我们能够从内部“感受”一个网络的形状，就像一个人通过在黑暗的房间里四处走动来熟悉其布局一样。

作为网络的大脑：绘制连接组

让我们从已知最复杂的网络之一——人脑——开始。神经科学家们不再仅仅对大脑的哪些区域活跃感兴趣，而是对它们如何连接成一个“连接组”（connectome）感兴趣。这个布线图——其中大脑区域是节点，神经通路是边——掌握着认知、行为和疾病的秘密。假设我们有两组人的连接组数据，一组是健康的，另一组患有神经系统疾病。我们如何以一种有意义的方式比较他们的大脑？

一种天真的方法可能是简单地列出每个大脑的所有连接及其强度，然后比较这些列表。但这完全没有抓住要点。大脑的功能源于其拓扑结构——其路径、枢纽和模块的复杂结构。简单地将连接向量化是脆弱的，并且对这种结构视而不见；这就像试图通过查看按字母顺序排列的街道列表而不是地图来理解一个城市的交通流。

这正是图核提供一种深刻更优方法的地方。通过在机器学习模型中使用图核，我们可以根据两个连接组的内在结构属性来比较它们。例如，一个随机游走核实际上在问：“在这两个大脑中可能传播的随机神经信号模式有多相似？”它对高阶特征——那些定义网络架构的路径和模体——很敏感。这使我们能够构建分类器，可以识别健康和患病大脑之间微妙但一致的拓扑差异，为疾病提供潜在的生物标志物和更深入的神经学基础理解。核使我们能够看到网络拓扑的森林，而不仅仅是突触连接的 einzelnen Bäumen。

作为社会形态的细胞：揭示生命蓝图

让我们从大脑缩小到单个细胞的内部世界。一个细胞是一个由蛋白质组成的繁忙社会，它们在一个巨大的蛋白质-蛋白质相互作用（PPI）网络中相互作用。比较这些网络——例如，人类和酵母之间的网络——是系统生物学的核心任务。我们如何能说，一个人类蛋白质的“社交网络”与一个酵母蛋白质的相似？

同样，随机游走核提供了这种语言。我们不能直接比较这些图；人类的 PPI 网络要大得多，也复杂得多。但我们可以构建一个足够聪明的核来处理这些差异。可以构建一个复杂的带标签的随机游走核来比较两个网络上所有可能的游走。这个核做了两件绝妙的事情。首先，它使用一种归一化形式（余弦归一化），使得比较对网络的整体大小具有鲁棒性。其次，它不仅仅看原始结构；它还整合了关于节点本身的信息。通过使用一个知道如何比较两种蛋白质生化属性的“节点核”，随机游走核比较的是生物学上对应的蛋白质之间的游走。这个强大的思想使我们能够在整个生命之树中发现深刻的、保守的功能模块和进化模式。

双游走记：导航细胞景观

一个好的物理模型的美妙之处在于其假设。选择一个数学工具不是一个中立的行为；它是一种声明，表明你认为在你所研究的系统中什么是重要的。这在单细胞生物学领域得到了极好的阐释，科学家们旨在绘制细胞的发育路径，这一概念被称为“伪时间”（pseudotime）。他们构建一个图，其中每个细胞是一个节点，连接到其最相似的邻居。从干细胞到完全分化细胞的路径就是穿过这个图的一条轨迹。

我们如何模拟这段旅程？我们可以使用基于图的邻接矩阵 $A$ 的标准随机游走。在这个模型中，游走倾向于在图的更密集区域花费更多时间——也就是靠近拥有许多相似邻居的细胞。如果这种密度反映了生物学现实，比如一个细胞在做出发育决定前“徘徊”在一个稳定状态，那么这正是我们想要的行为！这个模型对密度的敏感性成了一个特性，而不是一个缺陷。

但如果采样密度只是我们实验的一个人为产物呢？如果我们只是偶然从一种状态捕获了比另一种状态更多的细胞呢？在这种情况下，我们需要一个忽略密度、纯粹关注发育景观潜在“形状”或几何的模型。为此，我们转向另一种游走——由图拉普拉斯算子 $L$ 描述的连续扩散过程。这种基于拉普拉斯算子的扩散被设计成对节点度不敏感，从而提供了对流形的一种去偏见的视图。因此，在基于 $A$ 的随机游走和基于 $L$ 的扩散之间做出选择，不仅仅是一个技术细节；它是关于所提出的科学问题的深刻选择。

从离散步骤到连续流动

基于拉普拉斯算子的游走思想将我们引向一个优美的推广。离散随机游走是一系列步骤。但如果我们把这个过程想象成一个连续的流动，就像热量在一组金属棒网络中扩散一样呢？这就是图热核（graph heat kernel）的概念， $K_t=e^{-tL}$ 。这个算子描述了图节点上“热量”（或任何信号）的初始分布如何随时间 $t$ 扩散。

这个热核具有非凡的性质。首先，它充当一个低通滤波器。就像热流会平滑剧烈的温差一样，热核通过抑制相邻节点之间的高频振荡来平滑图上的噪声信号。其次，对于任何时间 $t > 0$ ，矩阵 $K_t$ 本身就是一个对称正定矩阵。这意味着它可以被用作一个“扩散核”，给出任意两个节点之间的相似性得分：如果热量容易在两个节点之间流动，那么它们就是相似的。最后，它代表了连续时间随机游走的转移矩阵，统一了离散步骤和连续流动的世界。一个用于热流的模型，同时为机器学习提供了一个核，并为图上的随机过程提供了一个模型，这证明了贯穿数学的深刻联系。

锻造更好的工具：融合核的艺术

自然是复杂的，有时单一的工具，无论多么优雅，都是不够的。热核 $e^{-\beta L}$ 非常适合捕捉局部扩散，强调短路径。另一个相关的算子，预解式核 $(I+\delta L)^{-1}$ ，则更擅长捕捉全局、长程的传播。如果一个生物信号，比如疾病扰动，既有局部成分又有全局成分，该怎么办？

答案是成为一名艺术家和工程师。我们可以通过融合我们的构建模块来创建一个新的复合核： $K = w_1 e^{-\beta L} + w_2 (I + \delta L)^{-1}$ 通过选择非负权重 $w_1, w_2 \ge 0$ ，我们保证我们的新核仍然是一个有效的正半定核。这个融合核对应于一个定制设计的光谱滤波器。它允许我们精确地调整我们的模型以适应生物学问题的多尺度性质，平衡局部细节和全局结构之间的权衡。这就像同时拥有一把放大镜和一架望远镜来检查网络，给了我们构建我们需要的确切镜头以使潜在的生物学聚焦的灵活性。

药房中的网络漫步：药物发现的一场革命

让我们用这些思想最具影响力的应用之一来结束我们的旅程：新药的设计。几十年来，药物发现的信条是“魔弹”——一种通过打击一个特定靶点来治愈疾病的分子。我们现在知道这很少是事实。大多数药物，无论好坏，都表现出“多靶点药理学”（polypharmacology），即与细胞网络中的多个靶点结合。这使一切都变得复杂起来。如果一种药物打击了三个蛋白质并产生了治疗效果，我们如何知道是哪个相互作用负责？这就是“靶点解析”（target deconvolution）的艰巨挑战。

网络传播提供了答案。我们可以将细胞建模为一个巨大的 PPI 网络。当药物进入细胞时，它与多个靶点的结合可以被看作是在网络的几个节点上放置扰动的“种子”。每个种子的强度可以根据药物的浓度及其对该靶点的结合亲和力来估计。

然后，我们让随机游走开始。使用像带重启的随机游走（RWR）或扩散核这样的算法，我们模拟这些初始扰动如何通过网络传播。然后我们可以测量对已知与疾病表型有关的下游节点的累积效应。这使我们能够看到多个脱靶效应如何可能汇聚在单一通路上，产生协同或意想不到的结果。通过将系统作为一个整体来建模，我们可以超越“一药一靶”的范式。这些方法帮助我们理解现有药物为何有效，预测它们的副作用，以及最令人兴奋的是，设计新的多靶点药理学药物，智能地作用于多个靶点，以更有效地对抗像癌症这样的复杂疾病。随机游走这个简单、近乎异想天开的想法，当应用于生命之网时，成为开启理性药物设计新时代的一把钥匙。