Written by	title	date
zhengchu1994	《Relational inductive biases, deep learning, and graph networks》	2018-7-3 20:45:41

Intro

人类智能的标志是拥有“有限手段的无限利用”(infinite use of finite means)的能力，即有限的元素集合，有无限的组合方式。

反应了一个准则(principle)：组合泛化(combinatorial generalization)，即用已知的积木(building blocks)构建新的推理、预测和行动。

提高组合泛化能力：通过偏置(biasing)把学习方向对准到结构化表示和计算上。

深度学习中的“end-to-end”方法强调了最小先验表示和计算的假设。（”end-to-end” design philosophy which
emphasizes minimal a priori representational and computational assumptions），即表明了，用大量廉价数据和计算资源，用样本效率来换取更加灵活的学习方法。

现代人工智能的关键之路是将组合泛化作为首要任务，主张采取综合方法来实现这一目标。（深度学习+基于结构的方法：图数据）

这类方法都有一个共同的能力，即在离散实体和他们的关系上执行计算。

和传统方法的不同：研究如何学习实体和关系的表示和结构，以及相应的计算。

这些方法都带有很强的关系归纳偏置。（these methods carry strong relational inductive
biases, in the form of specific architectural assumptions, which guide these approaches towards
learning about entities and relations (Mitchell, 1980)）

Relational inductive biases

box1-Relational Reasoning

• structure:已知组件的组合物。
• Structured representation:一种方法，获取组件的组合方式。
• Structured computation:视组件和组合物为一体，在上面做计算。
• rules:函数，把实体和关系映射到其他实体和关系上，如 IS ENTITY X LARGE?
• Relational Reasoning:利用规则，在实体和关系的结构化表示上所做的操作。

box2-Inductive biases（关系归纳偏置）

• 学习过程涉及到寻找一个解空间中的解，这个解为数据提供更好的解释或获得更高的回报。

• 许多情况下，多个同样好的解决方案，归纳偏置（inductive bias） 让一个学习算法具有可以使某一个解决方案最优先被选择，这独立于观察到的数据。

• 在贝叶斯模型中，归纳偏差通常通过先验分布的选择和参数化来表示;在其他情况下，归纳偏差可能是避免过拟合的正则化;或归纳偏置被编码到算法本身的体系结构中。

• 归纳偏差通常以灵活性换取改进的样本复杂性

• 归纳偏差可以表达关于数据生成过程或解的空间的假设。比如，l2正则化是的参数值较小的解决方案被最优选择，进一步诱导出唯一的解和全局结构。这可以解释为一个关于学习过程的假设：当解决方案之间的歧义较少时，寻找好的解决方案更容易。

• 注：这些假设反映了模型或算法如何与世界交互的解释。

Relational inductive biases in standard deep learning building blocks

Computations over sets and graphs

现在的深度学习工具包含有各种形式的关系归纳偏置，但没有可在任意关系结构数据上进行操作的深度学习组件

需要有实体和关系的显式表示的模型，以及获取计算它们之间的相互作用的规则的学习算法。

世界上的实体（such as objects and agents）没有天然的顺序；相反，可以由实体之间关系的属性来定义顺序。
用深度学习组件进行关系推理应该具有的性质：对排序的不变性（Invariance to ordering）。即用深度学习得到规则，这种规则带有归纳偏置，即保持对序列的不变性
用集合表示无序实体组成的系统，集合内实体间的作用视为关系，实体和关系也可挂钩属性，这对应于图。
结论：图表示支持任意（成对）关系结构，在图上做计算比 CNNs和RNNs提供更强的关系归纳偏置。

Graph networks

Background

介绍了图神经网络在各个方向上被应用的论文，给出了一些综述文章。

3. Graph network (GN) block

图网络(Gn)框架，它定义了一类用于图结构表示上做关系推理的函数。

注：这些函数也可以用神经网络之外的技术实现，但本文关注神经网络。

Definition of “graph”

图定义为: G=(u,V,E)$G=(\mathbf{u},V,E)$,其中 u$\mathbf{u}$是全局属性，V$V$ 是点集，E={(ek,rk,sk)}k=1:Ne$E=\{(e_k,r_k,s_k){\}}_{k=1:N^e}$ 是边集,ek$e_k$ 是边的属性，rk$r_k$ 是终点(receiver node),sk$s_k$ 是起点(sender node).

Internal structure of a GN block

一个 GN块 含有三个更新函数：ϕ$\varphi$ ，三个聚集函数： p$p$ ，如下：

• 其中，ϕe${\varphi }^e$ 是对所有边计算更新，ϕv${\varphi }^v$ 是对所有节点做更新，ϕu${\varphi }^u$是最后对全局状态的更新。
• p$p$ 则是输入一个集合（点或边的属性），输出归纳为单个聚集信息元素。
• p$p$ 函数必须对其输入的序列有不变性，并且应该采用可变的参数。

Computational steps within a GN block

更新过程：

1. 第一个for循环对每条边属性做更新得到e′k$e_k^{{}^{\prime }}$：进而得到每个节点(以这个节点作为终点的所有边)的集合 E′i={(e′k,rk,sk)}rk=i,k=1:Ne$E_i^{{}^{\prime }}=\{(e_k^{{}^{\prime }},r_k,s_k){\}}_{r_k=i,k=1:N^e}$；

