图神经网络（GCN）

一、GCN的起源

曾经深度学习一直都是被几大经典模型给统治着&＃xff0c;如CNN、RNN等等&＃xff0c;它们无论再CV还是NLP领域都取得了优异的效果。
但是对于图结构的数据&＃xff0c;无论是CNN还是RNN都无法解决或者效果不好。

&＃xff08;1&＃xff09;CV中的CNN&＃xff1a;图像识别的对象是图片&＃xff0c;是一个二维的结构&＃xff0c;可以同CNN来提取图片的特征。CNN的核心在于kernel&＃xff0c;它是一个小窗口&＃xff0c;在图片上平移&＃xff0c;通过卷积的方式来提取特征。这里的关键在于图片结构上的平移不变性&＃xff1a;一个小窗口无论移动到图片的哪一个位置&＃xff0c;其内部的结构都是一模一样的&＃xff0c;因此CNN可以实现参数共享。这就是CNN的精髓所在。
&＃xff08;2&＃xff09;NLP中的RNN&＃xff1a;自然语言处理的序列信息是一个一维的结构&＃xff0c;RNN就是专门针对这些序列的结构而设计的&＃xff0c;通过各种门的操作&＃xff0c;使得序列前后的信息互相影响&＃xff0c;从而很好地捕捉序列的特征。

这些的图片或者语言&＃xff0c;都属于欧式空间的数据&＃xff0c;因此才有维度的概念&＃xff0c;欧式空间的数据的特点就是结构很规则。
但是现实生活中&＃xff0c;其实有很多很多不规则的数据结构&＃xff0c;典型的就是图结构&＃xff0c;或称拓扑结构&＃xff0c;如社交网络、化学分子结构、知识图谱等等&＃xff1b;即使是语言&＃xff0c;实际上其内部也是复杂的树形结构&＃xff0c;也是一种图结构&＃xff1b;而像图片&＃xff0c;在做目标识别的时候&＃xff0c;我们关注的实际上只是二维图片上的部分关键点&＃xff0c;这些点组成的也是一个图的结构。

图结构数据特点&＃xff1a;图结构数据十分不规则的&＃xff0c;可以认为是无限维的一种数据&＃xff0c;所以它没有平移不变性。每一个节点的周围结构可能都是独一无二的&＃xff0c;这种结构的数据&＃xff0c;就让传统的CNN、RNN瞬间失效。所以很多学者从上个世纪就开始研究怎么处理这类数据了。这里涌现出了很多方法&＃xff0c;例如GNN、DeepWalk、node2vec等等&＃xff0c;GCN只是其中一种。

GCN&＃xff0c;图卷积神经网络&＃xff0c;实际上跟CNN的作用一样&＃xff0c;就是一个特征提取器&＃xff0c;只不过它的对象是图数据。GCN的目的就是一个学习图结构$\mathcal{G}\&＃61;(\mathcal{V},\mathcal{E})$特征的映射函数&＃xff0c;他的输入是&＃xff1a;
&＃xff08;1&＃xff09;A feature description xix_ixi​ for every node $i$; summarized in a N×D feature matrix X (N: number of nodes, D: number of input features)
&＃xff08;2&＃xff09;A representative description of the graph structure in matrix form; typically in the form of an adjacency matrix A (or some function thereof)
输出是一个node-level的output Z&＃xff08;它是一个N×F的特征矩阵&＃xff0c;F是每个节点的输出特征数量&＃xff09;。
每个神经网络结构就可以被写为一个non-linear function
H(l&＃43;1)&＃61;f(H(l),A)H^{(l&＃43;1)}&＃61;f(H^{(l)},A)H(l&＃43;1)&＃61;f(H(l),A)
其中&＃xff0c;H(0)&＃61;XH^{(0)}&＃61;XH(0)&＃61;X和H(L)&＃61;ZH^{(L)}&＃61;ZH(L)&＃61;Z&＃xff0c;(L是层的个数)。然后&＃xff0c;具体的模型只在如何选择和参数化映射函数$f(.,.)$方面有所不同。
GCN精妙地设计了一种从图数据中提取特征的方法&＃xff0c;从而让我们可以使用这些特征去对图数据进行节点分类&＃xff08;node classification&＃xff09;、图分类&＃xff08;graph classification&＃xff09;、边预测&＃xff08;link prediction&＃xff09;&＃xff0c;还可以顺便得到图的嵌入表示&＃xff08;graph embedding&＃xff09;&＃xff0c;可见用途广泛。

GCN原理&＃xff1a;对于给定的一批图数据&＃xff0c;其中有N个节点&＃xff08;node&＃xff09;&＃xff0c;每个节点都有D维度特征&＃xff0c;组成特征矩阵X&＃61;N×D&＃xff0c;然后各个节点之间的关系也会形成一个N×N维的矩阵A&＃xff0c;也称为邻接矩阵&＃xff08;adjacency matrix&＃xff09;。X和A便是GCN模型的输入。
GCN也是一个神经网络层&＃xff0c;用以下这个公式就可以很好地提取图的特征&＃xff0c;即&＃xff0c;GCN的层与层之间的传播方式是&＃xff1a;

