刘忠雨作者萝卜兔编辑整理

Higher-order Graph Neural Networks

本文探讨了图神经网络 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。有一个式子来表示更新公式:

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

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

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

比较上式和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。具体地:
其中s 表示由k个节点组成的subgraph,u 是这个这个子图s的邻居子图,其中邻居子图的定义如下:
也就是一个k个节点组成的subgraph,其邻居子图必须和其有且仅有 k-1个公共节点。有了这样的思路之后,我们在建模一些 graph level 的任务时,就可以考虑更多的 high order 信息聚合,如下图所示:

实验

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

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

参考链接

项目链接:

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

论文链接:

https://arxiv.org/abs/1810.02244


极验
极验

极验是全球顶尖的交互安全技术服务商,于2012年在武汉成立。全球首创 “行为式验证技术” ,利用生物特征与人工智能技术解决交互安全问题,为企业抵御恶意攻击防止资产损失提供一站式解决方案。

理论层次分类进化算法GNN
1
相关数据
图神经网络技术

图网络即可以在社交网络或其它基于图形数据上运行的一般深度学习架构,它是一种基于图结构的广义神经网络。图网络一般是将底层图形作为计算图,并通过在整张图上传递、转换和聚合节点特征信息,从而学习神经网络基元以生成单节点嵌入向量。生成的节点嵌入向量可作为任何可微预测层的输入,并用于节点分类或预测节点之间的连接,完整的模型可以通过端到端的方式训练。

推荐文章
暂无评论
暂无评论~