GINConv
1. Weisfeiler-Lehman Test
论文名称：Weisfeiler-Lehman Graph Kernels
论文地址：https://www.jmlr.org/papers/volume12/shervashidze11a/shervashidze11a.pdf
Weisfeiler-Lehman Test用于判断两个图是否同构。Weisfeiler-Lehman Test是一个迭代的过程， Algorithm 1给出简洁的算法描述。
这个算法的关键思想是对node节点赋予标签，然后对邻居节点进行升序排列，然后，将这些标签压缩产生新的标签。重复以上步骤，直到
G
G
G和
G
′
G^\prime
G′的标签不同或者迭代次数到达
n
n
n. Figure2 a-d描述这些步骤（需要注意的是，这两个图是非同构的，因为他们的标签在开始就不同）。
如果初始化标签不存在，开始的时候，可以初始化标签为1.
以下图的参考链接: https://davidbieber.com/post/2019-05-10-weisfeiler-lehman-isomorphism-test/
2. GIN
论文名称：HOW POWERFUL ARE GRAPH NEURAL NETWORKS?
论文地址：https://arxiv.org/pdf/1810.00826.pdf
Graph Neural Networks. GNN使用图的结构和节点的特征
X
v
X_v
Xv?, 学习节点的embedding
h
v
h_v
hv?或者整个图的embedding
h
G
h_G
hG?。现在GNN汇总邻居节点信息和更新节点表征。在
k
k
k迭代汇总后，当前节点 的表征就会捕捉到
k
-hop
k\text{-hop}
k-hop的邻居信息。GNN
k
-th
k\text{-th}
k-th 的layer如下：
a
v
(
k
)
=
A
G
G
R
E
G
A
T
E
(
k
)
(
{
h
u
(
k
?
1
)
:
u
∈
N
(
v
)
}
)
,
h
v
(
k
)
=
C
O
M
B
I
N
E
(
k
)
(
h
v
(
k
?
1
)
,
a
v
(
k
)
)
(2.1)
a_{v}^{(k)}=\mathrm{AGGREGATE}^{(k)}\left(\left\{h_{u}^{(k-1)}: u \in \mathcal{N}(v)\right\}\right), \quad h_{v}^{(k)}=\mathrm{COMBINE}^{(k)}\left(h_{v}^{(k-1)}, a_{v}^{(k)}\right)\tag{2.1}
av(k)?=AGGREGATE(k)({hu(k?1)?:u∈N(v)}),hv(k)?=COMBINE(k)(hv(k?1)?,av(k)?)(2.1)
其中
h
v
(
k
)
h_v^{(k)}
hv(k)?代表节点
v
v
v在
k
-th
k\text{-th}
k-th layer的特征表示。我们初始化
h
v
(
0
)
=
X
v
h_{v}^{(0)}=X_{v}
hv(0)?=Xv?, 其中
N
(
v
)
\mathcal{N}(v)
N(v)是节点
v
v
v的邻居。
2.1 BUILDING POWERFUL GRAPH NEURAL NETWORKS
首先，我们描述以下GNN模型的表征能力，通常来说，一个强大的GNN模型能否将不同的图结构映射到不同的向量表征空间中。将不同的图映射到不同的向量空间，用来判别两个图是否同构图。同构图映射到相同的空间中，非同构图映射到不同的空间中。我们设计的 G N N GNN GNN具备Weisfeiler-Lehman (WL) graph isomorphism test同样的判别能力，泛化能力更高。
Lemma 2. 设 G 1 G_1 G1?和 G 2 G_2 G2?是两个非同构图。如果GNN A : G → R d \mathcal{A}: \mathcal{G} \rightarrow \mathbb{R}^{d} A:G→Rd将其映射为不同到embedding，Weisfeiler-Lehman test也能判定其是非同构的。
是否存和WL test具备同等能力的GNN？我们的 回答是的，如果没满足Theorem 3，即eighbor aggregation 和 graph-level readout函数都是单射的，我们的GNN就具备和WL test同样的能力。
Theorem 3. 设 A : G → R d \mathcal{A}: \mathcal{G} \rightarrow \mathbb{R}^{d} A:G→Rd为一个 G N N GNN GNN, 一个多层GNN。对于任何两个图 G 1 G_1 G1?和 G 2 G_2 G2?, Weisfeiler-Lehman test将两个图判别为非同构图。 A \mathcal{A} A满足以下条件，将两个图映射到不同的embedding（也就是说， A \mathcal{A} A具备和 Weisfeiler-Lehman test同样的能力）:
a) 通过以下迭代的方式更新和汇总节点的特征：
h
v
(
k
)
=
?
(
h
v
(
k
?
1
)
,
f
(
{
h
u
(
k
?
1
)
:
u
∈
N
(
v
)
}
)
)
h_{v}^{(k)}=\phi\left(h_{v}^{(k-1)}, f\left(\left\{h_{u}^{(k-1)}: u \in \mathcal{N}(v)\right\}\right)\right)
hv(k)?=?(hv(k?1)?,f({hu(k?1)?:u∈N(v)}))
其中，对于函数
f
f
f， 它是基于multisets，
?
\phi
?是单射函数。
b) A \mathcal{A} A是单射的，它能够作用于multiset 节点特征 { h v ( k ) } \left\{h_{v}^{(k)}\right\} {hv(k)?}, 是单射的。
需要注意的是GNN不仅能够判别图，而且，通过将图接否映射为低维的embedding，能够衡量不同图之间的相似性。
2.2 GRAPH ISOMORPHISM NETWORK (GIN)
我们开发简单架构GIN, 满足Theorem 3，这个模型是WL test的泛化，因此也能够对GNN进行判别。
Lemma 5. 假设 X \mathcal{X} X是可枚举的。对于每个有限集 multiset X ? X X\subset \mathcal{X} X?X， 存在函数 f : X → R n f: \mathcal{X} \rightarrow \mathbb{R}^{n} f:X→Rn使得 h ( X ) = ∑ x ∈ X f ( x ) h(X)=\sum_{x \in X} f(x) h(X)=∑x∈X?f(x)是唯一的。甚至，对于任何一个multiset函数 g g g对于某些 ? \phi ?可以分解为 g ( X ) = ? ( ∑ x ∈ X f ( x ) ) g(X)=\phi\left(\sum_{x \in X} f(x)\right) g(X)=?(∑x∈X?f(x)).
深度multisets和sets一个重要的区别在于它的单射性，像mean aggregator不是单射函数。我们设计聚合框架满足Theorem 3中的单射性。
Corollary 6. 假设 X \mathcal{X} X是可枚举的。存在一个函数 f : X → R n f: \mathcal{X} \rightarrow \mathbb{R}^{n} f:X→Rn, 对于任意 ? \epsilon ?和pair ( c , X ) (c, X) (c,X)， h ( c , X ) = ( 1 + ? ) ? f ( c ) + ∑ x ∈ X f ( x ) h(c, X)=(1+\epsilon) \cdot f(c)+\sum_{x \in X} f(x) h(c,X)=(1+?)?f(c)+∑x∈X?f(x)是唯一的， 其中 c ∈ X c\in\mathcal{X} c∈X， X ? X X\subset \mathcal{X} X?X。基于pair, 对于任意一个函数 g g g可以分解为 g ( c , X ) = φ ( ( 1 + ? ) ? f ( c ) + ∑ x ∈ X f ( x ) ) g(c, X)=\varphi\left((1+\epsilon) \cdot f(c)+\sum_{x \in X} f(x)\right) g(c,X)=φ((1+?)?f(c)+∑x∈X?f(x)).
在实践中，我们使用针对
f
(
k
+
1
)
°
φ
(
k
)
f^{(k+1)} \circ \varphi^{(k)}
f(k+1)°φ(k)我们使用同一个MLP，
?
\epsilon
?是可学习的参数，GIN表示如下：
h
v
(
k
)
=
MLP
?
(
k
)
(
(
1
+
?
(
k
)
)
?
h
v
(
k
?
1
)
+
∑
u
∈
N
(
v
)
h
u
(
k
?
1
)
)
h_{v}^{(k)}=\operatorname{MLP}^{(k)}\left(\left(1+\epsilon^{(k)}\right) \cdot h_{v}^{(k-1)}+\sum_{u \in \mathcal{N}(v)} h_{u}^{(k-1)}\right)
hv(k)?=MLP(k)???(1+?(k))?hv(k?1)?+u∈N(v)∑?hu(k?1)????
通常存在很多这样GNN, GIN只是其中比较简单的一个。
2.3 GRAPH-LEVEL READOUT OF GIN
GIN会产生node embedding，用于节点分类和链路预测。如果需要对图进行分类还需要"readout"函数，根据节点的embedding产生整个图的embedding。
graph-level readout一个重要的方面，随着迭代次数的增加，节点的表征和subtree结构的刻画能力越强，对于图的判别能力越强。当然，初始迭代中，特征的泛化能力比较好。
h
G
=
READOUT
?
(
{
h
v
(
K
)
∣
v
∈
G
}
)
(2.4)
h_{G}=\operatorname{READOUT}\left(\left\{h_{v}^{(K)} \mid v \in G\right\}\right)\tag{2.4}
hG?=READOUT({hv(K)?∣v∈G})(2.4)
与Eq. 2.4不同的是，GIN的图表征是指将所有迭代层的输出拼接起来:
h
G
=
CONCAT
?
(
READOUT
?
(
{
h
v
(
k
)
∣
v
∈
G
}
)
∣
k
=
0
,
1
,
…
,
K
)
(4.2)
h_{G}=\operatorname{CONCAT}\left(\operatorname{READOUT}\left(\left\{h_{v}^{(k)} \mid v \in G\right\}\right) \mid k=0,1, \ldots, K\right)\tag{4.2}
hG?=CONCAT(READOUT({hv(k)?∣v∈G})∣k=0,1,…,K)(4.2)