Press "Enter" to skip to content

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 的图神经网络

 

实验验证了模型的效果。

 

模型

 

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 的框架,有很多地方需要手动选择设计。

 

Be First to Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注