《Delaunay Graph：Addressing Over-Squashing and Over-Smoothing Using Delaunay Triangulation》论文解读

2024-08-09

深度学习 / 图神经网络

字数统计: 1.2k | 阅读时长≈ 4 分钟

论文传送门：click here

code：Delaunay Graph(github)

论文动机

本文是来自2024ICML的论文。

图神经网络在计算节点的特征时采用了聚合的思路，但随着gnn层数的增长，会面对如下两个问题：

Over-smoothing：如果GNN层很深的话，随着聚合节点的不断扩散，任意两个节点所共享的邻居就会非常多（感受野重叠），导致这两个节点的嵌入非常相似。
Over-Squashing：随着层数的增加，一个结点的k-hop邻居的数量将会呈指数的形式增长，但是与前几层gnn相比，更多的信息被压缩到了一个定长的向量中，这就是 over squashing。

本文就针对这两个现象，通过改变图结构来得到更好的gnn效果。

与前人的工作不同，此工作不需要原始的图结构信息，即仅根据feature即可对图结构进行重构。

本工作从曲率的角度出发，通过引入Delaunay rewiring方法来使得最大化曲率。

方法论

曲率计算方式

Augmented Forman Curvature：此种曲率度量建议考虑图中的三角形来扩展 Forman 的曲率，以使其更具表现力。对于无向图，边 $e_{ij}$ 的曲率 $c_{ij}$ 计算如下:
$$
c_{ij}=4-d_i-d_j+3m
$$
其中 $m$ 是包含 $e_{ij}$ 的三角形数。

Balanced Forman Curvature：考虑了四元环：
$$
c_{ij}=\frac2{d_i}+\frac2{d_i}-2\frac m{\max(d_i,d_j)}+\frac m{\min(d_i,d_j)} + \frac {(\Gamma_{max})^{-1}}{\max(d_i,d_j)}(\gamma_i+\gamma_j)
$$

$\Gamma_{max}(i,j)$ 代表以 $e_{ij}$ 为边且过相同其它节点的四元环数目的最大值
$\gamma_i$ 代表以 $e_{ij}$ 为边，参与到形成无对角线的四元环中 $i$ 的邻居的数目

这篇论文有详细的介绍。

Delaunay三角剖分

对于 $d$ 维欧几里得空间中的一组点集合 $P$，Delaunay 三角剖分表示为 $DT (P )$，是一个三角剖分，其中 $P$ 中没有点位于 $DT (P)$ 中任何 d-单纯形的环绕超球面内。

网上资料有如下描述：

这种剖分方法有两点好处：

最大化由一组点形成的三角形的角度，努力创建尽可能接近等边三角形。（最大化三角形中最小角度的读书）
它确保每个三角形的外接圆不包含集合中的其他点

而这导致：两个节点越像，则越可能在一个三角形内。

为了缓解Over-Squashing的问题，我们希望减少负弯曲边的数量。根据曲率的许多定义，入射在边缘上的三角形数量 $m$ 在增加边缘曲率方面起着重要作用。应用三角剖分可以最大化上述两个曲率的值，同时确保最大团大小为 3。

实验流程

整体流程：首先对feature进行GNN编码，对得到的编码使用UMAP方法进行降为，对降维后的数据进行Delaunay三角剖分，最终在新的图结构上进行GNN的编码与预测。

为什么不直接对feature进行降维？因为作者发现这样的效果不好：

实验设置与结果

初步检验图结构的有效性

Homophily：图的同质性在确定节点分类任务体系结构的效率方面起着至关重要的作用。且有方法可以度量。对新得到的图结构计算其同质性，能够发现有极大的改善——一定程度上证明了方法的有效性。此外边的数量也大大减少。

Ollivier curvature：使用Olliver的曲率(Ollivier, 2007)来统计图的曲率分布，因为它是有界的，更容易解释。在三角剖分之后构建的图，删除了自然高度负弯曲的边缘，这些边缘负责瓶颈（Ttopping 等人，2022），减轻Over-Squashing；得到的新图不具有强正弯曲的边缘，减轻Over-Smoothing。