作者 | yyl424525
来源 | CSDN博客
编辑 | AI科技大本营
文章目录
1 相关介绍
1.1 Simple Graph Convolution (SGC)提出的背景
1.2 SGC效果
2 Simple Graph Convolution 简化的图卷积
2.1 符号定义
2.2 图卷积网络GCN
2.3 简化的图卷积SGC
3 谱分析
3.1 在图上的初步做法
3.2 SGC and Low-Pass Filtering 简化的图卷积和低通滤波器
4 相关工作
4.1 图神经网络
4.2 其他在图上的工作
graph embedding methods
5 实验结果
5.1 Citation Networks & Social Networks
5.2 下游任务
Text classification
Semi-supervised user geolocation
Relation extraction
Zero-shot image classification
Graph classification
论文:Simplifying Graph Convolutional Networks 简化的图卷积网络GCN(SGC)
作者:Felix Wu, Tianyi Zhang, Amauri Holanda de Souza Jr., Christopher Fifty, Tao Yu, Kilian Q. Weinberger
来源:ICML 2019
论文链接:
https://arxiv.org/abs/1902.07153v1
Github代码链接:
https://github.com/Tiiiger/SGC
GCN在学习图的表示方面已经引起了广泛的关注,应用也非常广泛。GCNs的灵感主要来自最近的一些深度学习方法,因此可能会继承不必要的复杂度和冗余计算。文中通过反复消除GCN层之间的非线性并将得到的函数折叠成一个线性变换来减少GCNs的额外复杂度。并从理论上分析了得到的线性模型SGC,并证明了SGC相当于一个固定的低通道滤波器和一个线性分类器。实验结果表明,这些简化不会对许多下游应用的准确性产生负面影响。此外,得到的SGC模型可扩展到更大的数据集,并且比FastGCN产生两个数量级的加速。
1 相关介绍
1.1 Simple Graph Convolution (SGC)提出的背景
传统的机器学习方法的复杂度变化趋势都是从简单到复杂。例如从线性Perceptron到非线性MLP,从简单的线性图片filters到CNN都是这个趋势。GCN也是源于传统的机器学习方法,继承了这个复杂度的变化。此文的目的就是要把非线性的GCN转化成一个简单的线性模型SGC,通过反复消除GCN层之间的非线性并将得到的函数折叠成一个线性变换来减少GCNs的额外复杂度。
SGC中的特征提取等价在每个特征的维度上应用了单个固定的filter。
1.2 SGC效果
实验表明
2 Simple Graph Convolution 简化的图卷积
2.1 符号定义
数据集中只知道部分节点的标签,目标是预测未知的节点的标签。
2.2 图卷积网络GCN
GCN vs MLP
GCNs和MLPs相似,都是通过多层网络学习一个节点的特征向量Xi,然后再把这个学到的特征向量送入的一个线性分类器中进行分类任务。一个k层GCN与k 层MLP在应用于图中每个节点的特征向量Xi是相同的,不同之处在于每个节点的隐藏表示在每一层的输入时是取的它的邻居的平均。
每个图中的卷积层和节点表示都是使用三个策略来更新
Feature propagation 特征传播
GCN的特征传播是区别MLP的,因为每一层的输入都是节点局部邻居的平均值:
(2)
用一个简单的矩阵运算来表示公式(2)的更新:
(3)
用公式(2)对所有节点进行同时更新,得到了一个简单的稀疏矩阵乘法:
(4)
这一步平滑了沿着图的边的局部隐藏表示,并最终支持在局部连接的节点之间进行类似的预测。
Feature transformation and nonlinear transition
在局部平滑之后,一个GCN层就等于一个标准的MLP。每一个层对应一个可学习的权重矩阵
,所以平滑处理了的隐藏特征表示是线性转换的(后面乘一个参数矩阵是线性的)。最后在逐节点应用一个非线性激活函数,例如ReLU就可以得到输出的特征表示
(5)
分类器
对于节点分类任务,最后一层和MLP相似,都是使用一个softmax分类器预测节点的标签,一个K KK层的GCN的所有节点的类别预测可以写作:
(6)
2.3 简化的图卷积SGC
在传统的MLP中,层数变深加强了网络的表达能力,因为它允许创建特征的层次结构,例如,第二层的特征构建在第一层特征的基础上。在GCNs中,每一层都有一个重要的函数:在每一层中,隐藏的表示在1跳距离的邻居之间求平均值。这意味着在k kk层之后,一个节点从图中所有k kk跳的节点处获得特征信息。这种效果类似于卷积神经网络,深度增加了内部特征的感受野。虽然卷积网络可以在层数加深时提升性能(Deep networks with stochastic depth, 2016),但通常MLP的深度只限于为3至4层。
线性化
假设GCN层之间的非线性不是最关键的,最关键的是局部邻居的平均聚合操作。因此,考虑删除每层之间的非线性转换函数(如ReLU),只保留最终的softmax(以获得概率输出)。得到的模型是线性的
(7)
简化如下
(8)
这个简化的版本就叫做Simple Graph Convolution (SGC)。
逻辑回归
公式(8)给了SGC的一个自然直观的解释:SGC由两部分组成
可以看出,由于计算不需要权值,因此可以把这部分计算作为特征的预处理步骤,整个模型的训练可以直接简化为对预处理特征的多类逻辑回归。
优化细节
逻辑回归的训练是一个凸优化问题,可以用任何有效的二阶方法或随机梯度下降法进行执行(Large-scale machine learning with stochastic gradient descent,2010)。在图连通模式足够稀疏的情况下,SGD可以很自然地运用在非常大的图上,SGC的训练比GCN快得多。
3 谱分析
文中从图卷积的角度来研究SGC,并证明了SGC在图谱域上对于应一个固定的滤波器。此外,还证明了在原始图上添加自循环,即renormalization trick,可以有效地缩小底层图的谱。在这个缩放的谱域上,SGC充当一个低通滤波器,在图上生成平滑的特征。因此,邻居节点倾向于共享相似的表示,从而实现预测。
3.1 在图上的初步做法
经过傅里叶变换的信号x和滤波器g的GCN卷积操作为
(11)
推导过程可以看GCN原始论文:Semi-Supervised Classification with Graph Convolutional Networks用图卷积进行半监督分类
最后,通过将卷积推广到d dd维的通道输入中的多个滤波器上,并在每一层之间用非线性激活函数的分层模型,就得到了如公式(5)所定义的GCN传播规则
(5)
3.2 SGC and Low-Pass Filtering 简化的图卷积和低通滤波器
定理1
对于一个简单,没有孤立节点的无向图。令
分别是对称归一化的拉普拉斯矩阵
的最小和最大的特征值。
的最小和最大的特征值。则有
(12)
关于定理1的证明,可参考文中提供的附录部分。
从定理1可以看出,当γ>0 \gamma>0γ>0时,相当于图中添加了自循环,则归一化的拉普拉斯矩阵的最大特征值会变小。
图2描述了在Cora数据集上使用的三种情况下特征值(频率)的变化和滤波器系数(谱系数)的变化关系
4 相关工作
4.1 图神经网络
4.2 其他在图上的工作
在图上的方法可分为两类:graph embedding methods和graph laplacian regularization methods。
graph embedding methods
5 实验结果
5.1 Citation Networks & Social Networks
Efficiency
5.2 下游任务
使用5个下游任务来研究SGC的适应性:
Text classification
Semi-supervised user geolocation
Relation extraction
Zero-shot image classification
Graph classification
图分类要求模型使用图结构对图进行分类。
(How powerful are graph neural networks?,ICLR 2019)从理论上证明了GCNs不足以区分特定的图结构,并证明了GIN更具表现力,在各种图分类数据集上获得了 state-of-the-art的结果。
将DCGCN中的GCN替换为SGC,分别获得NCI1和COLLAB数据集上的71.0%和76.2%,这与GCN相当,但远远落后于GIN。
在QM8量子化学数据集上,更高级的AdaLNet和LNet在QM8上得到0.01MAE,远远超过SGC的0.03 MAE。
原文:
https://blog.csdn.net/yyl424525/article/details/102576875