前言

在上一篇文章中[1]，我们介绍了Graph Convolution Network的推导以及背后的思路等，但是，其实我们会发现，在傅立叶域上定义出来的GCN操作，其实也可以在空间域上进行理解，其就是所谓的消息传递机制，我们在本篇文章将会接着[1]，继续介绍Message Passing机制。如有谬误，请联系指正。转载请注明出处。

$\nabla$∇ 联系方式：
e-mail: [email protected]
QQ: 973926198
github: https://github.com/FesianXu

---

Message Passing与GCN

消息传递(Message Passing) 正如其名，指的是目的节点$S1$S1的邻居$\mathcal{N}(S1)$N(S1)，如Fig 1所示，红色节点$S1$S1的邻居正是蓝色节点$B1,B2,B3$B1,B2,B3，这些邻居节点根据一定的规则将信息，也就是特征，汇总到红色节点上，就是所谓的信息传递了。
让我们举个信息汇聚的最简单的例子，那就是逐个元素相加。假设我们的每个节点的特征为$H^{(l)} \in \mathbb{R}^{d}$H(l)∈Rd，那么有：
$\sum_{u \in \mathcal{N}(v)} H^{(l)}(u) \in \mathbb{R}^{d_i} \tag{1.1}$u∈N(v)∑​H(l)(u)∈Rdi​(1.1)
其中，$\mathcal{N}(v)$N(v)表示的是节点$v$v的邻居节点。

通常来说，我们会加入一个线性变换矩阵$W^{(l)} \in \mathbb{R}^{d_i \times d_o}$W(l)∈Rdi​×do​，以作为汇聚节点特征的特征维度转换（或者说是映射）。有：
$(\sum_{u \in \mathcal{N}(v)} H^{(l)}(u)) W^{(l)} \in \mathbb{R}^{d_o} \tag{1.2}$(u∈N(v)∑​H(l)(u))W(l)∈Rdo​(1.2)
加入**函数后有:
$\sigma((\sum_{u \in \mathcal{N}(v)} H^{(l)}(u)) W^{(l)}) \tag{1.3}$σ((u∈N(v)∑​H(l)(u))W(l))(1.3)

其实式子(1.3)可以用更为紧致的矩阵形式表达，为：
$f(H^{(l)}, A) = \sigma(AH^{(l)}W^{(l)}) \tag{1.4}$f(H(l),A)=σ(AH(l)W(l))(1.4)
其中$A$A为邻接矩阵，接下来我们以Fig 2的拓扑结构举个例子进行理解。

此时假设我们的输入特征为10维，输出特征为20维，那么我们有：
$f_{in} \in \mathbb{R}^{10}, f_{out} \in \mathbb{R}^{20}, H^{(l)} \in \mathbb{R}^{6 \times 10}, W^{(l)} \in \mathbb{R}^{10 \times 20}, A \in \mathbb{R}^{6 \times 6}$fin​∈R10,fout​∈R20,H(l)∈R6×10,W(l)∈R10×20,A∈R6×6
那么进行运算的过程如：


我们不难发现，其实$HW$HW的结果乘上邻接矩阵$A$A的目的其实在于选在邻居节点，其实本质就是在于邻居节点的信息传递。因此信息传递的公式可以用更为紧致的式子(1.4)进行描述。但是我们注意到，如Fig 3的绿色框所示的，每一行的节点总数不同，将会导致每个目的节点汇聚的信息尺度不同，容易造成数值尺度不统一的问题，因此实际计算中常常需要用标准化进行处理，这正是[1]中提到的对拉普拉斯矩阵$L$L进行标准化的原因。

除了标准化的问题之外，式子(1.4)还存在一些需要改进的地方，比如没有引入节点自身的信息，一般来说，比如二维卷积，像素中心往往能提供一定的信息量，没有理由不考虑中心节点自身的信息量，因此一般我们会用自连接将节点自身连接起来，如Fig 4所示。

因此，邻接矩阵就应该更新为:
$\tilde{A} = A+I_n \tag{1.5}$A~=A+In​(1.5)
而度数矩阵更新为：
$\tilde{D}_{i,i} = \sum_{j} \tilde{A}_{i,j} \tag{1.6}$D~i,i​=j∑​A~i,j​(1.6)

为了标准化邻接矩阵$A$A使得每行之和为1，我们可以令：
$A = D^{-1}A \tag{1.7}$A=D−1A(1.7)
也就是邻居节点的特征取平均，这里对这个过程同样制作了个详细解释的图。

我们可以看到，通过式子(1.7)，我们对邻接矩阵进行了标准化，这个标准化称之为random walk normalization。然而，在实际中，动态特性更为重要，因此经常使用的是symmetric normalization [2,3]，其不仅仅是对邻居节点的特征进行平均了，公式如：
$A = D^{-\frac{1}{2}} A D^{-\frac{1}{2}} \tag{1.8}$A=D−21​AD−21​(1.8)
同样，这里我制作了一个运算过程图来解释。

对拉普拉斯矩阵进行对称标准化，有：
$L^{sym} := D^{-\frac{1}{2}} L D^{-\frac{1}{2}} =D^{-\frac{1}{2}} (D-A) D^{-\frac{1}{2}} =I_n - D^{-\frac{1}{2}} A D^{-\frac{1}{2}} \tag{1.9}$Lsym:=D−21​LD−21​=D−21​(D−A)D−21​=In​−D−21​AD−21​(1.9)
这就是为什么在[1]中提到的拉普拉斯矩阵要这样标准化的原因了。

所以，经过了对称标准化之后，我们的式子(1.4)可以写成：
$H^{(l+1)} = \sigma(\tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}} H^{(l)} W^{(l)}) \tag{1.10}$H(l+1)=σ(D~−21​A~D~−21​H(l)W(l))(1.10)
其中$\tilde{A} = A+I_n, \tilde{D}_{i,i} = \sum_{j} \tilde{A}_{i,j}$A~=A+In​,D~i,i​=∑j​A~i,j​
熟悉吧，这个正是根据频域上ChebNet一阶近似得到的结果来的GCN表达式，因此GCN在空间域上的解释就是Message Passing。

---

Reference

[1]. https://blog.****.net/LoseInVain/article/details/90171863
[2]. https://people.orie.cornell.edu/dpw/orie6334/lecture7.pdf
[3]. https://math.stackexchange.com/questions/1113467/why-laplacian-matrix-need-normalization-and-how-come-the-sqrt-of-degree-matrix