GNN初学笔记（一）—— Relational inductive biases, deep learning, and graph networks简要解析

GNN初学笔记（一）—— Relational inductive biases, deep learning, and graph networks文献学习
（我会在每个术语解释后面加入自己的理解，若有错误恳请指正）

这篇文献首先阐释AI如何模拟人类的学习能力，即组合泛化能力（combinatorial generalization），总结了目前深度学习“端到端”（end to end）的模型，并将其与“手动设计结构”（hand-engineering）相结合，提出了“图网络”（the graph network）。
接着作者将各深度学习视作模块，对它们的关系归纳偏差（Relational inductive biases）做比较，引入对“Graph network”(简称GN块)的解释。先介绍了GN块的结构、算法，然后提出它的设计原则：灵活的表示（属性、图结构），可配置块内结构，可组合的多块体系结构。
最后提出讨论，对图网络的组合推广，局限性以及未来研究方向做了一个大致的说明。

一.摘要
在摘要中，作者提出
组合泛化是AI的首要任务，结构化表示以及计算能力是实现这个目标的关键
（We argue that combinatorial generalization must be a top priority for AI to achieve human-like abilities, and that structured representations and computations are key to realizing this objective. ）
然后由生物学通过自然以及人工培育合作的方式类比，我们应该
将手动设计结构与端到端相结合，构建可结构化的图网络。

二、介绍
在介绍中，作者用各种具体的例子阐述人类的学习能力对AI的启发。
人类的关键能力是以有限来表示无穷
（A key signature of human intelligence is the ability to make “infinite use of finite means”）
人类组合泛化的能力关键取决于我们表达结构和关系推理的认知机制。
（Humans’ capacity for combinatorial generalization depends critically on our cognitive mecha- nisms for representing structure and reasoning about relations.）
在学习时，我们要么将新知识融入我们现有的结构化表示中，要么调整结构本身来将旧的知识融入新的知识。
（When learning, we either fit new knowledge into our existing structured representations, or adjust the structure itself to better accommodate (and make use of) the new and the old ）
我们认为，现代人工智能的一个关键路径是将组合泛化作为首要任务，我们提倡采用综合方法来实现这一目标。
（We suggest that a key path forward for modern AI is to commit to combinatorial generalization as a top priority, and we advocate for integrative approaches to realize this goal.）

三、关系归纳偏差
box 1、关系推理
关系推理涉及操纵实体和关系的结构化表示，使用关于如何组合的规则。
（Relational reasoning, then, involves manipulating structured representations of entities and relations, using rules for how they can be composed. ）
明确表达变量之间的稀疏依赖性提供了各种有效的推理和推理算法。
（Explicitly expressing the sparse dependencies among variables provides for various efficient inference and reasoning algorithms）

这里举了消息传递模型的例子，所以在我看来作者意思通俗来讲就是通过现实世界的规律来训练模型，使训练出的模型能够在由A->B->C->…这样推导下去。.

box 2、归纳偏差
理想情况下，归纳偏差既可以改善对解决方案的搜索，又不会显着降低性能，也可以帮助找到以理想方式推广的解决方案; 然而，不匹配的归纳偏差也可能通过引入过于强大的约束而导致次优性能。
（Ideally, inductive biases both improve the search for solutions without substantially diminishing performance, as well as help find solutions which generalize in a desirable way; however, mismatched inductive biases can also lead to suboptimal performance by introducing constraints that are too strong.）

我的理解是，归纳偏差就像过滤器一样，有着种种的约束条件，最终能够给出一个最优解决方案。

总得来说，关系归纳偏差就是对学习过程中的实体关系以及互动加以约束和限制。
根据下面的内容，我觉得在这里加入一个词“共享”会更好理解。使用不同模型学习时，输入的各部分权重是否共享，若无共享，则关系归纳偏差较小，若共享并循环，则会大大的他的关系归纳偏差。

接下来解释了几种深度学习构建模块的关系归纳偏差


figure.Reuse and sharing in common deep learning building blocks.
(a)完全连接的层，其中所有权重是独立的，并且没有共享。
(b)卷积层，其中局部核函数在输入上多次重复使用。共享权重由具有相同颜色的箭头指示。
©循环层，其中相同的功能在不同的处理步骤中重复使用。

全连接（Fully connected layers）
通常实现为向量输入的非线性向量值函数，输出向量的每个元素或“单位”是权重向量之间的点积，后跟增加的偏置项，最后是非线性。因此，实体是网络中的单元，关系是all to all的，且规则由权重和偏差指定。规则的参数是完整的输入信号，没有重用，并且没有信息隔离。所以，完全连接层中的隐式关系归纳偏差非常弱。

卷积层（Convolutional layers）
它通过将输入向量或张量 与相同等级的内核卷积，添加偏置项并应用逐点非线性来实现。这里的实体仍然是单独的 单元(或网格元素，例如像素)，但关系更稀疏。完全连接层和卷积层之间的差异强加了一些重要的关系归纳偏差：局部性和平移不变性。局部性反映了关系规则的参数是 在输入信号的坐标空间中彼此非常接近的实体，与远端实体隔离。翻译不变性反映了输入中跨地方重用相同规则。这些偏差对于处理自然图像数据非常有效，因为在局部内存在高协方差邻域，随着距离的增加而减少，并且因为统计数据在图像中基本上是静止的。

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

最后提出了图结构用以引出下文对graph network的讲解。

这部分主要提出了这样的观点，通常情况下图形支持任意关系结构的表示，并且在图形上的计算能够提供超出卷积和循环层的强关系归纳偏差。

