Skip to content

图上的 Ricci 曲率:Ollivier 与 Forman

在离散结构(如图、网络)上定义曲率是几何深度学习、网络科学和图分析中的一个核心挑战。由于图没有传统的微分结构,我们需要通过不同的方式来「离散化」黎曼几何中的曲率概念。

在黎曼几何中,Ricci 曲率描述一束测地线在演化过程中是汇聚还是发散。它依赖切空间、联络与度量张量,看起来很难直接搬到离散对象上。Ollivier 在 2009 年给出了一种相当经济的替代方案:把「点」换成「局部概率测度」,把「沿测地线搬运切向量」换成「用最优传输搬运概率质量」。由此得到的量称为 Ollivier-Ricci 曲率(Ollivier-Ricci curvature,ORC),它对任何度量空间都有定义,因此可以直接用在图上。

Ollivier-Ricci 曲率和 Forman-Ricci 曲率是目前图上最常用的两种 Ricci 曲率离散化方法,它们源于不同的数学直觉,适用于不同的场景。

一、直觉:邻域之间的距离

设 x,yx,y 是度量空间中的两个点,记 δ=d(x,y)\delta=d(x,y)。在 xx 与 yy 附近各取一个半径为 ε\varepsilon 的小球,并在球上放置概率测度 mx,mym_x,m_y。如果空间是平坦的,把 mxm_x 搬运到 mym_y 的平均成本应当接近 δ\delta。如果空间正弯曲,例如球面,两个小球会向着彼此倾斜,最优匹配的平均位移小于 δ\delta。如果空间负弯曲,例如双曲空间,小球会背向彼此张开,平均位移大于 δ\delta。

于是可以定义

κ(x,y)=1−W1(mx,my)d(x,y),\kappa(x,y)=1-\frac{W_1(m_x,m_y)}{d(x,y)},

其中 W1W_1 是一阶 Wasserstein 距离,也就是最小平均搬运成本。比值 W1/δW_1/\delta 是邻域在运输意义下的收缩系数,1−W1/δ1-W_1/\delta 就是曲率。正、零、负分别对应收缩、保持与扩张。

这个构造有两个值得注意的特点。它既没有使用切空间,也没有要求空间光滑,只需要距离和测度。更重要的是,曲率不再是度量本身的函数,而是「度量 + 局部测度」的联合性质。后一点在图上尤其重要,因为随机游走的定义会直接改变曲率。

二、Ollivier-Ricci 曲率的定义

2.1 耦合与 Wasserstein 距离

定义 2.1(耦合与 Wasserstein-1 距离) #

设 (X,d)(X,d) 是 Polish 度量空间,μ,ν\mu,\nu 是 XX 上的两个 Borel 概率测度。若 X×XX\times X 上的概率测度 π\pi 满足

π(A×X)=μ(A),π(X×B)=ν(B)\pi(A\times X)=\mu(A),\qquad \pi(X\times B)=\nu(B)

对任意 Borel 集 A,BA,B 成立,则称 π\pi 是 μ\mu 与 ν\nu 的一个耦合,所有耦合的集合记为 Π(μ,ν)\Pi(\mu,\nu)。一阶 Wasserstein 距离定义为

W1(μ,ν)=inf⁡π∈Π(μ,ν)∫X×Xd(u,v) dπ(u,v).W_1(\mu,\nu)=\inf_{\pi\in\Pi(\mu,\nu)}\int_{X\times X} d(u,v)\,\mathrm{d}\pi(u,v).

直观上,π\pi 描述一种搬运方案,dπ(u,v)\mathrm{d}\pi(u,v) 是从 uu 搬到 vv 的质量,积分就是总运输成本。W1W_1 取所有方案中的最小值。

2.2 曲率的定义

定义 2.2(Ollivier-Ricci 曲率) #

设 (X,d)(X,d) 是度量空间。对每个 x∈Xx\in X,给定一个以 xx 为中心的概率测度 mxm_x。对任意 x≠yx\neq y,定义

κ(x,y)=1−W1(mx,my)d(x,y).\kappa(x,y)=1-\frac{W_1(m_x,m_y)}{d(x,y)}.

称 κ(x,y)\kappa(x,y) 为 mx,mym_x,m_y 在 x,yx,y 处的 Ollivier-Ricci 曲率。

测度族 {mx}x∈X\{m_x\}_{x\in X} 通常取成随机游走的一步转移分布,也可以取成小球上的均匀分布、热核分布或个性化 PageRank 分布。不同的取法给出不同的曲率,这一点在阅读文献时需要特别注意。

由定义可以直接读出三条基本性质。由于 W1≥0W_1\ge 0,恒有 κ≤1\kappa\le 1。W1W_1 关于两个测度对称,所以 κ(x,y)=κ(y,x)\kappa(x,y)=\kappa(y,x)。当 mx=mym_x=m_y 时 W1=0W_1=0,曲率取到最大值 11。

曲率的符号有明确的几何含义。κ>0\kappa>0 表示两个邻域在运输意义下彼此靠近,对应局部收缩。κ=0\kappa=0 表示运输成本恰好等于中心点之间的距离,对应局部保持。κ<0\kappa<0 表示运输成本更大,对应局部扩张。

