[论文翻译]关系归纳偏差、深度学习和图网络


原文地址:1806.01261


1介绍

人类智能的一个关键特征是能够“无限使用有限手段” (Humboldt,1836 年;Chomsky,1965 年),其中可以以无限的方式(如成新句子)。这反映了组合泛化的原则,即从已知的构建块构建新的推理、预测和行为。在这里,我们探索如何通过将学习偏向结构化表示和计算,尤其是在图形上运行的系统,来提高现代人工智能的组合泛化能力。

人类组合概括的能力在很大程度上取决于我们表示结构和推理关系的认知机制。我们将复杂系统表示为实体及其相互作用的组合22这是否需要“思想语言” (Fodor,1975)超出了这项工作的范围。 (纳冯,1977 ;麦克莱兰和鲁梅哈特,1981 ;普劳特等人,1996 ;马库斯,2001 ; Goodwin和约翰逊莱尔德,2005 ; Kemp和特南鲍姆,2008),如判断对象的偶然堆栈是否为稳定(Battaglia的等人,2013 年)。我们使用层次结构从细粒度的差异中抽象出来,并捕获表示和行为之间更普遍的共性(Botvinick,2008 年;Tenenbaum 等人,2011 年),例如对象的一部分、场景中的对象、城镇中的社区和国家/地区的城镇。我们通过编写熟悉的技能和例程来解决新问题(Anderson,1982),例如通过编写熟悉的程序和目标(例如“乘飞机旅行”、“到圣地亚哥”、“吃饭”和“一家印度餐厅”。我们通过对齐两个领域之间的关系结构并根据对另一个领域的相应知识进行推断来进行类比(Gentner 和 Markman,1997 年;Hummel 和 Holyoak,2003 年)。

Kenneth Craik 的“解释的本质”(1943 年)将世界的构成结构与我们内部心理模型的组织方式联系起来:

……[人类心智模型] 与它模仿的过程具有相似的关系结构。我所说的“关系结构”并不是指参与模型的一些晦涩的非物理实体,而是指它是一个工作物理模型,其工作方式与其平行的过程相同……物理现实显然是建立起来的,从一些基本类型的单元中,这些单元的属性决定了最复杂现象的许多属性,这似乎为这些组合之间机制之间的类比和关系结构的相似性的出现提供了充分的解释,而无需任何客观普遍性理论。 (克雷克,1943 年,第 51-55 页)

也就是说,世界是组合的,或者至少,我们用组合的术语来理解它。在学习时,我们要么将新知识融入我们现有的结构化表示中,要么调整结构本身以更好地适应(并利用)新知识和旧知识(Tenenbaum 等,2006;Griffiths 等,2010;Ullman 等)等,2017 年)。

如何构建具有组合泛化的人工系统的问题自诞生以来一直是人工智能的核心,也是许多结构化方法的核心,包括逻辑、语法、经典规划、图形模型、因果推理、贝叶斯非参数和概率编程(斯基,1957 ; Nilsson的和Fikes,1970 ;珍珠,19862009 ; Russell和诺维格,2009 ; Hjort等人,2010 ; Goodman等人,。2012 ; Ghahramani,2015)。整个子领域都专注于显式以实体和关系为中心的学习,例如关系强化学习(Džeroski 等人,2001 年)和统计关系学习(Getoor 和 Taskar,2007 年)。在以前的时代,结构化方法对机器学习如此重要的一个关键原因部分是因为数据和计算资源非常昂贵,而结构化方法强大的归纳偏差所提供的改进的样本复杂性非常有价值。

与过去的 AI 方法相比,现代深度学习方法(LeCun 等人,2015 年;Schmidhuber,2015 年;Goodfellow 等人,2016 年)通常遵循“端到端”设计理念,强调最小的先验表征和计算假设,并试图避免显式结构和“手工工程”。这种强调与当前大量廉价数据和廉价计算资源相吻合——或许也得到了证实,这使得折衷样本效率以获得更灵活的学习成为一种理性选择。从图像分类(Krizhevsky 等人,2012; Szegedy 等人,2017 年),到自然语言处理(Sutskever 等人,2014 年;Bahdanau 等人,2015 年),到游戏(Mnih 等人,2015 年;Silver 等人,2016 年;Moravčík 等人) , 2017 ),证明了这一极简主义原则。一个突出的例子来自语言翻译,其中序列到序列方法(Sutskever 等人,2014 年;Bahdanau 等人,2015 年)已被证明非常有效,而无需使用显式解析树或语言实体之间的复杂关系。

然而,尽管深度学习取得了成功,但仍有一些重要的批评 (Marcus,2001;Shalev-Shwartz 等,2017;Lake 等,2017;Lake 和 Baroni,2018;Marcus,2018ab;Pearl,2018;Yuille 和 Liu,2018 年) 强调了它在复杂语言和场景理解、结构化数据推理、超越训练条件的迁移学习以及从少量经验中学习方面面临的关键挑战。这些挑战需要组合概括,因此避开组合性和显式结构的方法难以满足这些挑战也就不足为奇了。

