Hierarchical Graph Representation Learning with Differentiable Pooling

1. Abstract说什么?

​ 最近,图神经网络通过有效地学得节点嵌入,革新了图表示学习领域并在节点分类和链路预测取得了很好的效果。然而,目前的GNN方法都是平的而不是层次的表示,这对于图分类任务来说是个很大的问题,图分类的目标是预测整个图的标签。在此我们提出DIFFPOOL,一个可微的能生成层次化的图表示的图池化模块,并且还能和各种图神经网络以一种端到端的方式结合。DIFFPOOL在一个深度GNN中为每层的节点学得一个可微的软聚类任务,把节点投影到一个聚类点的集合,然后形成下一个GNN层的粗糙输入。我们的实验结果展示组合现有的GNN和DIFFPOOL在图分类任务上产生了一个平均5%-10%的准确度提高,比较所有显存的池化方式,在4/5benchmark上达到了最先进的效果。

image-20200409174644007
image-20200409174644007

2. end to end 什么意思?

​ 就是说它能够完成全过程,能够读取数据到输出结果。它忽略了中间要经过的几个步骤,不被那些限制。

3. Hard vs Soft Clustering 什么意思?

​ 硬聚类就是每个数据项只能分配给一个类。而软聚类就是每个数据并非非黑即白,软聚类中一个数据项能够存在不同的类别中。Fuzzy C-means是一个著名的软聚类算法,它基于模糊逻辑总是归类于FCM算法。

4. 介绍讲了什么?

​ GNN大火,人们想把神经网络应用到图结构数据上,如社交网络或者图表示的分子。通用措施是把底层的图看成是一个计算图,然后在图上对节点信息进行传播、变换等学得节点嵌入,然后再用神经网络的一般做法去做,进而进行节点分类、链路预测等等,整个模型是end to end的。

​ 有一个大问题,现在GNN都是扁平的,通过边传播信息进行推断。但是,为了保存所有结构信息,我们得对小结构进行编码(就比如分子)。同时对于图分类任务,全图的pool会损失掉很多信息,妨碍全图的预测任务。

​ DIFFPOOL是层次地、end to end的一个图池化模块。图不像CNN那样有局部概念且可以逐层粗糙化。并且,图数据集里的图节点数量和便数量都是不一样的。

​ 我们需要一个模型学习聚类节点在基础层的顶部构建一个多层的支架。我们的DIFFPOOL在深度GNN的每一层学得一个可微的软分类任务,基于学得的表示映射节点到一个聚类集合。在这个框架中,我们GNN每一层粗化了网络,经过训练后能生成一个层次化的表示。我们看到DIFFPOOL能和各种各样的GNN做合起来,效果很好。最后,展示一下可解释性。

5. 有何相关工作?

​ 我们的工作建立于现有的对图神经网络和图分类的研究工作上。

​ 一大堆图神经网络近些年被提出,基于各种卷积神经网络的结构,如CNN、循环神经网络、周期神经网络和loopy belief propagation。大多数这些方法适用于Gilmer提出的神经消息传播框架,GNN用一个可微的聚类函数迭代计算邻居节点的属性。Hamilton提出了一个概念上的review,Bronstein描绘了和谱图卷积之间的联系。

​ 用图神经网络做图分类任务。GNN被应用到了很多任务上,包括节点识别、链路预测、图分类和化学信息学。在图分类任务中,主要挑战是从节点嵌入到整个图的表示。简单的方式是求和或者平均,引入虚拟节点,或者在集合里用深度学习完成聚集。然而,所有方法都是从全图在一个层上嵌入,没有层次化的表示,因此不能不换显示图的自然结构。一些想做成CNN那样,但是没有顺序,所以很难同构。

​ 最后,很多工作想合GNN和确定的图聚类算法,一个两状态方法。然而,不像之前提到的,我们尝试以end to end的类型学得一个层次化的结构,而不是依靠确定的图聚类子程序。

6. 方法是什么?

​ 关键的idea是DIFFPOOL通过提供一个可微的模块层次化地池化图节点,所以能够建造深层、多层的GNN模型。在这个部分,我们给出DIFFPOOL的概要然后展示怎么应用到深度GNN结构。

6.1 准备阶段

​ 图的表示是(A, F),即邻接矩阵和节点属性矩阵。邻接矩阵非0即1,节点有d个属性。与其它机器学习分类方法比起来,我们需要一个程序将每个图转化到一个有限维向量空间。

图神经网络 在这个工作中,我们为了以一个end to end的模式为了图分类学到更有用的图表示。特别地,我们考虑GNN用了下面信息传播结构:

​ 有很多种M的实现,比如GCN的线性变换和RELU。我们提出的可微的池化模型能够应用到任何上面公式形式的GNN。

​ 一个完整的GNN模块将会运行K次上述公示的迭代生成节点嵌入,K通常在2-6.我们用Z=GNN(A, X)来表示任意K次迭代的GNN模型。

