图神经网络的困境,用微分多少和代数拓扑解决

微分多少和代数拓扑在主流机器进修中并不常见。在本系列文章中,作者展示了如何使用这些规模的工具从头解释图神经网络并解决一些常见困境。

图片

本文的作者是 Twitter 首席科学家、DeepMind 人工智能教授 Michael Bronstein。以下是博客原文。

对称,无论从广义还是狭义的角度讲,都是人类一直以来试图理解和创造秩序与美的一种观念。

——Hermann WeylHermann Weyl 这类诗意的描述强调了对称性在科学中的基石作用。Felix Klein 在 1872 年的「Erlangen Programme」中用对称群表征多少。这不仅是数学上的一个突破,即统一了「多少大家庭」,还推进了现代物理理论的发展,这些理论可以完全从对称性的第一原理推导出来。多少深度进修规模也出现了类似的原则,通过群不变性和等变性能够推导出大多数流行神经网络架构的通用蓝图。

图片

图神经网络可以被认为是多少深度进修蓝图的一个特例,其构建模块是具有对称群的域(在这类情况下是具有置换群的图)、域上的信号(节点特点)和此类信号的群等变函数(消息传递)。多少深度进修蓝图可以应用于不同的规模,例如 grid、mesh 或图 (graph)。然而,前两者具有明确的连续方式的类比对象,grid 可以被认为是欧几里得空间或更一般的均匀空间(如球体)的失散化,mesh 则是二维流形的常见失散化),图却没有直接的连续方式的类比。这类不可类比有点令人不安,因此我们决定仔细研究用于图进修的连续模型。

图片