当深度学习的联结主义者(Rumelhart 等人,1987 年)面临来自结构化、象征性立场的类似批评(Fodor 和 Pylyshyn,1988 年;Pinker 和 Prince,1988 年)时,他们做出了建设性的努力(Bobrow 和 Hinton,1990 年;Marcus)。 , 2001 )直接而谨慎地应对挑战。在类比制作、语言分析、符号操作和其他形式的关系推理等领域,开发了各种用于表示和推理结构化对象的创新子符号方法(Smolensky,1990 年;Hinton,1990 年); 波拉克,1990 年;埃尔曼,1991 年;版,1995 年;Eliasmith,2013 年),以及关于大脑如何运作的更多综合理论(Marcus,2001 年)。这些工作还有助于培养最近的深度学习进展,这些进展使用分布式向量表示来捕获文本中丰富的语义内容(Mikolov 等人,2013 年;Pennington 等人,2014 年)、图(Narayanan 等人,2016 年2017 年) , 代数和逻辑表达式(Allamanis et al., 2017 ; Evans et al., 2018 )和程序(Devlin 等人,2017 年;Chen 等人,2018b)。

我们建议现代 AI 前进的关键路径是将组合泛化作为首要任务,我们提倡采用综合方法来实现这一目标。正如生物学不会在先天后天之间做出选择——它联合使用先天和后天来构建大于各部分总和的整体——我们也拒绝接受结构和灵活性在某种程度上不一致或不相容的观点,并且拥抱两者,以期获得互补的优势。本着最近许多基于结构的方法和深度学习的原则性混合示例的精神(例如,Reed 和 De Freitas,2016 年;Garnelo 等人,2016 年;Ritchie 等人,2016 年;Wu 等人,2017 年;Denil 等人,2017 年;Hudson 和 Manning,2018 年),我们看到了通过利用完整的 AI 工具包并将当今的最佳方法与数据和计算非常宝贵的时期必不可少的方法相结合来合成新技术的巨大希望。

最近,在深度学习和结构化方法的交叉点出现了一类模型,它侧重于对显式结构化数据进行推理的方法,特别是图(例如 Scarselli 等人,2009b;Bronstein 等人,2017 年;Gilmer 等人al., 2017 ; Wang et al., 2018c ; Li et al., 2018 ; Kipf et al., 2018 ; Gulcehre et al., 2018 ). 这些方法的共同点是能够对离散实体及其之间的关系进行计算。它们与经典方法的区别在于如何学习实体和关系的表示和结构以及相应的计算,从而减轻需要提前指定它们的负担。至关重要的是,这些方法以特定架构假设的形式带有强烈的关系归纳偏差,引导这些方法学习实体和关系(Mitchell,1980 年),我们加入了许多其他方法(Spelke 等人,1992 年;Spelke 和金茨勒,2007 年;马库斯,2001 年; 特南鲍姆等人,2011 年;莱克等人,2017 年;莱克和巴罗尼,2018 年;Marcus, 2018b ),建议是类人智能的重要组成部分。

在本文的其余部分,我们通过各种深度学习方法的关系归纳偏差来研究它们,表明现有方法通常带有并不总是明确或立即显而易见的关系假设。然后,我们提出了一个基于实体和关系的推理的通用框架——我们称之为图网络——用于统一和扩展现有的图操作方法,并描述使用图网络作为构建块构建强大架构的关键设计原则。

2关系归纳偏差

{mdframed}[frametitle=Box 1: Relational reasoning, backgroundcolor=black!6, nobreak=true, ] 我们将*结构*定义为组合一组已知构建块的产物。“结构化表示”捕获这种组合(即元素的排列),“结构化计算”对元素及其组合进行整体操作。然后,关系推理涉及操纵*实体*和*关系的*结构化表示,使用有关如何组合它们的*规则*。我们使用这些术语来捕捉来自认知科学、理论计算机科学和人工智能的概念,如下所示:

  • [注意事项]
  • 一个实体是与属性,例如一个尺寸和质量的物理对象的元素。
  • 一个关系是实体之间的财产。两个对象之间的关系可能包括与 相同、比 重和与 的距离。关系也可以具有属性。关系超过X比需要一个属性重的倍,X,其确定为关系的相对权重的阈值是真对假。关系也可能对全球背景很敏感。对于一块石头,一根羽毛,关系落在具有更大的加速比依赖于上下文是否是在空气中与在真空中。这里我们关注实体之间的成对关系。
  • 规则是映射实体和关系的其他实体和关系,如一个尺度比较的功能等(如非二进制逻辑谓词)是实体X大?并且是实体X比实体Y重?. 在这里,我们考虑采用一或两个参数(一元和二元)并返回一元属性值的规则。

作为机器学习中关系推理的一个说明性示例,图形模型(Pearl,1988 年;Koller 和 Friedman,2009 年)可以通过在随机变量之间进行显式随机条件独立来表示复杂的联合分布。此类模型非常成功,因为它们捕获了作为许多现实世界生成过程基础的稀疏结构,并且因为它们支持有效的学习和推理算法。例如,隐马尔可夫模型将潜在状态约束为条件独立于给定前一时间步的状态,而给定当前时间步的潜在状态的观察条件独立于许多现实世界的因果过程。显式表达变量之间的稀疏依赖关系提供了各种有效的推理和推理算法,例如消息传递、

{mdframed}[frametitle=Box 2: Inductive biases, backgroundcolor=black!6, nobreak=true, ] 学习是通过观察世界和与世界互动来理解有用知识的过程。它涉及为一个期望提供更好的数据解释或获得更高奖励的解决方案搜索空间。但在许多情况下,有多种同样好的解决方案(Goodman, 1955 )。的*感应偏压*允许学习算法的一个溶液(或演绎)在另一个独立的观测数据的优先级(米切尔,1980)。在贝叶斯模型中,归纳偏差通常通过先验分布的选择和参数化来表示(格里菲思等人,2010 年)。在其他情况下,归纳偏差可能是为避免过度拟合而添加的正则化项(McClelland, 1994 ),或者可能在算法本身的架构中进行编码。归纳偏差通常会牺牲灵活性来提高样本复杂性,并且可以通过偏差-方差权衡来理解(Geman 等人,1992 年)。理想情况下,归纳偏置既可以在不显着降低性能的情况下改进对解决方案的搜索,也可以帮助找到以理想方式泛化的解决方案;然而,不匹配的归纳偏差也会通过引入太强的约束导致次优性能。

