摘要:人工智能Artificial intelligence: AI
最近经历了一场复兴,并在视觉、语言、控制、决策等关键领域取得了重大进展。取得这些进展的部分原因是由于廉价的数据、廉价的计算资源,这符合深度学习的天然优势。然而,在不同压力下发展起来的人类智力,其许多决定性特点对于目前的人工智能方法而言仍然是触不可及的。具体而言,超越经验的泛化能力--人类智力从幼年开始发展的标志--仍然是现代人工智能面临的巨大挑战。
论文 《Relational inductive biases, deep learning, and graph networks》
认为:组合泛化combinatorial generalization
是AI
实现人类相似能力的首要任务,而结构化表示和计算structured representations and computations
是实现该目标的关键。正如生物学把先天 nature
和后天 nurture
相结合,论文摒弃手动设计特征 hand-engineering
、端到端学习 end-to-end learning
之间进行二选一选择的错误做法,而是提倡一种利用它们进行优势互补的做法。
论文探索深度学习框架中使用关系归纳偏置 relational inductive biases
如何促进对实体 entity
、关系 relation
、以及构成它们的规则 rule
的了解。论文为AI toolkit
提供了一个新的、具有强大关系归纳偏置的构建块 building block
:Graph Network
。Graph Network
概括和扩展了图上运行的各种神经网络方法,并为操作结构化知识 manipulating structured knowledge
和产生结构化行为 producing structured behaviors
提供了直接接口。
论文讨论Graph Network
如何支持关系推理 relational reasoning
、组合泛化combinatorial generalization
。这为更复杂、更可解释、更可扩展的推理模式 reasoning pattern
奠定了基础。
作为论文的补充,作者还发布了一个用于构建 Graph Network
的开源软件库,并演示了如何在实际工作中应用它们。
引言:人类智能的一个重要标志是 “无限使用有限方法” (infinite use of finite means
) 的能力,其中一小部分的、有限的原始(如单词 word
)可以无限地组合(如构成无限多的句子 sentence
)。这反映了组合泛化combinatorial generalization
的原理,即从已知的构建块 building block
来创建新的推论 inference
、预测 prediction
、行为 behavior
。这里我们探索如何通过将偏置学习 biasing learning
用于结构化的表示和计算 structured representations and computations
从而提高现代 AI
的组合泛化能力,尤其是对图 graph
进行操作的系统。
人类的组合泛化能力很大程度上取决于我们表达结构representing structure
和推理关系 reasoning about relations
的认知机制。
entity
及其相互作用 interaction
的组合。fine-grained
的差异,并捕获representations
和 behaviors
之间的更一般的共性,比如:同一个物体的一部分、同一个场景的物体、同一个城镇的社区。skills
和惯例 routines
来解决新的问题。Kenneth Craik
的 The Nature of Explanation
将世界的组成结构 compositional structure of the world
和我们内在的心理模型 internal mental model
的组织方式联系起来,即:世界是组合的 compositional
,或者至少我们是从组合的角度来理解它的。当我们学习的时候,我们要么将新知识放入现有的结构化表示 structured representations
中、要么调整结构本身从而更好地适应(和使用)新旧知识。
自 AI
诞生以来,如何构建具有组合泛化的人工智能系统一直就是 AI
的核心问题,它是很多结构化方法 structured approach
的核心,包括:逻辑 logic
、语法 grammar
、经典规划 classic planning
、图模型 graphical model
、因果推理causal reasoning
、贝叶斯非参数化 Bayesian nonparametric
以及概率规划 probabilistic programming
。
所有子领域都集中于显式的以实体 entity
和关系 relation
为中心的学习上,例如关系强化学习relational reinforcement learning
、统计关系学习 statistical relational learning
。结构化方法对于之前的机器学习如此重要的一个关键原因,部分是因为数据和计算资源的昂贵,而结构化方法强大的归纳偏置 inductive biases
所带来的样本复杂度 sample complexity
的改善是非常有价值的。
与过去的人工智能方法相比,现代深度学习经常遵循 “端到端”(end-to-end
) 的设计理念,强调最小限度的先验表征的、计算的假设 minimal a priori representational and computational assumptions
,并力求避免使用显式的结构 explicit structure
和特征工程hand-engineering
。这种强调 emphasis
和当前的大量廉价数据和廉价计算资源非常契合,也得到了充分的验证。这使得牺牲样本效率 sample efficiency
从而更灵活地学习成为一种理性的选择。从图像分类到自然语言处理,深度学习在很多具有挑战性的领域中取得了令人瞩目的快速发展,这证明了这种极简主义原则 minimalist principle
的成功。一个突出的例子是语言翻译,事实证明sequence-to-sequence
方法非常有效,无需使用显式的解析树 parse tree
或者语言实体 linguistic entity
之间的复杂关系。
尽管深度学习取得了巨大成功,但是也有一些严厉的批评:深度学习在复杂的语言和场景理解complex language and scene understanding
、结构化数据的推理reasoning about structured data
、训练条件之外的迁移学习 transferring learning beyond the training condition
以及少量经验中学习learning from small amounts of experience
时面临重大挑战。这些挑战需要组合泛化,因此摒弃组合性 compositionality
以及显式结构 explicit structure
的方法难以满足这些挑战,这并不奇怪。
当深度学习的前辈连接主义 connectionist
面临诸如结构性的structured
、符号性的 symbolic
立场 position
等类似批评时,有些工作直接地、细致地做出了建设性的努力来解决这些挑战。在诸如模拟制造 analogy-making
、语言分析 linguistic analysis
、符号操作 symbol manipulation
以及其它形式的关系推理之类的领域中,符号主义开发了用于表示和推理结构化对象的各种创新的亚符号 sub-symbolic
方法,以及有关大脑如何工作的更多综合理论 integrative theory
。这些工作还有助于培养更多的深度学习进展advances
,这些进展使用分布式向量表示来捕获文本text
、图 graph
、代数表达式 algebraic expression
、逻辑表达式 logical expression
、以及程序programs
中的丰富语义内容。
我们认为,现代 AI
的关键途径是致力于将组合泛化作为首要任务,并且我们主张采用综合方法 integrative approache
来实现这一目标。正如生物学没有在先天 nature
和后天 nurture
之间进行选择一样(生物学同时利用先天和后天,这种整体效果强于每个部分之和),我们也拒绝这样的观念(即,结构 struture
和灵活性 flexibility
在某种程度上是矛盾的或不相容的),并且我们同时拥抱结构和灵活性从而获得它们的互补优势。根据大量最新的一些混合了 structure-based
方法、deep learning
方法的案例,我们发现:将当今最好的方法(即 deeplearning
方法)和早期算力昂贵时必不可少的方法(即结构化方法)相结合的综合技术具有广阔的前景。
近年来,在深度学习和结构化方法的交集中出现了一类模型,这些模型聚焦于推理有关显式结构化数据(特别是图 graph
)的方法。这些方法的共同点是可以对离散实体 entity
以及实体之间的关系 relation
进行计算。这些方法和经典方法不同之处在于:如何学习实体和关系的representation
以及structure
,以及相应的计算,从而缓解了事先需要指定它们的负担。即,这些知识是通过学习而来,而不是预先指定的。至关重要的是,这些方法以特定的体系架构假设的形式引入强烈的关系归纳偏置 relational inductive biases
,这些偏置指导这些方法学习实体和关系。我们和很多其他人一起认为,这是类似人类智力的基本组成部分。
在文章的剩余部分,我们通过关系归纳偏置的角度考察了各种深度学习方法,表明现有方法通常带有关系假设relational assumptions
,这些假设并不总是很明显或者显而易见。然后我们提出了一个基于实体和关系推理的通用框架,我们称之为 Graph Network:GN
。GN
统一和扩展了图上运行的现有方法,并描述了使用 Graph Network
作为构建块 building block
来构建强大架构的关键设计原理。我们还发布了一个用于构建 Graph Network
的开源库。
定义结构 structure
为通过一组已知构建块 building block
组成的产品 product
。结构化表示 Structured representations
捕获了这种组成composition
,如元素element
的排列arrangement
。结构化计算 structured computations
以一个整体的方式对所有这些元素及其组合进行操作。关系推理 Relational Reasoning
涉及利用实体entity
和关系relation
的组成规则 composed rule
,从而操作实体和关系的结构化表示。我们用以下数据来描述认知科学、理论计算机科学、人工智能的相关概念:
实体 entity
:具有属性的元素,如具有大小、质量的物理对象。
关系 relation
:实体之间的属性。如两个对象之间的关系可能包括:相同大小 same size as
、比.. 更重 heavier than
、距离distance from
。
more than X times heavier than
带有一个属性 X
,它决定了这个关系取值为 true/false
的阈值。falls with greater accelaration than
取决于环境是在空气中还是真空中。这里我们关注实体之间的成对关系 pairwise relations
。
规则 rule
:将实体和关系映射到其它实体和关系的函数,就像一个非二元的逻辑谓词 non-binary logical predicate
。例如 is entity X large?
、 is entity X heavier than entity y?
这样的尺度比较scale comparison
。
这里我们仅考虑带有一个参数或两个参数、并返回一个属性的规则。
我们以图模型 graphical model
来作为机器学习中关系推理的示例性说明。
图模型可以通过在随机变量之间指定显式的条件独立性来建模复杂的联合分布。这样的模型非常成功,因为它捕获了稀疏结构 sparse structure
,而稀疏结构是很多现实世界生成过程generative processes
的基础,并且它们支持有效的学习和推理算法。
例如,隐马尔可夫模型可以显式指定条件独立性:
这和很多现实世界因果过程 causal process
的关系结构非常契合。
明确表达变量之间的稀疏依赖关系提供了各种高效的推断 inference
和推理 reasoning
算法。例如,消息传递算法在图模型内的各个位置之间采用通用的消息传播过程,从而导致一个可组合的composable
、部分并行化的 partially parallelizable
推理过程reasoning procedure
,这适用于不同大小和形状的图模型。
学习是通过观察世界并与世界互动来理解有用知识的过程,它涉及搜索解空间 space of solutions
以期找到可以更好地解释数据、或获得更高回报的解决方案 solution
。但是在很多情况下,有多种解决方案同样出色。归纳偏置 inductive bias
允许学习算法独立于观测到的数据,从而将一种解决方案(或者解释)优先于另一种解决方案(或解释)。
在贝叶斯模型中,归纳偏置通常以先验分布的选择choice
、参数化 parameterization
来表示。而在其它模型中,归纳偏置可能是为避免过拟合而添加的正则化项,也可能被编码到算法本身的体系结构中。
归纳偏置通常以灵活性 flexibility
为代价从而换取改善的样本复杂性 sample complexity
,并且可以从偏差-方差平衡 bias-variance tradeoff
的角度来理解。理想情况下,归纳偏置既可以在不显著降低性能的情况下改善对于解空间的搜索,又可以帮助找到理想泛化的解决方案。但是,不匹配mismatched
的归纳偏置也会引入过强的约束从而导致欠拟合。
归纳偏置可以表达关于数据生成过程 data-generating process
或解空间的假设。例如,当使用一维函数拟合数据时,线性最小二乘法遵循近似函数为线性模型的约束,并且在 additive Gaussian noise
破坏的线性过程 line process
。
类似地,ill-posed problem
可以得到唯一的解决方案和全局结果。这可以解释为关于学习过程的一种假设:当解决方案之间的分歧较少时,寻找好的解决方案更加容易。
注意,这些假设不需要明确地解释模型或算法如何与世界交互。
机器学习和 AI
中很多具有关系推理能力的方法使用关系归纳偏置 relational inductive bias
。虽然不是精确的正式定义,但是我们通常使用该术语来指归纳偏置 inductive bias
,它对于学习过程中实体之间的关系和交互施加了约束。
近年来新型的机器学习体系架构迅速增加,从业人员经常遵循通过组合基本构建块 elementary building block
来形成更复杂、更深计算的层次hierarchies
和计算图。
例如:
full connected layer
被堆叠到多层感知机 multilayer perceptrons: MLPs
中。convolutional layers
被堆叠到卷积神经网络 convolutional neural networks: CNNs
中。CNN
变体 + MLP
的组合。这种 layer
的组合提供了一种特殊类型的关系归纳偏置:层次处理 hierarchical processing
的关系归纳偏置。其中计算分阶段 in stages
进行,这会导致输入信号中的信息之间产生越来越长距离的交互 long range interaction
。
正如我们在下面探讨的那样,构建块本身也带有各种关系归纳偏置(如下表所述)。尽管超出了本文的范围,但是在深度学习中也使用各种非关系归纳偏置 non-relational inductive biases
,例如:激活值的非线性 non-linearity
、权重衰减、dropout
、batch normalization/layer normalization
、data augmentation
、训练方式、优化算法都对学习的轨迹和结果施加了约束。
要探索各种深度学习方法中表达的关系归纳偏置,我们必须确定几个关键因素:实体是什么、关系是什么、组成实体和关系的规则是什么、计算实体和关系的规则是什么。在深度学习中,实体和关系通常表示为分布式表示 distributed representation
,规则通常表示为神经网络函数逼近器 approximator
。然后,实体、关系、规则的精确形式在不同体系架构之间有所不同。为了理解架构之间的这些差异,我们通过以下探索进一步理解每种架构如何支持关系推理:
rule function
的自变量 argument
,例如:哪些实体和关系作为输入。step
。representation
之间的交互 interaction
与隔离 isolation
。例如:通过在相关的实体上应用规则来得出结论,而不是对每个实体独立处理。Fully Connected Layers
全连接层:也许最常见的构建块是全连接层。
通常全连接层被实现为输入向量的非线性函数:
其中
因此实体是网络中的单元,关系是 all-to-all
:
因此,在全连接层中的隐式关系归纳偏置非常弱week
:所有输入单元之间可以交互从而决定任何输出单元的值,并且所有输出单元之间相互独立。
Convolutional Layers
卷积层:另一个常见的构建块是卷积层。
卷积层通常被实现为输入向量或张量的卷积:
其中
这里的实体仍然是单个单元(或者网格元素,如像素),但是实体之间的关系更为稀疏。全连接层和卷积层之间的差异在于卷积层增加了一些重要的关系归纳偏置:局部性 locality
和平移不变性 translation invariance
。
relational rule
的自变量是那些在输入信号的坐标空间中紧密相邻的实体、并且和远处实体隔离。这些偏置对于处理天然的图像数据非常有效,因为图像数据局部邻域内存在较高的协方差,且随着距离增加,协方差会减小。并且统计量在整个图上大多是平稳的stationary
。
Recurrent Layers
递归层:第三种常用的构建块是递归层,它是通过一系列 step
来实现的。这里我们将每个 step
的输入和 hidden state
视为实体,将马尔可夫过程视为关系:当前 hidden state
依赖于前一个 hidden state
和当前 input
。实体组合的规则将当前 step
的输入、前一个 hidden state
作为规则的自变量,然后更新当前 hidden state
。
这个规则在每个 step
被复用,这反映了时间不变性(类似于 CNN
在空间上的平移不变性)的关系归纳偏置。例如,某些物理事件序列的结果不应该取决于一天中的某个时刻。
RNN
也通过其马尔可夫结构对序列带来局部性 locality
的 bias
。
下图给出了常见的深度学习构建块中的复用和共享,共享的权重由具有相同颜色的箭头表示。
(a)
:全连接层,其中所有权重都是独立的,并且没有共享。(b)
:卷积层,其中局部核函数在输入中多次重复使用。(c)
:循环层,其中相同的函数可以在不同的 step
中复用(水平方向代表了时间线)。虽然标准的深度学习工具包所包含的方法具有各种形式的关系归纳偏置,但是没有默认的深度学习组件可以在任意关系结构上运行。我们需要模型具有显式的实体表示和关系表示,并需要学习算法,该算法用于找到计算实体和关系交互的规则、以及将规则置于数据中的方式。
重要的是,世界上的实体(如对象、agent
)没有自然顺序。相反,可以通过关系的性质来定义顺序。如:可以根据对象之间的大小、质量、年龄、毒性、价格之间的关系来对它们进行排序。顺序不变性invariance to ordering
(除了处理关系时)是一种理想的属性,这种不变性应该由用于关系推理的深度学习组件来反映。
集合 sets
是描述包含一组无序实体的系统的自然表达形式。具体而言,集合的关系归纳偏置并不是来自于 something
的存在,而是来自于 something
的缺失。
为了说明,考虑由
但是,如果要使用 MLP
来预测该任务,即使已经知道了特定顺序输入 MLP
可能会认为每种顺序从根本上看是不同的,因此需要指数级的输入/输出训练样本来学习近似函数。
处理类似组合爆炸的自然方法是允许预测依赖于输入的对称函数。这可能意味着首先计算 per-object
参数共享的特征 Deep Sets
以及相关模型的本质。我们在后文进一步讨论。
当然,在很多问题中排列不变性 permutation invariance
并不是底层结构的唯一重要形式。例如,一个集合中的每个对象都可能受到集合中其它对象的 pairwise interaction
的影响。在我们的行星case
中,考虑在时间间隔
取而代之的是,我们可以将每个对象的状态计算为
我们在各处都使用相同的 global permutation invariance
。但是,它也支持不同的关系结构,因为
上述太阳系的例子说明了两种关系结构 relation structure
:一种完全没有关系,一种包含所有的 pairwise
关系。很多现实世界的系统(如下图所示)的关系结构在这两种极端 case
之间:某些实体 pair
对之间存在关系、另一些实体 pair
对之间缺乏关系。
在我们的太阳系例子中,如果该系统改为由行星及其卫星组成,则可能会试图通过忽略不同行星的卫星之间的相互作用来近似。实际上,这意味着仅计算某些对象之间的交互,即:
其中 graph
,因为第
注意:节点
下图为现实世界的不同系统,以及对应的graph
的表达:
(a)
:一个分子图,其中每个原子表示为一个节点,边对应于化学键。(b)
:一个质点弹簧系统,其中绳索由一个质点序列定义,这些质点在图中表示为节点。(c)
:一个 n body
系统,其中每个 body
为节点,节点之间全连接。(d)
:一个刚体系统,其中球和墙壁都为节点,底层的 graph
定义了球之间、球和墙壁之间的相互作用。(e)
:一个句子,其中单词对应于解析树上的叶结点,其它节点和边可以由解析器提供。或者也可以使用一个全连接的图。(f)
:一张图片,可以将其分解为图像块patch
,每个块代表一个节点,并且节点之间全连接。通常,图 graph
是支持任意 pairwise
关系结构的表示形式,并且图上的计算提供了超越卷积层、递归层的强大的关系归纳偏置。
图神经网络已经在监督学习、半监督学习、无监督学习、强化学习领域被应用。
visual scene understanding
任务、few-shot learning
任务等。physical system
和多智体系统 multi-agent system
,从而推理知识图谱、预测分子化学性质、预测道路交通流量、分类和分割图像/视频/3D
网格/点云、分类图像中的区域、执行半监督文本分类及机器翻译。model-free
和 model-based
连续控制中都被使用,用于 model-free
的强化学习,以及更经典的规划问题。satisfiability
、程序表示和验证、元胞自动机及图灵机建模,以及图模型上的 inference
。最近的工作还关注于图的生成模型、graph embedding
的无监督学习。这里介绍我们的图网络框架 Graph Networks:GN
,该框架定义了一族函数用于图结构表示graph-structured representations
的关系推理relational reasoning
。我们的 GN
框架概括并扩展了各种图神经网络、MPNN
、以及 NLNN
方法,并支持从简单的构建块构建复杂的体系架构。
注意,我们避免在 Graph Network
中使用术语 neural
来反映GN
可以使用除神经网络以外的函数来实现,尽管这里我们的重点是神经网络的实现。
GN
框架中的主要计算单元是 GN
块 GN block
。GN
块是一个 graph-to-graph
的模块,它将图作为输入,对结构进行计算,然后将图作为输出返回。图的节点表示实体,图的边表示关系,图的全局属性表示 system-level
属性。
GN
框架的 block
组织强调可定制性customizability
,以及综合了新的架构,这个新架构能够表达预期的关系归纳偏置。GN
框架的主要设计原则是:灵活的表示形式 flexible representations
、可配置的块内结构 configurable within-block structure
、可组合的多块体系架构 composable multi-block architectures
。我们引入一个例子来更具体的说明 GN
。可以在任意重力场中预测一组橡胶球的运动,这些橡胶球不会彼此弹跳,而是每个橡胶球都有一个或多个弹簧,这些弹簧将它们和其它橡胶球相连。我们将在下文中参考这个例子,从而启发 motivate
图的表示以及图上进行的计算。
这里我们使用图来表示带全局属性的、有向的、带属性的多图 multi-graph
。
graph-level
属性 sender
节点 receiver
节点 multi-graph
:节点之间可能存在多条边,包括自连接 self-edge
。在我们的 GN
框架内,图被定义为三元组
receiver
节点, sender
节点。例如:一个 GN
块包含三个更新函数
其中:
其物理意义为:
sender
节点属性 receiver
节点属性 receiver
为当前节点的所有边的属性(更新后的边属性)聚合后的 permutation invariant
,并且应该采用可变数量的自变量。一些典型的例子包括:逐元素求和、均值池化、最大值池化等。GN
块的计算步骤:
通过执行
receiver
。执行
通过执行
更新后,所有节点的属性集合为
通过执行
通过执行
通过执行
尽管这里我们给出了计算步骤的顺序,但是并不是严格地根据这个顺序来执行。例如,可以先更新全局属性、再更新节点属性、最后更新边属性。
GN block
更新函数 GraphNETWORK()
:
输入:图
输出:更新后的图
计算步骤:
迭代更新边的属性:
迭代更新节点的属性:
receiver
为当前节点 令
令
根据全局属性、聚合后的节点属性、聚合后的边属性来更新全局属性
返回更新后的图
给定一个图 GN
块的输入时,计算过程从边、节点、global-level
。下图给出了这些计算中,每一个计算都涉及哪些图元素。蓝色表示待更新的元素,黑色表示更新中涉及的其它元素(注意,蓝色元素更新之前的值也用于它的本次更新)。
下图给出了具有更新函数、聚合函数的完整 GN
块。它根据输入的节点属性、边属性、全局属性来预测输出的节点属性、边属性、全局属性。
当用于 learning process
的组成部分时,我们的 GN
框架会强制添加几个很强的关系归纳偏置:
首先,图可以表达实体之间的任意关系。这意味着 GN
的输入决定了 representation
是如何交互 interact
和隔离 isolated
的,而不是由固定 fixed
的体系架构来决定的。
即实体的交互和隔离是由数据决定,而不是由模型决定。
例如:
其次,图将实体及其关系表示为集合,这是排列不变的 permutation invariant
。这意味着 GN
对于这些元素的顺序是不敏感的,这通常是我们所需要的。
最后,GN
的 per-edge
函数、per-node
函数分别在所有边、所有节点之间重用。这意味着 GN
自动支持某种形式的组合泛化:由于图由边、节点、以及全局属性组成,因此单个 GN
可以在不同大小(以边和节点数量刻画)、不同形状(不同的连通性)的图上进行操作。
根据前述列出的设计原则,GN
框架可用于实现各种各样的体系架构。通常,GN
框架和特定的属性表示 attribute representation
和函数形式 functional form
无关。但是这里我们重点关注深度学习架构,该架构允许 GN
充当可学习的 graph-to-graph
的函数逼近器 function approximator
。
这里再回顾一下 GN
设计原则:灵活的表示 flexible representations
、可配置的块内结构 congurable within-block structure
、可组合的多块体系架构 composable multi-block architectures
。
这三个设计原则再我们的 GN
框架中结合在一起,非常灵活,适用于从感知、语言、到符号推理的广泛领域。并且,如前所述,GN
具有的强大的关系归纳偏置支持组合泛化,因此使得 GN
在实际和理论上都成为强大的工具。
灵活的表示有两层含义:
GN
块的全局属性、节点属性、边属性可以为任意表示形式 arbitrary representational formats
。属性形式:GN
块的全局属性、节点属性、边属性可以使用任意表示形式。在深度学习实现中,通常使用实值向量或张量。但是,也可以使用其它数据结构,如序列sequence
、集合set
、甚至是图 graph
。
通常我们需要决定:对某个问题采用何种表示形式来描述属性。例如:
patches
的张量。对于更广泛的体系架构中的每个 GN
块,每个边/节点的输出通常对应于一个张量/向量,而全局输出对应于单个张量/向量。这使得 GN
块的输出可以传递到其它深度学习构建块 building block
中,如 MLP,CNN,RNN
。GN
块的输出也可以根据任务需求进行定制化。具体而言:
edge-focused GN
可以仅仅将边作为输出。例如,做出有关实体之间相互作用的决策。node-focused GN
可以仅仅将节点作为输出。例如,用于推理物理系统。graph-focused GN
可以仅仅将全局属性作为输出。例如,预测物理系统的势能、分子性质、关于某个视觉场景问题的答案。节点属性、边属性、全局属性的输出也可以根据任务混合使用。
图结构形式:在定义如何将输入数据表示为图结构时,有两种情形:
首先,输入数据明确指定了关系结构。例如:知识图谱、社交网络、化学分子图、交通网络、以及具有已知交互作用的物理系统。
其次,需要从输入数据中推断或假设关系结构,即关系结构没有明确指定。例如视觉场景、文本文档等。
这里可以将数据表示为一组没有关系的实体,甚至仅表示为向量或张量(如:图像)。
如果未明确指定实体,则可以通过将诸如句子中的每个单词、或者 CNN
输出 feature map
中的 feature vector
视为节点来指定实体。
或者,也可以使用单独的学习机制从非结构化信号中推断实体,如通过解析树算法从文本中得到解析树。
如果关系不可用,则最简单的方法是在实体之间添加所有可能的有向边。如在图像的 patches
之间两两添加有向边。但是,这对于拥有大量实体的图而言是不可行的,因为边的数量会随着节点数量的增加而平方规模的增加。
因此,研发更复杂的方法来从非结构化数据中推断稀疏的图结构是未来的重要方向。
GN
块中的结构和函数可以通过不同的方式进行配置,从而可以灵活地确定哪些信息可以用作函数的输入,以及如何更新边属性、节点属性、全局属性。具体而言,GN
块中的每个 argument signature
决定了它需要哪些信息作为输入。
通过选择不同的函数 GN
框架可以表达其它各种架构,如下图所示。接下来讨论如何使用不同的方式配置 GN
的块内结构。
下图中,每个 incoming
箭头表示是否将
(a)
:full GN
(即完整的、原始的 GN
块)根据传入的节点属性、边属性、全局属性来输出节点属性、边属性、全局属性。(b)
:独立的循环块使用 input
和 hidden state
来进行更新,其中 RNN
。(c)
:MPNN
根据传入的节点属性、边属性来输出节点属性、边属性、全局属性。注意,全局预测中不包含聚合的边,输入中不包含全局属性。(d)
:NLNN
仅输出节点属性。(e)
:Relation Network
仅使用预测的边属性来输出全局属性。(f)
:Deep Set
没有采用边更新从而输出全局属性。
Full GN block
:《Relational inductive bias for physical construction in humans and machines》
和 《Graph networks as learnable physics engines for inference and control》
使用完整的 GN
块,如上图的 (a)
所示。
更新方程为:
其中:
MLP
作为 feature map
),通常采用 CNN
作为 RNN
,这需要额外的 hidden state
作为输入和输出。上图 (b)
展示了一个非常简单的 GN
块,其中 RNN
作为 block
可用于对某些 dynamic graph state
进行递归平滑 recurrent smoothing
。
当然,RNN
作为 full GN block
中使用。
Message-passing neural network: MPNN
概括了很多之前的体系架构,并且可以很自然地转换为 GN
的格式:
GN
中的 GN
的 GN
中的 readout
函数 GN
中的 GN
的 GN
中的 GN
的 上图 (c)
展示了如何根据 GN
块来构建 MPNN
。
Non-local Neural Networks:NLNN
统一了各种 intra/self/vertex/graph attention
方法,它也可以转换为 GN
的格式。
attention
指的是节点的更新方式:每个节点更新均基于其邻域节点属性(或者它的某些函数)的加权和,其中一个节点和它某个邻居之间的权重由属性之间的 scale pairwise
函数(然后整个邻域归一化)给出。
已发表的 NLNN
公式并未显式包含边,而是计算所有节点之间的 pairwise
注意力权重。但是,各种 NLNN-compliant
模型,例如节点注意力交互网络 vertex attention interaction network
、图注意力网络 graph attention network
都可以通过有效地将没有边的节点之间的权重设为零来显式处理边。
在 NLNN
中, pairwise-interaction
函数,该函数返回:
attention
系数,记作 non-pairwise
的向量值,记作 在 receiver
的所有边上归一化,然后
在 NLNN
论文中,set
(而不是图graph
)、并且这个图是根据集合中所有实体之间添加所有可能的边来构建的。
Transformer
体系架构中的 single-headed self-attention
,即 SA
, 实现为公式为:
其中
《Attention is all you need》
的 multi-head self-attention
机制增加了一个有趣的特性: Gated Graph Sequence Neural Networks
。
具体而言,multi-head self-attention
计算
Vertex Attention Interaction Networks
和 SA
很相似,但是它将欧几里得距离用于 attention
相似性度量,并在 attention
输入的 embedding
中共享参数,且在节点更新函数中使用节点的输入特征:
Graph Attention Networks
和 multi-head self-attention
相似,但是它使用神经网络作为 attention
相似性度量,并在 attention
输入的 embedding
中共享参数: