ICLR 2020 开源论文 | 隐空间的图神经网络：Geom-GCN
作者丨纪厚业
学校丨北京邮电大学博士生
研究方向丨异质图神经网络及其应用
引言
图神经网络（Graph Neural Network）已经成为深度学习领域最热⻔的方向之一。作为经典的 Message-passing 模型，图神经网络通常包含两步:从邻居节点收集消息 message，然后利用神经网络来更新节点表示。但是 Message-passing 模型有两个基础性的问题：
1. 丢失了节点与其邻居间的结构信息：
主要指拓扑模式相关的信息；
GNN 的结构捕获能力已经有了相关论文，下图来自 19 ICLR GIN How Powerful are Graph Neural Networks。
2. 无法捕获节点之间的⻓距离依赖关系：
大多数 MPNNs 仅仅聚合 k 跳内的节点邻居消息来更新节点表示。但是，图上两个节点可能具有相似的结构（社区中心、桥节点），即使他们的距离很远；
可能的解法是将现有的 GNN 堆叠多层，但是这可能带来过平滑问题。
针对上述问题，本文提出了一种 geometric aggregation scheme，其核心思想是：将节点映射为连续空间的一个向量（graph embedding），在隐空间查找邻居并进行聚合。
本文的主要贡献：
提出了一种 geometric aggregation scheme，其可以同时在真实图结构/隐空间来聚合信息来克服 MPNNs 两个基础性缺陷；
提出了一种基于 geometric aggregation scheme 的图神经网络 Geom-GCN；
实验验证了模型的效果。
模型
Geometric Aggregation Scheme
如下图所示，Geometric aggregation scheme 主要包含 3 个部分：node embedding (panel A1-A3)，structural neighborhood (panel B) 和 bi-level aggregation (panel C)。
A1->A2：利用 graph embedding 技术将图上的节点（如节点 v）映射为隐空间一个向量表示 。
A2->B1：针对某一个节点 v（参看 B2 中的红色节点）周围的一个子图，我们可以找到该节点的一些邻居 。
B2：圆形虚线（半径为 ρ）内的节点代表了红色节点在隐空间的邻居：
圆形虚线外的节点代表了节点在原始图上的真实邻居 。既然节点已经表示为向量，那么不同节点之间就有相对关系。在 B2 的 3x3 网格内，不同节点相对于红色节点有 9 种相对位置关系
，关系映射函数为
。
B3：基于 Bi-level aggregation 来聚合邻居 N(v) 的信息并更新节点的表示。
Low-level aggregation p：聚合节点 v 在某个关系 r 下的邻居的信息。这里用一个虚拟节点的概念来表示。
High-level aggregation q：聚合节点在多种关系 R 下的邻居的信息。
Non-linear transform：非线性变化一下。
其中， 是节点 v 在第 l 层 GNN 的表示。
这里本质上：先针对一种关系 r 来学习节点表示，然后再对多个关系下的表示进行融合。
Geom-GCN: An implementation of the scheme
这里将上一节中很抽象的 Low-level aggregation p 和 High-level aggregation q 以及关系映射函数 τ。给出了具体的形式：
关系映射函数 τ 考虑了 4 种不同的位置关系。
Low-level aggregation p 其实就是 GCN 中的平均操作。
High-level aggregation q 本质就是拼接操作。
How to distinguish the non-isomorphic graphs once structural neighborhood
本文 argue 之前的工作没能较好的对结构信息进行描述，这里给了一个 case study 来说明 Geom-GCN 的优越性。
假设所有节点的特征都是 a。针对节点 来说，其邻居分别为
和
。假设采用 mean 或者 maximum 的 aggregator。
之前的映射函数 f：
则两种结构无法区分。
本文的映射函数 ：
可以区分。
更多关于 GNN 表示能力的论文参⻅：19 ICLR GIN How Powerful are Graph Neural Networks。
实验
本文主要对比了 GCN 和 GAT，数据集⻅下表：
不同数据集的 homophily 可以用下式衡量。
本文为 Geom-GCN 选取了 3 种 graph embedding 方法：
Isomap (Geom-GCN-I)
Poincare embedding (Geom-GCN-P)
struc2vec (GeomGCN-S)
实验结果⻅下表：
作者又进一步测试了两个变种：
只用原始图上邻居，加上后缀 -g。如 Geom-GCN-I-g；
只用隐空间邻居，加上后缀 -s。如 Geom-GCN-I-s。
结果⻅下图：
可以看出：隐空间邻居对 β 较小的图贡献更大。
然后，作者测试了不同 embedding 方法在选取邻居上对实验结果的影响。
可以看出：这里并没有一个通用的较好 embedding 方法。需要根据数据集来设置，如何自动的找到最合适的 embedding 方法是一个 feature work。
最后是时间复杂度分析。本文考虑了多种不同的关系，因此，Geom-GCN 的时间复杂度是 GCN 的 2|R| 倍。另外，和 GAT 的实际运行时间相差无几，因为 attention 的计算通常很耗时。
总结
本文针对 MPNNs 的两个基础性缺陷设计了Geom-GCN 来更好地捕获结构信息和⻓距离依赖。实验结果验证了 Geom-GCN 的有效性。但是本文并不是一个 end-to-end 的框架，有很多地方需要手动选择设计。
点击以下标题查看更多期内容：
#投 稿 通 道#
让你的论文被更多人看到
如何才能让更多的优质内容以更短路径到达读者群体，缩短读者寻找优质内容的成本呢？答案就是：你不认识的人。
总有一些你不认识的人，知道你想知道的东西。PaperWeekly 或许可以成为一座桥梁，促使不同背景、不同方向的学者和学术灵感相互碰撞，迸发出更多的可能性。
PaperWeekly 鼓励高校实验室或个人，在我们的平台上分享各类优质内容，可以是最新论文解读，也可以是学习心得或技术干货。我们的目的只有一个，让知识真正流动起来。
???? 来稿标准：
• 稿件确系个人原创作品，来稿需注明作者个人信息（姓名+学校/工作单位+学历/职位+研究方向）
• 如果文章并非首发，请在投稿时提醒并附上所有已发布链接
• PaperWeekly 默认每篇文章都是首发，均会添加“原创”标志
???? 投稿邮箱：
• 投稿邮箱：[email protected]
• 所有文章配图，请单独在附件中发送
• 请留下即时联系方式（微信或手机），以便我们在编辑发布时和作者沟通
????
现在，在「知乎」也能找到我们了
进入知乎首页搜索「PaperWeekly」
点击「关注」订阅我们的专栏吧
关于PaperWeekly
PaperWeekly 是一个推荐、解读、讨论、报道人工智能前沿论文成果的学术平台。如果你研究或从事 AI 领域，欢迎在公众号后台点击「交流群」，小助手将把你带入 PaperWeekly 的交流群里。
▽ 点击 | 阅读原文 | 下载论文 & 源码