作者丨纪厚业
学校丨北京邮电大学博士生
研究方向丨异质图神经网络及其应用
引言
图神经网络(Graph Neural Network)已经成为深度学习领域最热⻔的方向之一。作为经典的 Message-passing 模型,图神经网络通常包含两步:从邻居节点收集消息 message,然后利用神经网络来更新节点表示。但是 Message-passing 模型有两个基础性的问题:
1. 丢失了节点与其邻居间的结构信息:
2. 无法捕获节点之间的⻓距离依赖关系:
针对上述问题,本文提出了一种 geometric aggregation scheme,其核心思想是:将节点映射为连续空间的一个向量(graph embedding),在隐空间查找邻居并进行聚合。
本文的主要贡献:
模型
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 以及关系映射函数 τ。给出了具体的形式: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。本文的映射函数 :更多关于 GNN 表示能力的论文参⻅:19 ICLR GIN How Powerful are Graph Neural Networks。实验
本文主要对比了 GCN 和 GAT,数据集⻅下表:不同数据集的 homophily 可以用下式衡量。
本文为 Geom-GCN 选取了 3 种 graph embedding 方法:
实验结果⻅下表:
作者又进一步测试了两个变种:
结果⻅下图:
可以看出:隐空间邻居对 β 较小的图贡献更大。
然后,作者测试了不同 embedding 方法在选取邻居上对实验结果的影响。
可以看出:这里并没有一个通用的较好 embedding 方法。需要根据数据集来设置,如何自动的找到最合适的 embedding 方法是一个 feature work。最后是时间复杂度分析。本文考虑了多种不同的关系,因此,Geom-GCN 的时间复杂度是 GCN 的 2|R| 倍。另外,和 GAT 的实际运行时间相差无几,因为 attention 的计算通常很耗时。总结
本文针对 MPNNs 的两个基础性缺陷设计了Geom-GCN 来更好地捕获结构信息和⻓距离依赖。实验结果验证了 Geom-GCN 的有效性。但是本文并不是一个 end-to-end 的框架,有很多地方需要手动选择设计。