图神经网络聚集。图神经网络 (GNN) 通过在图上执行某种方式的消息传递来进修。其中,特点通过边从一个节点传递到另一个节点。这类机制与图上的聚集过程有关,可以用称为「聚集方程」的偏微分方程 (PDE) 方式表示。我们最近在一篇论文中展示了这类具有非线性可进修聚集函数的 PDE 的失散化(称为 GRAND),泛化了一大类 GNN 架构,例如图注意力网络(GAT。PDE 的思维方式提供了多种优势,例如可以利用兼具稳定性和收敛性的高效数值求解器(例如隐式、多步、自适应和 multigrid 方案)。其中一些求解器在流行的 GNN 架构中没有直接的类比,可能会促成一些新型图神经网络设计。由于我们考虑的聚集 PDE 可以看作是一些相关能量的梯度流 ,因此这类架构可能比典型架构更易于解释。同时,虽然 GRAND 模型提供连续时间来代替传统 GNN 中的层,但方程的空间部分仍然是失散的,并且依赖于输出图。重要的是,在这个聚集模型中,域(图)是固定的,其上定义的某些属性会蜕变。微分多少中常用的一个不同概念是多少流(geometric flow),域本身的属性不断蜕变。我的博士生导师 Ron Kimmel 等研究者 20 世纪 90 年代在图像处理规模就采用了这个想法。他们将图像建模为嵌入在联合位子和颜色空间中的流形,并通过 PDE 对它们进行推导蜕变,以最小化嵌入的谐波能量。这样的偏微分方程称为贝尔特拉米流(Beltrami flow),具有各向同性非欧几里得聚集的方式,并产生保边图像去噪。我们将这类范式应用于「Beltrami 神经聚集(BLEND)」框架中的图。图的节点现在由位子坐标和特点坐标来表征,这两个坐标都是经过蜕变的,并且都决定了聚集性。在这类思维模式下,图本身就变成了一个辅助角色:它可以从位子坐标生成(例如作为 k – 最近邻图)并在整个蜕变过程中从头连接。下图说明了这类同时蜕变的过程。

图片

图的表达能力在最近的工作中,人们对图神经网络(GNN)的表达能力给予了极大的关注。消息传递的 GNN 等价于 Weisfeiler-Lehman 图同构尝试(一种通过迭代颜色细化来确定两个图是否在结构上等价 (同构) 的经典格式)。这个检验是一个必要但不充分条件:事实上,一些非同构图可能会通过 Weisfeler-Lehman 尝试。下图说明了 GNN 传递消息过程中该尝试「看到」了什么:两个高亮显示的节点看起来没有什么区别,然而这两个图显然具有不同的结构:

图片

位子编码。解决这个成绩的一个常见格式是通过为节点分配一些额外的特点来给节点「着色」,这些特点保证了图中节点的角色或「位子」。由于位子编码在 Transformer 中已得到普及,因此位子编码成为增加图神经网络表达能力的常用格式。 

图片

位子编码为图的节点分配了额外的特点,允许消息传递获得比 Weisfeiler-Lehman 尝试更高的表达能力。然而,对于位子编码,并没有一个「规范」的选择。 也许最直接的格式是赋予每个节点一个随机特点;然而,这类格式虽然可以更具表达性,但泛化能力较差(因为不可能在两个图中重现随机特点)。图拉普拉斯算子的特点向量提供了图的规模保持嵌入,并已成功用作位子编码。最后,我们(与 Giorgos Bouritsas 和 Fabrizio Frasca 合著)在一篇论文中表明,图的子结构计数可以用作位子或「结构」编码的一种方式,这说明它比基本的 Weisfeiler-Lehman 尝试更强大。 然而,位子编码有多种选择,如何选择以及哪种格式在哪种情况下效果更好,都没有明确的答案。我相信像 BLEND 这样的多少流可以根据这个成绩来解释:通过非欧几里得聚集来蜕变图的位子坐标,位子编码可以适用于下游任务。因此,答案是「视情况而定」:最佳位子编码是手头数据和任务的函数。高阶消息传递。表达性的另一种选择是放弃根据节点和边来考虑图,而是把图看作单位复合体(cell complex)对象的示例,单位复合体是代数拓扑规模的主要研究对象之一。在这类格式中,节点是 0-cell,边是 1-cell。不必止步于此:我们可以构造如下图所示的 2-cells(面),这使得上述示例中的两个图可以完美区分:

图片

在我最近与 Cristian Bodnar 和 Fabrizio Frasca 合作的两篇论文中,我们表明可以构建一个「提升变换」,用高阶单位来增强图,从而在这些单位上可以执行更复杂的分层消息传递方式。该方案可被证明比 Weisfeiler-Lehman 尝试的表达能力更强,并且在计算化学规模给出了有望的结果:比建模为图,建模为单位复合体表现更好。「over-squashing」现象GNN 的另一个常见成绩是「over-squashing」现象,或者由于输出图的某些结构特点,消息传递无法有效地传播信息。oversquashing 通常发生在体积呈指数增长的图中,例如小世界网络以及依赖于远程信息的成绩。换句话说,GNN 作用的输出图并不总是对消息传递友好。 

图片

「小世界」图中快速增长的邻居数量通常是 GNN 中观察到的过度挤压现象的根源。 从实验可以观察到,将输出图与计算图解耦并允许在不同的图上传递消息有助于缓解这一成绩。这类技术通常被称为「图从头布线(graph rewiring)」。事实上,许多流行的 GNN 架构都实现了某种方式的图重构,可以采用邻域采样(最初在 GraphSAGE 中提出以应对可扩展性)或多跳滤波器的方式。上面讨论的拓扑消息传递也可以看作是从头布线的一种方式,远距离节点之间的信息流可以认为是通过高阶单位的「捷径」。Alon 和 Yahav [23] 表明,即使像使用全连接图这样简单的格式也可能有助于改善图 ML 成绩中的 over-squashing。Klicpera 等研究者宣称「聚集改进了图进修」,提出了一个通用的 GNN 预处理步骤(DIGL),包括通过聚集过程来去噪图的连通性。总体而言,尽管进行了重要的实验研究,但 over-squashing 现象一直令人难以捉摸。我们最近在一篇论文中表明:导致 over-squashing 的瓶颈可归因于图的局部多少特性。具体来说,通过定义 Ricci 曲率的图类比,我们可以证明罪魁祸首是 negatively-curved 边。因此出现了一种类似于「反向 Ricci 流」的图从头布线过程,该过程去除有成绩的边并生成一个更易于消息传递的图,同时在结构上与输出图相似。

图片

使用基于聚集的格式(DIGL,中)和基于曲率的格式(Ricci,右)从头连接康奈尔图(左)的示例。基于曲率的格式显著减少了瓶颈,同时更接近于原始图结构。总结这些例子表明,微分多少和代数拓扑为图机器进修中重要且具有挑战性的成绩带来了新的视角。在本系列的后续文章中,我将更详细地展示如何使用这些规模的工具来解决上述图神经网络成绩。第二部分将讨论代数拓扑如何提高 GNN 的表达能力。第三部分将讲解多少聚集偏微分方程。第四部分将展示 over-squashing 现象与图曲率有何相关,并提供一种受 Ricci 流启发的图从头布线的新型多少格式。

原创文章,作者:机器之心,如若转载,请注明出处:https://www.iaiol.com/news/tu-shen-jing-wang-luo-de-kun-jing-yong-wei-fen-duo-shao-he/

(0)
上一篇 2022年 3月 27日 下午12:42
下一篇 2022年 3月 27日 下午12:59

相关推荐

  • 阿里数据中台底座的12年建造实践

    文/阿里云智能计较平台事业部研究员 关涛阿里巴巴数据平台发展的四大阶段建立数据中台,一个强大的数据平台作为底座必不可少。 阿里巴巴数据平台发展的四个阶段,一定程度上其实也是阿里巴巴数据中台发展的四个阶段。这四个阶段里,你可以看到阿里巴巴对自身数据的商业价值的萃取,对原有分而治之的数据系统的聚合,对计较数据财产化和数据高效应用的新思路以及对数据平台处置过程中面临的组织变革等。阶段一:交易百花齐放,发现数据价值2009年到2012年,阿里巴巴电商交易进入爆发期,涌现出非常多有名的交易团队,比如淘宝、

    2021年 9月 29日
  • 迈向模仿人脑的光电芯片:对一位热衷于改进 SNN 的 NIST 钻研人员的采访

    cIEEE Spectrum 近来与美国国家标准与技术钻研院(NIST)的物理学家 Jeffrey Shainline 从事了交谈,他的工作可能会对这个问题有所启发。Shainline 在钻研一种可以为高级形式的人工智能提供支持的计算方法——所谓的脉冲神经网络(spiking neural networks,SNN),与现在广泛部署的人工神经网络相比,它更接近地模仿大脑的工作方式。今天,主流的模式是运用在数字计算机上运行的软件来创建具有多层神经元的人工神经网络。这些「深度」人工神经网络已被

    2022年 4月 24日
  • 百分点数据科学实验室:产物生命周期料理创新应用落地实践

    编者按产物生命周期料理在数字经济发展过程中是必不可少的,在零售快消行业可用来指导产物的以销定采和精准投放,在IT行业可辅佐软件应用等产物的开发进程料理,同时还也会对环境料理产生影响,对建筑业在节能减排、减轻环境污染层面起到辅佐作用。因此,及时把控产物生命周期进程,用数据智能技术赋能料理至关重要。百分点数据科学实验室鉴于产物生命周期理论在多个行业的落地实践,总结了如何准确把握产物生命周期的四个阶段及辨别方法论。众所周知,一种产物在商场上的销售情况和获利能力并非是一成不变的,因此,任何一家企业的产物不可能永远畅销,但企

    2021年 3月 25日
  • 性能提升、成本降低,这是分布式强化进修算法最新研究进展

    深度强化进修(Deep Reinforcement Learning,DRL)是一种公认的解决连续决策问题的有效技术。为了应对 DRL 的数据低效(data inefficiency)问题,受到分布式机器进修技术的启发,分布式深度强化进修 (distributed deep reinforcement learning,DDRL) 已提出并成功应用于盘算机视觉和自然语言处理领域。有观点认为,分布式强化进修是深度强化进修走向大规模应用、解决复杂决策空间和长期规划问题的必经之路。分布式强化进修是一个综合的研究子领域,需

    2024年 2月 15日
  • 盘点如何用AI做动画,还有各种东西等你取用

    图象天生、视频天生、整合语音合成的人脸动画、天生三维的人物活动以及 LLM 驱动的东西…… 一切都在这篇文章中。天生式 AI 已经成为互联网的一个重要内容来源,现在你能看到 AI 天生的文本、代码、音频、图象以及视频和动画。今天我们要介绍的文章来自立陶宛博主和动画师 aulerius,其中按层级介绍和分类了动画领域应用的天生式 AI 手艺,包括简要介绍、示例、优缺点以及相关东西。他写道:「作为一位动画建造者,我希望一年前就有这样一份资源,那时候我只能在混乱的互联网上自行寻找可能性和不断出

    2024年 2月 19日
  • ICLR 2022 | 鉴于心智理论的多智能体通讯与分工

    本文是 ICLR 2022入选论文《ToM2C: Target-oriented Multi-agent Communication and Cooperation with Theory of Mind》的解读。该论文由北京大学王亦洲课题组完成。文章提出了一种鉴于心智理论的多智能体通讯与分工方法。每一个智能体鉴于对他人心理状态的推想独立地抉择通讯对象和个体行动,进而实现分布式的分工。试验表明该方法提高了多智能体分工的成功率,大幅降低了通讯价钱,并且具有良好的泛化性能。

    2022年 7月 18日
  • 做时光序列展望有必要用深度进修吗?事实证明,梯度提升返回树媲美甚至超越多个DNN模型

    在深度进修要领应用广泛的今天,所有范畴是不是非它不可呢?其实未必,在时光序列展望任务上,简略的呆板进修要领能够媲美甚至超越很多 DNN 模型。

    2022年 3月 6日
  • 李沐「下手学深度进修」第二全体CNN本周开课,也邀你挑战他10行代码的比赛问题

    本周六,课程将进入第二全体:卷积神经网络,接待对这全体有疑问的同砚上车进修。

    2021年 4月 23日
  • 1600米深海沉船如何索求?斯坦福人形机器人实现远程人机交互下潜

    深海里面藏着许多秘密,沉船,坠机,数不尽的金银珠宝和历史记忆都埋藏在深海中。从前索求这些遗址的方法多为整体打捞,许多证据难以保存。近日,斯坦福大学的机器人团队研发出名为 OceanOneK 的水下人机交互机器人,通过远程操控,让人形机器人以最接近真人潜水的方式在水下 1600 米实现索求,最大程度地实现了人机交互,也最大程度地保护了遗址的完整性。

    2022年 7月 29日

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注