这个定义把三个原本独立的领域接在一起。度量几何提供距离,最优传输提供比较两个测度的方法,概率论提供随机游走这一局部测度族。曲率不再需要微分结构,却仍然保留了「邻域如何形变」这一核心含义。

2.3 对偶形式

在图上直接求解 W1W_1 需要解一个线性规划。对偶形式把同一个量写成函数的上确界,往往更容易构造证明。

命题 2.3(Kantorovich-Rubinstein 对偶) #

设 (X,d)(X,d) 是 Polish 度量空间,μ,ν\mu,\nu 是概率测度。则

W1(μ,ν)=sup⁡f∈Lip⁡1(X)∫Xf d(μ−ν),W_1(\mu,\nu)=\sup_{f\in\operatorname{Lip}_1(X)}\int_X f\,\mathrm{d}(\mu-\nu),

其中 Lip⁡1(X)\operatorname{Lip}_1(X) 是 XX 上所有满足 ∣f(u)−f(v)∣≤d(u,v)|f(u)-f(v)|\le d(u,v) 的函数 ff 的集合。

在有限图上,对偶问题只有 ∣V∣|V| 个变量和 ∣E∣|E| 条边约束,因此可以精确求解,最优函数 ff 还可以当作最优性证书。后文证明下界时会反复使用这一点。

三、图上的计算

3.1 随机游走测度

设 G=(V,E)G=(V,E) 是无向简单图,deg⁡(x)\deg(x) 是节点 xx 的度数。最常用的选择是简单随机游走的一步分布。

定义 3.1(图上的随机游走测度) #

对每个 x∈Vx\in V,定义 VV 上的概率测度

