关系归纳偏差,深度学习和图网络(翻译)

2019-02-19

摘要

人工智能(AI)最近经历了一次复兴,在视觉、语言、控制和决策等关键领域取得了重大进展。这在一定程度上要归功于廉价的数据和廉价的计算资源,它们符合深度学习的自然优势。然而,在许多不同的压力下,发展起来的人类智能的许多决定性特征,对于目前的方法来说仍然是遥不可及的。特别是,从一个个体经验来泛化出来一些可以广泛适用群体的特征仍然是现代人工智能的一个艰巨的挑战。
以下是一些主观想法、回顾。我们认为,组合泛化(combinatorial generalization)必须是人工智能获得“类人智能”能力的首要任务,而结构化的表征(structured representations)和计算能力(computations)是实现这一目标的关键。如生物学中,将先天基因和后天孕育结合在一起,因此我们必须摒在“ 手动设计结构 (hand-engineering) ”和“ 端到端(end-to-end)”二选一的错误做法,而是把两者结合起来。我们探讨了如何在深度学习体系结构中使用关系归纳偏差来促进对实体、关系和组成它们的规则的学习。本文提出了一种新的基于关系归纳偏置的人工智能工具 – 图网络,它推广和扩展了神经网络在图上操作的各种方法,并为结构化知识的操作和结构化行为的产生提供了一个直观的接口。我们讨论了图网络如何支持关系推理和组合泛化,为更复杂、更可解释和更灵活的推理模式奠定了基础。作为本文的一部分,我们还发布了一个用于构建图网络的开源软件库,并演示了如何在实践中使用它们。

1. 介绍

人类智能的一个重要标志是能“无限使用有限手段”的能力(Humboldt,1836年;Chomsky,1965),在这种能力中,一小组元素(如单词)可以无限的方式进行组合(例如变成新的句子)。这反映了组合泛化的原则,即从已有的模块进行组合,来达到推理,预测等功能。在这里,我们将探索如何提高现代人工智能的组合泛化能力,通过偏重于结构化表示和计算的学习,特别是运行在图上的系统。
人类组合泛化能力依赖于我们对结构化表示和关系推理的认知。我们将复杂系统表示为实体及其相互作用的组成(Navon,1977年;McClelland和Rumelhart,1981年;Platut等人,1996年;Marcus,2001年;Goodwin和Johnson-Laird,2005年;Kemp和Tenenbaum,2008年),例如判断一堆杂乱无章的对象是否稳定(Battaglia等人,2013年)。我们使用层次结构来抽象出细粒度的差异,并捕获表示和行为之间更一般的共性(Botvinick,2008;Tenenbaum等人,2011),例如对象的各个部分、场景中的对象、城镇中的邻居和国家中的城镇。面对新颖的问题,会采用相似技能与常规经验相组合(composing familiar skills and routines)来解决。(Anderson,1982),例如,通过采用相似的方式或采用相似目标,到一个新的地点旅行,如“乘飞机旅行”、“到圣地亚哥”、“在餐馆吃饭”和“印度餐馆”。我们通过对齐两个域之间的关系结构, 并根据其中一个域来对另一个域相对应的知识得出一个推论或类比(Gentner和Markman,1997;Hummel和Holyoak,2003)。

肯尼斯·克雷克(Kenneth Craik,1943)的“解释的本质”一书中将世界的构成结构与我们内在心理模型的组织方式联系在一起:

..[人类心理模型]与它所模仿的过程有着相似的关系结构。这里所说的“关系结构”,并不是指参与模型的某种模糊的非物理实体,而是指这样一个事实,即它是一个工作的物理模型,它的工作方式与它运行的过程是相同的。显然,物理现实是由几种基本类型的单位建立起来的,它们的性质决定了最复杂现象的许多性质,这似乎提供了一个充分的解释。机制之间的类比和这些组合之间关系结构的相似之处的出现,没有任何客观共性理论的必要。(Craik,1943年,第51-55页)。

也就是说,世界是组成的,或者至少,我们从组成方面去理解他。当我们在学习时,我们把新的知识添加到已经学过的结构表示中,或是调整整体结构来适应新、旧知识的整合(Tenenbaum等人,2006年;Griffiths等人,2010年;Ullman等人,2017年)。