2. 第二个for循环对每个节点(最为终点)的边属性应用聚集函数，得到这个节点上的聚集信息 e¯′${\overline{e}}^{{}^{\prime }}$ ，然后据此更新每个节点的属性信息；

3. 得到新的点和边集，计算全部的边属性信息和点属性信息，更新全图的属性状态得到u′$u^{{}^{\prime }}$，返回新的图。
   如图：
   

注：更新过程可调换，如先2后1，也可以反向3、2、1进行。

Relational inductive biases in graph networks

GN框架在作为学习过程中的组件时施加了几个强烈的关系归纳偏差：

1. 图可以表示实体间的任意关系，意味着GN的输入决定了表示(representations)是如何相互作用和相互孤立的。

2. 图表示把实体及其关系作为集合，因此对目标的组成元素顺序具有不变性(比如图片有很多部分组成，这些组成打乱之后(被卷积)还是能识别这张图片)。

3. GN的边函数和节点函数分别在所有边和节点上重用，这意味着GN天然支持组合泛化的一种形式。

4. Design principles for graph network architectures

主要关注于深度学习架构，它允许GN成为可学习的图对图函数逼近器。

Flexible representations

灵活的图表示：第一，属性的表示方面；第二，图的结构方面

Attributes

• GN框架中属性的表示形式可以任意的，如在深度学习实现中，实值向量和张量是最常见的。
• 问题的需求通常决定属性应该使用什么表示。例如，输入数据是图像，属性可以表示为图像块的张量；当输入数据是文本文档时，属性可能是对应于句子的单词序列。
• GN块的输出也可以根据任务的要求而定制:edge-focused GN输出边信息、node-focused GN输出点信息、graph-focused GN输出图的全局信息。

注：节点、边和图全局输出也可以根据任务进行混合和匹配。

Graph structure

当定义输入数据将如何表示为一个图形时，通常有两种情况：

1. 输入明确指出了关系结构

   • 例子：知识图，社会网络，解析树，优化问题，化学图，道路网络，和已知相互作用的物理系统等。

1. 关系结构需要被推理或假设(inferred or assumed)

这种情况下,对实体做出假设，比如文本里的单词，局部特征向量视为节点，还可以使用单独的学习机制从非结构化信息中推断实体。

• 例子：可视化场景、文本语料库、编程语言源代码和多智能体系统等。

注：指出从非结构化数据推断稀疏结构( sparse structure) 是未来的一个重要方向。

Configurable within-block structure

Message-passing neural network (MPNN)

Non-local neural networks (NLNN)

Other graph network variants

Composable multi-block architectures

1. GNs块之间可以共享参数(如RNNs),也可以块与块之间参数独立（如CNNs中的每一层）。
2. GNs的输入是图，输出是图，继续可以作为新的GNs输入。
   三种结构：

(a) 任意数目的GN块可以组成被叠加，表示为 GNcore$G{N}_{\text{c}ore}$ 。
(b) 输入图  Ginp$G_{inp}$ 由编码器 GNenc$G{N}_{enc}$编码 得到 G0$G_0$，再由中间训练M次得到 GM$G_M$，在最后解码得到 Gout$G_{out}$
(c) 加入了时间序列的(b).

Implementing graph networks in code

更新边函数和点函数被所有的边和点共有，因此可并行计算；一系列独立子图也可视为一整个大图上的非连通子图作为批量输入进行计算。

Summary

图网络背后的设计原则：灵活的表示、可配置的块内结构和可组合的多块体系结构。

5. Discussion

结论1：CNNs and RNNs 包含关系归纳偏置(
relational inductive biases), 但它们不能处理更结构化的表示(more structured representations),如集合还有图(sets or graphs).

结论2：提倡使用 图网络(graph network) 把更强的关系归纳偏置加入到深度学习中， 图网络(graph network) 在图结构数据上进行计算。

Combinatorial generalization in graph networks

举了各个方向的文章作为例子，为以下观点提供了重要的支持：在现代人工智能中，采用显式结构和灵活学习(explicit structure and flexible learning)是更好的实现采样效率和泛化(sample efficiency and generalization)的可行方法。

[embracing explicit structure and flexible learning is a viable approach toward realizing better sample efficiency and generalization in modern AI]

Limitations of graph networks

递归、控制流和条件迭代这样的概念并不容易用图来表示，而且至少需要附加的假设(例如，在解释抽象语法树时)。

Open questions

如何将感官数据 (raw sensory data, such as images and text) 转换成更结构化的表示方式，比如图结构。

如何在计算过程中自适应地修改图形结构。如，表示一个对象的节点因这个节点的分解而分解成多个节点，边自适应的连接或者删除。

如何得到图网络行为的可解释性。

Integrative approaches for learning and structure

其他类型的结构化表示和计算方法。

Conclusion

主张将组合泛化作为人工智能的首要任务，并倡导采用综合方法，借鉴人类认知、传统计算机科学、标准工程实践和现代深度学习的思想。

图网络(graph network)使用可定制的图到图构建块来构建复杂的体系结构，它们的关系归纳偏差比其他标准机器学习构建块更能促进组合泛化和提高样本效率。