转载 纪厚业
目录
1.Introduction
2.Model
2.1Geometric aggregation scheme
2.2Geom-GCN: An implementation of the scheme
2.3How to distinguish the non-isomorphic graphs once structural neighborhood
3.Experiments
4. Conclusion
Geom-GCN: Geometric Graph Convolutional Networks
图神经网络（Graph Neural Network）已经成为深度学习领域最热门的方向之一。作为经典的Message-passing模型，图神经网络通常包含两步：从邻居节点收集消息message，然后利用神经网络来更新节点表示。但是Message-passing模型有两个基础性的问题：
- 丢失了节点与其邻居间的结构信息。
- 主要指拓扑模式相关的信息。
- GNN的结构捕获能力已经有了相关论文。下图来自19ICLR GIN How Powerful are Graph Neural Networks
- 无法捕获节点之间的长距离依赖关系。
- 大多数MPNNs仅仅聚合k跳内的节点邻居消息来更新节点表示。但是，图上两个节点可能具有相似的结构（社区中心、桥节点），即使他们的距离很远。
- 可能的解法是将现有的GNN堆叠多层，但是这可能带来过平滑问题。
针对上述问题，本文提出了一种geometric aggregation scheme，其核心思想是：将节点映射为连续空间的一个向量（graph embedding），在隐空间查找邻居并进行聚合。
本文的主要贡献：
- 提出了一种geometric aggregation scheme，其可以同时在真实图结构/隐空间来聚合信息来克服MPNNs两个基础性缺陷。
- 提出了一种基于geometric aggregation scheme的图神经网络Geom-GCN。
- 实验验证了模型的效果。
如下图所示，Geometric aggregation scheme主要包含3个部分：node embedding (panel A1-A3)，structural neighborhood (panel B) 和 bi-level aggregation (panel C)。
本文argue之前的工作没能较好的对结构信息进行描述.这里给了一个case study来说明Geom-GCN的优越性.
本文主要对比了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方法是一个future work.
最后是时间复杂度分析.本文考虑了多种不同的关系,因此,Geom-GCN的时间复杂度是GCN的 2|R|倍.另外,和GAT的实际运行时间相差无几,因为attention的计算通常很耗时.
本文针对MPNNs的两个基础性缺陷设计了Geom-GCN来更好的捕获结构信息和长距离依赖.实验结果验证了Geom-GCN的有效性.但是本文并不是一个end-to-end的框架.有很多地方需要手动选择设计.
