《Weisfeiler and Leman Go Neural Higher-order Graph Neural Networks》阅读笔记

最新推荐文章于 2025-03-07 20:58:11 发布

斯曦巍峨

最新推荐文章于 2025-03-07 20:58:11 发布

阅读量1.3k

点赞数

分类专栏： Graph Learning

本文链接：https://blog.csdn.net/qq_42103091/article/details/126294278

版权

Graph Learning 专栏收录该内容

26 篇文章

订阅专栏

一.论文概述

本文阐明了GNN和WL Test的联系，并基于此提出了 $k$ -GNNs，该模式是 $k$ -WL在GNN上的泛化。另外，作者还提出了多粒度的层次 $k$ -GNN。在分类和回归任务的实验结果表明， $k$ -GNNs比1-GNN的表达能力更强。

二.预备知识

2.1 符号说明

符号	说明
$G = (V, E)$	图，其中 $\subseteq\{\{u, v\} \subseteq V \mid u \neq v\}$
$N (v)$	节点 $v$ 的邻域
$G[S]=(S, E_{S})$	$\subseteq V(G)$ 对应的诱导子图
$\Sigma$	节点上色函数
$\operatorname{graph}(G, l)$	上色/标记过的图，其中 $l$ 便是节点上色函数
$l (v)$	节点 $v$ 的标签或颜色
$\sqsubseteq d$	节点着色 $c$ 细化（refine）了另一个节点着色 $d$ ，当前仅当对任意的 $\in V(G)$ ， $c (v) = c (w)$ 则表明 $d (v) = d (w)$
$\equiv d$	$\sqsubseteq d$ 且 $\sqsubseteq c$
$\subseteq V(G)$	一个节点着色 $c$ 的颜色类（最大节点子集），对于任意 $\in Q$ ，都有 $c (v) = c (w)$
$[S]^{k}={U \subseteq S
$\{\{\ldots\}$	多集

图同构：两个图 $G$ 和 $H$ 称为同构图，当且仅当存在一个双射函数 $\varphi$ ，能将 $G$ 中的每个节点都一一对应到 $H$ 的每个节点，使得对于 $G$ 中的边 $(u, v)$ 在图 $H$ 中存在边 $(\varphi(u), \varphi(v))$ 。若 $G$ 和 $H$ 同构，则可以写为 $\simeq H$ 。

1-WL Test

图源：维基百科图同构

2.2 Weisfeiler-Leman算法

1-WL算法：对于标记过的（labeled）图 $(G, l)$ ，在每轮迭代 $\geq 0$ 中，1-WL会依据上一轮迭代的着色来计算本轮新的节点着色。在第 $0$ 次迭代时（初始时），设置 $c_l^{(0)} = l$ ，在第 $t$ 次迭代中，每个节点都会收集其邻居节点的着色：
$c_{l}^{(t)}(v)=\operatorname{HASH}\left(\left(c_{l}^{(t-1)}(v),\left\{\left\{c_{l}^{(t-1)}(u) \mid u \in N(v)\right\}\right)\right)\right.$
其中 $\text{HASH}$ 函数会将每个节点收集的不同的着色（来自第 $t - 1$ 轮）都映射为一个新的没有出现过的值（颜色）。重复上述过程，在达到稳定后，若两个图的颜色分布一致，则表明两个图是同构的。1-WL算法并不能区分所有的非同构图，例如：

1-wl-unable

图源自：Weisfeiler-Lehman图同构测试及其他

$k$ -WL算法：1-WL的推广，它为节点的 $k$ 元组着色。 $k$ 元组 $s=(s_{1}, \ldots, s_{k})$ 的第 $j$ 个邻域的定义：
$N_{j}(s)=\left\{\left(s_{1}, \ldots, s_{j-1}, r, s_{j+1}, \ldots, s_{k}\right) \mid r \in V(G)\right\}$
也就是说， $s$ 的第 $j$ 个邻域是通过用 $V (G)$ 中的每个节点来替换 $s$ 中的第 $j$ 个分量（元素）来获取的。在第0次迭代中，算法用原子类型（atomic type）来标记每个 $k$ 元组。对于两个 $k$ 元组 $s$ 和 $s^{\prime}$ ，若其诱导产生的子图同构，则其标记为相同的颜色。对于 $t > 0$ 次迭代，定义
$C_{j}^{(t)}(s)=\mathrm{HASH}\left(\left\{\left\{c_{l, k}^{(t-1)}\left(s^{\prime}\right) \mid s^{\prime} \in N_{j}(s)\right\}\right\}\right),$
则
$c_{k, l}^{(t)}(s)=\operatorname{HASH}\left(\left(c_{k, l}^{(t-1)}(s),\left(C_{1}^{(t)}(s), \ldots, C_{k}^{(t)}(s)\right)\right)\right.$

2.3 图神经网络

令 $(G, l)$ 为标记的图，其初始节点着色为 $f^{(0)}: V(G) arrow \mathbb{R}^{1 \times d}$ ，其与 $l$ 一致，即对于任意节点 $u, v$ ，若 $f^{(0)}(u)=f^{(0)}(v)$ ，则必须满足条件 $l (u) = l (v)$ 。作者将GNN的传播规则表达为：
$f^{(t)}(v)=\sigma\left(f^{(t-1)}(v) \cdot W_{1}^{(t)}+\sum_{w \in N(v)} f^{(t-1)}(w) \cdot W_{2}^{(t)}\right)$
其中 $\sigma$ 常用ReLU， $W$ 为权重矩阵。

2.4 1-WL和1-GNNs间的联系

结论：1-GNNs的表达能力上限为1-WL算法。

三. $k$ 维图神经网络

作者基于 $k$ -WL提出了 $k$ -GNNs。令 $s=\{s_{1}, \ldots, s_{k}\}$ 表示一个包含 $k$ 个节点的集合，其邻域可以定义为：
$N(s)=\left\{t \in[V(G)]^{k}|| s \cap t \mid=k-1\right\} .$

上式用通俗的话来说就是， $s$ 的邻居指与 $s$ 有仅仅有 $k - 1$ 个相同节点的 $k$ -set。

$s$ 的邻域可以划分为：

局部邻域 $N_{L}(s)$ ：由 $\ t s \backslash t$ 间存在边的 $t$ 组成， $\in N(S)$ 。
全局邻域 $N_{G}(s)$ ： $\ N L ( s ) N(s) \backslash N_{\mathrm{L}}(s)$

基于上述定义，下面给出 $k$ -GNN的传播公式：
$f_{k}^{(t)}(s)=\sigma\left(f_{k}^{(t-1)}(s) \cdot W_{1}^{(t)}+\sum_{u \in N_{L}(s) \cup N_{G}(s)} f_{k}^{(t-1)}(u) \cdot W_{2}^{(t)}\right)$
对于该传播公式的第二部分，作者提出可以将局部领域和全局领域分开聚合。另外，考虑到GNN的扩展性和过拟合问题，作者提出了局部 $k$ -GNNs，即不聚合全局邻居：
$f_{k, \mathrm{~L}}^{(t)}(s)=\sigma\left(f_{k, \mathrm{~L}}^{(t-1)}(s) \cdot W_{1}^{(t)}+\sum_{u \in N_{L}(s)} f_{k, \mathrm{~L}}^{(t-1)}(u) \cdot W_{2}^{(t)}\right)$

层次变体（Hierarchical Variant）：作者提出可以将不同粒度的表示进行组合，作者设置 $k$ 值不同大小的 $k$ -GNN，然后更高层次（ $k$ 值更大）的 $k$ -GNN，可以组合低层次 $k$ -GNN得到的中间表示，即：
$f_{k}^{(0)}(s)=\sigma\left(\left[f^{\text {iso }}(s), \sum_{u \subset s} f_{k-1}^{\left(T_{k-1}\right)}(u)\right] \cdot W_{k-1}\right)$
其中方括号表示的是拼接操作。层次 $k$ -GNN模块可视化如下所示：