《Understanding over-squashing and bottlenecks on graphs via curvature》论文浅析

论文传送门：click here

论文简述

本文是ICLR 2022中的一篇高分工作（openreview：10/8/8/8）。

本文从理论上提出了一种Ricci曲率计算方法，并根据对其的分析指出重要结论：负曲率是导致瓶颈的原因。而后将其与Cheeger constant联系，说明了他们一定程度上是比较相似的，后期也使用Cheeger constant来说明随机游走重建方法的劣势。

根据Ricci曲率的计算方法与得到的结论，文章提出了一种仅仅基于图结构的图重建方法。此外，文章对当前基于随机游走的方法进行了分析，说明其并不能消除瓶颈效应。

最后通过实验证明了方法的有效性。

与我之前介绍的ICML2024论文不同，那一篇只基于feature而不用structure，本篇只基于原始structure而不基于feature。

本文内容实在是太丰富且深入了。因此这里仅对文章的核心内容简单聊个大概。

Balanced Forman curvature

这个定义是比较复杂的，我也不好简单对其进行描述，因此将原文的内容在这里展示。其中每一条每一句对理解都很重要。特别要搞清楚里面每个变量是怎么算出来的。

曲率反映了空间的性质，曲率大于0那么平行线会相交，等于0则距离不变，小于零会发散。分别对应着球形空间、平面和双曲空间：

曲率与瓶颈

常见的信息传递范式如下：
$$
h_i^{(\ell+1)}=\phi_\ell\left(h_i^{(\ell)},\sum_{j=1}^n\hat A_{ij}\psi_\ell(h_i^{(\ell)},h_j^{(\ell)})\right)
$$
存在点 $i$ 二阶邻居的一个子集满足如下条件：

当 $\delta$ 越小，则导数绝对值越小，即点 $i$ 对 $k$ 的影响越小——信息瓶颈。又因为Ricci曲率本身有性质 $Ric(i,j)>-2$，因此根据 $(ii)$ 可知 $\delta$ 越小也就代表着更大的负曲率。从而得到文章中可能是最重要的一个结论：

Cheeger constant

图的spectral gap可以解释为图被划分为两个社区的拓扑障碍，这个量与图瓶颈有关。因此其应该可以由曲率控制。

从一个直观的解释开始：假设我们得到一个图 $G$，其中两个社区由少数边分隔。在这种情况下，我们看到图可以很容易地断开连接——这就是一个瓶颈。

具体度量方法为：

更进一步的，作者通过一些定理与推导，得到：曲率的正下界为我们提供了对 $h_G$ 的控制，即对图的spectral gap的控制。

根据Ricci曲率的图结构改造方法

直观来看，本方法就是干了如下的事：

伪代码为：

简单来说，主要做了两件事：

• 以添加边后Ricci增益为度量，进行一定概率的加边。大的Ricci曲率增益有更高可能性被添加新边，反之更小概率。
• 减少曲率过大的边缘。

其中 $B_1(i)$ 代表的是到 $i$ 距离小于等于1的点的集合，其实就是一阶邻居加自己，核心其实是添加三元环或四元环，这些变量在Ricci曲率计算中起着重要的作用。

经过这样操作后，大大减少了负曲率的数量，同时减少过大正曲率，让整体曲率分布较为集中。

从图结构保存的角度来讲，主要实现了两点（原文）：

• Theorem 4 tells us how to do the rewiring under such constraints in order to best address the over-squashing: the topological modifications need to be localized around the most negatively-curved edges.
• Secondly, we also point out that $Ric(i, j) < −2 + \delta$ implies that $\min\{di, dj\} > 2/\delta$. Therefore, if we mostly modify the edge set at those nodes $i, j$ joined by an edge with large negative curvature, then we are perturbing nodes with high degree where such a change is relatively insignificant, and thus overall statistical properties of the rewired graph such as degree distribution are likely to be better preserved.

从结果上来看，本方法得到的度分布与原图是很像的，并不像其他方法一般大大改变了度的分布。因此这也反映出本方法能够较好的保留原图的信息。

为什么随机游走方法无法解决瓶颈问题

随机游走模型为：
$$
R_{\alpha}:=\sum_{k=0}^{\infty}\theta_k^{PPR}(D^{-1}A)^k=\alpha\sum_{k=0}^{\infty}\left((1-\alpha)(D^{-1}A)\right)^k
$$
其中 $\alpha$ 是停机概率，即当前状态有 $\alpha$ 的可能不继续游走，$1-\alpha$ 的概率继续游走。

作者此时就用到了之前提到的Cheeger constant。给出游走后的一个上界。

文章指出这种方法优先在community内部进行加边操作而非community间，这也就代表它不会处理掉瓶颈问题。