写点什么

图神经网络表达能力不足时,我们能做什么?

2020 年 7 月 22 日

图神经网络表达能力不足时,我们能做什么?

在本文中,作者认为图同构设置对于分析图神经网络的表达能力来说太过有限,并建议基于度量嵌入进行更广泛的设置。


前文回顾


《图深度学习:成果、挑战与未来》


《图神经网络的表达能力与 Weisfeiler-Lehman 测试》


《如何设计局部的、计算效率高的、可证明的图神经网络?》


本文最初发表在 TowardsDataScience 博客,经原作者 Michael Bronstein 授权,InfoQ 中文站翻译并分享。



Weisfeiler-Lehman(WL)测试【1】是图论多项式时间迭代算法层次结构的总称,为图同构提供了必要但不充分的条件。在图深度学习的背景下,消息传递神经网络被证明与 1-WL 测试一样强大【2】。进行更高阶、更强大的 k-WL 测试会导致图神经网络复杂度和非局部运算【3】,这在实际应用中是不切实际的。


我们在最近的一篇论文【4】中介绍了一种不同的方法,即打破 Weisfeiler-Lehman 层次结构,并采用一种能够感知局部图结构(如环、团和道路)的消息传递机制。这使得图神经网络具有标准消息传递架构的诱人的局部性和低复杂度,同时被证明比 2-WL 更强大,至少不低于 3-WL。这样的观点为图论中的开放性问题打开了深层次的联系,而这些问题是以前在图神经网络表达力方面从未探索过的。


故事到此结束了吗?我相信,我们可以通过改变对这一问题的看法,我们还可以做得更好,我将在本文中讨论几个方向。


近似同构。虽然从与图同构问题的联系中,人们对图神经网络的表达能力有了重要的认识,但这种设置本身是相当有限的。图神经网络可以看做是试图找到一个嵌入 f(G) 的图,具有期望性质 f(G)=f(G’) 当且仅当 G~G’。不幸的是,由于 Weisfeiler-Lehman 测试是图同构的必要条件,但不是充分条件,因此只有一种方法可行:如果 G~G’,则 f(G)=f(G’),但反过来并不一定成立:两个非同构图可以导致相等的嵌入。


在实际应用中,我们很少处理完全同构的图,而是处理近似同构的图,如下图所示:



近似同构图的示例:图中两对 G、G’ 和 G、G" 是非同构的。但是,G 和 G’ 只有一条边不同,因此比 G 和 G"“更同构”,而 G 和 G" 有五条边不同。


量化“近似同构”概念的是当方式是度量 d 的形式,如果两个图相似,则度量 d 就大,否则,度量 d 就小。图编辑距离【5】或 Gromov-Hausdorff 距离【6】是两个可能的例子。重要的是,将度量定义为 d(G,G’)=0,当且仅当 G~G’,这意味着两个同构图是不可区分的【7】。关于等距嵌入问题:


对于所有 G、G’, (♠)


尝试用用欧几里得距离 |.| 代替图的距离,以使两个距离相等(在这种情况下,嵌入 f 被称为“等距”或“保持距离”)。对图神经网络表达能力的研究表明,在 Weisfeiler-Lehman 测试成功的图族上,可以用多项式时间构造满足 (♠) 的图嵌入。这个设置似乎限制太多了。首先,很有可能不可能设计出一个局部的、有效的算法来保证所有图的 (♠)【8】。其次,图同构问题对近似同构图不提供任何保证,在这种情况下, d(G,G’)>0。原则上是可能的,例如,更多相似的图在嵌入空间中相似度较低,即 ,但


另一方面,度量公式提供了更多的灵活性。不要求 (♠) 完全成立,而是可以通过约束度量扩张来放松它。


可以通过限制度量扩张来放松它,而不是要求 (♠) 完全成立。


对于 ,则 (♣)


这可以表示为嵌入 f 的双李普希茨 (bi-Lipschitz)常数 c。这意味着嵌入不会“拉伸”或“收缩”距离 d 的 Ground Truth 图超过因子 c,理想情况下,因子 c 应尽可能接近于 1。


注意,图同构是 (♣) 的特例,因为对于同构图 G~G’,有 d(G,G’),从而 f(G)=f(G’)。如上所述,这不可能对所有图都能实现。相反,模型 (♣) 可以进一步放宽,允许附加度量失真 ε。


对于 ,则 (♦)


它设置了同构图之间的可以相距多远的公差。在许多应用程序中,这是一个很小的代价,如果一个应用程序能够满足 (♦) 比 (♠) 大得多的图族。



近似等距嵌入问题。


可能近似等距。近似同构问题可以改写为“可能近似正确”(probably approximately correct,PAC)形式的概率陈述:


其中,“近似”是在度量扩张 c 的意义上理解的,而“可能”是对于图的某些分布来说,边界(♦)具有很高的概率 1−δ【9】。这种设置可能比确定性近似等距嵌入问题更容易分析。


桥接连续和离散结构。最后但并非不重要的是,图神经网络表达力问题主要集中在图的拓扑结构上。然而,在大多数实际应用中,图还具有节点或边的特征或属性,通常表示为向量【10】。度量框架通过定义属性图之间的适当距离自然地处理这两种结构。


作为最后的意见,我要提醒大家也应该记住,大多数关于图神经网络表达能力的研究著作都是建立在图论经典成果基础上的最近进展。扩展到其他数学领域,例如度量几何学,似乎是一条很有前途的途径,有望在不久的将来结出硕果。