如何构建具有组合泛化能力的人工系统是人工智能的核心问题,也是许多结构化方法的核心,包括逻辑、语法、经典规划、图模型、因果推理、无参数贝叶斯模型和概率规划(Chomsky,1957;Nilsson和Fikes,1970;Pearl,1986,2009;Russell和Norvig,2009;Hjort等人,2010年;Goodman等人,2012年;Ghahramani,2015年)。整个子领域都侧重于以实体和关系为中心的显式学习,如关系增强学习(Dˇzeroski等人,2001年)和统计关系学习(Getoor和Taskar,2007年)。在以前的时代,结构化方法对机器学习如此重要的一个关键原因,部分是因为数据和计算资源昂贵,而结构化方法强大的归纳偏差所带来的,更高的样本复杂性是非常有价值的。

与人工智能中的过去方法相反,现代深度学习方法(Lecun等人,2015年;Schmidhuber,2015年;Goodfeler等人,2016年)往往遵循一种“端到端”的设计哲学,这种哲学强调最小化先验表征和计算假设,并避免明确的结构和手工设计结构。这一强调与目前大量的廉价数据和廉价计算资源非常吻合,这使得以样本效率为代价进行更灵活的学习成为一种合理的选择。从图像分类(Krizhevsky等人,2012年;Szegedy等人,2017年)到自然语言处理(SutSkever等人,2014年;Bahdanau等人,2015年),再到游戏(Mnih等人,2015年;Silver等人,2016年),在许多具有挑战性的领域取得了显著而迅速的进展。(Moravˇc´ık等人2017年),是这一最低限度原则的证明。一个突出的例子是语言翻译,其中序列到序列的方法(Sutkever等人,2014年;Bahdanau等人,2015年)证明非常有效,而没有使用明确的解析树或语言实体之间的复杂关系。

然而,尽管深度学习取得了成功,但也遭受了很多的批评(Marcus,2001年;Shalev-Shwartz等人,2017年;Lake和Baroni,2018年;Marcus,2018a,b;珀尔,2018年);Yuille和Liu(2018年)。正是由于深度学习刻意避开了组合性和明确的结构方法,而面对像复杂语言、场景理解、结构化数据推理、基础训练上的迁移学习和少量经验学习这些需要组合泛化功能实现的任务,深度学习在这些任务上就难以实现了。

当深度学习的连接主义者(Rumelhart等人,1987年)的祖先面对来自结构化、象征性立场的类似批评(Fodor 和 Pylyshyn, ,1988年;Pinker 和 Prince ,1988年)时,一些人作出了建设性的努力(Bobrow 和 Hinton,1990年;Marcus ,2001年),以直接和谨慎地应对挑战。在类比、语言分析、符号操作和其他形式的关系推理等领域中,出现了各种创新性的次符号方法来表示和推理结构化对象(Smolensky,1990;Hinton,1990;Polack,1990;Elman,1991;Platet,1995;Smolensky,1990;Hinton,1990;Elias.hk,2013年),以及更多关于思维如何运转的综合理论(Marcus,2001年),这项工作还帮助培养了更新的深度学习进展,利用分布式向量表示法在文本(Mikolov等人,2013年;Penington等人,2014年)、图(Narayanan等人,2016年,2017年)、代数和逻辑表达式(Allamanis等人,2017年,Evans等人,2018年)和程序(Devlin等人,2017年;Chen等人,2018b)中捕捉丰富的语意内容。

我们建议,现代人工智能的一个关键途径是致力于将组合泛化作为首要任务,并主张采用综合的方法来实现这一目标。正如生物学不会在先天和后天之间做出选择一样-它联合使用天性和后天培养,来构建大于其各部分总和的整体,我们也拒绝结构和灵活性在某种程度上不一致或不相容的观点,如果同时将两者结合起来,就能获得它们的互补优势。本着最近许多基于结构的方法与深入学习原则相结合的例子的精神(例如,Reed和de Freitas,2016年;Garnelo等人,2016年;Ritchie等人,2016年;Wu等人,2017年;Denil等人,2017年;Hudson和Manning,2018),我们看到了利用完整的人工智能工具综合新技术的巨大希望,并将当今最好的方法与数据和计算结合在一起。

