图上的 Ricci 曲率:Ollivier 与 Forman
在离散结构(如图、网络)上定义曲率是几何深度学习、网络科学和图分析中的一个核心挑战。由于图没有传统的微分结构,我们需要通过不同的方式来「离散化」黎曼几何中的曲率概念。
在黎曼几何中,Ricci 曲率描述一束测地线在演化过程中是汇聚还是发散。它依赖切空间、联络与度量张量,看起来很难直接搬到离散对象上。Ollivier 在 2009 年给出了一种相当经济的替代方案:把「点」换成「局部概率测度」,把「沿测地线搬运切向量」换成「用最优传输搬运概率质量」。由此得到的量称为 Ollivier-Ricci 曲率(Ollivier-Ricci curvature,ORC),它对任何度量空间都有定义,因此可以直接用在图上。
Ollivier-Ricci 曲率和 Forman-Ricci 曲率是目前图上最常用的两种 Ricci 曲率离散化方法,它们源于不同的数学直觉,适用于不同的场景。
一、直觉:邻域之间的距离
设 是度量空间中的两个点,记 。在 与 附近各取一个半径为 的小球,并在球上放置概率测度 。如果空间是平坦的,把 搬运到 的平均成本应当接近 。如果空间正弯曲,例如球面,两个小球会向着彼此倾斜,最优匹配的平均位移小于 。如果空间负弯曲,例如双曲空间,小球会背向彼此张开,平均位移大于 。
于是可以定义
其中 是一阶 Wasserstein 距离,也就是最小平均搬运成本。比值 是邻域在运输意义下的收缩系数, 就是曲率。正、零、负分别对应收缩、保持与扩张。
这个构造有两个值得注意的特点。它既没有使用切空间,也没有要求空间光滑,只需要距离和测度。更重要的是,曲率不再是度量本身的函数,而是「度量 + 局部测度」的联合性质。后一点在图上尤其重要,因为随机游走的定义会直接改变曲率。
二、Ollivier-Ricci 曲率的定义
2.1 耦合与 Wasserstein 距离
设 是 Polish 度量空间, 是 上的两个 Borel 概率测度。若 上的概率测度 满足
对任意 Borel 集 成立,则称 是 与 的一个耦合,所有耦合的集合记为 。一阶 Wasserstein 距离定义为
直观上, 描述一种搬运方案, 是从 搬到 的质量,积分就是总运输成本。 取所有方案中的最小值。
2.2 曲率的定义
设 是度量空间。对每个 ,给定一个以 为中心的概率测度 。对任意 ,定义
称 为 在 处的 Ollivier-Ricci 曲率。
测度族 通常取成随机游走的一步转移分布,也可以取成小球上的均匀分布、热核分布或个性化 PageRank 分布。不同的取法给出不同的曲率,这一点在阅读文献时需要特别注意。
由定义可以直接读出三条基本性质。由于 ,恒有 。 关于两个测度对称,所以 。当 时 ,曲率取到最大值 。
曲率的符号有明确的几何含义。 表示两个邻域在运输意义下彼此靠近,对应局部收缩。 表示运输成本恰好等于中心点之间的距离,对应局部保持。 表示运输成本更大,对应局部扩张。
这个定义把三个原本独立的领域接在一起。度量几何提供距离,最优传输提供比较两个测度的方法,概率论提供随机游走这一局部测度族。曲率不再需要微分结构,却仍然保留了「邻域如何形变」这一核心含义。
2.3 对偶形式
在图上直接求解 需要解一个线性规划。对偶形式把同一个量写成函数的上确界,往往更容易构造证明。
设 是 Polish 度量空间, 是概率测度。则
其中 是 上所有满足 的函数 的集合。
在有限图上,对偶问题只有 个变量和 条边约束,因此可以精确求解,最优函数 还可以当作最优性证书。后文证明下界时会反复使用这一点。
三、图上的计算
3.1 随机游走测度
设 是无向简单图, 是节点 的度数。最常用的选择是简单随机游走的一步分布。
对每个 ,定义 上的概率测度
也就是说,从 出发均匀地选择一个邻居。
对相邻节点 ,有 ,于是
对不相邻的节点,则需保留分母 。
这里有一个容易被忽略的问题。随机游走不一定是简单随机游走。加入自环会得到惰性游走
其中 是 处的点质量。不同的 给出不同的曲率。Lin、Lu 与 Yau 在研究图上的 Ricci 曲率时,采用的是 的极限版本,后文第 5.5 节会再回到这个约定。
3.2 几个可以手算的例子
路径图。 取一条无限路径, 与 相邻。此时 ,两个邻域分别是 与 。最优方案把 送到 ,把 送到 ,每条路径的长度为 ,总成本为 。因此 ,。这与平坦的直觉一致。
完全图。 在 中,每个节点的度数为 。两个相邻节点的邻域有 个公共节点,这部分质量可以原地匹配。剩下的质量是 在 处的 与 在 处的 ,搬运距离为 。因此
当 时 ,当 时 。团越稠密,正曲率越强。
星形图。 设 是中心, 是叶子。叶子的测度是 ,中心的测度均匀分布在所有叶子上。把 搬到这些叶子,每一份质量都要走距离 ,所以 ,。这个例子说明,度数很高并不自动意味着正曲率。
双星图。 取边 ,其中 另有两个叶子邻居 , 另有两个叶子邻居 。此时 ,并且
一个看似自然的方案是把 送到 ,把 送到 ,再把 送到 。三条路径的长度分别是 ,总成本为 。但这个方案不是最优的。更好的方案是令 ,,,成本为 ,平均为 。为确认它确实最优,取
容易逐边检查 是 -Lipschitz 的。于是
对偶下界与原始方案的上界相同,故 ,从而
这个例子值得记住,因为它说明负曲率并不需要很大的图,一个很小的树状结构就可以产生明显的负曲率。
3.3 一个只依赖度数的下界
对于一般图,精确的 不容易手算。但相邻边的曲率有一个仅由两端度数决定的下界,证明只需要对偶形式。
证明。 设 是任意 -Lipschitz 函数。由于 在 上加常数不变,不妨设 。记 。因为 ,有 。
对任意 ,由 -Lipschitz 性得 。对任意 ,同理得 。注意 时 也成立,因为 。于是
其中
因为 ,有 ,所以右端作为 的函数单调不增。它在 处取到最大值 。因此对任意 -Lipschitz 的 都有
由命题 2.3 对 取上确界,得到 。再代入 ,即得
证毕。
这个下界在双星图与 -正则树上都可以取等。双星图两端度数都是 ,下界给出 ,恰好等于上一节算出的值。-正则树给出 ,下面说明它确实取等。
设 是 -正则树,。构造运输方案:令 ,,其余 对邻居 两两匹配。前两条路径的长度为 ,其余路径的长度为 ,总成本为
平均成本为 。另一方面,定义
在树中, 与 的距离为 , 与 的距离为 , 与 的距离为 ,逐一检查可知 是 -Lipschitz 的。它给出的对偶值为
与原始方案相同。因此
当 时回到路径图的 。当 时得到 ,与双星图一致,因为双星图正是 -正则树在边附近的截断。
顺带可以得到一个对任意相邻边都成立的下界。邻域中任意两点之间的距离不超过 ,因为
所以 ,从而 。这个界不依赖度数,但通常比度数下界更松,两者可以配合使用。
3.4 计算复杂度
精确计算 ORC 的主要开销在 。对一条边,两侧邻域的大小分别为 与 ,对应的线性规划大约有 个变量和 条边际约束。文献中常给出 的总复杂度估计,其中 是最大度数。对度数很高的图,这个成本很快就会变得不可接受。
实践中常用的替代方案有几种。熵正则化的 Sinkhorn 算法把线性规划换成可并行的矩阵缩放,以近似解替代精确的 。另一种做法是只在抽样的边或子图上计算曲率,用局部估计指导全局算法。如果愿意更换曲率定义,Forman 曲率的单边成本可以降到 ,Balanced Forman 曲率则是 。
四、与经典 Ricci 曲率的关系
4.1 局部展开
ORC 之所以被称为 Ricci 曲率,不只是因为直觉相似。在光滑流形上,经过适当的缩放,它确实恢复出经典的 Ricci 曲率。
设 是 维光滑黎曼流形,, 是单位切向量, 是沿 方向、与 距离足够近的点。取 为测地球 上的归一化黎曼体积测度, 同理。则当 、 时,
这个展开有三层含义。
ORC 在固定流形上随 趋于零。它不是 Ricci 曲率的逐点极限,而是经过 缩放后的极限。因此 ORC 是一种「模糊化」的曲率,它看到的是一个邻域上的平均行为,而不是某一点的无穷小行为。
常数 则与测度的选择有关。如果不用球上的均匀测度,而用热核测度,常数会改变。这与前文的观察一致:ORC 是度量与测度的联合性质。
公式中的 是沿 方向的 Ricci 曲率。取与 正交的一组单位正交基 ,则 等于由 与各个 张成的平面的截面曲率之和。因此 ORC 捕捉的是「在与 正交的各个方向上,邻域整体是收缩还是扩张」。
几个标准空间可以作为检验。半径为 的球面上 ,于是 。欧氏空间上 ,于是 。双曲空间上 ,于是 。符号与直觉完全一致。
4.2 收缩性与谱隙
ORC 的另一个重要作用是控制随机游走的长期行为。下面的收缩性质是 Ollivier 理论的核心结论之一。
设 是度量空间上的马尔可夫核, 是它的一步转移测度。若存在 使得对任意 都有 ,则对任意两个概率测度 ,
当 时,上式说明随机游走把任意两个分布之间的距离按几何速率压缩。迭代 步得到
这就是「正曲率导致快速混合」的精确表述。对有限可逆链,还可以进一步推出谱隙的下界 。这类结论把局部几何与全局分析连接起来,也是 ORC 与单纯的图指标最重要的区别。
在连续情形,正 Ricci 曲率还推出直径上界,形式上对应 Bonnet-Myers 定理。离散版本需要额外的假设,但基本思想相同:正曲率限制空间向外扩张的速度。
五、Forman-Ricci 曲率
5.1 无权形式
Forman 曲率来自 Forman 对 CW 复形上离散 Ricci 曲率的研究。它不使用最优传输,而是直接对每个胞腔统计相邻胞腔的贡献。在图这种一维复形上,公式会退化成非常简单的形式。
设 是无向简单无权图,。未增强的 Forman-Ricci 曲率定义为
若把三角形视为二维胞腔并计入其贡献,则得到增强形式
其中 是包含边 的三角形个数。
公式中的 可以拆成 。边本身贡献 ,两个端点各贡献 。每多一条与端点关联的边,就减去 。因此,一条边的两端越「拥挤」,它的 Forman 曲率越低。
几个简单情形可以直接验证。路径图的内部边满足 。设星形图的中心度数为 ,则叶子边满足 ,中心度数越高,曲率越负。在增强形式下,完全图 的每条边满足 ,数值随 增大而增大。
星形图的叶子边值得与第 3.2 节的结果对照。同样的边在 ORC 下给出 ,因为叶子的测度就是中心处的点质量,搬运成本恰好等于边长。未增强的 Forman 曲率却把它判成 ,度数越大越负。这个差异说明,只统计度数会把「没有迂回路径、但也没有扩张」的结构误判为强负曲率。
这里需要提醒符号约定。部分文献把曲率写成 ,与上式正好相反。比较不同论文的曲率数值之前,必须先确认符号与归一化方式。
5.2 加权形式
在实际网络中,节点和边通常带有权重。权重可以表示连接强度、通信容量、距离或相似度。Forman 曲率的加权版本把这些权重纳入同一个局部求和。
设边 的权重为 ,节点 的权重分别为 。定义
其中第二个求和遍历与 关联且不等于 的边。
当所有 都取 时,方括号内变成
与定义 5.1 一致。平方根来自 Forman 原始公式中对几何平均的归一化,它保证权重的量纲在乘积中保持一致。
加权形式给了使用者很大的设计空间,但也带来一个容易出错的地方。边权的语义必须与任务匹配。如果把权重解释为「距离」,权重大表示两点相距远。如果把权重解释为「强度」,权重大表示连接紧密。两种解释下曲率的含义会反过来,使用前需要先固定语义。
5.3 有向图
对有向图,Forman 曲率需要区分入边与出边。以有向边 为例,在尾节点 只统计与它同向的出边,在头节点 只统计与它同向的入边。只有「同向平行」的边才参与抵消,反方向的边不参与。
在无权情形,这个约定给出
其中 是出度, 是入度。这个量对信息流的汇聚与发散比较敏感。一个出度很大的源节点会把经过它的边的曲率压低,一个入度很大的汇节点也有同样的效果。
不同的实现会对「在尾节点统计入边还是出边」作出不同选择。使用现成库时,最好先用一个小图核对符号与方向约定。
5.4 节点曲率与全图曲率
边曲率可以聚合成节点曲率与全图曲率。节点曲率通常定义为与该节点关联的所有边的曲率之和
有时也取平均,以便在不同度数之间比较。全图曲率则对所有边求和或平均。
对无权、未增强的形式,全图求和有一个简洁的恒等式
也就是说,全图曲率本质上只依赖度数的二阶矩。若使用增强形式,还需要加上三角形项的贡献。每个三角形被三条边各计一次,因此总和多出 ,其中 是三角形个数。
这个恒等式暴露了无权 Forman 曲率的一个根本限制:它本身不包含任何环的信息。增强形式把三角形显式计入,但仍然看不到四环。以二维方格网为例,每个内部节点的度数为 ,每条边满足
方格网在几何上是平坦的,ORC 给出的曲率是 ,而 Forman 曲率却给出强负值。原因不是计算出错,而是公式里根本没有 -环的信息。增强形式也救不了它,因为方格网没有三角形。这正是 Balanced Forman 曲率要解决的问题。
5.5 Balanced Forman 曲率
Topping 等人在 2022 年提出 Balanced Forman 曲率,在 Forman 的组合框架里加入三角形与四边形的贡献,使其单边成本保持在 ,同时更准确地反映局部几何。
设 是无向简单无权图,,且 。记 为包含边 的三角形集合, 与 分别为在 侧与 侧基于该边、内部无对角线的四环集合, 为所有节点中基于该边且经过该节点的四环数的最大值。定义
若不存在四环,最后一项取 。当 时,规定 。
公式可以分成三部分理解。最前面的 是基线,度数为 时为零,度数变大时变负。中间两项统计三角形,三角形越多,曲率越正,并且按两端度数做了平衡,避免高度数节点主导结果。最后一项统计四环。内部无对角线的四环说明,即使去掉边 ,两侧邻域仍然通过另一条长度为 的路径相连,因此它抵消基线的负值,使方格网回到零曲率。
几个标准图可以检验这个定义。对 -正则树,没有三角形也没有四环,,与第 3.3 节算出的 完全一致。对二维方格网的内部边,,基线为 ,每条边两侧各有两个四环,最后一项为 ,总和为 ,与平坦直觉一致。对 ,包含一条给定边的三角形数为 ,代入可得 。
设 是无向简单无权图。对任意边 ,
其中 是 Lin–Lu–Yau 意义下的修正 Ollivier-Ricci 曲率。
这里的 需要单独说明。它定义为
也就是说,它先把自环质量加到 ,再让 ,并用 而不是 作归一化。它与本文第 2 节定义的 不一定相等。后者直接使用简单随机游走(相当于 )并按 归一化,而 是先取 的极限再按 归一化。
以四环 为例。简单随机游走给出 ,所以 。而修正版本给出 ,恰好等于 Balanced Forman 曲率。这个例子说明,定理 5.4 不能直接套用到简单随机游走的版本上。阅读文献时先确认采用哪一种约定,是避免这类数值矛盾的可靠办法。
在计算成本上,Balanced Forman 曲率对每条边只需要枚举两端邻居的交集与局部四环,文献给出的总复杂度为 ,比精确 ORC 的 低一档。这使它可以作为大规模图上的替代指标。
六、两种曲率的比较
它们从不同的粒度描述同一件事:一条边周围的局部结构,到底是让邻域收缩,还是让邻域扩张。
6.1 共同的几何直觉
ORC 与增强后的 Forman 曲率都把三角形视为正曲率的来源。一个三角形意味着边两端共享一个邻居,邻域在局部「折起来」了。对两端度数都大于 的树状桥边,两者也都给出负值。桥边两侧没有替代路径,邻域必须向外绕行,运输或组合成本都会增加。对长度至少为 的环与二维方格网,ORC 给出中性值,Balanced Forman 也能做到这一点。未增强的 Forman 曲率则不同,它不包含环的信息,会把这些结构误判为负曲率。
这种共同直觉使两者都可以用来定义离散 Ricci 流。给定边曲率,按 更新权重,反复迭代,负曲率的边会被压缩,正曲率的边会被保留。社群发现、图重连与网络简化都可以建立在这个流程上。
6.2 关键差异
信息范围是两者最根本的差别。ORC 使用整张图的最短路径距离,因此它能看到邻域之间的所有绕行方式。Forman 曲率只使用关联关系与局部胞腔,因此它对全局绕行不敏感。前者更「几何」,后者更「组合」。
计算成本上的差距同样明显。精确 ORC 需要对每条边解一个线性规划,成本随度数快速增长。Forman 曲率的无权形式对每条边只需读取两个度数,几乎可以视为 。Balanced Forman 处于两者之间,用局部枚举换取可接受的速度。
两者依赖的额外结构也各不相同。ORC 必须指定随机游走或局部测度,不同的自环质量 、惰性步长与个性化参数都会改变结果。Forman 曲率必须指定权重与胞腔结构,不同的权重语义也会改变结果。因此,ORC 是「图 + 测度」的函数,Forman 曲率则依赖「图 + 权重 + 胞腔」的约定,两者都不能脱离这些约定单独谈论。
理论保证与数值行为的差别同样值得注意。ORC 有流形上的局部展开、Wasserstein 收缩与谱隙下界,这些结论把它与经典几何和随机分析连接起来。Forman 曲率的优势是定义初等、计算稳定、对局部扰动不敏感,但它没有与 ORC 同等强度的连续极限定理。在数值上,无权 Forman 曲率在无三角形时只依赖度数,因此它无法区分方格网与度数相同的随机图。增强形式加入了三角形,但仍看不到四环,Balanced Forman 通过四环项修正了这一点。ORC 通过距离度量天然看到所有环,但代价是计算。
在真实网络上,两者的边排序通常呈正相关,相关强度依赖网络结构以及是否使用增强形式。Samal 等人在 2018 年的比较研究中报告了这种相关性,同时指出两者并不等价。把 Forman 当作 ORC 的廉价代理是合理的工程选择,但不应把两者的数值直接互换。
七、在机器学习中的用法
7.1 过挤压与曲率重连
消息传递网络在第 层把 -跳邻域的信息压缩进固定维度的向量。随着 增大,邻域大小可以指数增长,而隐藏状态的维度不变,远端信息只能挤过少数几条边。这种现象称为过挤压(over-squashing)。
Topping 等人在 2022 年给出了一个定量联系。记第 层的隐藏状态为 、输入为 ,他们证明 Jacobian 的绝对值满足
其中 是聚合与更新的 Lipschitz 常数, 是激活函数的 Lipschitz 常数, 是归一化邻接矩阵。负曲率的边正好对应那些使 衰减很快的瓶颈。换句话说,负曲率边是信息流动的瓶颈。
由此产生了一类重连算法。SDRF(Stochastic Discrete Ricci Flow)在每一轮随机选取一批负曲率边,向它们的局部邻域添加边,使曲率上升,类似离散版本的 Ricci 流。BORF(Batch Ollivier-Ricci Flow)把这一过程批量化,降低了大规模图上的开销。实验表明,这类方法在长程依赖任务上可以带来提升,但也会改变图的同质性,增加边数,并且需要重新计算曲率。
7.2 曲率感知的消息传递
另一类做法是把曲率直接写进消息传递的权重。一个简单的形式是
参数 的符号决定了曲率如何调节边权。 时 随 增大而减小,正曲率边被压低,负曲率边被放大,聚合会更依赖桥接边。 时方向相反,正曲率边被增强,负曲率边被抑制,聚合会更依赖团内边。选择哪一种取决于任务更看重跨社群的长程信息,还是更希望抑制少数瓶颈边对表示的支配。
这类方法没有统一的理论保证,更接近一种归纳偏置。它通常与注意力机制、边特征或位置编码结合使用,单独使用时提升有限。
7.3 数据几何与长尾结构
ORC 也可以用来描述表示空间的几何。给定数据集 与特征提取器 ,得到表示 ,在表示上构建 KNN 图,再计算每条边的曲率 。由此可以提出一些可检验的问题:正曲率区域是否对应高密度聚集,负曲率区域是否对应类别边界,曲率分布是否随训练过程发生系统性变化。
这些问题有研究价值,但不能把直觉当作结论。正曲率不等价于高密度,负曲率也不等价于类别边界。
在长尾分类中,可以观察到一个常见的经验模式。Head 类别容易形成较大的团状结构,Tail 类别容易形成稀疏的链状结构。前者倾向正曲率,后者倾向负曲率。但这只是统计倾向,不是定理。Tail 类内部的规则结构同样可能给出零曲率甚至正曲率。把曲率作为辅助描述符,而不是类别不平衡的直接诊断量,是更稳妥的用法。
小结
Ollivier-Ricci 曲率的核心操作只有一步:把点 替换成它周围的概率测度 ,把两点之间的距离替换成两个测度之间的最优传输成本。由此得到的 同时包含了距离信息与扩散信息,正、零、负分别对应邻域的收缩、保持与扩张。在光滑流形上,它经过 缩放后恢复经典 Ricci 曲率。在图上,它可以通过线性规划精确计算,并有只依赖度数的下界。
Forman-Ricci 曲率走了另一条路。它用组合关联数代替最优传输,把曲率写成度数、权重、三角形与四环的局部函数。无权形式 极其廉价,但只看得到度数。增强形式加入三角形,Balanced Forman 再加入四环,才逐步恢复对局部几何的分辨能力。
两种曲率都值得掌握,但使用时需要保持谨慎。曲率依赖定义它的测度或权重约定,不能脱离这些约定单独比较。不同文献的符号、归一化与随机游走约定也可能不同,简单随机游走版本与 Lin–Lu–Yau 的修正版本可以给出不同的数值, 就是一个清晰的例子。更重要的是,曲率是有用的归纳偏置,却不是万能的诊断工具,任何几何直觉都需要实验验证。
如果要留下一句话,那就是:ORC 把「点与点之间的距离」换成了「分布与分布之间的距离」。这个替换看似只是技术上的推广,实际上改变了我们观察离散结构的方式。用一条链概括就是:数据 → 局部概率测度 → 最优传输 → 曲率。对机器学习而言,这意味着不必只把样本看成欧氏空间中的点,也可以把它们看成某个度量测度空间中的概率结构。