【综述专栏】图卷积神经网络(GCN)速览

在科学研究中，从方法论上来讲，都应“先见森林，再见树木”。当前，人工智能学术研究方兴未艾，技术迅猛发展，可谓万木争荣，日新月异。对于AI从业者来说，在广袤的知识森林中，系统梳理脉络，才能更好地把握趋势。为此，我们精选国内外优秀的综述文章，开辟“综述专栏”，敬请关注。

来源：知乎—NoobImp

地址：https://zhuanlan.zhihu.com/p/374887413

01

基于谱方法

0. 谱方法的核心思想是对图进行傅里叶变换

根据信号处理中的时域卷积定理（信号卷积的傅里叶变换等于信号傅里叶变换的点积）在频域进行点积，再进行图傅里叶逆变换回到时域，获得两图信号的卷积。假设  是两个图信号：

1. 图的邻接矩阵  、度矩阵  、拉普拉斯矩阵  

前两个不必多说，而  ，根据度规范化的拉普拉斯矩阵  ，元素级别定义如下：

在数字图像处理中，拉普拉斯算子通过n维欧氏空间中的二阶微分刻画了中心像素与它四联通像素的差异。拉普拉斯矩阵也有类似的意义，考虑第i行：第i个位置是1，其他和i相连的节点位置处的值描述了中心节点与邻居节点信号的差异，并且若某节点度数很大，则它对邻居节点的影响会被分摊。

2. 图的傅里叶变换

拉普拉斯矩阵是实对称矩阵，可被正交对角化：

正交对角化步骤：
1.求出特征值和特征向量
2.对特征向量施密特正交化（根据一组线性无关向量构建一组正交向量）
3.再单位化

这样矩阵  就变成了一组正交基，你想到了啥？傅里叶变换里用的正交函数集。这组正交基就可以用作图傅里叶基了。这样图傅里叶变换和逆变换可写作：

  （向量）中的值，称作傅里叶系数，本质上是图信号  在每个傅里叶基上的投影。

而  则可以被表示成傅里叶基的线性加权，权重即傅里叶系数。

3. Spectral networks

我们整一个卷积核  ，对图卷积看看频域发生了肾么：

这样，频域中真正的卷积核其实就是  ，Spectral Network  就是这样做的，对高维的图信号进行GFT，再卷积处理一下，进行IGFT，再做一个非线性变换。但是这个过程中有几个很麻烦的地方，第一，依赖拉普拉斯矩阵的特征分解；第二，需要进行稠密矩阵乘法；第三，图信号的频率是全图反映出来的，因此谱域中的卷积不是局部化的，这和我们直观希望的卷积操作背道而驰。

4. ChybeNet

如果我们令  ，则  

就把频域中的卷积运算转化为了一个对原图信号的“操作”，这个“操作”其实就是所谓的图滤波。

我们在线性代数中了解过，特征值越大，对应的特征向量（傅里叶基）的变化就越剧烈，因此可以把特征值等价为频率。这样图上的滤波操作就可以定义为对图信号频谱中各个频率分量的强度进行增强或衰减。

设图滤波器为  ,输入、输出图信号为  ，

则   

则  ，相较于拉普拉斯矩阵，图滤波器只改变了对角线上的值，即操作了特征值，即操作了频率。

我们希望实现任意性质的图滤波器，可以用泰勒展开构成多项式逼近任意函数：

把系数摘出来之后，因为  的每一列是彼此正交的单位向量，  ，所以卷积操作变成了这个样子：

这个形式  解决了什么问题呢，不需要特征分解了，拉普拉斯矩阵是稀疏的，不需要稠密矩阵乘法了，另外，拉普拉斯矩阵的意义是每个节点与它一阶邻居的连接性/差异，所以整个计算需要所有节点的k阶邻居参与，具有了局部性。

02

基于空间方法

空间卷积的操作就很直观了，核心就是利用图的连接性，用邻居节点的信息更新中心节点的信息。重点有两个：特征表示+聚合操作。

0. DeepWalk、LINE、Node2Vec

其实个人认为最直观的空间域采样邻居的方法就是随机游走，基于此也有一些网络表示学习的工作，如标题。 @Ph0en1x 学长这篇文章写的很详细了，我就不赘述了。

