查看原文
其他

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

纪厚业 PaperWeekly 2022-03-17


作者丨纪厚业

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

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




引言


图神经网络(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 或许可以成为一座桥梁,促使不同背景、不同方向的学者和学术灵感相互碰撞,迸发出更多的可能性。 


PaperWeekly 鼓励高校实验室或个人,在我们的平台上分享各类优质内容,可以是最新论文解读,也可以是学习心得技术干货。我们的目的只有一个,让知识真正流动起来。


📝 来稿标准:

• 稿件确系个人原创作品,来稿需注明作者个人信息(姓名+学校/工作单位+学历/职位+研究方向) 

• 如果文章并非首发,请在投稿时提醒并附上所有已发布链接 

• PaperWeekly 默认每篇文章都是首发,均会添加“原创”标志


📬 投稿邮箱:

• 投稿邮箱:hr@paperweekly.site 

• 所有文章配图,请单独在附件中发送 

• 请留下即时联系方式(微信或手机),以便我们在编辑发布时和作者沟通




🔍


现在,在「知乎」也能找到我们了

进入知乎首页搜索「PaperWeekly」

点击「关注」订阅我们的专栏吧



关于PaperWeekly


PaperWeekly 是一个推荐、解读、讨论、报道人工智能前沿论文成果的学术平台。如果你研究或从事 AI 领域,欢迎在公众号后台点击「交流群」,小助手将把你带入 PaperWeekly 的交流群里。


▽ 点击 | 阅读原文 | 下载论文 & 源码

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存