归纳偏差可以表达对数据生成过程或解决方案空间的假设。例如,当将一维函数拟合到数据时,线性最小二乘法遵循逼近函数是线性模型的约束,并且在二次惩罚下逼近误差应该最小。这反映了一个假设,即数据生成过程可以简单地解释为被加性高斯噪声破坏的线过程。相似地,升2正则化优先考虑参数值较小的解决方案,并且可以为其他不适定问题引入独特的解决方案和全局结构。这可以解释为关于学习过程的假设:当解决方案之间的歧义较少时,寻找好的解决方案会更容易。请注意,这些假设不必是明确的——它们反映了对模型或算法如何与世界交互的解释。

机器学习和人工智能中的许多具有关系推理能力的方法(框 2)都使用关系归纳偏差。虽然不是一个精确、正式的定义,但我们使用这个术语来泛指归纳偏差(框 2),它对学习过程中实体之间的关系和交互施加约束。

成分 实体 关系 相对。感应偏置 不变性
全连接 单位 一应俱全 虚弱的 ——
卷积 网格元素 当地的 地域性 空间翻译
经常性 时间步长 顺序的 顺序性 时间翻译
图网络 节点 边缘 随意的 节点、边排列

表 1:标准深度学习组件中的各种关系归纳偏差。另见第2节 。近年来,创造性的新机器学习架构迅速激增,(鉴于本文的论点也许并不奇怪)从业者经常遵循一种设计模式,即组合基本构建块以形成更复杂、更深入的33这种深度组合模式在深度学习中无处不在,也是“深度”的来源。计算层次结构和图形44最近的方法(Liu et al., 2018 )甚至通过学习的图形编辑程序使架构构建自动化。. 诸如“全连接”层之类的构建块被堆叠到“多层感知器”(MLP)中,“卷积层”被堆叠到“卷积神经网络”(CNN)中,并且图像处理网络的标准配方通常是一些由 MLP 组成的各种 CNN。这种层的组合提供了一种特殊类型的关系归纳偏差——分层处理——其中计算是分阶段执行的,通常会导致输入信号中信息之间越来越长的范围交互。正如我们在下面探讨的那样,构建块本身也带有各种关系归纳偏差(表 1)。尽管超出了本文的范围,深度学习中也使用了各种非关系归纳偏差:例如,激活非线性、权重衰减、辍学(Srivastava 等人,2014 年)、批处理和层归一化(Ioffe 和Szegedy, 2015 ; Ba et al., 2016 )、数据增强、培训课程和优化算法都对学习的轨迹和结果施加了限制。

为了探索各种深度学习方法中表达的关系归纳偏差,我们必须确定几个关键要素,类似于框2 中的要素 :什么是实体,什么是关系,以及组成实体和关系的规则是什么,以及计算它们的含义?在深度学习中,实体和关系通常表示为分布式表示,规则表示为神经网络函数逼近器;然而,实体、关系和规则的精确形式因架构而异。为了理解架构之间的这些差异,我们可以通过探索进一步询问每个架构如何支持关系推理:

  • [注意事项]
  • 规则函数的参数(例如,提供哪些实体和关系作为输入)。
  • 如何跨计算图(例如,跨不同实体和关系、跨不同时间或处理步骤等)重用共享规则函数。
  • 体系结构如何定义表示之间的交互隔离(例如,通过应用规则来得出有关相关实体的结论,而不是单独处理它们)。

2.1标准深度学习构建块中的关系归纳偏差

全连接层

也许最常见的构建块是全连接层(Rosenblatt, 1961 )。通常实现为向量输入的非线性向量值函数,输出向量的每个元素或“单位”是权重向量之间的点积,后跟一个附加的偏置项,最后是一个非线性,例如作为整流线性单元(ReLU)。因此,实体是网络中的单元,关系是全对全的(层中的所有单元一世 连接到层中的所有单元 j),规则由权重和偏差指定。该规则的论点是完整的输入信号,没有重用,也没有信息隔离(图 1a)。因此,全连接层中隐含的关系归纳偏差非常弱:所有输入单元都可以交互以确定任何输出单元的值,独立于输出(表 1)。

卷积层

另一个常见的构建块是卷积层(Fukushima,1980 年;LeCun 等人,1989 年)。它是通过将输入向量或张量与相同等级的内核进行卷积、添加偏置项并应用逐点非线性来实现的。这里的实体仍然是单个单元(或网格元素,例如像素),但关系更稀疏。全连接层和卷积层之间的差异强加了一些重要的关系归纳偏差:局部性和平移不变性(图 1b)。局部性反映了关系规则的参数是那些在输入信号的坐标空间中彼此非常接近的实体,与远端实体隔离。平移不变性反映了输入中跨位置的相同规则的重用。这些偏差对于处理自然图像数据非常有效,因为局部邻域内存在高协方差,协方差随距离减小,并且因为统计数据在图像上大多是静止的(表 1)。

循环层

