论文分享 | Deeper Insights into GCN for Semi-Supervised Learning

转载 2020-05-27 16:26  阅读 104 次 评论 0 条

自从深度学习兴起,许多机器学习中有趣的问题重新被提起。最近提出的图卷积完美的整合了局部顶点特征和图拓扑信息。虽然GCN优于其他state-of-the-art的方法,但是GCN的工作机制并不清晰。本文介绍来自AAAI 2018的工作,深入的剖析了图卷积层中是什么在起作用,并且针对少量标签数据集上的GCN训练,提出Co-Training和self-Training方法。

Graph Conv

Kipf & Welling提出的图卷积包括下面几步:1. 利用图邻接矩阵创建图卷积滤镜。每个节点增加self-loop。这样新的邻接矩阵为,新的节点度矩阵。归一化得到滤镜

2. 定义图卷积层传播规则:

其中,为第l层的激活值矩阵,表示第l层训练权重矩阵。代表图卷积的操作是归一化的邻接矩阵左乘每层的输入。然后,节点的卷积特征输入标准的全连接层。

3. 叠加两层卷积,后接softmax,构建预测模型 :

在有标签的数据集上,使用交叉熵损失函数训练模型。

Why GCNs Work

The Key of GCN

对比GCN与普通的全连接网络的区别,FC分层传播规则为:

GCN与FC的传播法则唯一的区别在图卷积矩阵。分别使用GCN和FC在标记点为20个的Cora citation数据集上测试,发现即使只使用单层的GCN,效果也远远优于单层FC。

只看单层的GCN,他实际上只对输入数据做了两步操作:

1)通过图卷积生成了新的特征矩阵,

2)将生成的新特征Y喂给FC层。很显然,关键就在图卷积层。那么图卷积层做了什么? 搞清楚这个问题之前,我们先来看看什么是拉普拉斯平滑。

Laplacian Smoothing一条折线包含一系列离散的点pi。如何平滑这条折现?一个有效的方法是,将每个点移动到其邻居点的加权平均值:

其中,。如此操作,反复迭代。

将折线换成邻接矩阵为A的图,对角矩阵D对角线上的元素dii表示第i个顶点的度。那么上述的平滑写成矩阵的形式 :

其中,

这里的L是归一化的图拉普拉斯算子。定义,它有两个版本,即对称形式和标准形式。这样拉普拉斯平滑就是:

这里,控制平滑的强度。如果为图中的每个节点增加self-loop,邻接矩阵变为, 再将拉普拉斯算子的标准形式替换为对称形式,那么平滑方法与与GCN中的图卷积层一样。

此时,γ参数控制节点本身特征和邻居特征之间的权重,设置γ=1,可以得到熟悉的图卷积形式:

拉普拉斯平滑法计算每个顶点的局部邻居特征的平均值,作为顶点的新特征。因为同一类别的顶点之间往往连接紧密,所以平滑时他们的特征趋于相似,为后续的工作降低了难度。这就是GCN的工作原理。
When GCNs Fail

半监督GCN中建议最多使用两层叠加,可见,图卷积不是叠加层次越多越好。一方面卷积层越多越难训练,另一方面频繁使用拉普拉斯平滑会导致over-smoothing。来自不同类别的节点的特征会通过节点簇之间的连接混淆,这时,即使来自不同类别的两个节点特征也会很相似。作者使用不同层数的图卷积模型,在karate club数据集上试验。随机初始化模型参数,不训练。隐藏层维度为16,输出层维度为2,所有节点特征使用one-hot向量。实验结果,如图Figure2,它有效的说明了图卷积(拉普拉斯平滑)在小数据集上的影响。当使用一次时,两类节点没有很好的分开,使用两次时,已经能够比较好的分开了,继续增加次数,效果变得越来越差。由于节点数量少,两个类别的节点之间存在一定数量的连接,通过这些连接,不同类别节点之间的差异被平滑掉了。

 

