Relational inductive biases, deep learning, and graph networks

• Intro

  • Relational inductive biases
    • box1-Relational Thinking
    • box2-Inductive Biases（关系归纳偏置）
      • The relational inductive biases embedded within the core components of modern deep learning frameworks are crucial for processing structured data.
      • Operations performed on sets and graph structures enable efficient reasoning about complex relationships.

• Graph neural networks (GNNs)

• Overview

• 3. Graph neural network (GN) block

  • Definition of a graph
  • The internal architecture of the GN block
  • A detailed computational process within the GN block
  • Inductive biases inherent to relational reasoning

*4. Design principles governing the characteristics and topological configuration of graph-based systems *

• 支持模块化结构的可配置性

  • • 消息传递神经网络（MPNN）

• 非局部神经网络（NLNN）

• 其他类型的图网络变体

• 可组合的多块架构

  • 在代码中构建图网络
  • 摘要

• 5. Discussion

• 探讨了基于图结构的数据处理方法及其扩展可能性

• 分析了当前基于图的网络模型存在的主要限制

• 提出了几个值得深入探讨的问题

• 研究了整合学习与结构表征的新方法

• 总结以上讨论的主要发现及其对未来研究的指导意义

Intro

人类智能的表现体现在"通过有限资源实现无限可能性"(infinite use of finite means)这一特性上；这也就是通过有限元素所构成的各种组合来展现无限多的变化形式。

遵循了这一原则：组合推理 (combinatorial generalization)，即通过现有的模块构建新的推理逻辑体系、预测模型以及执行策略。

提升模型的组合泛化能力：通过引入偏差（biasing）将学习焦点定向于结构化的数据表示与计算流程中。

该设计哲学旨在强调深度学习体系中所涉及的最小先验假设及其相关的计算架构。（该设计哲学旨在强调深度学习体系中所涉及的最小先验假设及其相关的计算架构）即表明这一方法通过基于大量的廉价数据与计算资源以提升样本效率作为代价换取更加灵活与适应性的学习机制。

确定将系统化整合作为关键路径进行规划，并主张采用多元化策略以实现这一目标。（深度学习+基于结构的方法：图数据）

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

和传统方法的不同：在探索实体与关系表示及结构方面采取了新的方式，并构建了高效的计算模型。

这类方法表现出显著的归纳倾向（Mitchell, 1980）。这类方法基于特定的架构假设，在 Mitchell 的理论中（ Mitchell, 1980），这些假设引导着这些系统去学习有关实体和关联的知识。

Relational inductive biases

box1-Relational Reasoning

• structure : 组件所构成的对象。
• Structured representation : 一种结构化的表示方法，用于获取组件之间的组合方式。
• Structured computation : 将组件及其组合物统一为一个整体，在此基础上进行相应的计算处理。
• rules : 一种机制，在给定的实体与关系之间建立映射关系。
• Relational Reasoning : 基于规则的方法，在结构化的实体与关系间进行推理操作。

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

• 学习过程涵盖探索解空间中的解答过程，在多数情形下能够助益于数据的合理解释或带来更高的回报。
  • 在多数情形下, 多个同样有效的解决方案, 归纳偏置（inductive bias） 使得其中一个方案得以优先选择,这一特性独立于观察到的数据。

在贝叶斯模型构建过程中, 归纳偏差主要由先验分布的选择以及参数化过程所体现；而在其他应用场景下, 归纳偏差可能会表现为防止过拟合的正则化措施；或者更具体地说, 在算法体系结构中会嵌入这种偏置因素。

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

*归纳偏差（bias）可以反映数据生成过程以及解空间之间的关系假设。例如，在应用l2正则化时，默认选择参数值较小的解决方案作为最优选项，并最终导致单一解以及整体结构的变化。这可被视为对学习进程的一种假设——当不同解决方案间的分歧较小时，寻优变得更加容易。

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

The relational inductive biases are inherent within the core components of conventional deep learning frameworks.

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被定义为：G = (\mathbf{u}, V, E), 其中\mathbf{u}被标记为全局属性, 点集合V由多个点组成, 边集合E包含若干元组(e_k, r_k, s_k)（其中k=1:N^e）, 每个元组中的e_k代表边属性, r_k指定接收节点（即接收器节点）而s_k指定发送节点（即发送者节点）。

Internal structure of a GN block

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

• 其中涉及到为所有边进行update操作；同时还有针对每个node的状态进行update的过程；最后则是完成整个graph state的综合update。

  • 则是输入一个集合（点或边的属性），输出归纳为单个聚集信息元素。

  • 函数必须对其输入的序列有不变性，并且应该采用可变的参数。

  • Computational steps within a GN block

更新过程：

