GCN的通俗理解，无复杂公式

近期在鼓捣图神经网络，发现直接读state-of-art的论文基本读不懂，于是先决定搞懂图神经网络的最基本概念，即工作原理、处理数据流程等。因网上的众多文章（包括原论文）都有复杂的数学公式，我不是否认数学公式不好，而是胡乱的堆公式对讲明白原理没有丝毫帮助。于是决定做一篇GCN的简单阐述，意在用最简单的语言，表达最清晰的思路。

定义

图的表示为$G=(V,E)$，将图的节点表示和邻接矩阵作为网络的输入：

• 对于每一个节点$i$的特征描述$x_i$，组成一个$N\times D$的矩阵$X$，$N$是节点的数量，$D$是特征的维度；
• 图的邻接矩阵为$A$；
• 网络的输出是$Z$，维度是$N\times F$，$F$是输出维度的特征。

每一层神经网络可以定义为非线性函数：

\begin{equation}
H^{l+1}=f(H^l, A)
\end{equation}

其中，$H^0=X,H^l=Z$，$l$是网络的层数，$f$是选择的网络模型，就这样一层一层的输出。

简单实例

首先定义逐层之间的传播规则：

\begin{equation}f(H^l,A)=\sigma (AH^lW^l)\end{equation}

其中，$W^l$是第$l$层的网络权重，$\sigma$是非线性的激活函数，这是最简单的定义。对这个最简单的定义添加两个限制：

• $A\times H^l$意味着对于图中的每一个节点，将它所有的邻居节点的全部特征向量求和，但没有考虑自己（除非有链接到自己的环），所以要对矩阵$A$增加单位矩阵$I$，这样矩阵的每一个节点就具有链接到自己的回路；
• 考虑到邻接矩阵$A$的同时，也要考虑到节点的度，度越大，表明该节点和其他节点的关系越大，如果直接提取度数很大节点和周围节点的联系，即将邻居节点的全部特征向量求和，势必会导致数据分布的不均衡。此时标准化的方式为：要取该节点的周围节点特征值的平均值。通俗点说，就是一个节点和四个节点挨着，那么对这四个节点，取每个节点特征值的$1/4$在求和就行了。而实现这种方式只需要一个矩阵变换：方式为$D^{-1}A$/其中，$D$是对角矩阵，矩阵元素是节点的度。论文中使用了对称标准化$D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$的方式，这不再严格等于相邻节点的平均。
• （只是这么一种处理方式，不必太在意），还是要在意一下，我之前认为傅立叶变换等数学推导可以忽略，结果发现这是傅立叶变换和逆变换的两个过程，如果想要看懂这个过程，可以参考：李宏毅机器学习课程 GNN 的第二章节的课程。

此时，传播规则为：

\begin{equation}f(H^l,A)=\sigma (\hat{D}^{-\frac{1}{2}}\hat{A}\hat{D}^{-\frac{1}{2}}H^lW^l)\end{equation}

其中，$\hat{A}=A+I$，$\hat{D}$是$\hat{A}$的节点度的矩阵。

模型操作

如果你看到这里还不是很懂，那我很建议去看它的代码，一目了然。值得注意的是，模型产生了这些节点的嵌入，它们非常类似于图的社区结构。

半监督学习

只对有标签的数据训练，没有标签的数据在损失函数中不考虑。

代码

恕我直言，上古时期的tensorflow代码没有看懂，keras的代码还能看懂，但没有调通，看源代码的众多issue就知道了。

1. 第一步加载数据，X, A, y = load_data(dataset=DATASET)，其中X是特征矩阵，即节点的向量表示，A是临界矩阵，y是标签；
2. 然后得到训练数据graph，由X和A_（处理后的矩阵，包括增加单位矩阵和对称标准化）组成；
3. 之后数据经过doupout，传入GraphConvolution层；

GraphConvolution 解析

重要的一点是，图卷积网络和卷积核无关。而是直接矩阵相乘，在得到节点的嵌入表示后，再去划分就很容易了。可以参看原文的代码（我删除了一部分无关紧要的代码）：

class GraphConvolution(Layer):
    """Basic graph convolution layer as in https://arxiv.org/abs/1609.02907"""
    
    def compute_output_shape(self, input_shapes):
        features_shape = input_shapes[0]
        output_shape = (features_shape[0], self.units)
        return output_shape  # (batch_size, output_dim)

    def build(self, input_shapes):
        features_shape = input_shapes[0]
        assert len(features_shape) == 2
        input_dim = features_shape[1]

        self.kernel = self.add_weight(shape=(input_dim * self.support,
                                             self.units),
                                      initializer=self.kernel_initializer,
                                      name='kernel',
                                      regularizer=self.kernel_regularizer,
                                      constraint=self.kernel_constraint)

        self.bias = self.add_weight(shape=(self.units,),
                                        initializer=self.bias_initializer,
                                        name='bias',
                                        regularizer=self.bias_regularizer,
                                        constraint=self.bias_constraint)

        self.built = True

    def call(self, inputs, mask=None):
        features = inputs[0]
        basis = inputs[1:]

        supports = list()
        for i in range(self.support):
            supports.append(K.dot(basis[i], features))
        supports = K.concatenate(supports, axis=1)
        output = K.dot(supports, self.kernel)

        output += self.bias
        return self.activation(output)

如上，我么很容易看出 GCN 的工作就是矩阵相乘，将输出的维度不断的压缩，得到节点的嵌入表示。也许你会很疑惑？众多科普文章中的拉普拉斯算子什么的呢？关于这一点，原作者也做出了解释：

spectral graph convolution（我不知道该怎么翻译了）：定义为信号与图的傅立叶空间中的滤波器相乘。说人话的意思是：矩阵$X$要和矩阵$U$相乘，矩阵$U$是图灵拉普拉斯矩阵$L$的特征向量矩阵，$L$的计算方式是：$L=I-\hat{A}$，但是具有高昂的计算代价。

结语

也许你会疑问，图网络是用来干什么的？正如作者所说，GCN仅仅是一个开始。据我个人的粗俗分析，可以用来：

1. 借助GCN学习得到的节点表示，来进行大规模图划分；
2. 如果GCN的标签是自己本身，那是不是可以用类似 autoencoder 的形式来进行链接预测？
3. 能否学习节点之间的隐藏联系，推断序列数据的结构？
4. 能否与周围环境交互，对已有的模型进行调整，主动构建关系、对象等？

当然，距离实现以上这些还有很长的路要走。

参考

站在巨人的肩膀上，我们能更好的前行：

1. 参考论文: https://arxiv.org/pdf/1609.02907.pdf
2. 参考博客(原文讲的很好): http://tkipf.github.io/graph-convolutional-networks/
3. 数据集(cora): http://www.cs.umd.edu/~sen/lbc-proj/LBC.html
4. 代码参考(tensorflow): https://github.com/tkipf/gcn
5. 代码参考(keras): https://github.com/tkipf/keras-gcn