导读
节点分类是图数据挖掘中一个基础而且重要的任务，已有的工作通常先使用图卷积网络（GCNs）学出每个节点的表达然后再分类。 但是大多数主流的图神经网络层数比较浅（仅有两层或三层），而且缺乏“图池化”机制，这使得每个节点只能获取有限的局部信息而无法感知全局信息，从而限制了模型的性能。现实中，由于海量的图数据规模和高昂的标注成本，我们通常面临的是一种弱监督节点分类的场景（即标记数据很少，待预测的节点和标记节点通常距离较远），这更加要求模型有足够大的感受野来感知到标记样本的信息。本次报告以增大图网络的感受野为出发点，介绍了我们在IJCAI2019上的最新工作。在这次分享会中：
- 我首先介绍了弱监督图节点分类的任务和存在的挑战；
- 接着分享了一些相关的经典论文；
- 最后介绍了我们最新的IJCAI 2019的工作H-GCN：, 通过引入粗化和还原操作，设计了层次化的对称图神经网络，分别用9层和11层的网络取得了SOTA的结果。当训练数据极少时，相比之前方法至少有6个百分点的精度提升。
作者简介
呼奋宇，中国科学院自动化研究所智能感知与计算研究中心17级直博生，目前的主要研究方向是图数据挖掘。已发表IJCAI2019论文一篇。
具体内容推文分享
第一部分：任务及挑战
图节点分类的任务如图1所示。在现实生活中，图数据无处不在，例如社交网络，知识图谱，蛋白质分子等。许多应用都需要分析每个节点的性质，图节点分类任务就是这样一个基础的任务：给定图数据中部分样本的标签，预测其他节点的类别。
图1
介绍图节点分类的一些挑战。主要包括：图数据的非欧式空间难以应用传统的深度学习方法；节点之间的关系错综复杂；实际应用中标注数据相比总体数据很稀少等。
第二部分：介绍图神经网络相关的一些经典论文，包括：GCN、GraphSAGE、GAT、Diffpool和Harp
图卷积神经网络的示意图如图2所示。每个节点通过邻域聚合的方式，把它的邻居节点的特征通过一定的方式聚合到一起，学出来中心节点的表达。一般而言，n层图卷积网络可以聚合n-hop内的所有邻居节点的信息。然而，传统的GCN，GraphSAGE、GAT等图卷积方法通常只有2到3层网络，因此每个节点只能获取有限的局部信息而无法感知全局信息，从而限制了模型的性能。
图2
设计层次化的深度图神经网络可以更好地捕获到全局信息。Diffpool通过学习的方式学习图上的“pooling”操作，但是它的每一层网络都需要一个辅助的链接预测的任务和一个正则项来约束学习过程。当神经网络加深时，这些额外的超参数可能会比较难调。Harp设计了一套coarsening（粗化）机制，先把图的规模逐层减小，然后在最小的图上通过Deepwalk等方法学出来每个超节点的表达，最后再逐层还原。但Harp不是端到端的模型，它是每一层上单独使用deepwalk进行训练。即后面的神经网络对前面网络的表达优化没有影响，当前面网络学习的表达不好时，后面的网络也会因此变差，容易造成误差累积。因此针对图节点分类任务设计一个端到端的层次图神经网络就显得非常有必要。
第三部分：介绍IJCAI 2019的工作H-GCN，论文地址: https://arxiv.org/abs/1902.06667 ,代码地址: https://github.com/CRIPAC-DIG/H-GCN (预计7月底之前公布)
图3
H-GCN的网络结构如图3所示，它是一个对称的网络结构：在图3的左侧，在每次GCN操作后，我们使用Coarsening方法把结构相似的节点合并成超节点，因此可以逐层减小图的规模。由于每个超点对应了原始图中的一个局部结构，对超节点组成的超图进行图卷积操作就可以获得更大的更大的感受野。对应地，在示意图的右侧，我们在每次GCN操作后将超节点进行还原，即可得到每个原始节点的表达。同时，我们在对称的神经网络层之间加了shortcut连接，从而可以更好地训练。
具体的coarsening方法如图4所示。
图4
为了验证H-GCN的有效性，我们在主流的节点分类任务上进行了测试，数据集包括引文数据集和知识图谱。分类结果如表1所示，H-GCN取得了SOTA的结果。一个有意思的发现是：相比在引文数据集上的效果，H-GCN在知识图谱数据集NELL上的精度远远超过其他baseline方法。这是因为在NELL数据集上的训练数据量最少（仅0.3%的标记率），这可以定性地说明H-GCN能有效的增大感受野，使节点感受到相距比较远的标记节点的标签信息。
表1
为了进一步定量验证H-GCN对模型感受野的增大作用，我们在Pubmed上逐渐减小训练数据量，从每类20个标记样本到每类仅5个样本，结果如表2所示。可以发现，当训练样本逐渐减少时，baseline的精度下降非常明显，而H-GCN却能保持很高的准确率。在每类仅5个样本时，H-GCN比其他方法至少高出6个百分点。这是个非常有用的性质，因为现实生活中由于海量的数据量和高昂的标记成本，我们通常没有太多的标记样本，而H-GCN更大的感受野可以更充分地利用标记样本的标签信息。
表2
相比于传统模型，H-GCN的一个特点是网络层数更深了，我们进一步分析了层数加深对性能的影响。如图5所示，当网络层数加深时，精度逐渐提升，但是当网络太深时，由于过拟合等原因，精度开始下降。在实验中，我们在引文数据集上使用了4层粗化层（对应的网络共有9层），在NELL数据集上使用了5层粗化层（对应的网络共有11层），这可能是由数据集的规模不同导致的。因为NELL的数据集最大，所以网络容量可以更大一点。
图5
总结
图数据上的coarsening/pooling机制可以有效地增大模型的感受野，从而获取足够的全局信息。不同于传统的浅层图神经网络，我们提出了层次化的深度（分别为9层和11层）图卷积模型H-GCN，在节点分类任务上取得了SOTA的结果。特别地，在训练数据非常少的场景下，H-GCN的提升更为明显。