该过程对所有边属性进行更新操作以获得e_k^{'}；从而导出每个节点与其相关联的所有边构成的集合E_i^{'}=\{(e_k^{'},r_k,s_k)\}_{r_k=i,k=1:N^e}；

在处理每个主要目标节点时，在其边属性上应用聚合函数计算出各边的聚合结果 \bar e^{'} ，进而更新所有相关节点的信息。

生成一个新的点集和边集，并对所有边及其连接的点计算其属性信息；根据当前的状态更新整个图的信息并获得新状态u^{'}；返回更新后的图实例。

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

Relational inductive biases in graph networks

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

图形能够体现各实体之间的各种联系。这表明GN的输入参数会影响representations之间的互动模式及其独立性程度。

图示通过将实体及其关系以集合的形式表达出来，并进而得出该图示处理后的元素顺序具有保持不变的特性；例如一张图片通常由多个部分构成，在经过卷积处理后，该结构依然能够有效识别原始图像。

GN的各向异性函数各自在整个边上及节点上进行了重用，并且这表明GN内在地具备了组合泛化的潜力。

4. Design principles for graph network architectures

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

Flexible representations

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

Attributes

• 在GN框架中对属性的表现形式具有灵活性，在深度学习实现过程中，默认情况下实值向量和张量是最常见的表现形式。
  • 不同任务的需求决定了属性应采用何种表现形式：例如，在图像数据处理场景下其属性可表征为图像块对应的张量；而在文本文档分析任务中则可能将对应于句子序列的形式作为节点属性。
  • 根据具体任务需求GN模块的设计方案也可相应进行定制：包括基于边的行为关注边相关的信息提取模块基于节点的行为聚焦于节点特征提取模块以及基于图结构的整体信息提取的整体性模块。

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

Graph structure

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

输入明确指出了关系结构

这些实例包括知识图谱、社会网络结构、解析树模型、优化挑战、化学图论、道路网络系统以及与已知相互作用的物理系统等

关系结构需要被推理或假设(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

GNs块之间可以实现共享参数（如RNNs），同时各具独立的参数结构（如CNNs中的每一层）。
GNs的输入形式为图状数据，在经过处理后仍输出为图状数据，并可作为新的GNs模型输入。
三种基本结构如下：
第一种结构是以递归神经网络为基础构建的层次分明的递进模型。
第二种结构采用基于卷积神经网络的空间并行设计。

(a) 任意数量的GN模块能够组合并叠加，并用符号表示为\ GN_{\text core} \,.
(b) 输入图G_{inp}经由编码器GN_{enc}进行编码生成G_0, 接着经过中间训练共M次得到结果图G_M, 最终通过解码模块得到目标图G_{out}\,.
(c) 将时间序列信息整合到步骤(b)中进行处理.

Implementing graph networks in code

优化边函数与点函数在所有边与点中进行共享（共用），从而实现了并行计算的可能性；将一批独立子图整合到一个大图中的非连通子图上进行批量处理即可实现计算功能。

Summary

图网络的设计理念体现在三个方面：首先在于其灵活的表现能力；其次在于模块化且可定制的内部架构；最后在于高度可组合的多层次架构。

5. Discussion

结论1：CNNs and RNNs 具备关系归纳能力(relational inductive capacities), 但它们无法处理更为复杂的表达形式(more complex representations),例如集合或图(sets or graphs)。

结论2：强调采用graph network这一技术框架，在深度学习模型中融入更具表达力的关联性参数，并将其应用于图结构数据处理的过程中以提升模型性能。graph network 通过构建复杂关系模型实现对图数据特征的有效捕捉与运算。

Combinatorial generalization in graph networks

列举了不同领域的案例为此论点提供了有力的支持，在现代人工智能领域中，《The Elements of Statistical Learning》中的显式结构能够更有效地提升采样效率与泛化能力的方法。

Introducing structured frameworks and adaptable learning paradigms represents a promising strategy for enhancing data utilization and improving the model's broader applicability in modern AI systems.

Limitations of graph networks

这些概念难以通过图形化的方式呈现，并且在解析抽象语法树时通常需要依赖某些额外的假设。

Open questions

将原始感官数据（包括图像和文本内容）转译为更具结构性的表示形式，并采用图结构作为主要表示方式

探讨计算过程中基于需求动态调整图形架构的方法。例如，在一个对象中被分解出的节点会分裂为多个独立的节点，并根据系统状态动态切换连接方式或移除不相关的边。

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

Integrative approaches for learning and structure

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

Conclusion

主要强调组合泛化应被视为人工智能领域的核心问题，并建议采取全面的方法，在借鉴人类认知理念的基础上结合传统计算机科学理论以及现代深度学习模型的基础理论进行深入研究与实践。

Graph Networks通过可配置的Graph-to-Graph组件搭建复杂架构；这些关系归纳偏差能够显著地促进组合泛化，并在提升样本效率方面表现更为出色。