graph中节点类别簇之间总是存在连接,多次使用拉普拉斯平滑,不同类别的顶点特征会收敛到同一个值。假设graph中有k个连通分量,各连通分量的指示向量为。对称拉普拉斯算子的特征值为0的特征空间,由各连通分量组成。对做特征分解,。根据图谱理论,如果图中没有二分分量,拉普拉斯矩阵的特征值范围[0, 2),特征值0对应的特征向量值为1。 m次重复拉普拉斯平滑法矩阵形式:

由于,m趋于正无穷时,m次重复平滑矩阵的最大特征值为1(其他特征趋于0)。结果会收敛于特征值为1的特征向量,比如的线性组合。回到图卷积,由于为graph中的每个节点加上self-loop,graph中没有二分组件。所以over-smoothing会使节点的特征没有差异。下图直观的给出了over-smoothing的影响。

另一方面,Kipf and Welling 2017中的GCNs使用了两层卷积,然而图卷积是一个局部滤镜,它线性聚合邻居节点的特征。当GCNs模型层数太浅,标记的数据太少时,标签信息恐怕不能够传播到整个图。在图Figure1,中可以看到当graph中标记数据的比率下降时,模型效果下降的速度很快。

Solutions

 

图卷积可以是一个强大的特征提取器,可以简化分类任务,但是它是一个局部滤镜,无法适应少量标记样本。这里作者给出的解决办法是从增加标记节点的数量入手。提出Co-Training和Self-Training方法,实际训练的时候,综合Co-Training和Self-Training两个方法,将random walk和GCN模型预测的高度置信的样本加入训练。至于两个方法标记的样本,可以取并集也可以取交集。视实际表现来定。Co-Training利用随机游走模型对图全局结构信息的探索,与GCN协同训练。随机游走是对GCN的补充。随机游走模型直接标记一部分置信度高的节点,这些节点都是每类labeled节点的最近邻居。将这部分模型标记的节点加入到labeled训练集,训练GCN。这里作者选择PARW作为协同训练的随机游走模型。首先,计算标准化absorption概率矩阵,表示节点i与节点j来自相同类别的概率。然后计算顶点属于类别K的置信度。将已经有标签的节点划分为集合,其中表示标签为类别K的节点集合。对每个类别K,计算置信度矩阵,那么pi就是顶点i属于类别k的置信度。最后,选择置信度最高的t个节点,将它们标签记为K,加入样本集,训练GCN。

Self-Training另一个增加labeled节点的方式是self-train。首先,在当前标记节点上训练GCN,使用训练好GCN预测节点的类别,然后,比较softmax得分,选择最有信心的预测节点和预测标签,加入有标签训练集。这样,利用扩增的数据集,继续训练GCN。当然,使用之前pre-train的GCN初始化参数。对比高度置信的GCN预测节点和原始标记节点,如果它们标签相同,那么它们特征必然近似。将这些预测节点加入训练集有助于提升鲁棒性和准确度。

Experiment

分别在 CiteSeer、Cora和 PubMed 三个文献引用数据集上测试模型表现。对于ParWalks设置。GCNs超参数设置与(Kipf and Welling 2017)中一样。GCN+V中,采样另外的500个标记样本作为验证集。从实验结果中可以看出,当训练数据很小时,本方法表现优于GCN。当训练数据足够大时,效果与GCN持平,因为足够多的标记样本已经可以训练出一个比较好的分类器了。

参考链接

https://arxiv.org/pdf/1801.07606.pdf

https://graphics.stanford.edu/courses/cs468-12-spring/LectureSlides/06_smoothing.pdf

http://www.kyb.mpg.de/fileadmin/user_upload/files/publications/attachments/Luxburg07_tutorial_4488%5b0%5d.pdf

http://www1.se.cuhk.edu.hk/~manchoso/papers/parw-nips12.pdf

本文地址:http://51blog.com/?p=10331
关注我们:请关注一下我们的微信公众号:扫描二维码广东高校数据家园_51博客的公众号,公众号:数博联盟
温馨提示:文章内容系作者个人观点,不代表广东高校数据家园_51博客对观点赞同或支持。
版权声明:本文为转载文章,来源于 苏涛 ,版权归原作者所有,欢迎分享本文,转载请保留出处!

发表评论


表情