最近,在深度学习和结构化方法的交集中出现了一类模型,其侧重于推理明确结构化数据的方法,特别是图(例如,Scarselli等人,2009年b;Bronstein等人,2017年;Gilmer等人,2017年;Wang等人,2018c;Li等人,2018年;Kipf等人,2018年;Gulcehre等人,2018年)。这些方法的共同之处在于,它们都具有在离散实体以及它们之间的关系上执行计算的能力。使它们与传统方法区别开来的是如何可以学习实体和关系的表示和结构以及相应的计算,从而减轻了需要提前指定它们的负担。至关重要的是,特定的结构假设则会带来强烈的关系归纳偏差,而特定的假设结构会引导这些方法来学习实体和关系,偏好也是人类智能的基本成分

在本文的其余部分,我们通过它们的关系归纳偏差来研究各种深度学习方法,表明现有方法通常带有关系假设,这些假设并不总是明显的。 然后,我们提出了基于实体和关系的推理的一般框架 - 我们称之为图网络,用于统一和扩展在图上运行的现有方法,并描述使用图网络作为构建块构建强大架构的关键设计原则。 我们还发布了一个用于构建图网络的开源库,可以在这里找到:Graph_Nets.

Box 1:关系推理

我们将结构定义为已知模块组合而成的产品 (We de ne structure as the product of composing a set of known building blocks)。“结构化表示”捕获了这种组合(即元素的排列),而“结构化计算”对元素及其组合作为一个整体进行操作。关系推理则是使用规则(rules)来操纵实体(entities)、关系(relations)的结构表示。我们用如下术语来捕获AI和计算机科学中的概念:

实体是具有属性的元件,例如具有大小和质量的物理对象。
关系是实体之间的属性。两个对象之间的关系可能包括与、大于和距离相同的大小。关系也可以有属性。比如取一个属性“重X倍”的关系,X属性确定关系的相对权重阈值为true或者false。
规则是一个函数(如非二元逻辑谓词),用来衡量实体,关系和其它实体,关系,像规模比较(哪个实体更大,X实体比Y实体大多少)。

作为机器学习中关系推理的一个例子,图模型(Pearl,,1988;Koller和Friedman,2009)通过对随机变量进行显式的随机条件独立性来表示复杂的联合分布,模型能取得成功,是因为模型可以捕获到真实世界生成过程的稀疏结构并且能够进行推理和学习。例如,隐马尔科夫模型约束潜在的状态,在前一个时间步上有条件地独立于其他的状态,在当前时间步上有条件的独立于观察,这与许多现实世界因果关系结构很匹配。显示表示了稀疏的变量之间的依赖关系提供了各种有效的推理和算法,如消息传递,应用一个图模型中跨地区公共信息传播,得到一个可组合,部分并行的推理过程,同时可以应用于不同大小和形状的图模型。

Box 2: 归纳偏差

学习是通过观察和与世界互动来理解有用知识的过程。它涉及到寻找一个解空间中的解,以提供更好的数据解释或获得更高的奖励。但在许多情况下,有多种解决方案同样出色(Goodman,1955)。归纳偏差允许学习算法将一种解决方案(或解释)优先于另一种解决方案(或独立于观察到的数据)(Mitchell,1980)。在贝叶斯模型中,归纳偏差通常通过先验分布的选择和参数化来表达(Griffiths等,2010)。在其他情况下,归纳偏差可能是一个正则化项(McClelland,1994),以避免过度拟合,或者它可能在算法本身的架构中编码。归纳偏差通常会提高灵活性,以提高样本的复杂性,并可以根据偏差 - 方差权衡来理解(Geman等,1992)。理想情况下,归纳偏差既可以改善对解决方案的搜索,又不会显着降低性能,也可以帮助找到以理想方式推广的解决方案;然而,不匹配的归纳偏差也可能通过引入过于强大的约束得到一个次优解方案。

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

2. 关系归纳偏差

机器学习和AI中有许多具有关系推理能力的方法(Box 1)使用关系归纳偏差。也许这个说法不够准确和规范,但我们把在学习过程中,实体之间关系和相互作用施加约束叫做归纳偏差(Box 2)。