H(l&＃43;1)&＃61;σ(D~−12A~D~−12H(l)W(l))H^{(l&＃43;1)}&＃61;\sigma(\tilde D^{-\frac{1}{2}}\tilde A\tilde D^{-\frac{1}{2}}H^{(l)}W^{(l)})H(l&＃43;1)&＃61;σ(D~−21​A~D~−21​H(l)W(l))
其中&＃xff1a;
&＃xff08;1&＃xff09; A~&＃61;A&＃43;I\tilde A&＃61;A&＃43;IA~&＃61;A&＃43;I, $I$是单位矩阵
&＃xff08;2&＃xff09;D~\tilde DD~是A~\tilde AA~的度矩阵&＃xff08;degree matrix&＃xff09;
&＃xff08;3&＃xff09;H是每一层的特征&＃xff0c;对于输入层的话&＃xff0c;H就是X
&＃xff08;4&＃xff09;σ是非线性激活函数
作者Thomas Kipf在GRAPH CONVOLUTIONAL NETWORKS给出一个由简入繁的过程来解释上面公式&＃xff1a;
每一层GCN的输入都是邻接矩阵A和node的特征H&＃xff0c;直接做一个内积&＃xff0c;再乘一个参数矩阵W&＃xff0c;然后激活一下&＃xff0c;就相当于一个简单的神经网络层:
f(H(l),A&＃xff09;&＃61;σ(AH(l)W(l))f(H^{(l)},A&＃xff09;&＃61;\sigma( AH^{(l)}W^{(l)})f(H(l),A&＃xff09;&＃61;σ(AH(l)W(l))
实验证明&＃xff0c;即使就这么简单的神经网络层&＃xff0c;就已经很强大了。这个简单模型就是正常的神经网络操作。
但是这个简单模型有几个局限性&＃xff1a;
&＃xff08;1&＃xff09;只使用A的话&＃xff0c;由于A的对角线上都是0&＃xff0c;所以在和特征矩阵H相乘的时候&＃xff0c;只会计算一个node的所有邻居的特征的加权和&＃xff0c;该node自己的特征却被忽略了。因此&＃xff0c;可以做一个小小的改动&＃xff0c;给A加上一个单位矩阵 $I$ &＃xff0c;这样就让对角线元素变成$I$了。
&＃xff08;2&＃xff09;A是没有经过归一化的矩阵&＃xff0c;这样与特征矩阵相乘会改变特征原本的分布&＃xff0c;产生一些不可预测的问题。所以对A做一个标准化处理。首先让A的每一行加起来为1&＃xff0c;我们可以乘以一个D的逆&＃xff0c;D就是度矩阵。可以进一步把D的拆开与A相乘&＃xff0c;得到一个对称且归一化的矩阵 D~−12A~D~−12\tilde D^{-\frac{1}{2}}\tilde A\tilde D^{-\frac{1}{2}}D~−21​A~D~−21​ 。
通过对上面两个局限的改进&＃xff0c;便得到了最终的层特征传播公式&＃xff1a;
f(H(l),A&＃xff09;&＃61;σ(D^−12A^D^−12H(l)W(l))f(H^{(l)},A&＃xff09;&＃61;\sigma(\hat D^{-\frac{1}{2}}\hat A\hat D^{-\frac{1}{2}}H^{(l)}W^{(l)})f(H(l),A&＃xff09;&＃61;σ(D^−21​A^D^−21​H(l)W(l))
其中&＃xff0c;A^&＃61;A&＃43;I\hat A&＃61;A&＃43;IA^&＃61;A&＃43;I,其中&＃xff0c;$I$是单位矩阵&＃xff08;identity matrix&＃xff09;&＃xff0c;D^\hat DD^是A^\hat AA^的对角节点度矩阵
公式中与对称归一化拉普拉斯矩阵十分类似&＃xff0c;而在谱图卷积的核心就是使用对称归一化拉普拉斯矩阵&＃xff0c;这也是GCN的卷积叫法的来历。

上图中的GCN输入一个图&＃xff0c;通过若干层GCN每个node的特征从X变成了Z&＃xff0c;但是&＃xff0c;无论中间有多少层&＃xff0c;node之间的连接关系&＃xff0c;即A&＃xff0c;都是共享的。
假设构造一个两层的GCN&＃xff0c;激活函数分别采用ReLU和Softmax&＃xff0c;则整体的正向传播的公式为&＃xff1a;
Z&＃61;f(X,A)&＃61;softmax(A^ReLU(A^XW(0))W(1))Z&＃61;f(X,A)&＃61;softmax(\hat A ReLU(\hat AXW^{(0)})W^{(1)})Z&＃61;f(X,A)&＃61;softmax(A^ReLU(A^XW(0))W(1))
最后&＃xff0c;针对所有带标签的节点计算cross entropy损失函数&＃xff1a;
L&＃61;−∑l∈YL∑f&＃61;1FYlflnZlf\mathcal{L}&＃61;-\sum_{l\in\mathcal{Y}_L}\sum_{f&＃61;1}^F Y_{lf}lnZ_{lf}L&＃61;−l∈YL​∑​f&＃61;1∑F​Ylf​lnZlf​
就可以训练一个node classification的模型了。由于即使只有很少的node有标签也能训练&＃xff0c;作者称他们的方法为半监督分类。当然&＃xff0c;也可以用这个方法去做graph classification、link prediction&＃xff0c;只是把损失函数给变化一下即可。
注&＃xff1a;本文参考博客最通俗易懂的图神经网络&＃xff08;GCN&＃xff09;原理详解