一.文章概述
现如今存在许多工作探索GNN的表达能力，然而对于其中大多数方法，仍然缺乏对它们可以系统地和可证明地获取哪些额外表达力的深刻理解。在本文中，作者通过图双连通性（biconnectivity）引入一类新的表达能力度量，并指出现有大部分关于GNN表达能力的工作无法表达此类指标。之后，作者提出了GD-WL（Generalized Distance Weiseiler-Lehman），它能表达所有双连通性度量。作者通过类似Transformer的体系结构实现 GD-WL，该体系结构保留了表达能力并能并行。最后在合成数据集和真实世界数据集上的实验证明了该方法的有效性。
二.研究动机
在GNN领域，MPNN方面的工作很多，但其表达能力的上限为1-WL。为获取表达能力更强的GNN，有部分工作开始设计能与高阶WL Test匹配的GNN。这类工作在获取更强表达能力的同时也带来了高额的计算/内存成本。然而，这类工作的大多数主要是通过给出WL算法无法区分的toy example来证明其表现力。从理论上讲，目前还不清楚它们能系统地、可证明地获得什么样的额外表达力。此外，除了WL Test外，仍然缺乏原则性和令人信服的度量标准来正式测量表达能力，并指导可证明更好的GNN架构的设计。
为此，作者从图biconnectivity的角度，系统地研究了expressive GNNs的设计问题。
Biconnectivity通过将图分解为不连通的子连通分量（sub-component），并通过cut vertices/edges来将它们连接起来，形成树结构
（示意参见下图）。可见Biconnectivity能够捕获图的内在结构。
本文的主要贡献是给出了原则性的和高效的方法来设计能表达biconnectivity的GNNs。
三.预备知识
本文主要研究
无自环的简单图
G
=
(
V
,
E
)
G=(\mathcal{V},\mathcal{E})
G
=
(
V
,
E
)
。
Path
：节点元组
P
=
(
u
0
,
⋯
,
u
d
)
P=\left(u_0, \cdots, u_d\right)
P
=
(
u
0
,
⋯
,
u
d
)
，其满足
{
u
i
−
1
,
u
i
}
∈
E
\left\{u_{i-1}, u_i\right\} \in \mathcal{E}
{
u
i
−
1
,
u
i
}
∈
E
。若元组中没有重复节点，则称该Path为简单Path。
Induced subgraph
：由顶点子集
S
⊂
V
\mathcal{S} \subset \mathcal{V}
S
⊂
V
导出的子图
G
[
S
]
=
(
S
,
E
S
)
G[\mathcal{S}]=\left(\mathcal{S}, \mathcal{E}_{\mathcal{S}}\right)
G
[
S
]
=
(
S
,
E
S
)
，其中
E
S
:
=
{
{
u
,
v
}
∈
E
:
u
,
v
∈
S
}
\mathcal{E}_{\mathcal{S}}:=\{\{u, v\} \in \mathcal{E}: u, v \in \mathcal{S}\}
E
S
:=
{
{
u
,
v
}
∈
E
:
u
,
v
∈
S
}
。
Connectivity
：称图
G
G
G
是连通的，当前仅当图上任意两个节点
u
,
v
∈
V
u,v \in \mathcal{V}
u
,
v
∈
V
间都存在Path。称顶点子集
S
⊂
V
\mathcal{S} \subset \mathcal{V}
S
⊂
V
是
G
G
G
的连通组件，当前仅当
G
[
S
]
G[\mathcal{S}]
G
[
S
]
是连通的且不存在超集
T
⊋
S
\mathcal{T} \supsetneq \mathcal{S}
T
⊋
S
使得
G
[
T
]
G[\mathcal{T}]
G
[
T
]
是连通的。用
C
C
(
G
)
\mathrm{CC}(G)
CC
(
G
)
表示所有的连通组件子集，实际上
C
C
(
G
)
\mathrm{CC}(G)
CC
(
G
)
就是对顶点集
V
\mathcal{V}
V
的划分。
Biconnectivity
：若删除顶点
v
∈
V
v \in \mathcal{V}
v
∈
V
会增加连通分量数，即
∣
CC
(
G
[
V
\
{
v
}
]
)
∣
>
∣
C
C
(
G
)
∣
|\operatorname{CC}(G[\mathcal{V} \backslash\{v\}])|>|\mathrm{CC}(G)|
∣
CC
(
G
[
V
\
{
v
}])
∣
>
∣
CC
(
G
)
∣
，则称顶点
v
v
v
为cut vertex。若图是连通的且没有cut vertex，则称图是vertex-biconnected。称顶点子集
S
⊂
V
\mathcal{S} \subset \mathcal{V}
S
⊂
V
是图
G
G
G
的vertex-biconnected组件，当前仅当
G
[
S
]
G[\mathcal{S}]
G
[
S
]
是vertex-biconnected且不存在超集
T
⊋
S
\mathcal{T} \supsetneq \mathcal{S}
T
⊋
S
，使得
G
[
T
]
G[\mathcal{T}]
G
[
T
]
是vertex-biconnected。cut edge的定义与cut vertex的定义类似。最后作者用
BCC
V
(
G
)
\operatorname{BCC}^{\mathrm{V}}(G)
BCC
V
(
G
)
（resp.
B
C
C
E
(
G
)
\mathrm{BCC}^{\mathrm{E}}(G)
BCC
E
(
G
)
）表示vertex-biconnected组件集（resp edge-biconnected组件集）。
将biconnected组件和cut vertices/edges连接起来形成的树结构被称之为
block cut tree
。
Block cut-edge tree
：图
G
=
(
V
,
E
)
G=(\mathcal{V}, \mathcal{E})
G
=
(
V
,
E
)
上的block cut-edge tree定义为
BCETree
(
G
)
:
=
(
BCC
E
(
G
)
,
E
E
)
\operatorname{BCETree}(G):=\left(\operatorname{BCC}^{\mathrm{E}}(G), \mathcal{E}^{\mathrm{E}}\right)
BCETree
(
G
)
:=
(
BCC
E
(
G
)
,
E
E
)
，其中
E
E
:
=
{
{
S
1
,
S
2
}
:
S
1
,
S
2
∈
B
C
C
E
(
G
)
,
∃
u
∈
S
1
,
v
∈
S
2
,
s.t.
{
u
,
v
}
∈
E
}
\mathcal{E}^{\mathrm{E}}:=\left\{\left\{\mathcal{S}_1, \mathcal{S}_2\right\}: \mathcal{S}_1, \mathcal{S}_2 \in \mathrm{BCC}^{\mathrm{E}}(G), \exists u \in \mathcal{S}_1, v \in \mathcal{S}_2, \text { s.t. }\{u, v\} \in \mathcal{E}\right\}
E
E
:=
{
{
S
1
,
S
2
}
:
S
1
,
S
2
∈
BCC
E
(
G
)
,
∃
u
∈
S
1
,
v
∈
S
2
,
s.t.
{
u
,
v
}
∈
E
}
Block cut-vertex-tree
：图
G
=
(
V
,
E
)
G=(\mathcal{V}, \mathcal{E})
G
=
(
V
,
E
)
上的block cut-vertex tree定义为
BCVTree
(
G
)
:
=
(
B
C
C
V
(
G
)
∪
V
Cut
,
E
V
)
\operatorname{BCVTree}(G):=\left(\mathrm{BCC}^{\mathrm{V}}(G) \cup \mathcal{V}^{\text {Cut }}, \mathcal{E}^{\mathrm{V}}\right)
BCVTree
(
G
)
:=
(
BCC
V
(
G
)
∪
V
Cut
,
E
V
)
，其中
V
Cut
⊂
V
\mathcal{V}^{\text {Cut }} \subset \mathcal{V}
V
Cut
⊂
V
是图
G
G
G
中所有cut vertices组成的集合，并且
E
V
:
=
{
{
S
,
v
}
:
S
∈
BCC
V
(
G
)
,
v
∈
V
C
u
t
,
v
∈
S
}
.
\mathcal{E}^{\mathrm{V}}:=\left\{\{\mathcal{S}, v\}: \mathcal{S} \in \operatorname{BCC}^{\mathrm{V}}(G), v \in \mathcal{V}^{\mathrm{Cut}}, v \in \mathcal{S}\right\} .
E
V
:=
{
{
S
,
v
}
:
S
∈
BCC
V
(
G
)
,
v
∈
V
Cut
,
v
∈
S
}
.
定理
：与图biconnectivity相关的问题都包括识别所有的cut vertices/edges、寻找所有的biconnected组件和构建block cut tree都可以使用深度优先搜索算法在
Θ
(
∣
V
∣
+
∣
E
∣
)
\Theta(|\mathcal{V}|+|\mathcal{E}|)
Θ
(
∣
V
∣
+
∣
E
∣
)
的复杂度内解决。
Graph Isomorphism
：若图
G
=
(
V
G
,
E
G
)
G=\left(\mathcal{V}_G, \mathcal{E}_G\right)
G
=
(
V
G
,
E
G
)
和图
H
=
(
V
H
,
E
H
)
H=\left(\mathcal{V}_H, \mathcal{E}_H\right)
H
=
(
V
H
,
E
H
)
是同构的（
G
≃
H
G \simeq H
G
≃
H
），则存在一个双向映射（bijective mapping）
f
:
V
G
→
V
H
f: \mathcal{V}_G \rightarrow \mathcal{V}_H
f
:
V
G
→
V
H
，使得对任意节点
u
,
v
∈
V
G
,
{
u
,
v
}
∈
E
H
u, v \in \mathcal{V}_G,\{u, v\} \in \mathcal{E}_H
u
,
v
∈
V
G
,
{
u
,
v
}
∈
E
H
，有
{
f
(
u
)
,
f
(
v
)
}
∈
E
H
\{f(u), f(v)\} \in \mathcal{E}_H
{
f
(
u
)
,
f
(
v
)}
∈
E
H
。
Color refinement algorithm
：给定输入图
G
G
G
，颜色集
C
\mathcal{C}
C
，输出颜色映射
χ
G
:
V
G
→
C
\chi_G: \mathcal{V}_G \rightarrow \mathcal{C}
χ
G
:
V
G
→
C
。一个合法的颜色细化算法必须保持同构下的不变性，即对同构中的双向映射
f
f
f
和任意节点
u
∈
V
G
u\in \mathcal{V}_G
u
∈
V
G
，有
χ
G
(
u
)
=
χ
H
(
f
(
u
)
)
\chi_G(u)=\chi_H(f(u))
χ
G
(
u
)
=
χ
H
(
f
(
u
))
。因此颜色映射可以作为图同构的必要测试，即比较多集
{
{
χ
G
(
u
)
:
u
∈
V
G
}
}
\left\{\left\{\chi_G(u): u \in \mathcal{V}_G\right\}\right\}
{
{
χ
G
(
u
)
:
u
∈
V
G
}
}
和
{
{
χ
H
(
u
)
:
u
∈
V
H
}
}
\left\{\left\{\chi_H(u): u \in \mathcal{V}_H\right\}\right\}
{
{
χ
H
(
u
)
:
u
∈
V
H
}
}
，我们称之为图表示。相似地，
χ
G
(
u
)
\chi_G(u)
χ
G
(
u
)
可以被看作节点
u
∈
V
G
u \in \mathcal{V}_G
u
∈
V
G
的特征，
{
{
χ
G
(
u
)
,
χ
G
(
v
)
}
}
\left\{\left\{\chi_G(u), \chi_G(v)\right\}\right\}
{
{
χ
G
(
u
)
,
χ
G
(
v
)
}
}
表示边
{
u
,
v
}
∈
E
G
\{u, v\} \in \mathcal{E}_G
{
u
,
v
}
∈
E
G
的特征。
问题设置
：本篇论文聚焦于如下三种类型的问题：
-
对任意图
GG
G
和
HH
H
，若
GG
G
是vertex/edge-biconnected，但
HH
H
不是，则可以通过颜色细化算法来区分。 - 区分cut vertices和cut edges。
- 区分block cut-vertex/edge tree。
四.GD-WL Test
受之前工作的启发，作者研究是否在聚合过程中加入距离是否对解决biconnectivity问题很重要。为此，作者提出了一种新的颜色细化框架GD-WL，其更新规则为：
χ
G
t
(
v
)
:
=
hash
(
{
{
(
d
G
(
v
,
u
)
,
χ
G
t
−
1
(
u
)
)
:
u
∈
V
}
}
)
,
\chi_G^t(v):=\operatorname{hash}\left(\left\{\left\{\left(d_G(v, u), \chi_G^{t-1}(u)\right): u \in \mathcal{V}\right\}\right\}\right),
χ
G
t
(
v
)
:=
hash
(
{
{
(
d
G
(
v
,
u
)
,
χ
G
t
−
1
(
u
)
)
:
u
∈
V
}
}
)
,
其中
d
G
d_G
d
G
可以为任意距离度量。完整的算法为：
SPD-WL for edge-biconnectivity
SPD-WL指选择
最短路径距离（shortest path distance）
作为距离度量，SPD-WL的传播规则可以表示为：
χ
G
t
(
v
)
:
=
hash
(
χ
G
t
−
1
(
v
)
,
{
{
χ
G
t
−
1
(
u
)
:
u
∈
N
G
(
v
)
}
}
,
{
{
χ
G
t
−
1
(
u
)
:
dis
G
(
v
,
u
)
=
2
}
}
,
⋯
,
{
{
χ
G
t
−
1
(
u
)
:
dis
G
(
v
,
u
)
=
n
−
1
}
,
,
{
{
χ
G
t
−
1
(
u
)
:
dis
G
(
v
,
u
)
=
∞
}
}
)
.
\begin{aligned} & \chi_G^t(v):=\operatorname{hash}\left(\chi_G^{t-1}(v),\left\{\left\{\chi_G^{t-1}(u): u \in \mathcal{N}_G(v)\right\}\right\},\left\{\left\{\chi_G^{t-1}(u): \operatorname{dis}_G(v, u)=2\right\}\right\},\right. \\ & \cdots,\left\{\left\{\chi_G^{t-1}(u): \operatorname{dis}_G(v, u)=n-1\right\},,\left\{\left\{\chi_G^{t-1}(u): \operatorname{dis}_G(v, u)=\infty\right\}\right\}\right) . \end{aligned}
χ
G
t
(
v
)
:=
hash
(
χ
G
t
−
1
(
v
)
,
{
{
χ
G
t
−
1
(
u
)
:
u
∈
N
G
(
v
)
}
}
,
{
{
χ
G
t
−
1
(
u
)
:
dis
G
(
v
,
u
)
=
2
}
}
,
⋯
,
{
{
χ
G
t
−
1
(
u
)
:
dis
G
(
v
,
u
)
=
n
−
1
}
,,
{
{
χ
G
t
−
1
(
u
)
:
dis
G
(
v
,
u
)
=
∞
}
}
)
.
根据该公式可知SPD-WL显然比1-WL更具表达能力，因为它额外聚合了
k
k
k
-hop邻居。作者证明
SPD-WL完全表达了edge biconnectivity
。
定理
：令
G
=
(
V
G
,
E
G
)
G=\left(\mathcal{V}_G, \mathcal{E}_G\right)
G
=
(
V
G
,
E
G
)
和
H
=
(
V
H
,
E
H
)
H=\left(\mathcal{V}_H, \mathcal{E}_H\right)
H
=
(
V
H
,
E
H
)
为两个图，
χ
G
\chi_G
χ
G
和
χ
H
\chi_H
χ
H
分别为其对应的颜色映射，则如下成立：
-
对任意边
{w
1
,
w
2
}
∈
E
G
\left\{w_1, w_2\right\} \in \mathcal{E}_G
{
w
1
,
w
2
}
∈
E
G
和
{x
1
,
x
2
}
∈
E
H
\left\{x_1, x_2\right\} \in \mathcal{E}_H
{
x
1
,
x
2
}
∈
E
H
，若
{{
χ
G
(
w
1
)
,
χ
G
(
w
2
)
}
}
=
{
{
χ
H
(
x
1
)
,
χ
H
(
x
2
)
}
}
\left\{\left\{\chi_G\left(w_1\right), \chi_G\left(w_2\right)\right\}\right\}= \left\{\left\{\chi_H\left(x_1\right), \chi_H\left(x_2\right)\right\}\right\}
{
{
χ
G
(
w
1
)
,
χ
G
(
w
2
)
}
}
=
{
{
χ
H
(
x
1
)
,
χ
H
(
x
2
)
}
}
，则
{w
1
,
w
2
}
\left\{w_1, w_2\right\}
{
w
1
,
w
2
}
是cut edge当前仅当
{x
1
,
x
2
}
\left\{x_1, x_2\right\}
{
x
1
,
x
2
}
是cut edge。 -
若
{{
χ
G
(
w
)
:
w
∈
V
G
}
}
=
{
{
χ
H
(
w
)
:
w
∈
V
H
}
}
\left\{\left\{\chi_G(w): w \in \mathcal{V}_G\right\}\right\}=\left\{\left\{\chi_H(w): w \in \mathcal{V}_H\right\}\right\}
{
{
χ
G
(
w
)
:
w
∈
V
G
}
}
=
{
{
χ
H
(
w
)
:
w
∈
V
H
}
}
，则
BCETree
(
G
)
≃
BCETree
(
H
)
\operatorname{BCETree}(G) \simeq \operatorname{BCETree}(H)
BCETree
(
G
)
≃
BCETree
(
H
)
。
该定理将SPD、biconnectivity和WL Test结合到一个统一的结论中。
RD-WL for vertex-biconnectivity
作者选择Resistance Distance (RD)作为距离度量（用
dis
G
R
\text{dis}^R_G
dis
G
R
表示）。
dis
G
R
(
u
,
v
)
\operatorname{dis}_G^{\mathrm{R}}(u, v)
dis
G
R
(
u
,
v
)
的值被定义为节点
u
u
u
和节点
v
v
v
之间的有效电阻，将
G
G
G
视为电网，其中每条边对应1个1欧姆的电阻。RD有很多优雅的属性：
- RD是一个有效的度量（非负的，半定的、对称的并且满足三角不等式）
-
0≤
dis
G
R
(
u
,
v
)
≤
n
−
1
0 \leq \operatorname{dis}_G^{\mathrm{R}}(u, v) \leq n-1
0
≤
dis
G
R
(
u
,
v
)
≤
n
−
1
，且若
GG
G
是tree，则
dis
G
R
(
u
,
v
)
=
dis
G
(
u
,
v
)
\operatorname{dis}_G^{\mathrm{R}}(u, v)=\operatorname{dis}_G(u, v)
dis
G
R
(
u
,
v
)
=
dis
G
(
u
,
v
)
。
作者证明RD与图拉普拉斯高度相关且计算效率高。
定理
：令
G
=
(
V
G
,
E
G
)
G=\left(\mathcal{V}_G, \mathcal{E}_G\right)
G
=
(
V
G
,
E
G
)
和
H
=
(
V
H
,
E
H
)
H=\left(\mathcal{V}_H, \mathcal{E}_H\right)
H
=
(
V
H
,
E
H
)
表示两个图，
χ
G
\chi_G
χ
G
和
χ
H
\chi_H
χ
H
分别表示对应的RD-WL颜色映射，则如下成立：
-
对任意两个节点
w∈
V
G
w \in \mathcal{V}_G
w
∈
V
G
和
x∈
V
H
x \in \mathcal{V}_H
x
∈
V
H
，若
χG
(
w
)
=
χ
H
(
x
)
\chi_G(w)=\chi_H(x)
χ
G
(
w
)
=
χ
H
(
x
)
，则
ww
w
是一个cut vertex当且仅当
xx
x
是一个cut vertex。 -
若
{{
χ
G
(
w
)
:
w
∈
V
G
}
}
=
{
{
χ
H
(
w
)
:
w
∈
V
H
}
}
\left\{\left\{\chi_G(w): w \in \mathcal{V}_G\right\}\right\}=\left\{\left\{\chi_H(w): w \in \mathcal{V}_H\right\}\right\}
{
{
χ
G
(
w
)
:
w
∈
V
G
}
}
=
{
{
χ
H
(
w
)
:
w
∈
V
H
}
}
，则
BCVTree
(
G
)
≃
BCVTree
(
H
)
\operatorname{BCVTree}(G) \simeq \operatorname{BCVTree}(H)
BCVTree
(
G
)
≃
BCVTree
(
H
)
。
第4节的两个定理表明，所有的biconnectivity问题都可以在作者提出的GD-WL框架内解决。
当同时使用SPD和RD，GD-WL对vertex-biconnectivity和edge-biconnectivity都有效。
Practical Implementation
作者指出，GD-WL可以通过将距离信息注入到Multi-head Attention中，使用类似Transformer的架构轻松实现，其注意力称可以写为：
Y
h
=
[
ϕ
1
h
(
D
)
⊙
softmax
(
X
W
Q
h
(
X
W
K
h
)
⊤
+
ϕ
2
h
(
D
)
)
]
X
W
V
h
\mathbf{Y}^h=\left[\phi_1^h(\mathbf{D}) \odot \operatorname{softmax}\left(\mathbf{X} \mathbf{W}_Q^h\left(\mathbf{X} \mathbf{W}_K^h\right)^{\top}+\phi_2^h(\mathbf{D})\right)\right] \mathbf{X} \mathbf{W}_V^h
Y
h
=
[
ϕ
1
h
(
D
)
⊙
softmax
(
X
W
Q
h
(
X
W
K
h
)
⊤
+
ϕ
2
h
(
D
)
)
]
X
W
V
h
其中
X
∈
R
n
×
d
\mathbf{X} \in \mathbb{R}^{n \times d}
X
∈
R
n
×
d
表示上一层的输入节点特征，
D
∈
R
n
×
n
\mathbf{D} \in \mathbb{R}^{n \times n}
D
∈
R
n
×
n
为距离矩阵，其中
D
u
v
=
d
G
(
u
,
v
)
D_{u v}=d_G(u, v)
D
uv
=
d
G
(
u
,
v
)
，
W
Q
h
,
W
K
h
,
W
V
h
∈
R
d
×
d
H
\mathbf{W}_Q^h, \mathbf{W}_K^h, \mathbf{W}_V^h \in \mathbb{R}^{d \times d_H}
W
Q
h
,
W
K
h
,
W
V
h
∈
R
d
×
d
H
都是第
h
h
h
个head中的可学习的参数矩阵。
ϕ
1
h
\phi_1^h
ϕ
1
h
和
ϕ
2
h
\phi_2^h
ϕ
2
h
是应用在
D
\mathbf{D}
D
上的逐元素函数（可能是参数化的），
⊙
\odot
⊙
表示逐元素乘法。各个注意力图的结果
Y
h
∈
R
n
×
d
H
\mathbf{Y}^h \in \mathbb{R}^{n \times d_H}
Y
h
∈
R
n
×
d
H
组合起来用来获取最终的输出
Y
=
∑
h
Y
h
W
O
h
\mathbf{Y}=\sum_h \mathbf{Y}^h \mathbf{W}_O^h
Y
=
∑
h
Y
h
W
O
h
，其中
W
O
h
∈
R
d
H
×
d
\mathbf{W}_O^h \in \mathbb{R}^{d_H \times d}
W
O
h
∈
R
d
H
×
d
。作者将该体系结构称之为
Graphormer-GD
。
Graphormer-GD在区分非同构图方面最多与GD-WL一样强大。而且，当选择适当的函数
ϕ
1
h
\phi_1^h
ϕ
1
h
和
ϕ
2
h
\phi_2^h
ϕ
2
h
，并且使用足够多的头部和层数时，Graphormer-GD的性能与GD-WL相同。