存储GNNs和池化层 GNN完成公式固有的扁平,因为只以一个图上沿着边传播信息。本次工作目标就是定义一个通用的端到端的可微策略允许层次地存储很多GNN模块。给出Z,GNN模块输出和一个邻接矩阵A,我们想定义一个策略输出一个新的粗化的包含m<n个节点的图,邻接矩阵A‘和节点嵌入Z’.这个过程可以重复L次,生成一个L个GNN层的模型。那么,池化策略很关键了。

6.2 可微的通过学的任务的池化

​ 我们提出的方法,通过用GNN模型的输出学得一个节点上的分配矩阵解决上面挑战。用GNN既提取图分类的嵌入,又提取对层次化池化有用的节点嵌入,然后得到每层的分配矩阵。

用分配矩阵的池化 我们标注在l层学得的分配矩阵$S^{(l)}$,每行代表l层的一个节点, 每列代表l+1层的一个类。之解决上,给l层每个节点提供了到粗化的下一层的一个软分类。

​ 假定第l层的分配矩阵算过了。我们标注这层输入的邻接矩阵$A^{l}$并且节点嵌入矩阵为$Z^{(l)}$,具体就是每层输入为A,X,中间变量Z,S,输出A,X。

​ 方程3用节点嵌入Z然后根据S据集这些嵌入,生成下一层的聚类,相似地,方程四把邻接矩阵输入,申城粗化的邻接矩阵。

​ 通过3,4,DIFFPOOL层粗化了图,下一个层的邻接矩阵A是粗糙的邻接矩阵,每个节点代表上面层的一类节点。注意到A是一个实数矩阵,有权图,每个值代表连接强度。类似的,第i行代表i类的嵌入。组合一起,A和X被用于另一个GNN层的输入,下面我们详细说明。

学得分配矩阵 在下面我们描述DIFFPOOL的结构,怎么生成S和Z,我们用两个不同的GNN作用到X和A上,然后,嵌入的GNN是一个标准的GNN模块。S是一个池化GNN,然后softmax逐行使用,GNN的输出维度对应着一个预先定义好的l层的最大聚类数量,是模型的超参数。

​ 注意到两个GNN消耗着相同的输入但参数不同角色不同。

​ 在基本例子中,输入矩阵就是简单的A和F,在倒数层L-1层中用DIFFPOOL,我们设置分配矩阵为一个向量,所以所有节点都会被分配到一个类,生成整个图的最终嵌入。最终输出嵌入能够被用作特征输入一个可微的分类器,然后整个系统能够用随机梯度下降做end to end的训练。

排列不变式 注意到为了有用于图的分类,池化层应该在节点排列下不发生变化。对于DIFFPOOL我们得到如下正向结果,展示任何基于DIFFPOOL的GNN模型都有排列不变性,只要GNN成分是排列不变的。

​ 定理说明,只要DIFFPOOL用的GNN是不变的,那么DIFFPOOL的两个shrink的式子就不会变。(巧妙的甩锅)

6.3 辅助的链路预测目标和熵正则化

​ 在实践中,池化GNN只用图分类得到一个梯度的信号很难训练。直觉上,我们这是个非凸问题很难摆脱局部极值。为了减轻这些issue,我们用一个附加的链路预测目标训练池化GNN,直觉上相邻节点应该池化一起。实践中,每层的l,我们最小化一个小目标函数。池化GNN另一个重要的特点是每个节点输出的分配矩阵应该相近与one-hot向量,所以每个类或者子图是清晰定义的。我们因此正则化分类任务的熵通过减小一个每层的熵函数。在训练中,每层的两个损失加入到分类损失中。实践中我们观察到带着小目标的训练花费更长时间收敛,但是不仅达到了更好的表现还有更好的可解释性。

7. 实验设置?

​ 我们评估了DIFFPOOL和很多SOTA的图分类方法,回答了以下问题:

  • 和其它pooling方法比怎么样?
  • DIFFPOOL和GNN结合比起其它图分类任务怎么样?
  • DIFFPOOL计算的类可解释吗?

数据集 为了调查DIFFPOOL学得复杂深层结构的能力,我们选了很多大型数据集。我们用蛋白质数据集和社交网络数据集,科学合作数据集。我们用10折交叉验证评估模型表现,报告10折的平均accuracy。