创建新的机器学习结构在最近几年非常火,从业者经常遵循堆叠基本结构(the building block)的设计模式,以形成更复杂,更深入的计算层次结构和图。诸如“全连接层”的基本结构被堆叠成“多层感知器”(MLP),“卷积层”被堆叠到“卷积神经网络”(CNN)中,并且用于图像处理网络的标准方法通常是由各种CNN叠加到MLP中。这种“层组合”提供了特定类型的关系归纳偏差 – 分层处理 ,其中计算分阶段执行,通常导致输入阶段中的信息之间的长距离交互。正如我们在下面探讨的那样,基本结构本身也带有各种关系归纳偏差(表1)。虽然超出了本文的范围,但深度学习中也使用了各种非关系归纳偏差:例如,激活非线性,权重衰减,dropout(Srivastava等,2014),batch and layer normalization(Ioffe和Szegedy,2015; Ba等,2016),数据增强,模型训练和优化算法都对学习的过程和结果施加了限制。


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

  1. 规则函数的参数(例如,提供哪些实体和关系作为输入)。
  2. 规则函数如何在计算图中重复使用或共享(例如,跨越不同的实体和关系,跨越不同的时间或处理步骤等)。
  3. 架构如何定义交互与表示之间的隔离(例如,通过应用规则来得出关于相关实体的结论,而不是单独处理它们)。

2.1 关系归纳偏差在标准深度学习中的基本结构

2.1.1 全连接层

全连接层也许是最常见的基本结构。通常实现为输入向量和输出向量间的非线性函数,输出向量的每个元素或“单元”是权重向量之间的点积,后跟增加的偏置项,最后是非线性函数,例如整流线性单元(ReLU)。 因此,实体是网络中的单元,关系是all-to-all(层i中的所有单元都连接到层j中的所有单元),并且规则由权重和偏置指定。 规则的参数是完整的输入信号,没有重用,并且没有信息隔离(图1a)。 因此,全连接层中的隐式关系归纳偏差非常弱:所有输入单元可以相互作用以确定任何输出单元的值,独立地在输出之间(表1)。

2.1.2 卷积层

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

2.1.3 循环层

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

2.2 集合和图中的计算

尽管标准深度学习中包含具有各种形式的关系归纳偏差的方法,但没有一个“默认”的深度学习组件能在任意关系结构上运行。 我们需要具有实体和关系的明确表征的模型,用于计算其交互的规则的学习算法,以及将它们在数据上组合的方法。 重要的是,世界上的实体(例如对象和agent)没有天然的顺序; 相反,排序可以通过其关系的属性来定义。 例如,一组物体的大小之间的关系可以用来排列它们,它们的质量,年龄,毒性和价格也可以。 排列的不变性(除了在关系中) 是理想情况下应该由(关系推理的)深度学习组件反映的属性。

