ICLR 2020 开源论文 | 隐空间的图神经网络：Geom-GCN

2010 年 6 月 2 日

作者丨纪厚业

学校丨北京邮电大学博士生

研究方向丨异质图神经网络及其应用

引言

图神经网络（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 的 3x 3 网格内，不同节点相对于红色节点有 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 的框架，有很多地方需要手动选择设计。

About The Author

stack