第三个常见的构建块是循环层(Elman, 1990 ),它是通过一系列步骤实现的。在这里,我们可以将每个处理步骤的输入和隐藏状态视为实体,将一个步骤的隐藏状态对前一个隐藏状态和当前输入的马尔可夫依赖视为关系。组合实体的规则将步骤的输入和隐藏状态作为参数来更新隐藏状态。该规则在每个步骤中重复使用(图 1c),它反映了时间不变性的关系归纳偏差(类似于 CNN 在空间中的平移不变性)。例如,某些物理事件序列的结果不应取决于一天中的时间。RNN 还通过其马尔可夫结构(表1)对序列中的局部性进行了偏置 。

(a) 全连接 (b) 卷积 (c) 经常性

图 1:重用和共享常见的深度学习构建块。(a) 全连接层,其中所有权重都是独立的,没有共享。(b) 卷积层,其中局部核函数在输入中多次重用。共享权重由相同颜色的箭头表示。(c) 循环层,其中相同的函数在不同的处理步骤中重复使用。

2.2对集合和图的计算

图 2:不同的图形表示。(a) 一个分子,其中每个原子被表示为一个节点,边对应于键(例如 Duvenaud 等,2015)。(b) 质量弹簧系统,其中绳索由一系列质量定义,这些质量在图中表示为节点(例如 Battaglia 等人,2016 年;Chang 等人,2017 年)。(c) 一个n-body 系统,其中主体是节点,底层图是全连接的(例如 Battaglia 等人,2016 年;Chang 等人,2017 年)。(d) 一个刚体系统,其中球和墙是节点,底层图定义了球之间以及球和墙之间的相互作用(例如 Battaglia 等人,2016 年;Chang 等人,2017 年)。(e) 一个句子,其中的单词对应于树中的叶子,其他节点和边可以由解析器提供(例如 Socher 等人,2013 年)。或者,可以使用全连接图(例如 Vaswani 等人,2017 年). (f) 一张图像,可以分解为与全连接图中节点对应的图像块(例如 Santoro 等人,2017 年;Wang 等人,2018c)。虽然标准深度学习工具包包含具有各种形式的关系归纳偏差的方法,但没有“默认”深度学习组件可以在任意关系结构上运行。我们需要具有实体和关系的显式表示的模型,以及找到计算它们的交互的规则的学习算法,以及将它们置于数据中的方法。重要的是,世界上的实体(例如对象和代理)没有自然顺序;相反,排序可以通过它们关系的属性来定义。例如,一组对象的大小之间的关系可以潜在地用于对它们进行排序,它们的质量、年龄、毒性和价格也是如此。

集合是由顺序未定义或不相关的实体描述的系统的自然表示;特别是,他们的关系归纳偏差不是来自某物的存在,而是来自于不存在。例如,考虑预测太阳系质心的任务,包括n 行星,其属性(例如,质量、位置、速度等)表示为 {X1,X2,…,Xn}. 对于这样的计算,我们考虑行星的顺序并不重要,因为状态可以仅用聚合的平均数量来描述。然而,如果我们在这个任务中使用 MLP,在学习了特定输入的预测之后(X1,X2,…,Xn) 不一定会转移到对不同排序下的相同输入进行预测 (Xn,X1,…,X2). 由于有n!这种可能的排列,在最坏的情况下,MLP 可以将每个排序视为根本不同,因此需要指数数量的输入/输出训练示例来学习近似函数。处理这种组合爆炸的一种自然方法是仅允许预测依赖于输入属性的对称函数。这可能意味着计算共享的每个对象特征{F(X1),…,F(Xn)}然后以对称方式聚合(例如,通过取平均值)。这种方法是 Deep Sets 模型(Zaheer 等人,2017 年)的本质,我们将在第4.2.3节中进一步探讨 。

当然,在许多问题中,置换不变性并不是唯一重要的底层结构形式。例如,集合中的每个对象都可能受到与集合中其他对象的成对交互的影响。在我们的行星场景中,现在考虑在一个时间间隔后预测每个行星位置的任务,Δ吨. 在这种情况下,使用聚合的平均信息是不够的,因为每个行星的运动取决于其他行星对其施加的力。相反,我们可以将每个对象的状态计算为X′一世=F(X一世,∑jG(X一世,Xj)), 在哪里 G 可以计算由 j- 第一颗行星 一世-th 行星,和 F 可以计算未来的状态 一世- 由力和动力学产生的行星。我们使用相同的事实G处处又是系统全局置换不变性的结果;然而,它也支持不同的关系结构,因为G现在需要两个参数而不是一个。55我们可以将同样的分析扩展到越来越多的纠缠结构,这些结构依赖于三元组之间的关系(即, G(X一世,Xj,X克))、四重奏等。我们注意到,如果我们将这些函数限制为仅对X一世它们在空间上很接近,那么我们最终会得到类似于 CNN 的东西。在最纠结的意义上,只有一个关系函数的地方G(X1,…,Xn),我们最终得到一个类似于全连接层的结构。

上面的太阳系例子说明了两种关系结构:一种没有关系,另一种由所有成对关系组成。许多现实世界的系统(如图2所示 )具有介于这两个极端之间的关系结构,但是,一些实体对拥有关系,而其他实体则没有。在我们的太阳系示例中,如果该系统由行星及其卫星组成,人们可能会倾向于通过忽略不同行星卫星之间的相互作用来近似它。实际上,这意味着只计算某些对象对之间的交互,即X′一世=F(X一世,∑j∈δ(一世)G(X一世,X% j)), 在哪里 δ(一世)⊆{1,…,n} 是节点周围的邻域 一世. 这对应于一个图,因为一世-th 对象仅与其他对象的子集交互,由其邻域描述。请注意,更新后的状态仍然不依赖于我们描述邻域的顺序。66该模型强制执行的不变性是图同构下的不变性。