参考文献


【1】 《图的标准型化简及其代数》(The reduction of a graph to canonical form and the algebra which appears therein),B. Weisfeiler、A. Lehman,1968 年,英译本。


【2】 《图神经网络有多强大?》(How powerful are graph neural networks?),K. Xu 等人,2019 年,Proc.ICLR。


【3】 《可证明的强大图神经网络》( Provably powerful graph neural networks),K. Xu 等人,2019 年,Proc.ICLR。


【4】 《利用子图同构计数提高图神经网络的表达能力》(Improving graph neural network expressivity via subgraph isomorphism counting),G. Bouritsas 等人,2020 年,arXiv:2006.09252。


【5】 《用于模式识别的属性关系图间的距离度量》(A distance measure between attributed relational graphs for pattern recognition),A. Sanfeliu、K.-S. Fu,1983 年,IEEE Trans. Systems, Man, and Cybernetics (3):353–362。


【6】 《黎曼变量的结构度量)(Structures métriques pour les variétés riemanniennes),M.Gromov,1981 年。


【7】 从技术上讲,d 是一个伪度量,可以视为模同构关系图的商集 𝒢⧵~ 上的度量。


【8】 我之所以说“可能”,是因为图同构问题是否存在多项式时间解尚未可知。这种假设算法似乎不太可能具有实际的时间和空间复杂性。


【9】 在 N. M. Kriege 等人之前,有人曾使用概率度量设置来分析图核。《图核理论表达性的性质测试框架》(A property testing framework for the theoretical expressivity of graph kernels),2018 年,Proc. IJCAI。


【10】 虽然 Weisfeiler-Lehman 框架在技术上适用于彩色图,但它仅限于具有离散特征集的节点。


作者介绍:


Michael Bronstein,伦敦帝国理工学院教授,Twitter 图机器学习研究负责人,CETI 项目机器学习领导、Twitter 图机器学习负责人、研究员、教师、企业家和投资者。


原文链接:


https://towardsdatascience.com/beyond-weisfeiler-lehman-approximate-isomorphisms-and-metric-embeddings-f7b816b75751


2020 年 7 月 22 日 11:28968
用户头像
陈思 InfoQ编辑

发布了 575 篇内容, 共 202.3 次阅读, 收获喜欢 1178 次。

关注

评论

发布
暂无评论
发现更多内容

政策加持迎来区块链技术应用“红利期”

CECBC区块链专委会

500行代码写一个俄罗斯方块游戏

程序员生活志

话题讨论 | 特朗普正式封禁微信,iPhone 和微信二选一?

InfoQ写作平台官方

写作平台 话题讨论

我是如何参与硅谷顶级开源项目并赚得2500美金

阿水

硅谷 Minio

人生修炼秘籍

xiaoboey

时间管理 人生修炼 知行合一 熵增 时间复利

learn go with tests 学习笔记(三) 指针和错误

半亩房顶

golang golang新手

learn go with tests 学习笔记(五)并发

半亩房顶

golang golang新手

用户体验(UX)设计≠用户界面(UI)设计

刘华Kenneth

敏捷 设计 UX 用户体验

疫情之年 下半年区块链应用落地会加速么?

CECBC区块链专委会

区块链 场景应用落地

菊长说丨一文读懂MySQL4种事务隔离级别

华为云开发者社区

MySQL 数据库 事务隔离级别 事务 华为云

learn go with tests 学习笔记(一) hello world

半亩房顶

golang golang新手

learn go with tests 学习笔记(四)依赖注入

半亩房顶

golang golang新手

Netty之旅:你想要的NIO知识点,这里都有!

一枝花算不算浪漫

Netty nio

Python爬取微信公众号文章保存到数据库

wjchenge

“啰嗦”是成事唯一正确的方法

泰稳@极客邦科技

团队管理 个人成长 团队协作 沟通

零代码/无代码 vs 低代码 如何分类?如何区别?到底有什么不同?分析超过20款零代码低代码产品

代码制造者

编程 低代码 行业资讯 零代码

Executor看不懂?教你如何盘它

Edison

线程池 后端开发

关于微服务架构思考

Arthur

消息疯狂堆积!RocketMQ出Bug了?

Edison

RocketMQ 中间件

MySQL事物-学习笔记

Edison

MySQL 数据库 数据库事务

nested exception is java.lang.IllegalStateException: refreshAfterWrite requires a LoadingCache异常解决

谙忆

Web 开发必须掌握的三个技术:Token、Cookie、Session

华为云开发者社区

HTTP Token web开发 session Cookie

字符串匹配 - Sunday算法

半亩房顶

数据结构与算法 字符串匹配算法

learn go with tests 学习笔记(二) 数组与切片

半亩房顶

golang golang新手

learn go with tests 学习笔记(六)进程同步

半亩房顶

golang golang新手

learn go with tests 学习笔记(七)反射

半亩房顶

golang 反射 golang新手

《effective-go》 学习笔记

半亩房顶

golang

RocketMQ源码解析-开篇

Edison

RocketMQ 中间件

秒懂云通信:如何使用阿里云号码认证服务(小白指南)

阿里云Edge Plus

云通信 通信云 号码认证

Java项目如何分层

老胡爱分享

分层架构 项目

企业网站搭建避坑指南

姜奋斗

网站 新手指南 企业 网站搭建 避坑

演讲经验交流会|ArchSummit 上海站

演讲经验交流会|ArchSummit 上海站

图神经网络表达能力不足时,我们能做什么?-InfoQ