后几篇综述的切入点是，现实中存在许多图结构数据，传统DL方法无法处理这些数据，于是专门针对这些数据产生了图网络。而这篇综述直接上升到让人工智能接近人类智能的核心问题，即推理/组合泛化问题，需要结构化表示来解决，而图网络可以做到这一点。
推理到底是什么呢？
Combinatorial Generalization
人类智能的关键之一是组合泛化能力：“有限方法的无限使用”，一个小的元素集可以无限组合。从已知的模块构建新的推论、预测和行为，如单词->新句子。（用那几个固定的元素合成非常多样的化学分子，用性质一样的n个小球组成n体系统）在结构性表示和计算上的偏置学习可以实现AI的组合泛化能力，比如图结构。（为了实现组合泛化能力，需要构建图结构）
泛化：分类没见过的新数据，这一点深度学习能做到。
组合泛化：新数据是在结构方面的新，但结点和关系都是旧的，如果要做图像分类的few-shot那结点和关系表示什么呢，这时候千脑理论或许可以派上用场，（脑子里每个皮质柱的本质是一样的，能不能理解成组成所有待测物体的结点本质都是一样的。）
世界上存在无限的句子，我想要理解句子但是我不直接学句子，我学组成句子的有限种单词，和单词之间的关系，那么很快我就能理解一句我没见过的新结构的句子。
世界上存在无限的分子，我想要知道分子特性但是我不直接学分子，我学组成分子的有限种原子，和原子之间的化学键，那么很快我就能知道新结构分子的特性。（4000多种化合物，还是很多啊！但是相对于无限的分子来说还是few-shot吧）
世界上存在n可取任意值的n体系统，我想预测n体系统的动态但是我不直接学整个系统，我学组成系统的球球，和球球之间的作用力，那么很快我就能知道其他n的n体系统动态。
无限的分子，要学也能学（数量很多），就是现在的依靠大量样本的有监督学习，
人类的组合泛化能力取决于我们对结构表示和关系推理的认知机制。世界是组合的，复杂的系统可看作对象及其关系的组合。学习时，我们要么将新知识融入现有的结构化表示，要么调整结构本身以更好地适应（并利用）新的和旧的。
Key challenges of Deep Learning
complex language and scene understanding（复杂语言与场景理解）/ reasoning about structured data（结构数据推理，我们把思维都限制在这里了）/ transferring learning beyond the training conditions（迁移学习）/ learning from small amounts of experience（少经验学习）. 这些都需要Combinatorial Generalization来解决.（因此不用局限于图结构，而是思考组合泛化，只要是符合组合泛化的问题，都能设计出对应的图结构）
Assignment 1: 思考组合泛化的应用场景
Structured Approaches + Deep Learning
和传统方法（图模型方法）的区别：如何学习实体和关系的表示和结构以及相应的计算，从而减轻提前指定它们的负担。这些方法带有强烈的关系归纳偏置，以特定的架构假设的形式，引导这些方法学习实体和关系。（也就是说，通过DL来学习实体和关系的表示和结构，无需像传统的图模型（Bayes/HMM）要提前构建好实体和关系的表示，正如CNN避免了传统的特征工程。想看一下传统的图模型方法～）
Box1: Relational Reasoning
关系推理涉及到操纵实体和关系的结构化表示，使用它们如何组成的规则。
entity/ relation/ rule（一种映射）
传统的概率图模型 作为机器学习中关系推理的一个示例，图模型（Pearl，1988；Koller和Friedman，2009）可以通过在随机变量之间建立明确的随机条件独立性来表示复杂的联合分布。这些模型之所以非常成功，是因为它们捕获了构成许多现实世界生成过程的稀疏结构，并且支持用于学习和推理的特定算法。例如，隐马尔可夫模型将潜在状态约束为条件独立于前一时间步的状态，而观测值则是条件独立于当前时间步的潜在状态，这与许多现实世界因果过程的关系结构非常匹配。显式表达变量之间的稀疏依赖性提供了各种有效的推论和推理算法，例如消息传递，它在图模型中跨区域应用一个通用的信息传播过程，从而形成一个可组合的、部分可并行的、可应用的推理过程，并应用到不同尺寸和形状的图模型中。
Assignment 2: 了解一下传统概率图模型，纵向比较图模型+DL.
Relational Inductive biases
ML和AI中许多可以进行关系推理的方法都用到了关系归纳偏置，即对学习过程中实体之间的关系和交互施加约束。（inductive biases就是施加约束，relational inductive biases就是对关系和交互施加约束。图结构中把两个结点连起来就是归纳偏置8？）
Box2: Inductive biases
学习是通过对世界的观察和互动来获取有用知识的过程。它包括搜索一个解空间，能够更好地解释数据或获得更高回报。但在许多情况下，也有许多同样好的解决方案（Goodman，1955年）。归纳偏置允许学习算法将一个解决方案（或解释）优先于另一个解决方案（或解释），与观察数据无关（Mitchell，1980）。在贝叶斯模型中，归纳偏置通常通过先验分布的选择和参数化来表示（Griths等人，2010）。在其他情况下，归纳偏置可能是为了避免过度拟合而添加的正则化项（McClelland，1994），或者它可能被编码到算法本身的体系结构中。归纳偏置通常是为了提高样本复杂性而降低了灵活性，并且可以理解为偏差-方差tradeoff（Geman等人，1992年）。理想情况下，归纳偏置既能在不大幅降低性能的情况下改进对解决方案的搜索，也能帮助找到以理想方式归纳的解决方案；但是，不匹配的归纳偏置也会通过引入过强的约束而导致性能不佳。
归纳偏置可以表示关于数据生成过程或解空间的假设。例如，当将一维函数拟合到数据时，线性最小二乘法遵循近似函数为线性模型的约束，并且在二次惩罚下，近似误差应最小。这反映了一个假设，即数据生成过程可以简单地解释为被增加的高斯噪声破坏的线性过程。同样，二阶正则化将参数值较小的解优先化，并能将唯一解和全局结构引入到其他不适定问题中。这可以解释为关于学习过程的一个假设：当解决方案之间的歧义较少时，寻找好的解决方案更容易。注意，这些假设不需要是明确的，它们反映了模型或算法如何与世界交互的解释。
用基本的构建块，形成更复杂、更深入的计算层次结构和图，如FC->MLP。层的这种组合提供了一种特殊类型的关系归纳偏置，这种偏置是分级处理的，在分级处理中，计算是分阶段进行的，通常会导致输入信号中信息之间的交互作用越来越长。
在深度学习中，entity和relation通常表示为分布式表示，rule表示为神经网络函数逼近器；然而，实体、关系和规则的精确形式因体系结构而异。为了理解架构之间的这些差异，可以通过探测进一步询问每个架构如何支持关系推理：
1规则函数的参数（例如，哪些实体和关系作为输入提供：f(x_i,x_j,e), x_i,x_j,e为函数f的输入参数）
2如何在计算图中重用或共享规则函数（例如，跨不同实体和关系、跨不同时间或处理步骤等）
3架构如何定义“表示”之间的交互和隔离（例如，通过应用规则得出有关相关实体的结论，而不是单独处理它们）
全连接层 关系归纳偏置非常弱：所有的输入单元会影响输出单元.(类似于全连接图？)
卷积层 entities仍是独立单元（pixel），但关系较稀疏。fc和conv之间的区别反映了一些重要的关系归纳偏置：局部性和平移不变性。（类似于稀疏图，中心结点只与某些结点有关系，如果邻居数量都一样则可以reuse卷积核.）
（图网络的关系归纳偏置是随机的，因为图结构都不一样，对于某个中心点，影响它的邻居数量都不一样，边决定了关系归纳偏置）
Assignment 3: 用一个具体的例子分析关系归纳偏置的作用
Computations over sets and graphs
没有“默认”的深度学习组件可以在任意的关系结构上运行。我们需要具有实体和关系显式表示的模型，以及学习算法，可以找到计算它们之间交互的规则，并且将它们置于数据中。排序不变性是一种属性，应该由关系推理的深层学习组件反映出来。
集合是系统的一种自然表示，由顺序不确定或不相关的实体来描述；特别是，它们的关系归纳偏置不是来自于presence of something，而是来自于absense.(星球问题的最后一段解释，也就是说如果没有absence，即全连接图，关系归纳偏置就很差咯)
例：星球问题
任务1 预测由n个星球组成星系的质量中心（没关系）
星球的排列是无序的。不能用MLP来做，不然需要考虑n!种排列组合。让最终的预测依赖于输入属性的对称函数（如mean）。
任务2 预测每个星球在一段时间后的位置（有关系）
g可以计算第j个行星对第i个行星所产生的力，f可以计算第i个行星的未来状态，这是由力和动力学得出的。我们在任何地方都使用相同的g，这也是系统全局置换不变性的结果；但是，它也支持不同的关系结构，因为g现在采用两个参数而不是一个参数。
上面的太阳系例子说明了两种关系结构：一种是没有关系的，另一种是由所有的成对关系组成的。然而，许多现实世界系统（如图2所示）在这两个极端之间的某个地方有一个关系结构，一些实体对拥有一个关系，而另一些则缺少一个关系。在我们的太阳系例子中，如果系统由行星和它们的卫星组成，那么人们可能会忽略不同行星的卫星之间的相互作用来近似它。这对应于一个图，其中第i个对象只与其他对象的一个子集交互，称为邻域。注意，更新后的状态仍然不依赖于我们描述邻居的顺序。
一般来说，图是支持任意（成对）关系结构的表示，而对图的计算提供了一个强大的关系归纳偏置，超过了卷积层和循环层所能提供的。
Graph structure
在定义如何将输入数据表示为图时，通常有两种情况：第一，输入显式地指定关系结构；第二，必须推断或假定关系结构。
第一种情况：知识图、社会网络、解析树、优化问题、化学图、道路网络和具有已知交互的物理系统。
第二种情况：视觉场景、文本语料库、编程语言源代码和多代理系统。在这些类型的设置中，数据可以被格式化为一组没有关系的实体，甚至只是一个向量或张量（例如图像）。如果实体没有明确规定，可以假定，例如，将句子中的每个词（Vaswani等人，2017年）或CNN输出特征图中的每个局部特征向量视为节点（Watters等人，2017年；Santro等人，2017年；Wang等人，2018c）（图2e-f）。或者，可以使用单独的学习机制从非结构化信号中推断实体（Luong等人，2015；Mnih等人，2014；Eslami等人，2016；van Steenkiste等人，2018）。如果关系不可用，最简单的方法是实例化实体之间所有可能的有向边（图2f）。但是，对于大量的实体来说，这是不允许的，因为可能的边的数量与节点的数量呈四次方增长。因此，开发更复杂的方法从非结构化数据推断稀疏结构（Kipf等人，2018年）是一个重要的未来方向。
Discussion
图网络将更强大的关系归纳偏置构建到深层学习体系结构中。
Combinatorial generalization in graph networks
图网络的结构自然支持组合泛化，因为它们不仅严格地在系统（全局）级别执行计算，而且还跨实体和跨关系应用共享计算。这使得以前从未见过的系统可以被推理，因为它们是由熟悉的组件构成的，以反映冯·洪堡的“无限使用有限手段”的方式。
具体地，每个边和每个节点的gn函数分别在所有边和节点上重用。这意味着GNS自动支持一种组合泛化形式（见第5.1节）：因为图由边、节点和全局特征组成，单个GN可以在不同大小（边和节点数）和形状（边连接）的图上操作。
许多研究已经探索了GNs的组合泛化能力。Battaglia等人（2016）发现，接受过一步物理状态预测训练的GNs可以模拟未来数千个时间步，并且能够精确地向物理系统进行zero-shot，训练期间经历的实体数量是物理系统的两倍或一半。（训练时候是3个球球，测试用6个球球也能预测出来）Sanchez-Gonzalez等人（2018）在更复杂的物理控制设置中发现了类似的结果，包括在模拟多关节代理上训练为正向模型的GNS可以推广到具有新关节数量的代理。哈姆里克等人（2018）和Wang等人（2018b）每个人都发现，基于gn的决策政策也可以转移到新数量的实体。在组合优化问题中，Bello等人（2016）；Nowak等人（2017年）；Dai等人（2017年）；Kool和Welling（2018年）表明，GNs可以很好地概括出比他们所接受的培训规模大得多的问题。同样，Toyer等人（2017）对不同规模的规划问题进行了概括，Hamilton等人（2017）显示了对为以前未发现的数据生成有用的节点嵌入的概括。关于布尔SAT问题，Selsam等人（2018）证明了对不同问题大小和跨问题分布的概括：在强烈修改输入图及其典型局部结构的分布后，其模型保持了良好的性能。（也就是说，学很少的基础 可以推理出 很多的扩展）
在现代人工智能中，采用显式结构和灵活学习是实现更好的样本识别和泛化的可行方法.
Open Questions
（1）如何得到准确的图结构作为图网络的输入：
深度学习直接作用于原始感官数据（图像、文本），而如何将这些原始感官数据转化为准确的结构性表示（图结构），最好的方法目前还不得而知。有一种方法是使用全连接图，但这种表示可能无法准确地对应真实实体。另外，比起全连接图，很多情况下图结构是非常稀疏的，如何确定稀疏性？一些论文提出了解决方法，但还没有公认的唯一解决方法。这个问题一旦解决，就能打开更有效且灵活的推断算法的大门。
（2）如何在计算过程中适应性地修正图结构：
如果一个物体分裂成多个，那么表示该物体的节点也应该分裂成多个节点，同样，应该增加或移除边的连接，只保留有联系的物体之间的边。该如何保证这种适应性，一些研究也提出了它们的解决方案。
（3）可解释性：
人类认知作出了一个强有力的假设，即世界是由物体和关系组成的，由于图网络作出了类似的假设，他们的行为往往更易于解释。图网络运作的实体和关系通常与人类理解的事物（如物理对象）相对应，从而支持更可解释的分析和可视化。进一步探讨图网络行为的可解释性是今后工作的一个有趣方向。
虽然我们在这里关注的是图，但本文的一个要点并不是关于图本身，而是关于将强大的深度学习方法与结构化表示相结合的方法。
Conclusion
我们主张将组合泛化作为人工智能的首要任务，提倡采用综合方法，这种方法利用人类认知、传统计算机科学、标准工程实践和现代深度学习的思想。在这里，我们探索了灵活的基于学习的方法，实现了强大的关系归纳偏置，利用显式结构表示和计算，并提出了一个框架，称为图网络，它概括和扩展了神经网络应用于图的各种最新方法。图网络的设计目的是使用可定制的图来绘制构建块来促进构建复杂的体系结构，它们的关系归纳偏置比其他标准机器学习构建块促进组合泛化和提高采样效率。