图通常是一种支持任意(成对)关系结构的表示,对图的计算提供了强大的关系归纳偏差,超出了卷积层和循环层所能提供的范围。

3图网络

在“图神经网络” (Gori et al., 2005 ; Scarselli et al., 2005 , 2009a ; Li et al., 2016 ),但近年来在范围和受欢迎程度方面迅速增长。我们将在下一小节 ( 3.1 ) 中调查有关这些方法的文献。然后在剩余的小节中,我们展示了我们的图网络框架,它概括和扩展了该领域的几条工作。

3.1背景

图神经网络系列中的模型(Gori et al., 2005 ; Scarselli et al., 2005 , 2009a ; Li et al., 2016)已经在监督、半监督、无监督的各种问题领域中进行了探索和强化学习设置。它们在被认为具有丰富关系结构的任务上很有效,例如视觉场景理解任务(Raposo 等人,2017 年;Santoro 等人,2017 年)和小样本学习(Garcia 和 Bruna,2018 年)。它们还被用于学习物理系统的动力学(Battaglia 等人,2016; Chang 等人,2017 年;沃特斯等人,2017 年;van Steenkiste 等人,2018 年;Sanchez-Gonzalez 等人,2018 年)和多智能体系统(Sukhbaatar 等人,2016 年;Hoshen,2017 年;Kipf 等人,2018 年),对知识图进行推理(Bordes 等人,2013 年;Oñoro et al., 2017 ; Hamaguchi et al., 2017 ),预测分子的化学性质(Duvenaud et al., 2015 ; Gilmer et al., 2017),预测道路交通(Cui et al.,2018),对视频(Wang et al.,2018c)和3D网格和点云(Wang et al.,2018d)进行分类和分割,对图像中的区域进行分类(Chen et al.,2018a),进行半监督文本分类(Kipf 和 Welling,2017 年),以及机器翻译(Vaswani 等人,2017 年;Shaw 等人,2018 年;Gulcehre 等人,2018 年)。它们已用于无模型(Wang 等人,2018b)和基于模型(Hamrick 等人,2017 年); 帕斯卡努等人,2017 年;Sanchez-Gonzalez 等人,2018 年)连续控制,用于无模型强化学习(Hamrick 等人,2018 年;Zambaldi 等人,2018 年),以及更经典的规划方法(Toyer 等人,2017 年)。

许多涉及离散实体和结构推理的传统计算机科学问题也已通过图神经网络进行了探索,例如组合优化(Bello 等人,2016 年;Nowak 等人,2017 年;戴等人,2017 年)、布尔可满足性(Selsam 等人,2018 年)、程序表示和验证(Allamanis 等人,2018 年;Li 等人,2016 年)、元胞自动机和图灵机建模(Johnson,2017 年),以及在图形模型中进行推理(尹等人,2018 年). 最近的工作还侧重于构建图的生成模型(Li 等人,2018 年;De Cao 和 Kipf,2018 年;You 等人,2018 年;Bojchevski 等人,2018 年)和图嵌入的无监督学习(Perozzi 等人) al.,2014 年;Tang 等人,2015 年;Grover 和 Leskovec,2016 年;García-Durán 和 Niepert,2017 年)。

上面引用的作品绝不是一个详尽的列表,而是提供了图神经网络已被证明有用的领域广度的代表性横截面。我们向感兴趣的读者指出一些现有的评论,这些评论更深入地研究了图神经网络的工作主体。特别是,斯卡塞利等人。( 2009a )提供了早期图神经网络方法的权威概述。 布朗斯坦等。( 2017 )对非欧式数据的深度学习进行了出色的调查,并探索了图神经网络、图卷积网络和相关的谱方法。最近,吉尔默等人。( 2017 )介绍了消息传递神经网络 (MPNN),它统一了各种图神经网络和图卷积网络方法(Monti 等人,2017 年;Bruna 等人,2014 年;Henaff 等人,2015 年;Defferrard 等人,2016 年);Niepert 等人,2016 年;Kipf 和 Welling,2017 年;Bronstein 等人,2017 年)通过类比图形模型中的消息传递。同样,Wang 等人。( 2018c )介绍了非局部神经网络 (NLNN),它统一了各种“自我注意”风格的方法(Vaswani 等人,2017 年;Hoshen,2017 年); Veličković 等人,2018 年)通过类比计算机视觉和图形模型的方法来捕获信号中的长距离依赖关系。

3.2图网络(GN)块

{mdframed}[frametitle=Box 3:我们对“图形”的定义,backgroundcolor=black!6, nobreak=true, ]

这里我们使用“graph”来表示具有全局属性的有向、属性多重图。在我们的术语中,一个节点表示为v一世,边为 电子克,以及全局属性为 你. 我们也用秒克 和 r克 分别为边指示发送方和接收方节点的索引(见下文) 克. 更准确地说,我们将这些术语定义为:

[注意事项]

导演:单向边,从“发送者”节点到“接收者”节点。

属性:可以编码为向量、集合甚至另一个图的属性。

归因:边和顶点具有与之关联的属性。

全局属性:图形级属性。

多图:顶点之间可以有多个边,包括自边。

2显示了与我们可能对建模感兴趣的真实数据相对应的各种不同类型的图,包括物理系统、分子、图像和文本。

