论文：《 Semi-Supervised Classification with Graph Convolutional Networks 》(2017)

GCN是图神经网络之"开山之作"。

1.数学计算过程

我们使用一个示例来说明GCN的计算方法。

假设我们有一个包含n（n=5）个节点的无自环的有向带权图G，我们可以得到这个图的邻接矩阵A，用以表示图G中节点的相互关系。

$A=\left[\begin{array}{ccccc}0& \infty & \infty & \infty & 6\\ 9& 0& 3& \infty & \infty \\ 2& \infty & 0& 5& \infty \\ \infty & \infty & \infty & 0& 1\\ \infty & \infty & \infty & \infty & 0\end{array}\right]$

D为其度矩阵，度矩阵D是对角阵，对角上的元素为各个顶点的度。顶点vi的度表示和该顶点相关联的边的数量，其中有向图节点度=节点出度+节点入度。

$D=\left[\begin{array}{ccccc}3& 0& 0& 0& 0\\ 0& 2& 0& 0& 0\\ 0& 0& 3& 0& 0\\ 0& 0& 0& 2& 0\\ 0& 0& 0& 0& 2\end{array}\right]$

每一个节点有自己的一个d维（假设d=3）的特征，那么所有的节点的特征就可以构成一个n*d的特征矩阵X

$X=\left[\begin{array}{ccc}1& 2& 3\\ 9& 5& 3\\ 2& 2& 0\\ 0& 5& 7\\ 12& 5& 8\end{array}\right]$

这样我们就得到了GCN的初始输入：

• 邻接矩阵A：n * n维（5 * 5）
• 特征矩阵X：n * d维（5 * 3）
• 参数矩阵W（最开始的值是随机生成的）：d * h维（3 * h），h是隐藏层的节点数

计算说明：

1.首先，让邻接矩阵A * 特征矩阵X，便能得到一个新的特征矩阵（汇聚特征） $X^{\ast }=AX$，因为是带权图，所以可以理解成对所有节点做邻接点的加权和（专业名词可称之为消息传递）。

2.接着，将节点的汇聚特征利用线性变换矩阵W变换到h维的空间，这里的W就相当于普通神经网络中的w。我们就得到了这样的式子 $X^{\ast }\ast W=AXW$。
这时候如果再在外面套一个激活函数σ，就可以当作一个简单的神经网络层（其中H表示的是每一层的特征，输入层的话就是矩阵X*；σ是非线性激活函数）。

$$H^0=\sigma (AXW)$$
$$H^{(l+1)}=\sigma (A{H}^{(l)}{W}^{(l)})$$

3.仅是这样得到的一个简单的神经网络层，就已经足够强大了。但还是存在着不足：

• 1）只使用邻接矩阵A的话，由于图中没有自环，那么A的对角线上的值就都是0，这样在和特征矩阵相乘求加权和时，节点就会忽略自身的特征，所以我们给A加上单位矩阵I，得到的就是 $\tilde{A}=A+I$。
• 2）不同节点, 其边的数量和权重都不一样,这导致多边（或边权重很大）的节点在聚合后的特征值远远大于少边（或边权重小）的节点. 所以需要在节点在更新自身前, 对邻居传来的信息进行归一化来消除这问题， 让A的每一行加起来为1 ，可以将D拆开放两边对A做对称归一化，将A的行和列分别归一化，这样子就能很好的避免上述的问题：${\tilde{D}}^{-\frac{1}{2}}\tilde{A}{\tilde{D}}^{-\frac{1}{2}}$
  • 上述对邻接矩阵处理得到的矩阵称之为 对称归一化拉普拉斯矩阵，除此之外还有两种处理方式：组合拉普拉斯 和 随机归一化拉普拉斯
  • 组合拉普拉斯： $L=D-A$，这种处理方式更关注相邻节点的差分
  • 随机归一化拉普拉斯： ${\tilde{D}}^{-1}\tilde{A}$，这在差分卷积网络中经常使用