模型设置 在我们的实验中,GNN模型是建立在GRAPHSAGE结构上的,因为我们发现这个结构比起标准GCN又最好的表现。我们用GRAPHSAGE的平均变种然后在两个GRAPHSAGE层之后应用一个DIFFPOOL层,总共两个DIFFOOL层被用在这个数据集上。对于小的数据集,1个DIFFPOOL就能达到相似地效果。在每个DIFFPOOL层之后,3个图卷积层被应用,在下一个DIFFPOOL曾之前,或者读出层。嵌入矩阵和非陪矩阵通过两个分离的GRAPHSAGE模型。在两个DIFFPOOL层架构中,类别数被设置为节点数的25%,在1个DIFFPOOL层架构中,聚类数量被设置为10%。在每层GRAPHSAGE之后有个批正则化。我们还发现加入一个l2正则化让训练更稳定。我们还测试了一个DIFFPOOL在 Structure2Vec结构上的类比,为了说明DIFFPOOL能被应用到其它GNN上。所有的模型被训练3000epoch还有早停极值,我们还评估了两个简化版本DIFFPOOL。

  • DIFFPOOL-DET 分配矩阵用一个确定图聚类算法生成;
  • DIFFPOOL-NOLP是一个diffpool的变种,链路预测目标被取消了。

7.1 baseline方法

​ 在和其它图分类任务表现得比较中,我们考虑基于GNN的baseline还有最先进的基于核的方法。

基于GNN的方法

  • GraphSAGE和全局池化。其它GNN变种被忽略了;
  • Structure2Vec是最先进的结合GNN与潜在变量模型的算法,他用全局池化;
  • CNN对于图的边条件过滤器包含边信息到GCN模型里并且用一个图粗糙算法表现池化。
  • PatchySan为每个节点定义了一个接受域,然后用一个经典的节点顺序,应用卷积到节点嵌入的先行顺序。
  • Set2Set在传统GNN里取代了全局池化用聚集。SetsSet的聚集比meanpooling更好,我们用GraphSage作为GNN基模型。
  • SortPool应用了一个GNN结构然后表现出了单一的软池化层在一个1维卷积后。

​ 对于所有的GNN baselines,我们用10折交叉验证之前作者的报告。对于GraphSAGE和Set2Set的baseline,我们用基本完成和超参数搜索。当baseline方法没有达到之前效果,我们联系之前作者然后用他们代码跑模型,在前作者指导下完成超参数调整。

基于和的算法 我们用子图,最短路,weisfeiler-lehman核,还有weisfeiler-lehman优化任务核作为核baselines。对于每个核,我们计算正则克矩阵。我们用C-SVM的libsvm计算分类准确度,用10折交叉验证。C参数通过10折交叉验证在训练集上选择。不仅如此,对于两种方法我们额外选择迭代次数。

7.2 图分类的结果

​ 表1比较了DIFFPOOL核最先进的图分类方法的表现。这些结果对于Q1和Q2给出了积极的回答,我们观察到我们的DIFFPOOL方法得到了最高的平均效果,提高了6.27%,并且在4/5数据集上达到了最好的效果。有趣的是,我们的简化模型,Diffpool-det在collab数据集达到了最好的效果,能够从之前的图聚类算法中达到最好效果。Diffpool有时训练不稳定,在不同run中效果明显不同,尽管相同超参数。加入链路预测目标函数让训练更稳定,减少了标准预测精度差。

Structure2Vec上的可微池化 Diffpool可以被应用到其它GNN中捕获图数据的结构信息。为了更支持Q1,我们应用DiffPool到Structure2Vec上。我们用S2V和三个层结构,就想报告的那样。在第一个变种中,一个Diffpool被应用到一个s2v后,两个s2v被放到了diffpol的顶上。第二个变种在一二层s2v上都有个diffpool。在两个变种中,s2v模型被用来计算嵌入矩阵,graphsage模型被用来计算分配矩阵。

​ 结果就分类效果而言挺好的。我们看了diffpool显著提高了s2v在两个数据集上的效果。证明diffpool是个通用的提效手段。

running time 预计时间很长,但没差太多,因为减少了图的大小。速度甚至12倍快了。

7.3 Diffpool聚类任务的分析

层次化聚类任务 为了解决Q3,我们研究了DiffPool的分类过程可视化。很容易理解。

Dense还是稀疏子图结构 我们观察DiffPool会倾向于分类Dense的节点,对稀疏节点作用差。

对相似表示的节点的分类 因为分类网络基于输入节点和它们邻居计算软分类任务,相似feature和邻居的会分到相似类。事实上,不相连的属性一样的节点也会被分到一起。

​ 事实上根据定理1中的假设,我们认为节点是可以通过属性识别的。在很多数据集中如此。链路预测不利于这种远程连接,复杂GNN聚类函数区别节点在结构和属性上是相似的,整体矿机依然没变。

预训练最大类数目灵敏度 我们发现分配根据网络和C和最大聚类数不同。C大模型更复杂,C大噪音多灵敏度低。尽管C是预定义的,池化学得用恰当数目的类通过end to end训练。尤其,一些类可能不会被分配矩阵用到。一致于没用到的类的列对所有节点有更低的值。在2中被观测到,节点被分配到3个类。

8 结论?

​ 我们引入了GNN的可微的池化方法提取真实图的复杂层次化结构。通过用提出的池化层连接现有的GNN模型,达到了很好的效果。未来想要用硬聚类减少计算同时确保可微性,应用层次池化方法给其它下游任务。