集合是顺序未定义或不相关的实体描述的系统的自然表示;值得注意的是,他们的关系归纳偏差不是来自某事物的存在,而是来自事物的缺席。直观点,考虑预测由n个行星组成的太阳系的质心的任务,其属性(例如,质量,位置,速度等)由$(x_1, x_2, ... , x_n)$表示。对于这样的计算,我们考虑行星的顺序无关紧要,因为状态可以仅根据聚合的平均量来描述。但是,如果我们使用MLP执行此任务,那么特定输入$(x_1, x_2, ... , x_n)$的预测跟打乱他们顺序$(x_n, x_1, ... , x_2)$产生的预测就有可能不同。因为有n!种可能的排列,最坏的情况下,MLP可以将每个排序视为根本不同,因此需要指数数量的输入/输出训练示例来学习近似函数。处理这种组合爆炸的一种自然方法是仅允许预测依赖于输入属性的对称函数。这可能意味着计算共享的每个对象的特征$\lbrace{f(x_1), ... , f(x_n)}\rbrace$然后以对称的方式聚合(例如,通过取其平均值)。 这种方法是深度集成相关模型的本质(Zaheer等,2017; Edwards和Storkey,2016; Pevn`和Somol,2017),我们将在4.2.3节进一步探讨。

当然,在许多问题中,置换不变性不是底层结构的唯一形式。例如,集合中的每个对象可能受到与集合中其他对象的成对交互的影响(Hartford等,2018)。在我们的行星场景中,现在考虑在一个时间间隔Δt之后预测每个行星的位置的任务。在这种情况下,使用聚合的平均信息是不够的,因为每个行星的运动取决于其他行星施加在其上的力。相反,我们可以将每个对象的状态计算为$x_i^{'}=f(x_i,\sum_j{g(x_i,x_j)})$,其中$g$可以计算第$j$行星在第$i$行星上引起的力,$f$可以计算出第$i$行星受牵引力的影响的未来状态。我们在任何地方使用相同的$g$是因为系统的全局置换不变性;但是,它也支持不同的关系结构,因为$g$现在需要两个参数而不是一个参数。

上述太阳系实例说明了两个关系结构:一个内部没有关系,一个由全部的成对关系组成。 许多现实世界的系统(如图2所示)在这两者之间,这些系统具有关系结构,其中,一些实体拥有关系而其他实体则缺少这种关系。 在我们的太阳系示例中,如果系统由行星及其卫星组成,则可以通过忽略不同行星的卫星之间的相互作用来逼近它。 实际上,这意味着仅在某些对象之间计算交互,即$x_i^{'}=f(x_i,\sum_{j\in{\delta(i)}}{g(x_i,x_j)})$,其中$\delta(i)\subseteq\lbrace{1, ... , n\rbrace}$是$i$邻域上的节点。 这对应于图表,因为第i个对象仅与其领域描述的其他对象的子集交互。 注意,更新的状态仍然不依赖于我们描述邻域的顺序。


通常,图(Graph)支持任意(成对)关系结构的表征,并且图上的计算可以提供超过卷积和循环层的强大的关系归纳偏差。

3. 图网络

在“图神经网络”中,神经网络在图上运行并相应地构建其计算,已经被广泛开发和探索了十多年(Gori等,2005;Scarselli等,2005,2009a;Li,2016),但近年来发展更为迅速。 我们在下一小节(3.1)中对这些方法的文献进行概括。 然后在剩下的小节中,我们展示了我们的图形网络框架,该框架概括并扩展了该领域的几项工作。

Box 3:我们对“图”的定义


这里我们使用“图”来表示具有全局属性的有向的属性化(Attributed)的伪图(a directed, attributed multi-graph with a global attribute)。 在我们的术语中,节点用$v_i$表示,边用$e_k$表示,全局属性用$u$表示。 我们还使用$s_k$和$r_k$分别指示边$k$的发送节点和接收节点的索引(见下文)。 更确切地说,我们将这些术语定义为:

定向:有向边,从“发送”节点到“接收”节点。
属性:属性,可以编码为向量,集合甚至是另一个图。
属性化(Attributed):边和顶点具有与之关联的属性。
全局属性:图级别的(graph-level)属性。
伪图:顶点之间可以有多个边,包括自连接的边。
图2显示了对应于我们可能对建模感兴趣的实际数据的各种不同类型的图,包括物理系统,分子,图像和文本。

3.1 背景

图神经网络家族中的模型(Gori等人,2005; Scarselli等人,2005,2009a; Li等人,2016)已经在各种问题领域中进行了探索,跨监督,半监督,无监督和强化学习等。它们对被认为具有丰富关系结构的任务非常有效,例如视觉场景理解任务(Raposo等,2017; Santoro等,2017)和few-shot learning(Garcia和Bruna,2018)。它们也被用来学习物理系统的变化(Battaglia等,2016; Chang等,2017; Watters等,2017; van Steenkiste等,2018; Sanchez-Gonzalez等,2018) )和多代理系统(Sukhbaatar等,2016; Hoshen,2017; Kipf等,2018),知识图谱的推理(Bordes等,2013; O〜noro-Rubio等,2017; Hamaguchi等,2017),预测分子的化学性质(Duvenaud等,2015; Gilmer等,2017),预测道路交通(Li et al。,2017; Cui et al。,2018) ),分类和分割图像和视频(Wang et al。,2018c; Hu et al。,2017)和3D网格和点云(Wang et al。,2018d),对图像中的区域进行分类(Chen et al。, 2018a),进行半监督文本分类(Kipf和Welling,2017),以及机器翻译(Vaswani等,2017; Shaw等,2018; Gulcehre等,2018)。它们已被用于无模型(Wang等,2018b)和基于模型的连续控制(Hamrick等,2017; Pascanu等,2017; Sanchez-Gonzalez等,2018),无模型强化学习(model-free reinforcement learning)(Hamrick等,2018; Zambaldi等,2018),以及更经典的规划方法(Toyer等,2017)等。

任何传统的计算机科学问题,包括关于离散实体和结构的推理,也已经用图神经网络进行了探索,例如组合优化(Bello等,2016; Nowak等,2017; Dai等,2017) ,布尔可满足性问题(Selsam等,2018),程序表示和验证(Allamanis等,2018; Li等,2016),元胞自动机和图灵机的建模(Johnson,2017),在图模型中进行推理 (Yoon等,2018)。 最近的工作还集中在构建图的生成模型(Li et al。,2018; De Cao and Kipf,2018; You et al。,2018; Bojchevski et al。,2018),以及图嵌入(graph embeddings)的无监督学习(Perozzi et al。,2014; Tang et al。,2015; Grover and Leskovec,2016;Garc'ıa-Durán和Niepert,2017)。

上述工作不是一个详细的列表,而是提供了图神经网络已被证明大有可为的领域宽度的一个侧面反应。我们将感兴趣的读者指向一些现有的评论,这些评论更深入地研究了图神经网络的工作主体。特别是,Scarselli等人 (2009a)提供了早期图神经网络方法的权威概述。布朗斯坦等人(2017)提供了关于非欧几里德数据(non-Euclidean data)的深度学习的优秀调查,并探索了图神经网络,图卷积网络和相关的频谱方法(谱分析)。最近,吉尔默等人 (2017)引入了消息传递神经网络(MPNN),通过类比图模型中的消息传递,它统一了各种图神经网络和图卷积网络方法(Monti等人,2017; Bruna等人,2014; Henaff等人,2015; Defferrard等人,2016; Niepert等,2016; Kipf和Welling,2017; Bronstein等,2017)。同样,Wang等人(2018c)引入了非局部神经网络(NLNN),它统一了各种“self-attention”方面的相关方法(Vaswani等,2017; Hoshen,2017; Veli ckovi'c et al。,2018),通过类比计算机视觉和图模型的方法,用于捕获信号中的长程依赖性。

3.2 图网络(GN)块

我们现在展示我们的图网络(Graph Networks, GN)框架,它定义了一组在图结构上的关系推理的函数。 我们的GN框架概括和扩展了各种图神经网络,MPNN和NLNN方法(Scarselli等,2009a; Gilmer等,2017; Wang等,2018c),并支持从简单的构建块构建复杂的体系结构。 注意,我们避免在“图形网络”标签中使用术语“神经”来反映它们可以用神经网络之外的函数来实现,尽管这里我们的重点是神经网络实现。

GN框架中的主要计算单元是GN块,即“图到图”模块,它将图作为输入,对结构执行计算,并返回图作为输出。 如Box 3所述,实体用图的节点表示,关系用边表示,系统的性质由全局属性来表示(system-level properties by global attributes)。 GN框架的块组织强调可定制性和合成新架构来表达所期望的关系归纳偏差。 关键设计原则是:灵活的表征(Flexible representations)(见4.1节); 可配置的块内结构(Configurable within-block structure)(见4.2节); 和可组合的多块架构(Composable multi-block architectures)(参见第4.3节)。

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

3.2.1 “图”的定义

在我们的GN框架内,图被定义为三元组$G=(u, V, E)$(有关图表示的详细信息,请参Box 3)。 $u$是全局属性; 例如,$u$可能表示引力场。 $V=\lbrace{v_i\rbrace}_{i=1:N^v}$是节点集合(基为$N_v$),其中每个$v_i$都是节点的属性。 例如,$V$可能代表每个球,具有位置,速度和质量的属性。 $E=\lbrace{(e_k, r_k, s_k)\rbrace}_{k=1:N^e}$是边的集合(基为$N_e$),其中每个$e_k$是边的属性,$r_k$是接收节点的索引,$s_k$是发送节点的索引。 例如,$E$可能表示不同球之间存在弹簧,以及它们相应的弹簧常数。

3.2.2 GN块的内部结构

一个GN模块包括三个更新函数$\phi$和三个聚合函数$\rho$:

其中, $E_i^{'}=\lbrace{(e_k^{'}, r_k, s_k)\rbrace}_{r_k=i, k=1:N^e}$,$V^{'}=\lbrace{v_i^{'}\rbrace}_{i=1:N^v}$,$E^{'}=\bigcup_i{E_i^{'}}=\lbrace{(e_k^{'}, r_k, s_k)\rbrace}_{k=1:N^e}$。

$\phi^e$映射到所有边来更新边,$\phi^v$映射到所有节点来更新节点,$\phi^u$用来进行全局更新。 每个$\rho$函数都将一个集合作为输入,并将其减少为表示聚合信息的单个元素。 至关重要的是,函数必须对输入的排列不变,使用可变数量的参数(例如,元素求和,平均值,最大值等)。

3.2.3 GN块的内部计算步骤


当图G作为GN块的输入时,计算从边缘,到节点,再到全局。 图3显示了每个计算中涉及哪些图元素的描述,图4a显示了带有更新和聚合函数的完整GN块。 Algorithm 1显示了以下计算步骤:

  1. $\phi^{e}$应用每一条边,其参数$(e_k,v_{rk},v_{sk},u)$,返回$e_k^{'}$,在我们的例子中,它可能对应于两个连接球之间的力或势能。 每个节点$i$的相应边的计算输出结果的集合是$E_i^{'}=\lbrace{(e_k^{'}, r_k, s_k)\rbrace}_{r_k=i, k=1:N^e}$,并且,$E^{'}=\bigcup_i{E_i^{'}}=\lbrace{(e_k^{'}, r_k, s_k)\rbrace}_{k=1:N^e}$是所有边输出的集合。
  2. $\rho^{e\rightarrow{v}}$作用于$E_i^{'}$ 将投影到顶点$i$的边更新聚合到\overline{e}_i^{'}中,为下一步节点更新使用。在我们的例子中,这就像对第$i$个球上所有的力或者势能进行求和。
  3. $\phi^v$作用于每个节点$i$,计算更新过的节点属性$v_i^{'}$,在我们的例子中,$\phi^v$计算每个球的(更新过的)位置,速度,动能。所有节点的输出集合是$V^{'}=\lbrace{v_i^{'}\rbrace}_{i=1:N^v}$。
  4. $\rho^{e\rightarrow{u}}$作用于$E^{'}$,聚合所有的边更新,给\overline{e}^{'},给下一步全局更新使用,在我们的例子中,$\rho^{e\rightarrow{u}}$可以计算合力(在这种情况下应该为零,由于牛顿第三定律)和弹簧的势能。 5.$\rho^{v\rightarrow{u}}$作用于$V^{'}$,聚合所有的节点更新,并在接下来全局更新使用,在我们的例子中,$\rho^{v\rightarrow{u}}$可用来计算系统的总动能。
  5. $\phi^u$每一个图应用一次,计算并更新全局属性$u^{'}$,在我们的例子中,$\phi^u$可能会计算类似于物理系统的净力和总能量的东西。

注意,虽然我们这里写的时候有步骤顺序,但是没有严格的执行顺序:例如,可以反转更新函数从全局,到每个节点,到每个边的更新。 比如Kearnes等(2016)以类似的方式计算来自节点的边更新。

3.2.4 图网络中的关系归纳偏差

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

其次,图表示实体和关系作为集合,集合排列不变,意味着GN对于这些元素顺序不变,这通常是可取的。 例如,场景中的对象没有自然顺序(参见2.2节)。

第三,GN的边、节点函数分别可在所有边和节点上重复使用。 这意味着GNs自动支持一种组合泛化形式(参见5.1节):因为图由边,节点和全局特征组成,所以单个GN可以在不同大小(边和节点数目不同)和形状(不同的边连接)上运行。

4. 图网络结构的设计原则

GN框架可用于实现各种体系结构,上面3.2节中已经有所涉及,这些原则也对应于下面的子部分(4.1,4.2和4.3)。 通常,框架对特定的属性表示和功能形式是不可预知的,在这里,我们聚焦于深度学习框架,其中GNs扮演可学习的图到图的逼近功能函数。

4.1 灵活的表征(Flexible representations)

图网络以两种方式支持高度灵活的图表示:第一,属性(Attributes)的表征; 第二,图网络本身的结构。

4.1.1 属性(Attributes)

4.1.2 图结构(Graph structure)

4.2 可配置的块内结构

4.2.1 消息传递神经网络(Message-passing neural network)

4.2.2 非局部神经网络(Non-local neural networks)

4.2.3 其他图网络变种(Other graph network variants)

4.3 可组合的多块架构

4.4 图网络代码实现

4.5 小结

5. 讨论

5.1 图网络中的组合泛化(Combinatorial generalization)

5.2 图网络的局限性

5.3 开放式问题

5.4 学习和结构的综合方法(Integrative approaches)

5.5 结论