mx(v)={1deg⁡(x),v∼x,0,otherwise.m_x(v)= \begin{cases} \dfrac{1}{\deg(x)}, & v\sim x,\\[4pt] 0, & \text{otherwise}. \end{cases}

也就是说,从 xx 出发均匀地选择一个邻居。

对相邻节点 x∼yx\sim y,有 dG(x,y)=1d_G(x,y)=1,于是

κ(x,y)=1−W1(mx,my).\kappa(x,y)=1-W_1(m_x,m_y).

对不相邻的节点,则需保留分母 dG(x,y)d_G(x,y)。

这里有一个容易被忽略的问题。随机游走不一定是简单随机游走。加入自环会得到惰性游走

mxα=αδx+(1−α)mx,α∈[0,1),m_x^{\alpha}=\alpha\delta_x+(1-\alpha)m_x,\qquad \alpha\in[0,1),

其中 δx\delta_x 是 xx 处的点质量。不同的 α\alpha 给出不同的曲率。Lin、Lu 与 Yau 在研究图上的 Ricci 曲率时,采用的是 α→1\alpha\to1 的极限版本,后文第 5.5 节会再回到这个约定。

3.2 几个可以手算的例子

路径图。 取一条无限路径,xx 与 yy 相邻。此时 deg⁡(x)=deg⁡(y)=2\deg(x)=\deg(y)=2,两个邻域分别是 {x−,y}\{x^-,y\} 与 {x,y+}\{x,y^+\}。最优方案把 x−x^- 送到 xx,把 yy 送到 y+y^+,每条路径的长度为 11,总成本为 11。因此 W1=1W_1=1,κ=0\kappa=0。这与平坦的直觉一致。

完全图。 在 KnK_n 中,每个节点的度数为 n−1n-1。两个相邻节点的邻域有 n−2n-2 个公共节点,这部分质量可以原地匹配。剩下的质量是 mxm_x 在 yy 处的 1/(n−1)1/(n-1) 与 mym_y 在 xx 处的 1/(n−1)1/(n-1),搬运距离为 11。因此

W1=1n−1,κ=n−2n−1.W_1=\frac{1}{n-1},\qquad \kappa=\frac{n-2}{n-1}.

当 n=3n=3 时 κ=1/2\kappa=1/2,当 n→∞n\to\infty 时 κ→1\kappa\to1。团越稠密,正曲率越强。

星形图。 设 xx 是中心,yy 是叶子。叶子的测度是 my=δxm_y=\delta_x,中心的测度均匀分布在所有叶子上。把 δx\delta_x 搬到这些叶子,每一份质量都要走距离 11,所以 W1=1W_1=1,κ=0\kappa=0。这个例子说明,度数很高并不自动意味着正曲率。

双星图。 取边 x∼yx\sim y,其中 xx 另有两个叶子邻居 a,ba,b,yy 另有两个叶子邻居 c,dc,d。此时 dx=dy=3d_x=d_y=3,并且

mx=13(δa+δb+δy),my=13(δx+δc+δd).m_x=\frac13(\delta_a+\delta_b+\delta_y),\qquad m_y=\frac13(\delta_x+\delta_c+\delta_d).

一个看似自然的方案是把 aa 送到 cc,把 bb 送到 dd,再把 yy 送到 xx。三条路径的长度分别是 3,3,13,3,1,总成本为 7/37/3。但这个方案不是最优的。更好的方案是令 y→cy\to c,a→xa\to x,b→db\to d,成本为 1+1+3=51+1+3=5,平均为 5/35/3。为确认它确实最优,取

f(x)=0,f(y)=−1,f(a)=f(b)=1,f(c)=f(d)=−2.f(x)=0,\quad f(y)=-1,\quad f(a)=f(b)=1,\quad f(c)=f(d)=-2.

容易逐边检查 ff 是 11-Lipschitz 的。于是

∫f d(mx−my)=1+1−13−0−2−23=53.\int f\,\mathrm{d}(m_x-m_y) =\frac{1+1-1}{3}-\frac{0-2-2}{3} =\frac53.

对偶下界与原始方案的上界相同,故 W1=5/3W_1=5/3,从而

κ(x,y)=1−53=−23.\kappa(x,y)=1-\frac53=-\frac23.

这个例子值得记住,因为它说明负曲率并不需要很大的图,一个很小的树状结构就可以产生明显的负曲率。

3.3 一个只依赖度数的下界

对于一般图,精确的 W1W_1 不容易手算。但相邻边的曲率有一个仅由两端度数决定的下界,证明只需要对偶形式。

定理 3.2(相邻边的度数下界) #

设 GG 是无向简单图,x∼yx\sim y 且 deg⁡(x),deg⁡(y)≥2\deg(x),\deg(y)\ge 2。采用定义 3.1 的简单随机游走测度,则

κ(x,y)≥−2(1−1deg⁡(x)−1deg⁡(y)).\kappa(x,y)\ge -2\left(1-\frac{1}{\deg(x)}-\frac{1}{\deg(y)}\right).

证明。 设 ff 是任意 11-Lipschitz 函数。由于 ∫f d(mx−my)\int f\,\mathrm{d}(m_x-m_y) 在 ff 上加常数不变,不妨设 f(x)=0f(x)=0。记 t=f(y)t=f(y)。因为 x∼yx\sim y,有 ∣t∣≤1|t|\le1。

对任意 a∈N(x)a\in N(x),由 11-Lipschitz 性得 f(a)≤f(x)+1=1f(a)\le f(x)+1=1。对任意 b∈N(y)b\in N(y),同理得 f(b)≥f(y)−1=t−1f(b)\ge f(y)-1=t-1。注意 b=xb=x 时 f(b)=0≥t−1f(b)=0\ge t-1 也成立,因为 t≤1t\le1。于是

∫f d(mx−my)≤1deg⁡(x)∑a∈N(x)f(a)−1deg⁡(y)∑b∈N(y)f(b)≤deg⁡(x)−1+tdeg⁡(x)−(deg⁡(y)−1)(t−1)deg⁡(y)=2−s+(s−1)t,\begin{aligned} \int f\,\mathrm{d}(m_x-m_y) &\le \frac{1}{\deg(x)}\sum_{a\in N(x)}f(a) -\frac{1}{\deg(y)}\sum_{b\in N(y)}f(b)\\ &\le \frac{\deg(x)-1+t}{\deg(x)} -\frac{(\deg(y)-1)(t-1)}{\deg(y)}\\ &=2-s+(s-1)t, \end{aligned}

其中

s=1deg⁡(x)+1deg⁡(y).s=\frac{1}{\deg(x)}+\frac{1}{\deg(y)}.

因为 deg⁡(x),deg⁡(y)≥2\deg(x),\deg(y)\ge2,有 s≤1s\le1,所以右端作为 tt 的函数单调不增。它在 t=−1t=-1 处取到最大值 3−2s3-2s。因此对任意 11-Lipschitz 的 ff 都有

∫f d(mx−my)≤3−2s.\int f\,\mathrm{d}(m_x-m_y)\le 3-2s.

由命题 2.3 对 ff 取上确界,得到 W1≤3−2sW_1\le 3-2s。再代入 κ=1−W1\kappa=1-W_1,即得

κ(x,y)≥1−(3−2s)=2s−2=−2(1−1deg⁡(x)−1deg⁡(y)).\kappa(x,y)\ge 1-(3-2s)=2s-2=-2\left(1-\frac{1}{\deg(x)}-\frac{1}{\deg(y)}\right).

证毕。

这个下界在双星图与 dd-正则树上都可以取等。双星图两端度数都是 33,下界给出 −2/3-2/3,恰好等于上一节算出的值。dd-正则树给出 −2+4/d-2+4/d,下面说明它确实取等。

设 TdT_d 是 dd-正则树,x∼yx\sim y。构造运输方案:令 a1→xa_1\to x,y→b1y\to b_1,其余 d−2d-2 对邻居 (ai,bi)(a_i,b_i) 两两匹配。前两条路径的长度为 11,其余路径的长度为 33,总成本为

1+1+3(d−2)=3d−4,1+1+3(d-2)=3d-4,

平均成本为 3−4/d3-4/d。另一方面,定义

f(x)=0,f(y)=−1,f(a)=1 (a∈N(x)∖{y}),f(b)=−2 (b∈N(y)∖{x}).f(x)=0,\quad f(y)=-1,\quad f(a)=1\ (a\in N(x)\setminus\{y\}),\quad f(b)=-2\ (b\in N(y)\setminus\{x\}).

在树中,aa 与 bb 的距离为 33,aa 与 yy 的距离为 22,bb 与 xx 的距离为 22,逐一检查可知 ff 是 11-Lipschitz 的。它给出的对偶值为

(d−1)−1d−0−2(d−1)d=3d−4d,\frac{(d-1)-1}{d}-\frac{0-2(d-1)}{d}=\frac{3d-4}{d},

与原始方案相同。因此

κ(x,y)=1−3d−4d=−2+4d.\kappa(x,y)=1-\frac{3d-4}{d}=-2+\frac{4}{d}.

当 d=2d=2 时回到路径图的 00。当 d=3d=3 时得到 −2/3-2/3,与双星图一致,因为双星图正是 33-正则树在边附近的截断。

顺带可以得到一个对任意相邻边都成立的下界。邻域中任意两点之间的距离不超过 33,因为

d(a,b)≤d(a,x)+d(x,y)+d(y,b)=3.d(a,b)\le d(a,x)+d(x,y)+d(y,b)=3.

所以 W1≤3W_1\le3,从而 κ≥−2\kappa\ge-2。这个界不依赖度数,但通常比度数下界更松,两者可以配合使用。

3.4 计算复杂度

精确计算 ORC 的主要开销在 W1W_1。对一条边,两侧邻域的大小分别为 deg⁡(x)\deg(x) 与 deg⁡(y)\deg(y),对应的线性规划大约有 deg⁡(x)deg⁡(y)\deg(x)\deg(y) 个变量和 deg⁡(x)+deg⁡(y)\deg(x)+\deg(y) 条边际约束。文献中常给出 O(∣E∣dmax⁡3)O(|E|d_{\max}^3) 的总复杂度估计,其中 dmax⁡d_{\max} 是最大度数。对度数很高的图,这个成本很快就会变得不可接受。

实践中常用的替代方案有几种。熵正则化的 Sinkhorn 算法把线性规划换成可并行的矩阵缩放,以近似解替代精确的 W1W_1。另一种做法是只在抽样的边或子图上计算曲率,用局部估计指导全局算法。如果愿意更换曲率定义,Forman 曲率的单边成本可以降到 O(1)O(1),Balanced Forman 曲率则是 O(dmax⁡2)O(d_{\max}^2)。

四、与经典 Ricci 曲率的关系

4.1 局部展开

ORC 之所以被称为 Ricci 曲率,不只是因为直觉相似。在光滑流形上,经过适当的缩放,它确实恢复出经典的 Ricci 曲率。

命题 4.1(Ollivier 的局部展开) #

设 MM 是 NN 维光滑黎曼流形,x∈Mx\in M,vv 是单位切向量,yy 是沿 vv 方向、与 xx 距离足够近的点。取 mxεm_x^{\varepsilon} 为测地球 B(x,ε)B(x,\varepsilon) 上的归一化黎曼体积测度,myεm_y^{\varepsilon} 同理。则当 ε→0\varepsilon\to0、d(x,y)→0d(x,y)\to0 时,

κ(x,y)=ε22(N+2)(Ric⁡(v,v)+O(ε)+O(d(x,y))).\kappa(x,y)=\frac{\varepsilon^2}{2(N+2)}\Bigl(\operatorname{Ric}(v,v)+O(\varepsilon)+O\bigl(d(x,y)\bigr)\Bigr).

这个展开有三层含义。

ORC 在固定流形上随 ε→0\varepsilon\to0 趋于零。它不是 Ricci 曲率的逐点极限,而是经过 ε2\varepsilon^2 缩放后的极限。因此 ORC 是一种「模糊化」的曲率,它看到的是一个邻域上的平均行为,而不是某一点的无穷小行为。

常数 1/(2(N+2))1/(2(N+2)) 则与测度的选择有关。如果不用球上的均匀测度,而用热核测度,常数会改变。这与前文的观察一致:ORC 是度量与测度的联合性质。

公式中的 Ric⁡(v,v)\operatorname{Ric}(v,v) 是沿 vv 方向的 Ricci 曲率。取与 vv 正交的一组单位正交基 e1,…,eN−1e_1,\dots,e_{N-1},则 Ric⁡(v,v)\operatorname{Ric}(v,v) 等于由 vv 与各个 eie_i 张成的平面的截面曲率之和。因此 ORC 捕捉的是「在与 vv 正交的各个方向上,邻域整体是收缩还是扩张」。

几个标准空间可以作为检验。半径为 RR 的球面上 Ric⁡(v,v)=(N−1)/R2\operatorname{Ric}(v,v)=(N-1)/R^2,于是 κ>0\kappa>0。欧氏空间上 Ric⁡=0\operatorname{Ric}=0,于是 κ=0\kappa=0。双曲空间上 Ric⁡<0\operatorname{Ric}<0,于是 κ<0\kappa<0。符号与直觉完全一致。

4.2 收缩性与谱隙

ORC 的另一个重要作用是控制随机游走的长期行为。下面的收缩性质是 Ollivier 理论的核心结论之一。

定理 4.2(Wasserstein 收缩) #

设 PP 是度量空间上的马尔可夫核,{mx}\{m_x\} 是它的一步转移测度。若存在 κ0≤1\kappa_0\le1 使得对任意 x≠yx\neq y 都有 κ(x,y)≥κ0\kappa(x,y)\ge\kappa_0,则对任意两个概率测度 μ,ν\mu,\nu,

W1(μP,νP)≤(1−κ0)W1(μ,ν).W_1(\mu P,\nu P)\le(1-\kappa_0)W_1(\mu,\nu).

当 κ0>0\kappa_0>0 时,上式说明随机游走把任意两个分布之间的距离按几何速率压缩。迭代 tt 步得到

W1(μPt,νPt)≤(1−κ0)tW1(μ,ν),W_1(\mu P^t,\nu P^t)\le(1-\kappa_0)^tW_1(\mu,\nu),

这就是「正曲率导致快速混合」的精确表述。对有限可逆链,还可以进一步推出谱隙的下界 λ≥κ0\lambda\ge\kappa_0。这类结论把局部几何与全局分析连接起来,也是 ORC 与单纯的图指标最重要的区别。

在连续情形,正 Ricci 曲率还推出直径上界,形式上对应 Bonnet-Myers 定理。离散版本需要额外的假设,但基本思想相同:正曲率限制空间向外扩张的速度。

五、Forman-Ricci 曲率

5.1 无权形式

Forman 曲率来自 Forman 对 CW 复形上离散 Ricci 曲率的研究。它不使用最优传输,而是直接对每个胞腔统计相邻胞腔的贡献。在图这种一维复形上,公式会退化成非常简单的形式。

定义 5.1(无权图的 Forman-Ricci 曲率) #

设 G=(V,E)G=(V,E) 是无向简单无权图,e=uv∈Ee=uv\in E。未增强的 Forman-Ricci 曲率定义为

F(e)=4−deg⁡(u)−deg⁡(v).F(e)=4-\deg(u)-\deg(v).

若把三角形视为二维胞腔并计入其贡献,则得到增强形式

Faug(e)=4−deg⁡(u)−deg⁡(v)+3te,F_{\mathrm{aug}}(e)=4-\deg(u)-\deg(v)+3t_e,

其中 tet_e 是包含边 ee 的三角形个数。

公式中的 44 可以拆成 2+1+12+1+1。边本身贡献 22,两个端点各贡献 11。每多一条与端点关联的边,就减去 11。因此,一条边的两端越「拥挤」,它的 Forman 曲率越低。

几个简单情形可以直接验证。路径图的内部边满足 F=4−2−2=0F=4-2-2=0。设星形图的中心度数为 dd,则叶子边满足 F=4−1−d=3−dF=4-1-d=3-d,中心度数越高,曲率越负。在增强形式下,完全图 KnK_n 的每条边满足 F=4−2(n−1)+3(n−2)=nF=4-2(n-1)+3(n-2)=n,数值随 nn 增大而增大。

星形图的叶子边值得与第 3.2 节的结果对照。同样的边在 ORC 下给出 κ=0\kappa=0,因为叶子的测度就是中心处的点质量,搬运成本恰好等于边长。未增强的 Forman 曲率却把它判成 3−d3-d,度数越大越负。这个差异说明,只统计度数会把「没有迂回路径、但也没有扩张」的结构误判为强负曲率。

这里需要提醒符号约定。部分文献把曲率写成 deg⁡(u)+deg⁡(v)−4\deg(u)+\deg(v)-4,与上式正好相反。比较不同论文的曲率数值之前,必须先确认符号与归一化方式。

5.2 加权形式

在实际网络中,节点和边通常带有权重。权重可以表示连接强度、通信容量、距离或相似度。Forman 曲率的加权版本把这些权重纳入同一个局部求和。

定义 5.2(加权 Forman-Ricci 曲率) #

设边 e=uve=uv 的权重为 wew_e,节点 u,vu,v 的权重分别为 wu,wvw_u,w_v。定义

F(e)=we[wuwe+wvwe−∑e′∼ue′≠ewuwewe′−∑e′∼ve′≠ewvwewe′].\begin{aligned} F(e)=w_e\Biggl[&\frac{w_u}{w_e}+\frac{w_v}{w_e}\\ &-\sum_{\substack{e'\sim u\\ e'\neq e}}\frac{w_u}{\sqrt{w_e w_{e'}}} -\sum_{\substack{e'\sim v\\ e'\neq e}}\frac{w_v}{\sqrt{w_e w_{e'}}}\Biggr]. \end{aligned}

其中第二个求和遍历与 vv 关联且不等于 ee 的边。

当所有 we,wu,wvw_e,w_u,w_v 都取 11 时,方括号内变成

1+1−(deg⁡(u)−1)−(deg⁡(v)−1)=4−deg⁡(u)−deg⁡(v),1+1-(\deg(u)-1)-(\deg(v)-1)=4-\deg(u)-\deg(v),

与定义 5.1 一致。平方根来自 Forman 原始公式中对几何平均的归一化,它保证权重的量纲在乘积中保持一致。

加权形式给了使用者很大的设计空间,但也带来一个容易出错的地方。边权的语义必须与任务匹配。如果把权重解释为「距离」,权重大表示两点相距远。如果把权重解释为「强度」,权重大表示连接紧密。两种解释下曲率的含义会反过来,使用前需要先固定语义。

5.3 有向图

对有向图,Forman 曲率需要区分入边与出边。以有向边 u→vu\to v 为例,在尾节点 uu 只统计与它同向的出边,在头节点 vv 只统计与它同向的入边。只有「同向平行」的边才参与抵消,反方向的边不参与。

在无权情形,这个约定给出

F(u→v)=4−deg⁡+(u)−deg⁡−(v),F(u\to v)=4-\deg^{+}(u)-\deg^{-}(v),

其中 deg⁡+\deg^{+} 是出度,deg⁡−\deg^{-} 是入度。这个量对信息流的汇聚与发散比较敏感。一个出度很大的源节点会把经过它的边的曲率压低,一个入度很大的汇节点也有同样的效果。

不同的实现会对「在尾节点统计入边还是出边」作出不同选择。使用现成库时,最好先用一个小图核对符号与方向约定。

5.4 节点曲率与全图曲率

边曲率可以聚合成节点曲率与全图曲率。节点曲率通常定义为与该节点关联的所有边的曲率之和

F(v)=∑e∋vF(e),F(v)=\sum_{e\ni v}F(e),

有时也取平均,以便在不同度数之间比较。全图曲率则对所有边求和或平均。

对无权、未增强的形式,全图求和有一个简洁的恒等式

∑e∈EF(e)=∑uv∈E(4−deg⁡(u)−deg⁡(v))=4∣E∣−∑v∈Vdeg⁡(v)2.\sum_{e\in E}F(e)=\sum_{uv\in E}\bigl(4-\deg(u)-\deg(v)\bigr) =4|E|-\sum_{v\in V}\deg(v)^2.

也就是说,全图曲率本质上只依赖度数的二阶矩。若使用增强形式,还需要加上三角形项的贡献。每个三角形被三条边各计一次,因此总和多出 9T9T,其中 TT 是三角形个数。

这个恒等式暴露了无权 Forman 曲率的一个根本限制:它本身不包含任何环的信息。增强形式把三角形显式计入,但仍然看不到四环。以二维方格网为例,每个内部节点的度数为 44,每条边满足

F(e)=4−4−4=−4.F(e)=4-4-4=-4.

方格网在几何上是平坦的,ORC 给出的曲率是 00,而 Forman 曲率却给出强负值。原因不是计算出错,而是公式里根本没有 44-环的信息。增强形式也救不了它,因为方格网没有三角形。这正是 Balanced Forman 曲率要解决的问题。

5.5 Balanced Forman 曲率

Topping 等人在 2022 年提出 Balanced Forman 曲率,在 Forman 的组合框架里加入三角形与四边形的贡献,使其单边成本保持在 O(dmax⁡2)O(d_{\max}^2),同时更准确地反映局部几何。

定义 5.3(Balanced Forman 曲率) #

设 GG 是无向简单无权图,i∼ji\sim j,且 min⁡{di,dj}>1\min\{d_i,d_j\}>1。记 Δij\Delta_{ij} 为包含边 ijij 的三角形集合,□i\square_i 与 □j\square_j 分别为在 ii 侧与 jj 侧基于该边、内部无对角线的四环集合,γmax⁡\gamma_{\max} 为所有节点中基于该边且经过该节点的四环数的最大值。定义

Ric⁡(i,j)=2di+2dj−2+2∣Δij∣max⁡{di,dj}+∣Δij∣min⁡{di,dj}+γmax⁡−1max⁡{di,dj}(∣□i∣+∣□j∣).\begin{aligned} \operatorname{Ric}(i,j) ={}&\frac{2}{d_i}+\frac{2}{d_j}-2 +\frac{2|\Delta_{ij}|}{\max\{d_i,d_j\}}+\frac{|\Delta_{ij}|}{\min\{d_i,d_j\}}\\ &+\frac{\gamma_{\max}^{-1}}{\max\{d_i,d_j\}}\bigl(|\square_i|+|\square_j|\bigr). \end{aligned}

若不存在四环,最后一项取 00。当 min⁡{di,dj}=1\min\{d_i,d_j\}=1 时,规定 Ric⁡(i,j)=0\operatorname{Ric}(i,j)=0。

公式可以分成三部分理解。最前面的 2di+2dj−2\frac{2}{d_i}+\frac{2}{d_j}-2 是基线,度数为 22 时为零,度数变大时变负。中间两项统计三角形,三角形越多,曲率越正,并且按两端度数做了平衡,避免高度数节点主导结果。最后一项统计四环。内部无对角线的四环说明,即使去掉边 ijij,两侧邻域仍然通过另一条长度为 33 的路径相连,因此它抵消基线的负值,使方格网回到零曲率。

几个标准图可以检验这个定义。对 dd-正则树,没有三角形也没有四环,Ric⁡=4/d−2\operatorname{Ric}=4/d-2,与第 3.3 节算出的 κ\kappa 完全一致。对二维方格网的内部边,di=dj=4d_i=d_j=4,基线为 −1-1,每条边两侧各有两个四环,最后一项为 (1/4)(2+2)=1(1/4)(2+2)=1,总和为 00,与平坦直觉一致。对 KnK_n,包含一条给定边的三角形数为 n−2n-2,代入可得 Ric⁡=n/(n−1)\operatorname{Ric}=n/(n-1)。

定理 5.4(Balanced Forman 是 ORC 的下界) #

设 GG 是无向简单无权图。对任意边 i∼ji\sim j,

κLLY(i,j)≥Ric⁡(i,j),\kappa_{\mathrm{LLY}}(i,j)\ge \operatorname{Ric}(i,j),

其中 κLLY\kappa_{\mathrm{LLY}} 是 Lin–Lu–Yau 意义下的修正 Ollivier-Ricci 曲率。

这里的 κLLY\kappa_{\mathrm{LLY}} 需要单独说明。它定义为

κLLY(x,y)=lim⁡α→11−W1(μxα,μyα)1−α,μxα=αδx+(1−α)mx.\kappa_{\mathrm{LLY}}(x,y)=\lim_{\alpha\to1}\frac{1-W_1(\mu_x^{\alpha},\mu_y^{\alpha})}{1-\alpha}, \qquad \mu_x^{\alpha}=\alpha\delta_x+(1-\alpha)m_x.

也就是说,它先把自环质量加到 α\alpha,再让 α→1\alpha\to1,并用 1−α1-\alpha 而不是 d(x,y)d(x,y) 作归一化。它与本文第 2 节定义的 κ\kappa 不一定相等。后者直接使用简单随机游走(相当于 α=0\alpha=0)并按 d(x,y)d(x,y) 归一化,而 κLLY\kappa_{\mathrm{LLY}} 是先取 α→1\alpha\to1 的极限再按 1−α1-\alpha 归一化。

以四环 C4C_4 为例。简单随机游走给出 W1=1W_1=1,所以 κ=0\kappa=0。而修正版本给出 κLLY=1\kappa_{\mathrm{LLY}}=1,恰好等于 Balanced Forman 曲率。这个例子说明,定理 5.4 不能直接套用到简单随机游走的版本上。阅读文献时先确认采用哪一种约定,是避免这类数值矛盾的可靠办法。

在计算成本上,Balanced Forman 曲率对每条边只需要枚举两端邻居的交集与局部四环,文献给出的总复杂度为 O(∣E∣dmax⁡2)O(|E|d_{\max}^2),比精确 ORC 的 O(∣E∣dmax⁡3)O(|E|d_{\max}^3) 低一档。这使它可以作为大规模图上的替代指标。

六、两种曲率的比较

它们从不同的粒度描述同一件事:一条边周围的局部结构,到底是让邻域收缩,还是让邻域扩张。

6.1 共同的几何直觉

ORC 与增强后的 Forman 曲率都把三角形视为正曲率的来源。一个三角形意味着边两端共享一个邻居,邻域在局部「折起来」了。对两端度数都大于 11 的树状桥边,两者也都给出负值。桥边两侧没有替代路径,邻域必须向外绕行,运输或组合成本都会增加。对长度至少为 55 的环与二维方格网,ORC 给出中性值,Balanced Forman 也能做到这一点。未增强的 Forman 曲率则不同,它不包含环的信息,会把这些结构误判为负曲率。

这种共同直觉使两者都可以用来定义离散 Ricci 流。给定边曲率,按 dwe/dt=−κewe\mathrm{d}w_e/\mathrm{d}t=-\kappa_e w_e 更新权重,反复迭代,负曲率的边会被压缩,正曲率的边会被保留。社群发现、图重连与网络简化都可以建立在这个流程上。

6.2 关键差异

信息范围是两者最根本的差别。ORC 使用整张图的最短路径距离,因此它能看到邻域之间的所有绕行方式。Forman 曲率只使用关联关系与局部胞腔,因此它对全局绕行不敏感。前者更「几何」,后者更「组合」。

计算成本上的差距同样明显。精确 ORC 需要对每条边解一个线性规划,成本随度数快速增长。Forman 曲率的无权形式对每条边只需读取两个度数,几乎可以视为 O(1)O(1)。Balanced Forman 处于两者之间,用局部枚举换取可接受的速度。

两者依赖的额外结构也各不相同。ORC 必须指定随机游走或局部测度,不同的自环质量 α\alpha、惰性步长与个性化参数都会改变结果。Forman 曲率必须指定权重与胞腔结构,不同的权重语义也会改变结果。因此,ORC 是「图 + 测度」的函数,Forman 曲率则依赖「图 + 权重 + 胞腔」的约定,两者都不能脱离这些约定单独谈论。

理论保证与数值行为的差别同样值得注意。ORC 有流形上的局部展开、Wasserstein 收缩与谱隙下界,这些结论把它与经典几何和随机分析连接起来。Forman 曲率的优势是定义初等、计算稳定、对局部扰动不敏感,但它没有与 ORC 同等强度的连续极限定理。在数值上,无权 Forman 曲率在无三角形时只依赖度数,因此它无法区分方格网与度数相同的随机图。增强形式加入了三角形,但仍看不到四环,Balanced Forman 通过四环项修正了这一点。ORC 通过距离度量天然看到所有环,但代价是计算。

在真实网络上,两者的边排序通常呈正相关,相关强度依赖网络结构以及是否使用增强形式。Samal 等人在 2018 年的比较研究中报告了这种相关性,同时指出两者并不等价。把 Forman 当作 ORC 的廉价代理是合理的工程选择,但不应把两者的数值直接互换。

七、在机器学习中的用法

7.1 过挤压与曲率重连

消息传递网络在第 rr 层把 rr-跳邻域的信息压缩进固定维度的向量。随着 rr 增大,邻域大小可以指数增长,而隐藏状态的维度不变,远端信息只能挤过少数几条边。这种现象称为过挤压(over-squashing)。

Topping 等人在 2022 年给出了一个定量联系。记第 rr 层的隐藏状态为 hi(r)h_i^{(r)}、输入为 xsx_s,他们证明 Jacobian 的绝对值满足

∣∂hi(r+1)∂xs∣≤(αβ)r+1(A^r+1)is,\left|\frac{\partial h_i^{(r+1)}}{\partial x_s}\right|\le(\alpha\beta)^{r+1}\bigl(\hat A^{r+1}\bigr)_{is},

其中 α\alpha 是聚合与更新的 Lipschitz 常数,β\beta 是激活函数的 Lipschitz 常数,A^\hat A 是归一化邻接矩阵。负曲率的边正好对应那些使 A^r+1\hat A^{r+1} 衰减很快的瓶颈。换句话说,负曲率边是信息流动的瓶颈。

由此产生了一类重连算法。SDRF(Stochastic Discrete Ricci Flow)在每一轮随机选取一批负曲率边,向它们的局部邻域添加边,使曲率上升,类似离散版本的 Ricci 流。BORF(Batch Ollivier-Ricci Flow)把这一过程批量化,降低了大规模图上的开销。实验表明,这类方法在长程依赖任务上可以带来提升,但也会改变图的同质性,增加边数,并且需要重新计算曲率。

7.2 曲率感知的消息传递

另一类做法是把曲率直接写进消息传递的权重。一个简单的形式是

hi(l+1)=AGG⁡({wij ϕ(hi(l),hj(l)):j∈N(i)}),wij=exp⁡(−βκ(i,j)).h_i^{(l+1)}=\operatorname{AGG}\Bigl(\bigl\{w_{ij}\,\phi(h_i^{(l)},h_j^{(l)}):j\in N(i)\bigr\}\Bigr), \qquad w_{ij}=\exp(-\beta\kappa(i,j)).

参数 β\beta 的符号决定了曲率如何调节边权。β>0\beta>0 时 wijw_{ij} 随 κ\kappa 增大而减小,正曲率边被压低,负曲率边被放大,聚合会更依赖桥接边。β<0\beta<0 时方向相反,正曲率边被增强,负曲率边被抑制,聚合会更依赖团内边。选择哪一种取决于任务更看重跨社群的长程信息,还是更希望抑制少数瓶颈边对表示的支配。

这类方法没有统一的理论保证,更接近一种归纳偏置。它通常与注意力机制、边特征或位置编码结合使用,单独使用时提升有限。

7.3 数据几何与长尾结构

ORC 也可以用来描述表示空间的几何。给定数据集 {xi}\{x_i\} 与特征提取器 fθf_\theta,得到表示 zi=fθ(xi)z_i=f_\theta(x_i),在表示上构建 KNN 图,再计算每条边的曲率 κ(zi,zj)\kappa(z_i,z_j)。由此可以提出一些可检验的问题:正曲率区域是否对应高密度聚集,负曲率区域是否对应类别边界,曲率分布是否随训练过程发生系统性变化。

这些问题有研究价值,但不能把直觉当作结论。正曲率不等价于高密度,负曲率也不等价于类别边界。

在长尾分类中,可以观察到一个常见的经验模式。Head 类别容易形成较大的团状结构,Tail 类别容易形成稀疏的链状结构。前者倾向正曲率,后者倾向负曲率。但这只是统计倾向,不是定理。Tail 类内部的规则结构同样可能给出零曲率甚至正曲率。把曲率作为辅助描述符,而不是类别不平衡的直接诊断量,是更稳妥的用法。

小结

Ollivier-Ricci 曲率的核心操作只有一步:把点 xx 替换成它周围的概率测度 mxm_x,把两点之间的距离替换成两个测度之间的最优传输成本。由此得到的 κ=1−W1/d\kappa=1-W_1/d 同时包含了距离信息与扩散信息,正、零、负分别对应邻域的收缩、保持与扩张。在光滑流形上,它经过 ε2\varepsilon^2 缩放后恢复经典 Ricci 曲率。在图上,它可以通过线性规划精确计算,并有只依赖度数的下界。

Forman-Ricci 曲率走了另一条路。它用组合关联数代替最优传输,把曲率写成度数、权重、三角形与四环的局部函数。无权形式 F(e)=4−deg⁡(u)−deg⁡(v)F(e)=4-\deg(u)-\deg(v) 极其廉价,但只看得到度数。增强形式加入三角形,Balanced Forman 再加入四环,才逐步恢复对局部几何的分辨能力。

两种曲率都值得掌握,但使用时需要保持谨慎。曲率依赖定义它的测度或权重约定,不能脱离这些约定单独比较。不同文献的符号、归一化与随机游走约定也可能不同,简单随机游走版本与 Lin–Lu–Yau 的修正版本可以给出不同的数值,C4C_4 就是一个清晰的例子。更重要的是,曲率是有用的归纳偏置,却不是万能的诊断工具,任何几何直觉都需要实验验证。

如果要留下一句话,那就是:ORC 把「点与点之间的距离」换成了「分布与分布之间的距离」。这个替换看似只是技术上的推广,实际上改变了我们观察离散结构的方式。用一条链概括就是:数据 → 局部概率测度 → 最优传输 → 曲率。对机器学习而言,这意味着不必只把样本看成欧氏空间中的点,也可以把它们看成某个度量测度空间中的概率结构。

甘肃兰州