专栏首页图与推荐最强大的GNN出现了!

最强大的GNN出现了!

本文介绍斯坦福 Jure Leskovec 组近日发表在 arXiv 上的最新工作 ヽ(✿゚▽゚)ノ 距离编码-为结构表示学习设计更强大的GNN.

Distance Encoding – Design Provably More Powerful GNNs for Structural Representation Learning

论文:https://arxiv.org/pdf/2009.00142.pdf 代码:https://github.com/snap-stanford/distance-encoding

摘要

从图结构数据中学习节点集的结构表示对于从节点角色发现到链接预测和分子分类的各种应用至关重要。图神经网络(GNNs)在结构表示学习方面取得了巨大的成功。然而:

  1. 大多数 GNN 受到 1-Weisfeiler-Lehman(WL)test 的限制,因此有可能为实际上不同的结构和图形生成相同的表示
  2. 最近通过模仿高阶 WL tests 提出的更强大的 GNN 只关注全图表示,不能利用图结构的稀疏性来提高计算效率

这篇文章提出了一类与结构相关的特征,称为距离编码(Distance Encoding,DE),以帮助 GNN 以比 1-WL test 更严格的表达能力来表示任意大小的节点集。DE 本质上捕获了要学习表示的节点集与图中每个节点之间的距离,其中包括与图相关的重要度量,如最短路径距离和广义 PageRank 得分。

此外,此文还提出了两个通用的 GNNs 框架来使用 DEs

  • 作为额外的节点属性
  • 进一步作为 GNNs 中消息聚合的控制器

这两个框架仍然可以利用稀疏结构来保持处理大型图的可扩展性

理论上,作者证明了这两个框架可以区分传统 GNN 经常失效的几乎所有规则图中嵌入的节点集。还严格分析了它们的局限性。 实验上,作者在6个真实网络上分别从节点结构角色预测、链路预测和三角形预测三个方面对这两个框架进行了实证评估。 结果表明,DE-assisted GNNs 的平均准确率比没有 DEs 的 GNNs 提高了15%,DE-assisted GNNs 的性能也明显优于专门为这些相应任务设计的其他最先进的基线。

介绍

图1:(a)该图是具有8个节点的3正则图,并且所有节点属性都是相同的(不具有歧视性)。WLGNN 将为所有节点分配相同的表示形式,因此无法区分它们。但是,具有不同颜色的节点应该有不同的表示,因为它们在结构上不是等价的(或者说是“同构”)。此外,WLGNN 不能区分虚圆突出显示的所有节点对,无论这些节点对是否有连边。但是,我们可以使用节点之间的最短路径距离(SPD)作为特征来区分蓝色节点和绿色或红色节点,因为对于感兴趣的蓝色节点(例如,红框突出显示的那对蓝色节点)存在另一个SPD=3的蓝色节点,而其他节点到红色/绿色节点之间的所有SPD都小于3。要区分红色节点和绿色节点,需要深入分析 GNN 的计算图(树)(见附录C中的图3)。请注意,任何两个水平排列的节点之间的结构等价性可以从图的垂直自反性中获得,而两个垂直排列的蓝色节点之间的结构等价性可以进一步从右边所示的节点排列中获得。(b)WLGNN 表示大小为

p

的节点集——fi(·)是任意神经网络;AGG(·)是集合聚合;L是层数。

这项工作解决了 WLGNNs 的局限性,并提出了一类结构特征,称为距离编码(DE)。DE 既有理论保障,又有实证效率。 给定要学习其结构表示的节点集,图上节点的 DE 被定义为从感兴趣的节点集中的每个节点到该节点的随机游走的一组落地概率的映射。 DE 通常包括诸如最短路径距离(SPD)和广义 PageRank 分数之类的度量,其实质上捕获了图的结构信息。DE 可以通过简单而有效的方式融入到 GNN 的设计中:

  • 首先,此文提出了 DEGNN,它利用 DE 作为额外的节点特征。
  • 此外,通过允许 DE 控制 WLGNN 的聚合过程来进一步增强 DEGNN,这产生了另一个模型 DEAGNN