我们现在展示我们的图网络(GN) 框架,它定义了一类用于对图结构表示进行关系推理的函数。我们的 GN 框架概括和扩展了各种图神经网络、MPNN 和 NLNN 方法(Scarselli 等人,2009a;Gilmer 等人,2017 年;Wang 等人,2018c),并支持从简单的构建块构建复杂的架构。77我们还计划在今年晚些时候发布一个用于图网络的开源库。 请注意,我们避免在“图网络”标签中使用术语“神经”,以反映它们可以使用神经网络以外的功能来实现,尽管这里我们的重点是神经网络的实现。

GN 框架中的主要计算单元是GN 块,这是一个“图到图”模块,它以图为输入,对结构执行计算,并返回图作为输出。如框 3.2 所述,实体由图的节点表示,关系由边表示,系统级属性由全局属性表示。GN 框架的块组织强调可定制性和综合表达所需关系归纳偏差的新架构。关键的设计原则是: 灵活的表示(见第4.1节 );可配置的块内结构(参见第4.2); 和可组合的多块架构(参见第4.3节 )。

我们引入了一个激励性的例子来帮助使 GN 形式主义更加具体。考虑在任意引力场中预测一组橡皮球的运动,这些橡皮球不是相互弹跳,而是有一个或多个弹簧将它们连接到其他一些(或全部)。我们将在下面的定义中引用这个运行示例,以激发图形表示和在其上运行的计算。图 2描绘了一些其他常见的场景,这些场景可以用图表示并使用图网络进行推理。

“图形”的定义

在我们的 GN 框架中,被定义为一个三元组G=(\全局变量,伏,乙)(有关图形表示的详细信息,请参见框 3.2)。这\全局变量是一个全局属性;例如,\全局变量可能代表引力场。这伏={v一世}一世=1:Nv 是节点集(基数 Nv),其中每个 v一世是节点的属性。例如,伏可能代表每个球,具有位置、速度和质量的属性。这乙={(电子克,r克,秒克)}克=1:N电子 是边的集合(基数的 N电子),其中每个 电子克 是边的属性, r克 是接收节点的索引,并且 秒克是发送节点的索引。例如,乙 可能代表不同球之间存在弹簧,以及它们相应的弹簧常数。

GN块的内部结构

一个 GN 块包含三个“更新”功能, φ,以及三个“聚合”函数, ρ,

电子′克=φ电子(电子克,vr克,v秒克,\全局变量)v′一世=φv(¯电子′一世,v一世,\全局变量)\全局变量′=φ你(¯电子′,¯v′,\全局变量)¯电子′一世=ρ电子→v(乙′一世)¯电子′=ρ电子→你(乙′)¯v′=ρv→你(伏′) (1)

在哪里 乙′一世={(电子′克,r克,秒克)}r克=一世,克=1:N电子, 伏′={v′一世}一世=1:Nv, 和 乙′=⋃一世乙′一世={(电子′克,r克,秒克)}克=1:N电子.

这 φ电子 映射到所有边以计算每边更新, φv 映射到所有节点以计算每个节点的更新,并且 φ你作为全局更新应用一次。这ρ每个函数都将一个集合作为输入,并将其简化为代表聚合信息的单个元素。至关重要的是,ρ 函数必须对其输入的排列保持不变,并且应该采用可变数量的参数(例如,元素求和、均值、最大值等)。

GN 块中的计算步骤

函数 GraphNetwork (乙, 伏, 你)

为了 克∈{1…N电子} 做

     电子′克←φ电子(电子克,vr克,v秒克,\全局变量)▹ 1. 计算更新的边属性

 结束 于

 为了 一世∈{1…Nn} 做

     让 乙′一世={(电子′克,r克,秒克)}r克=一世,克=1:N电子

     ¯电子′一世←ρ电子→v(乙′一世)▹ 2. 聚合每个节点的边属性

     v′一世←φv(¯电子′一世,v一世,\全局变量)▹ 3. 计算更新的节点属性

 结束 于

 让 伏′={v′}一世=1:Nv

 让 乙′={(电子′克,r克,秒克)}克=1:N电子

 ¯电子′←ρ电子→你(乙′)▹ 4.全局聚合边缘属性

 ¯v′←ρv→你(伏′)▹ 5.全局聚合节点属性

 \全局变量′←φ你(¯电子′,¯v′,\全局变量)▹ 6. 计算更新后的全局属性

 返回 (乙′,伏′,你′)

结束 函数

算法 1 完整 GN 块中的计算步骤。当一个图形, G, 作为输入提供给 GN 块,计算从边缘进行,到节点,再到全局级别。图 3显示了在这些计算中的每一个中涉及哪些图元素的描述,图 3(a)显示了一个完整的 GN 块,及其更新和聚合函数。算法 1显示了以下计算步骤:

  1. [注意事项]
  2. φ电子 每条边应用,带参数 (\ev克,\vvr克,\vv秒克,\紫外线),并返回 \ev′克. 在我们的弹簧示例中,这可能对应于两个连接球之间的力或势能。每个节点的每条边输出结果集,一世, 是, 乙′一世={(电子′克,r克,秒克)}r克=一世,克=1:N电子. 和乙′=⋃一世乙′一世={(电子′克,r克,秒克)}克=1:N电子 是所有每边输出的集合。
  3. ρ电子→v 应用于 乙′一世,并聚合投影到顶点的边的边更新 一世, 进入 ¯电子′一世,将在下一步的节点更新中使用。在我们的运行示例中,这可能对应于对作用在物体上的所有力或势能求和。一世吨H 球。
  4. φv 应用于每个节点 一世, 计算更新的节点属性, v′一世. 在我们的运行示例中,φv可以计算类似于每个球的更新位置、速度和动能的东西。产生的每个节点输出的集合是,伏′={v′一世}一世=1:Nv.
  5. ρ电子→你 应用于 乙′,并将所有边更新聚合到 ¯电子′,然后将在下一步的全局更新中使用。在我们的运行示例中,ρ电子→你 可以计算总和力(在这种情况下,由于牛顿第三定律,它应该为零)和弹簧的势能。
  6. ρv→你 应用于 伏′,并将所有节点更新聚合到 ¯v′,然后将在下一步的全局更新中使用。在我们的运行示例中,ρv→你 可以计算系统的总动能。
  7. φ你 每个图应用一次,并计算全局属性的更新, \全局变量′. 在我们的运行示例中,φ你 可能会计算类似于物理系统的净力和总能量的东西。

