Higher-order Graph Neural Networks

栏目: 数据库 · 发布时间: 5年前

内容简介:本文探讨了图神经网络GNN 与 Weisfeiler-Leman 算法的联系,指出 GNN 在图同构 graph isomorphism 任务上和 Weisfeiler-Leman 算法具有同样的能力,同时二者也存在着同样的缺陷,基于此,本文提出了一种新的GNN变体:Weisfeiler-Leman Algorithm and Graph Neural NetworksWeisfeiler-Leman Algorithm 是用来确定两个图是否是同构的,其基本思路是通过迭代式地聚合邻居节点的信息来判断当前中心

本文探讨了图神经网络GNN 与 Weisfeiler-Leman 算法的联系,指出 GNN 在图同构 graph isomorphism 任务上和 Weisfeiler-Leman 算法具有同样的能力,同时二者也存在着同样的缺陷,基于此,本文提出了一种新的GNN变体:  higher-order GNN ,并在相关任务上验证了该方法的优越性。

Weisfeiler-Leman Algorithm and Graph Neural Networks

Weisfeiler-Leman Algorithm 是用来确定两个图是否是同构的,其基本思路是通过迭代式地聚合邻居节点的信息来判断当前中心节点的独立性Identity,从而更新整张图的编码表达 code reprsentation。有一个式子来表示更新公式:

Higher-order Graph Neural Networks 把(1)去掉具体的例子可以参考我们之前讲的 《Graph learning》| 图传播算法(下) ,这里由于每轮迭代都是聚合一阶邻居节点,所以作者特称这个算法为 1-WL。

我们再来看一看 GCN 的核心更新公式:

Higher-order Graph Neural Networks

相信对于这个式子很熟悉,我们就不做变量说明了。在GraphSage算法中,上式被抽象成:

Higher-order Graph Neural Networks

比较上式和1-WL,我们可以发现如下几点:

1、两个方法都是在聚合邻居节点;

2、存在一套特定的GNN模型,其效果完全等价于1-WL;

3、在图的同构问题上,GNN和1-WL的能力是一样的,谁也超不过谁;

4、1-WL算法的局限性被研究的很清晰,因此在GNN有着同样的问题。

在 On the power of color refinement 一文的研究中指出 1-WL算法对图的一些基本性质难以分辨,如循环图、三角计数等,特别是三角计数问题是研究社交网络的一个关键因素。

k-dimensional Graph Neural Networks

为了解决上述问题,作者借鉴1-WL到k-WL的拓展,将GNN拓展到k-GNN,称之为 higher-order GNN。具体地:

Higher-order Graph Neural Networks

其中s 表示由k个节点组成的subgraph,u 是这个这个子图s的邻居子图,其中邻居子图的定义如下:

Higher-order Graph Neural Networks

也就是一个k个节点组成的subgraph,其邻居子图必须和其有且仅有 k-1个公共节点。有了这样的思路之后,我们在建模一些 graph level 的任务时,就可以考虑更多的 high order 信息聚合,如下图所示:

Higher-order Graph Neural Networks 实验

本文的改进主要是针对GNN在 graph level上的任务,因此我们就来看看这方面的效果吧。这里,作者使用了QM9数据集,这是一个分子结构数据集,任务是通过分子的结构来确定其12项物理化学指标。实验效果如下:

Higher-order Graph Neural Networks

可以看到本文的方法在每一项指标的预测上均有效果提升。

参考链接

项目链接:

https://github.com/chrsmrrs/k-gnn

论文链接:

https://arxiv.org/abs/1810.02244


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

引爆点

引爆点

【加】马尔科姆•格拉德威尔(Malcolm Gladwell) / 钱清、覃爱冬 / 中信出版社 / 2014-4 / 36.00元

《引爆点》是《纽约客》怪才格拉德威尔的一部才华横溢之作。他以社会上突如其来的流行潮为切入点,从全新角度探索了控制科学和营销模式。他认为,思想、行为、信息及产品常会像传染病暴发一样迅速传播。正如一个病人就能引起全城流感;几位涂鸦爱好者能在地铁掀起犯罪浪潮;一位满意而归的顾客还能让新开张的餐馆座无虚席;发起小规模流行的团队能引发大规模流行风暴。这些现象均属“社会流行潮”,它达到临界水平并爆发的那一刻,......一起来看看 《引爆点》 这本书的介绍吧!

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

随机密码生成器
随机密码生成器

多种字符组合密码

URL 编码/解码
URL 编码/解码

URL 编码/解码