由于 DE 完全依赖于图的结构,独立于节点标识符,因此具有归纳和泛化能力。此文的贡献如下:

  1. 从理论上分析了 DEGNN 和 DEAGNN 相对于 WLGNN 在结构表征学习中的附加表达能力。在表达能力方面,这两个模型能够区分嵌入在几乎所有稀疏规则图中的两个非同构的大小相等的节点集(包括节点、节点对、…、整体图),其中如果没有可用的区分节点/边属性,则 WLGNN 总是失效。
  2. 此文还证明了这两个模型在学习距离正则图上节点的结构表示时并不比没有节点/边判别属性的 WLGNN 强,这意味着 DEs 的局限性。然而,作者还证明了它们在学习距离正则图上的节点对的结构表示方面具有额外的能力。
  3. 实证评估了这两个模型在节点角色分类(节点级)、链接预测(节点对级)、三角形预测(节点三联体级)三个任务层次上的性能。提出的方法在所有三个任务上的预测平均准确率都比WLGNN显著提高了15%,也优于其他专门为这些任务设计的基线

实验结果

表1:平均准确度和ROC曲线下面积(AUC)表现(以百分比±95%置信水平表示)。†强调了最佳基线。∗、粗体、粗体∗ 分别强调了提出的模型的性能以平均、超过70%的置信度和95%的置信度超过最佳基线的情况。

本文分享自微信公众号 - 图与推荐(GraphRec),作者:庄可乐ovO

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-09-02

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 图池化经典之作: 18NIPS DiffPool

    原文链接: https://zhuanlan.zhihu.com/p/106214278

    Houye
  • KDD20 | AM-GCN:自适应多通道图卷积网络

    题目:AM-GCN: Adaptive Multi-channel Graph Convolutional Networks

    Houye
  • KDD19开源论文 Heterogeneous Graph Neural Network

    文章针对异构图网络进行建模,得到每个节点的向量表示。首先,利用基于重启的随机游走策略为每个节点根据节点类型选择邻居,然后利用两个模块聚合邻居节点特征:一方面,对...

    Houye
  • 【从二叉树到红黑树】清晰理解红黑树的演变---红黑的含义

    网上关于红黑树的博文很多,但是多是上来即讲定义,未说其所以然,难以理解且无所营养,甚者示例图有误且概念模糊的比比即是;

    云服务器最新
  • Newick: tree文件格式简介

    Newick 是最常见的进化树文件格式,了解这种格式之前,有必要先掌握树状结构的构成。首先来看一个tree的示例

    生信修炼手册
  • 动画 | 什么是2-3树?(修改删除操作方式)

    我们回忆一下AVL树,它在插入和删除节点时,总要保证任意节点左右子树的高度差不超过1。正是因为有这样的限制,插入一个节点和删除一个节点都有可能调整多个节点的不平...

    我脱下短袖
  • 动画 | 什么是红黑树?(基于2-3树)

    学习过2-3树之后就知道应怎样去理解红黑树了,如果直接看「算法导论」里的红黑树的性质,是看不出所以然。我们也看看一颗二分搜索树满足红黑的性质:

    我脱下短袖
  • 我画了 20 张图,给女朋友讲清楚红黑树

    红黑树是一种常见的自平衡二叉查找树,常用于关联数组、字典,在各种语言的底层实现中被广泛应用,Java的TreeMap和TreeSet就是基于红黑树实现的。本篇分...

    范蠡
  • Redis主从复制

    爱撒谎的男孩
  • Gephi实战,从零开始

    Gephi 是一款网络分析领域的数据可视化处理软件,开发者对它寄予的希望是:成为 “数据可视化领域的Photoshop” ,可运行在Windows,Linux及...

    咻咻ing

扫码关注云+社区

领取腾讯云代金券