原标题：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 默许每篇文章都是首发，均会增加“原创”标志
责任编辑：