https://zhuanlan.zhihu.com/p/64991884

1. GCN

怎么说呢，因为图卷积等价于图滤波，所以感觉GCN  说是基于谱方法也彳亍，说是基于空间方法也彳亍。作者称这是对chebynet的一阶近似，但其实这也是用的空域一阶邻居的信息。沈华伟老师原话："这个方法巨简单。"

主要是通过增加自连接，用重归一化的拉普拉斯矩阵作聚合：

令  

def normalization(adjacency):
    adjacency += sp.eye(adjacency.shape[0])
    degree = np.array(adjacency.sum(1))
    d_hat = sp.diags(np.power(degree, -0.5).flatten())
    return d_hat.dot(adjacency).dot(d_hat).tocoo()

GCN layer:  ,  是为了增强表达能力的变换矩阵。

class GraphConvolution(nn.Module):
    def __init__(self, input_dim, output_dim, use_bias=True):
        super(GraphConvolution, self).__init__()
        self.input_dim = input_dim
        self.output_dim = output_dim
        self.use_bias = use_bias
        self.weight = nn.Parameter(torch.Tensor(input_dim, output_dim))
        if self.use_bias:
            self.bias = nn.Parameter(torch.Tensor(output_dim))
        else:
            self.register_parameter('bias', None)
        self.reset_parameters()

    def reset_parameters(self):
        init.kaiming_uniform_(self.weight)
        if self.use_bias:
            init.zeros_(self.bias)

    def forward(self, adjacency, input_feature):
        support = torch.mm(input_feature, self.weight)
        output = torch.sparse.mm(adjacency, support)
        if self.use_bias:
            output += self.bias
        return output

    def __repr__(self):
        return self.__class__.__name__ + ' (' \
            + str(self.input_dim) + ' -> ' \
            + str(self.output_dim) + ')'

#in_dim=, hid_dim=, class_num=
class GcnNet(nn.Module):
    def __init__(self, input_dim=in_dim):
        super(GcnNet, self).__init__()
        self.gcn1 = GraphConvolution(input_dim, hid_dim)
        self.gcn2 = GraphConvolution(hid_dim, class_num)

    def forward(self, adjacency, feature):
        h = F.relu(self.gcn1(adjacency, feature))
        logits = self.gcn2(adjacency, h)
        return logits

2. GraphSAGE  

对中心节点，采样固定个数的邻居节点，聚合信息（Sampling and Aggregating）。

聚合操作包括但不限于：平均、求和、池化（取最值）等，这之前往往伴随着特征变换。GraphSAGE最大的贡献是，不需要载入整张图进行训练了，考虑每个结点的k阶邻居即可，大大提升了工程价值。

3. GAT  

对于不同的邻居，不认为他们提供的信息权重相等，希望学习到这样的权重分配。其实这已经隐含了图结构学习的思想。

权重系数：

其中，  是一个计算相关度的函数。

更新特征：

文中还用了多头注意力机制，即多个独立的注意力机制进行拼接或求和平均，这样可将注意力的分配放到中心节点与邻居节点之间的多处相关特征上。

仅供自己复习用，如有错误，欢迎指出，非常感谢！

参考

1. Joan Bruna, Wojciech Zaremba, Arthur Szlam, Yann LeCun: Spectral Networks and Locally Connected Networks on Graphs. ICLR 2014

2. Michaël Defferrard, Xavier Bresson, Pierre Vandergheynst: Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering. NIPS 2016: 3837-3845

3. Thomas N. Kipf, Max Welling: Semi-Supervised Classification with Graph Convolutional Networks. ICLR (Poster) 2017

4. William L. Hamilton, Zhitao Ying, Jure Leskovec: Inductive Representation Learning on Large Graphs. NIPS 2017: 1024-1034

5. Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, Yoshua Bengio: Graph Attention Networks. ICLR (Poster) 2018

本文目的在于学术交流，并不代表本公众号赞同其观点或对其内容真实性负责，版权归原作者所有，如有侵权请告知删除。

“综述专栏”历史文章

更多综述专栏文章，

请点击文章底部“阅读原文”查看

分享、点赞、在看，给个三连击呗！