最终公式如下：
$$H^{(0)}=\sigma ({\tilde{D}}^{-\frac{1}{2}}\tilde{A}{\tilde{D}}^{-\frac{1}{2}}X{W}^{(0)})$$
$$H^{(l+1)}=\sigma ({\tilde{D}}^{-\frac{1}{2}}\tilde{A}{\tilde{D}}^{-\frac{1}{2}}{H}^{(l)}{W}^{(l)})$$

2.代码实现

import torch
import torch.nn as nn
from torch.nn import Linear

from torch_geometric.nn import GCNConv
from torch_geometric.nn import global_mean_pool as gmp, global_max_pool as gap

from torchsummary import summary


embedding_size = 64


class GCN(nn.Module):
    def __init__(self):
        # Initialization
        super().__init__()
        torch.manual_seed(42)

        self.initial_conv = GCNConv(3, embedding_size)
        self.conv1 = GCNConv(embedding_size, embedding_size)
        self.conv2 = GCNConv(embedding_size, embedding_size)
        self.conv3 = GCNConv(embedding_size, embedding_size)

        self.out = Linear(embedding_size*2, 1)

    def forward(self, x, edge_index, edge_weight, batch_index):

        # 1st Conv layer
        hidden = self.initial_conv(x, edge_index, edge_weight)

        hidden = torch.tanh(hidden)

        # Other layers
        hidden = self.conv1(hidden, edge_index)
        hidden = torch.tanh(hidden)
        hidden = self.conv2(hidden, edge_index)
        hidden = torch.tanh(hidden)
        hidden = self.conv3(hidden, edge_index)
        hidden = torch.tanh(hidden)

        # Global pooling
        hidden = torch.cat((gmp(hidden, batch_index), gap(hidden, batch_index)), dim=1)
        out = self.out(hidden)

        return out, hidden

以self.initial_conv = GCNConv(data.num_features, embedding_size) 为例说明初始GCN的计算，公式如下：

$$H^{(0)}=\sigma ({\tilde{D}}^{-\frac{1}{2}}\tilde{A}{\tilde{D}}^{-\frac{1}{2}}X{W}^{(l)})$$

GCNConv输入为：特征矩阵X，连接关系矩阵（edge_index），edge_index支持格式如下：

$$A=\left[\begin{array}{cccccc}0& 1& 1& 2& 2& 3\\ 4& 0& 2& 0& 3& 4\end{array}\right]$$

输出为：hidden = self.initial_conv(x, edge_index)，这里的hidden就是 $H^{(0)}$，
这里权重矩阵W的shape为[data.num_features, embedding_size] ，
因此根据公式可得，hidden的shape为[节点数量, embedding_size]

我们可以看到这里edge_index采用的是边集数组的输入方式，但上述数学公式中用的是邻接矩阵的形式？实际上， GCNConv源代码中会有一个转换，将输入的边集数组转换为邻接矩阵，然后再进行上述计算

3.应用场景

应用：

• 整体图的分类：根据输入的图结构，将其分到某类中或预测这个图结构的整体属性，例如，化学分子的分类/溶解性预测，…等等
• 节点的分类：根据图的属性和关联关系，预测节点的类别/属性

优点：

• 不经过训练、随机初始化的参数，GCN提取的特征就十分优秀，这意味着不训练的GCN，也可以用来提取graph embedding
• 没有节点的特征仍可以使用GCN，如原文中的俱乐部网络，采用的方法就是用单位矩阵 I 替换特征矩阵 X
• 支持半监督分类：即只有很少的node有标签也能训练
• GCN 2-3层效果就比较好了

缺点：

• 属于直推式学习，扩展性差，也就是说图的结构是固定的
• 训练是full-batch的，难以扩展到大规模网络，并且收敛较慢

在谱分解图卷积的进一步改进中,Li等人认为目前大部分谱分解图卷积的过滤器被设计用来处理具有共享和固定的图结构数据,没有考虑图到在大小和连通性上的变化

因此Li等人提出一个概括性的动态图卷积网络(AdaptiveGraphConvolutionNetwork, AGCN)