请注意,虽然我们在这里假设了这个步骤序列,但顺序并不是严格执行的:例如,可以颠倒更新函数以从全局更新到每个节点,再到每个边缘更新。卡恩斯等人。( 2016 )以类似的方式从节点计算边更新。

(a) 边缘更新 (b) 节点更新 (c) 全球更新

图 3:GN 块中的更新。蓝色表示正在更新的元素,黑色表示更新中涉及的其他元素(注意蓝色元素的更新前值也用于更新)。有关符号的详细信息,请参见公式 1

图网络中的关系归纳偏差

当用作学习过程中的组件时,我们的 GN 框架会施加几个强烈的关系归纳偏差。首先,图可以表达实体之间的任意关系,这意味着 GN 的输入决定了表示如何交互和隔离,而不是由固定架构决定这些选择。例如,假设两个实体具有关系——因此应该交互——由实体对应节点之间的边表示。类似地,没有边表达了节点没有关系并且不应该直接影响彼此的假设。

其次,图将实体及其关系表示为集合,这些集合对于排列是不变的。这意味着 GN 对这些元素的顺序是不变的88注意,可以通过对节点或边属性中的索引进行编码,或通过边本身(例如,通过对链或偏序进行编码)来实施排序。,这通常是可取的。例如,场景中的对象没有自然排序(参见第2.2节 )。

第三,GN 的每边和每节点功能分别在所有边和节点上重用。这意味着 GN 自动支持一种组合泛化形式(参见第5.1节 ):因为图由边、节点和全局特征组成,单个 GN 可以对不同大小(边和节点的数量)和形状(边的数量)的图进行操作连通性)。

4图网络架构的设计原则

的GN框架可被用于实现各种体系结构中的,按照上面节中列出的设计原则 3.2,这也相应于子部分(4.14.2,以及4.3以下)。通常,该框架与特定的属性表示和功能形式无关。然而,在这里,我们主要关注深度学习架构,它允许 GN 充当可学习的图到图函数逼近器。

4.1灵活的表示

图网络以两种方式支持高度灵活的图表示:第一,在属性的表示方面;其次,就图本身的结构而言。

属性

GN 块的全局、节点和边属性可以使用任意表示格式。在深度学习实现中,实值向量和张量是最常见的。但是,也可以使用其他数据结构,例如序列、集合甚至图。

问题的要求通常会决定属性应该使用什么表示。例如,当输入数据是图像时,属性可能表示为图像块的张量;然而,当输入数据是文本文档时,属性可能是与句子对应的单词序列。

对于更广泛架构中的每个 GN 块,边和节点输出通常对应于向量或张量列表,每个边或节点一个,而全局输出对应于单个向量或张量。这允许将 GN 的输出传递给其他深度学习构建块,例如 MLP、CNN 和 RNN。

GN 块的输出也可以根据任务的需求进行定制。特别是,

  • [注意事项]
  • 边缘为中心的GN 使用边缘作为输出,例如对实体之间的交互做出决策(Kipf 等人,2018 年;Hamrick 等人,2018 年)。
  • 节点为中心的GN 使用节点作为输出,例如对物理系统进行推理(Battaglia 等人,2016 年;Chang 等人,2017 年;Wang 等人,2018b;Sanchez-Gonzalez 等人,2018 年)。
  • 图形为中心的GN 使用全局变量作为输出,例如预测物理系统的势能(Battaglia 等人,2016 年)、分子的属性(吉尔默等人,2017 年)或有关问题的答案一个视觉场景(Santoro et al., 2017)。

节点、边和全局输出也可以根据任务进行混合匹配。例如,哈姆里克等人。( 2018 )使用输出边缘和全局属性来计算动作策略。

图结构

在定义如何将输入数据表示为图时,通常有两种情况:第一,输入明确指定关系结构;其次,必须推断或假设关系结构。这些不是硬性区别,而是连续统一体中的极端。

具有更明确指定实体和关系的数据示例包括知识图、社交网络、解析树、优化问题、化学图、道路网络和具有已知交互作用的物理系统。图 2 A-D示出了如何将这些数据被表示为曲线图。

关系结构未明确且必须推断或假设的数据示例包括视觉场景、文本语料库、编程语言源代码和多代理系统。在这些类型的设置中,数据可能被格式化为一组没有关系的实体,甚至只是一个向量或张量(例如,图像)。如果未明确指定实体,则可以假设它们,例如,通过将句子中的每个单词(Vaswani 等人,2017 年)或 CNN 输出特征图中的每个局部特征向量视为一个节点(Watters 等人2017 年)., 2017 ; Santoro et al., 2017 ; Wang et al., 2018c )(图 2ef)。或者,也可以使用单独的学习机制从非结构化信号中推断实体(Luong 等人,2015 年;Mnih 等人,2014 年;Eslami 等人,2016 年;van Steenkiste 等人,2018 年)。如果关系不可用,最简单的方法是实例化实体之间所有可能的有向边(图 2 f)。然而,这对于大量实体来说可能是令人望而却步的,因为可能的边数与节点数成二次方增长。因此,开发从非结构化数据中推断稀疏结构的更复杂的方法(Kipf 等人,2018 年)是一个重要的未来方向。