下面一段就是本篇文献的重点了
四、GN块（Graph network block）
1、图形的定义
box 3、图的定义

提出了将图形定义为三元组结构，即G = (u, V, E) 。
u：全局属性
V：节点属性
E：边缘属性（E = {(ek,rk,sk)} ek是边的属性、rk 是接收节点的属性、sk 是发送节
点的属性 ）
（Here we use “graph” to mean a directed, attributed multi-graph with a global attribute. In our terminology, a node is denoted as vi, an edge as ek, and the global attributes as u. We also use sk and rk to indicate the indices of the sender and receiver nodes (see below), respectively, for edge k. To be more precise, we define these terms as:
Directed : one-way edges, from a “sender” node to a “receiver” node.
Attribute : properties that can be encoded as a vector, set, or even another graph. Attributed : edges and vertices have attributes associated with them.
Global attribute : a graph-level attribute.
Multi-graph : there can be more than one edge between vertices, including self-edges.）

2、GN块算法
文字叙述：

step1：更新边缘属性。

step2：每个节点聚合边缘属性。
step3：更新节点属性。

step4：全局聚合边缘属性。

step5：全局聚合节点属性。

step6：更新全局属性。

算法图示：

算法伪代码：

算法中的三个更新函数（左）和三个聚合函数（右）

3、图网络的关系归纳偏差
GN框架在用作学习过程中的组件时会产生一些强大的关系归纳偏差，原因如下：
（1）图形可以表示实体之间的任意关系，这意味着GN的输入决定了表示如何交互和隔离，而不是由固定体系结构决定的那些选择。
例如：假设两个实体具有关系（因此应该相互作用）由实体的对应节点之间的边缘表示。类似地，没有边缘表示假设节点没有关系并且不应该直接相互影响。
（2）图表将实体及其关系表示为集合，这些集合对于排列是不变的。这意味着GNs对这些元素的顺序是不变的，这通常是可取的。
例如：场景中的对象没有自然顺序。
（3）GN的每边缘和每节点功能分别在所有边缘和节点上重复使用。这意味着GNs自动支持一种组合泛化形式: 因为图形由边，节点和全局特征组成，所以单个GN可以在不同大小(边和节点的数量)和形状(边连通性)的图上操作。

四、图网络架构的设计原则
1、灵活的表示（属性和图结构）
（1）属性
GN块的全局，节点和边缘属性可以使用任意表示格式。在深度学习实现中，实值向量和张量是最常见的。但是，也可以使用其他数据结构，例如序列，集合甚至图形。
输入：
当输入数据是图像时，属性可以表示为图像块的张量;然而，当输入数据是文本文档时，属性可以是与句子对应的单词序列。
输出：
边缘和节点输出通常对应于矢量或张量列表，每个边缘或节点一个，并且全局输出对应于单个矢量或张量。这允许将GN的输出传递给其他深度学习构建块，例如MLP，CNN和RNN。
同时，GN块的输出也可以根据任务的需求进行定制。特别是：

• 边缘聚焦的GN使用边缘作为输出，例如，以做出关于实体之间的交互的决定。
• 以节点为中心的GN使用节点作为输出，例如推理物理系统。
• 以图形为中心的GN使用全局变量作为输出，例如预测物理系统的潜在能量。

节点，边和全局输出也可以根据任务进行混合和匹配。（Deepmind在星际争霸中训练了一个机器人与该项目世界冠军进行比赛，应该就是采用这样的方法）

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

• 输入明确指定关系结构： 如知识图，社交网络，解析树，优化问题， 化学图，道路网和具有已知交互的物理系统等；
• 必须推断或假设关系结构：如视觉场景，文本语料库，编程语言源代码和多代理系统；

最后提出开发更复杂的方法来推断非结构化数据的稀疏结构是一个重要的未来方向。

2.可配置的块内结构

图（a）就是作者提到的GN完全块，后面的其他已有的结构都可以视作完全块的一部分，所需要做的就是根据需求修改输入输出，更新以及聚合函数。

3、可组合的多块体系结构

（a）按顺序组成多个GN块以形成GN“核心”的示例。 这里，GN块可以使用共享权重，也可以是独立的。
（b）编码 - 处理 - 解码架构，它是组成GN块的常用选择（见4.3节）。 这里，GN编码输入图，然后由GN核处理。 核心的输出由第三个GN块解码为输出图形，其节点，边缘和/或全局属性将用于特定于任务的目的。
（c）在顺序设置中应用的编码 - 处理 - 解码架构，其中核心也随着时间推移（可能使用GRU或LSTM架构），除了在每个时间步骤内重复之外。 这里，合并的行表示连接，分割线表示复制。

这里作者写了一个MPNN（消息传递网络）的例子：

消息传递的示例。 每行突出显示从特定节点开始通过图表扩散的信息。 在第一行中，感兴趣的节点位于右上角; 在底行，感兴趣的节点位于右下角。 阴影节点表示来自原始节点的信息可以在m步消息传递中传播多远; 粗体边缘表示信息有可能穿过的边缘。 请注意，在完整的消息传递过程中，信息的传播同时发生在图中的所有节点和边缘（不仅仅是这里显示的两个）。

五、演示
下周run一下。
链接：github.com/deepmind/graph_nets

六、讨论
这里主要就提了，这是作者们迈出的一小步，需要我们去迈出更多的步子，探索它的潜能。
作者给出了一些仍需解决的问题：

• Where do the graphs come from that graph networks operate over?
• A related question is how to adaptively modify graph structures during the course of computation.

（ps：希望能够一起交流，以及下一次会做一下实例演示）