Geom-GCN（几何图形卷积网络）论文分享

Geom-GCN（几何图形卷积网络）论文分享

一、背景

  MPNNs（消息传递网络）已成功地应用于各种实际的图的表示学习中。然而，MPNNs聚合器的两个基本弱点限制了它们表示图结构数据的能力:丢失邻域节点的结构信息，缺乏捕获异配图中的远程依赖关系的能力。

  其中MPNNs是从现有模型（GCN、Gated-GNN等等）抽象出来的一个框架，通过每个节点向其邻居节点发送其特征表示，一条消息;然后通过聚合来自邻域的所有消息更新其特征表示。

  回到主题，现有模型的缺陷一：目前大部分图神经网络普遍丢失领域节点的结构信息，这个是普遍存在的，例如GCN一般是直接使用平均聚合或者最大聚合的方式直接聚合邻域节点信息，没有利用邻域节点的结构信息。这个是什么意思呢，如图所示，如果不建模这些结构信息，现有的MPNNs就无法区分某些非同构图。在这种情况下，MPNNs可能会将非同构图映射到相同的特征表示，这显然不是图表示学习所需要的。这种聚合方式，基本上不会对领域节点的结构进行分析，无法获取每个邻域节点对中心节点具体贡献情况。而在CNNs里面使用卷积核来完成对邻域信息的聚合，区分邻域信息，本文以此为启发点，对图神经网络的几何关系进行建模，完成对图神经网络结构信息的提取。

  第二个缺陷是缺乏捕获异配图中的远程依赖关系的能力，这个异配图具体的定义我查了一下但是没有查到，只看到有篇博客里讲了一句：在异配图中，同一类节点的结构相似度很高，但彼此之间距离很远。也就是说在这类图中存在结构很相似的节点，在实际图中距离很远。而按照我们对MPNNs(例如GCN)的理解，目前的图神经网络是只聚合来自附近的节点信息。这样的话无法利用一些相隔很远但是很相似的节点信息，导致MPNNs的表达能力收到限制。CNNs是通过多层连接的方式提取复杂和全局的特征，例如DenseNet。但是多层MPNNs又有两个问题导致它效果不好，一个是多层MPNNs会导致大量不相关信息不可分辨地混合在一起，这意味着相关信息会被洗掉，无法有效提取。第二个是在多层MPNNs中，不同节点的表示将变得非常相似，而且每个节点的表示实际上携带了关于整个图的信息。所以，这里就无法借鉴CNNs的方法了。

  针对上面这两个问题，提出了几何卷积网络Geom-GCN：通过节点嵌入方法（ISOMAP、PoinCare embedding）将一个图映射到一个连续的潜在空间，然后利用潜在空间中定义的几何关系来建立用于聚合的结构邻域。此外，设计了一个双层聚合器，操作在结构邻域更新节点的特征表示。其中，节点嵌入的方法里包含了对空间结构相似行的计算。

二、GEOMETRIC AGGREGATION SCHEME（几何聚合方案）

  原图A1->A2映射到一个潜在连续空间。
  A2->B1 构造邻域, 在B2中，图中的邻域包含图中所有相邻节点;潜在空间中的邻域包含了虚线圆内半径为圆心的节点。关系运算符T由一个彩色的3*3网格表示，其中每个单元对应于红色目标节点的几何关系。
  C图是结构邻域上的双层聚集。虚线箭头和实线箭头分别表示低级和高级聚合。蓝色和绿色箭头分别表示图中邻域和潜在空间上的集合。蓝色和绿色的点是虚拟节点。低级聚合就是把隐含领域节点和实际领域节点聚合到虚拟节点，然后高级聚合是将虚拟节点聚合到中心节点，完成对中心节点的更新。我们在后面讲解如何设计双层聚集的方案。

2.1 Geom-GCN的一种实现

2.1.1 节点嵌入

  节点嵌入:我们使用了三种嵌入方法:Isomap、PoinCare嵌入和struc2vec，从而产生了三个Geom-GCN变体:Geom-GCN-i、Geom-GCN-P和Geom-GCN-s。
  Isomap算法，我查了资料，它是引进了邻域图，样本只与其相邻的样本连接，他们之间的距离可直接计算，较远的点可通过Floyd算法算出最小路径算出距离，在此基础上进行降维保距。
  PoinCare嵌入，是一种双曲几何嵌入，针对欧式空间中表达能力不足的问题提出的。
  在struc2vec的假设中，顶点u和顶点v是具有空间结构相似的。他们的度数分别为5和4，分别连接3个和2个三角形结构，通过2个顶点(d,e;x,w)和网络的其他部分相连。

2.1.2 空间划分

  节点v的结构邻域N (v) = ({Ng(v)， Ns(v)}，出)包括其在图空间和潜在空间中的邻域。图中邻域Ng(v)由图中v个相邻节点的集合，以及与v的距离小于潜在空间中的参数列的邻域Ns(v)组成。我们通过从0开始增加倾斜，直到Ns(v)的平均基数等于Ng(v)， v v即来确定倾斜。，当图和潜在空间中的平均邻域大小相同时。我们在欧氏空间中使用欧氏距离。在双曲空间中，通过节点在局部切平面上的欧几里得距离来逼近两个节点之间的测地线距离。

2.1.3 双层聚合

  最后，采用与GCN (Kipf &Welling, 2017)作为低层聚合中的聚合函数p
  其中，deg(v)是图中节点v的度数，而琅(·，·)是一个克罗内克函数，只允许包含关系r到v的节点。将所有虚拟节点ev,l+1 (i,r)的特性进一步聚合到高级聚合中。聚合函数q是||的连接，用于除最后一层之外的所有层，最后一层使用mean作为其聚合函数。然后，给出了整体的两层聚合
  其中ReLU为非线性激活函数参数(·)，Wl为反向传播估计的权重矩阵。

三、实验结果

  作者在9个数据集上进行了测评，发现通过三种空间嵌入方式的分类准确率普遍高于基线算法，
  然后作者做了一个消融实验，就是去掉图空间领域或者去掉潜在空间领域进行分析哪个领域的作用更大，结果是图空间作用大
  作者又交叉搭配使用空间嵌入方式，比如图空间领域使用isomap，潜在空间领域使用poincare等等

四、总结

  我们解决了现有图上消息传递神经网络的两个主要弱点:区分结构的丢失和远程依赖。
  我们利用卷积原理:在有意义的空间上进行空间聚合，我们的方法因此从图中提取或恢复嵌入空间中丢失的信息(区分结构和长期依赖关系)。
  我们提出了一种通用的几何聚合方案，并用几种特定的Geom-GCN实现实例化了它，我们的实验验证了与目前最先进的几何聚合方案相比的明显优势。