(a) 完整的 GN 块 (b) 独立循环块 (c) 消息传递神经网络 (d) 非局部神经网络 (e) 关系网络 (f) 深集

图 4:不同的内部 GN 块配置。有关符号的详细信息,请参阅第3.2节,有关每个变体的详细信息,请参阅第 4节 。(a) 完整的 GN 根据传入节点、边和全局属性预测节点、边和全局输出属性。(b) 一个独立的、循环的更新块接受输入图和隐藏图,并且φ函数是 RNN (Sanchez-Gonzalez 等人,2018 年)。(c) MPNN (Gilmer et al., 2017 )根据传入的节点、边和全局属性预测节点、边和全局输出属性。请注意,全局预测不包括聚合边。(d) NLNN (Wang et al., 2018c )只预测节点输出属性。(e) 关系网络(Raposo 等人,2017 年;Santoro 等人,2017 年)仅使用边缘预测来预测全局属性。(f) 深度集(Zaheer 等人,2017 年)绕过边缘更新并预测更新的全局属性。

4.2可配置的块内结构

GN 块内的结构和功能可以以不同的方式配置,这在哪些信息可用作其功能的输入以及如何产生输出边、节点和全局更新方面提供了灵活性。特别是,每个φ在等式 1 中必须用一些函数来实现,F, 在哪里 F的参数签名决定了它需要什么信息作为输入;在图 4 中,每个的传入箭头φ 描绘是否 \全局变量, 伏, 和 乙被视为输入。 哈姆里克等人。( 2018 )和Sanchez-Gonzalez 等人。( 2018 )使用了图3(a)中所示的完整 GN 块 。他们的φ 使用神经网络的实现(表示 NN电子, NNv, 和 NN你下,以表明它们是具有不同参数的不同函数)。他们的ρ 实现使用元素求和,但也可以使用平均值和最大值/最小值,
表示向量/张量串联。对于向量属性,MLP 通常用于φ,而对于图像特征图等张量,CNNs 可能更合适。

这 φ函数也可以使用 RNN,这需要额外的隐藏状态作为输入和输出。图 3(b)显示了一个非常简单的带有 RNN 的 GN 块版本φ功能:在这个公式中没有消息传递,这种类型的块可能用于一些动态图状态的循环平滑。当然,RNNsφ函数也可以用于完整的 GN 块(图 3(a))。

在 GN 框架中可以表达各种其他架构,通常表现为不同的功能选择和块内配置。其余小节探讨了如何以不同方式配置 GN 的块内结构,并提供使用此类配置的已发表作品示例。详情请参阅附录。

消息传递神经网络 (MPNN)

吉尔默等人。( 2017 )的 MPNN 概括了许多以前的架构,并且可以自然地转化为 GN 形式主义。遵循 MPNN 论文的术语(参见Gilmer 等人(2017 年),第 2-4 页):

  • [注意事项]
  • 消息功能, 米吨, 扮演 GN 的角色 φ电子,但不采取 \全局变量 作为输入,
  • 元素求和用于 GN ρ电子→v,
  • 更新功能, 你吨, 扮演 GN 的角色 φv,
  • 读出函数, 电阻, 扮演 GN 的角色 φ你,但不采取 \全局变量 要么 乙′ 作为输入,因此是 GN 的模拟 ρ电子→你 不需要;
  • d米一种秒吨电子r 与 GN 的用途大致相似 \全局变量,但被定义为连接到所有其他节点的额外节点,因此不会直接影响边缘和​​全局更新。然后它可以在 GN 中表示伏.

3(c)显示了根据 GN 框架,MPNN 的结构。有关详细信息和各种 MPNN 架构,请参阅附录。

非局部神经网络 (NLNN)

图 5:NLNN 作为 GN。显示 NLNNs (Wang et al., 2018c )如何由φ电子 和 ρ电子→v在 GN 框架下。通常,NLNN 假设图像的不同区域(或句子中的单词)对应于全连接图中的节点,并且注意机制在聚合步骤期间定义了节点的加权总和。王等人。( 2018c )的 NLNN,它统一了各种“内部/自我/顶点/图形注意”方法(Lin 等人,2017 年;Vaswani 等人,2017 年;Hoshen,2017 年;Veličković 等人,2018 年) ; 肖等人,2018 年), 也可以翻译成 GN 形式主义。标签“注意力”是指节点如何更新:每个节点更新基于其邻居节点属性(的某个函数)的加权和,其中节点与其邻居之一之间的权重由它们的属性之间的标量成对函数(然后在邻居之间进行归一化)。已发布的 NLNN 形式没有明确包含边,而是计算所有节点之间的成对注意力权重。但是各种符合 NLNN 的模型,例如顶点注意力交互网络(Hoshen,2017 年)和图注意力网络(Veličković 等人,2018 年),能够通过有效地将不共享边的节点之间的权重设置为零来处理显式边。

如图 3(d)5所示,φ电子 被分解到标量成对交互函数中,该函数返回未归一化的注意项,表示为 α电子(vr克,v秒克)=一种′克,以及一个向量值的非成对项,表示为 β电子(v秒克)=乙′克. 在里面ρ电子→v 聚合 一种′克 项在每个接收器的边缘上进行归一化, 乙′克,并按元素求和: