一、GNN

1. 很多领域的数据的底层关系可以表示为图结构，如计算机视觉、分子化学、分子生物学、模式识别、数据挖掘等领域。

   最简单的图结构为单节点图，以及作为节点序列的图，更复杂的图结构包括树、无环图、带环图等。

2. 关于图的任务可以分为两类：

   • 基于图的任务graph-focused：以图为单位，直接在图结构的数据上实现分类或者回归。

     如：图表示化学化合物，每个顶点表示一个原子或者化学基团、边表示化学键。模型可以用于评估被检测的化合物的类别。

     

   • 基于节点的任务 node-focused：以节点为单位，在每个结点上实现分类或者回归。如：

     • 目标检测任务中需要检测图像是否包含特定的目标并进行目标定位。该问题可以通过一个映射函数来解决，该映射函数根据相应区域是否属于目标对象从而对邻接的顶点进行分类。

       如下图所示，对应于城堡的黑色顶点的输出为1，其它顶点输出为 0 。

       

     • 网页分类任务中需要判断每个网页的类别。我们将所有的网页视作一个大图，每个网页代表一个顶点、网页之间的超链接代表边。可以利用网页的内容和图结构来进行建模。

       

3. 传统的机器学习算法通过使用预处理阶段来处理图结构的数据。在这一阶段，算法将图结构数据映射到一个更简单的表达representation，如一个实值向量。即：预处理阶段首先将图结构的数据“压缩” 为实值向量，然后使用 list-based 数据处理技术来处理。

   在数据压缩过程中，一些重要的信息（如：每个顶点的拓扑依赖性）可能会被丢失。最终的效果严重依赖于数据预处理算法。

   最近有很多算法尝试在预处理阶段保留数据的图结构性质，其基本思路是：利用图的结点之间的拓扑关系对图结构的数据进行编码，从而在数据预处理过程中融合图的结构信息。递归神经网络RNN、马尔科夫链都是这类技术。

   论文 《The graph neural network model》 提出了 GNN 模型，该模型扩展了RNN 和马尔科夫链技术，适合处理图结构的数据。

   • GNN 既适用于 graph-focused 任务，又适用于 node-focused 任务。
   • GNN 扩展了RNN，它可以处理更广泛的图任务，包括无环图、带环图、有向图、无向图等。
   • GNN 扩展了马尔科夫链，它通过引入学习算法并扩大了可建模的随机过程的类型从而扩展了随机游走理论。

4. GNN 是基于消息扩散机制 information diffusion mechanism 。图由一组处理单元来处理，每个处理单元对应于图的一个顶点。

   • 处理单元之间根据图的连接性来链接。
   • 处理单元之间交换信息并更新单元状态，直到达到稳定的平衡为止。
   • 通过每个处理单元的稳定状态可以得到对应顶点的输出。
   • 为确保始终存在唯一的稳定状态，消息扩散机制存在约束。

1.1 模型

1. 定义图 ，其中 为顶点集合、 为边集合。边可以为有向边，也可以为无向边。

   对于顶点 ，定义 为其邻接顶点集合，定义 为包含顶点 的边的集合。

2. 顶点和边可能含有额外的信息，这些信息统称为标签信息（它和监督学习中的标记label 不是一个概念）。

   • 标签信息以实值向量来表示，定义顶点 的标签为 ，定义边 的标签为 ，其中 为顶点标签的维度、 为边标签的维度。

   • 顶点标签通常包含顶点的特征，边标签通常包含顶点之间关系的特征。如下图中：

     • 顶点标签可能代表区块的属性，如：面积、周长、颜色的平均强度。
     • 边标签可能代表区块之间的相对位置，如：重心之间的距离、轴线之间的角度。

     

3. 一个直觉的想法是：将图中的顶点视作对象或者概念 concept，边表示对象之间的关系。每个对象通过各自的特征以及关联对象的特征来定义。因此，我们可以通过顶点 包含的信息，以及顶点 邻居顶点包含的信息，从而给顶点 定义一个状态向量 ，其中 为状态向量的维度。

   • 是顶点 对应对象的 representation，可用于产生顶点 的输出 。

   • 定义局部转移函数 local transition function ：它是一个参数可学习的函数，刻画了顶点 和邻居顶点的依赖性。

     

     其中：

     • 为顶点 的标签信息向量。
     • 为包含顶点 的所有边的标签信息向量拼接的向量。
     • 为顶点 的所有邻居的状态向量拼接的向量。
     • 为顶点 的所有邻居的标签信息向量拼接的向量。

   • 定义局部输出函数 local output function ：它也是一个参数可学习的函数，刻画了顶点 的输出。

     

4. 可以采取不同的邻域定义。

   • 可以移除 ，因为 中已经包含了邻居顶点的信息。
   • 邻域不仅可以包含顶点 的直接链接的顶点，还可以包含顶点 的二跳、三跳的顶点。

5. 上述定义仅仅针对无向图，也可以通过改造 来支持有向图。我们引入一个变量 ：如果边 的终点为 则 ；如果边 的起点为 则 。则有：

   

6. 如果图的顶点可以划分为不同的类别，则对不同类别的顶点建立不同的模型是合理的。假设顶点 的类别为 ，转移函数为 ，输出函数为 ，对应参数为 ，则有：

   

   但是为了表述方便，我们假设所有的顶点都共享相同的参数。

7. 令 分别代表所有顶点状态向量的拼接、所有顶点输出向量的拼接、所有标签（包含顶点标签以及边的标签）向量的拼接、所有顶点标签向量的拼接：

   

   则有：

   

   其中：

   • 称作全局转移函数 global transition fucntion，它由 个 组成。
   • 称作全局输出函数 global output function ，它由 个 组成。

   令图和顶点的 pair 对的集合为 ，其中 为所有图的集合， 为这些图中所有顶点的集合。全局转移函数和全局输出函数定义了一个映射 ，它以一个图作为输入，然后对每个顶点 返回一个输出 。

8. 图结构的数据可以是位置相关的 positional 或者是位置无关的 non-positional 。前面描述的都是位置无关的，位置相关的有所不同：需要为顶点 的每个邻居分配唯一的整数标识符来指示其位置。即：对于顶点 的邻域 ，存在一个映射函数 ，使得顶点 的每个邻居 都有一个位置 。

   • 邻居位置可以隐式的表示一些有意义的信息。 如下图所示，邻居位置可以表示区块的相对空间位置。在这个例子中，我们可以按照顺时针来枚举顶点的邻居。

     

   • 对于位置相关的图， 必须接收邻居顶点的位置信息作为额外的输入。

     实际中我们可以根据邻居的位置进行排序，然后对 按照排序之后的顺序进行拼接。如果在某些位置处的邻居不存在，则需要填充 null 值。

     如：

     

     其中：

     • 为所有顶点的最大邻居数。

     • 为第 个位置邻居的状态向量：

       

       即：如果 为 的第 个邻居节点，则 ；如果 没有第 个邻居节点，则 为null 值 。

   • 对于位置无关的图，我们可以将 替换为：

     

     其中 为待学习的函数，它和邻居的位置无关，也和邻居的邻居无关。这种形式被称作 nonpositional form，而原始形式被称作 positional form。

9. 为实现 GNN 模型，我们必须解决以下问题：

   • 求解以下方程的算法：

     

   • 从训练集种学习 和 参数的学习算法。

   • 和 的实现方式，即：解空间。

1.1.1 方程求解算法

1. Banach 不动点理论为上述方程解的存在性和唯一性提供了理论依据。根据 Banach 不动点理论，当 满足以下条件时，方程 存在唯一解： 是一个收缩映射 contraction map 。即存在 ，使得对任意 都有：

   

   其中 表示向量范数。

   本文中我们假设 是一个收缩映射。实际上在 GNN 模型中，这个条件是通过适当的选择转移函数来实现的。

2. Banach 不动点理论不仅保证了解的存在性和唯一性，还给出了求解的方式：采用经典的迭代式求解：

   

   其中 表示状态 的第 次迭代值。

   • 对于任意初始值 ，上式指数级收敛到方程 的解。

   • 我们将 视为状态向量，它由转移函数 来更新。因此输出向量 和状态向量 的更新方程为：

     

     这可以解释为由很多处理单元unit 组成的神经网络，每个处理单元通过 计算其状态，并通过 计算其输出。这个神经网络被称作编码网络 encoding network，它类似于 RNN 的编码网络。

     在编码网络中，每个单元根据邻居单元的状态、当前顶点的信息、邻居顶点的信息、边的信息，通过 计算下一个时刻的状态 。

     注意：这里没有根据 没有考虑 ，也就是没有自环。

   • 当 和 通过前馈神经网络实现时，编码网络就成为 RNN ，其中神经元之间的连接可以分为内部连接和外部连接。内部连接由实现神经元的神经网络架构决定，外部连接由图的链接决定。

     如下图所示：上半图对应一个图Graph，中间图对应于编码网络，下半图对应于编码网络的展开图。在展开图中，每一层layer 代表一个时间步，layer 之间的链接（外部连接）由图的连接性来决定，layer 内神经元的链接（内部连接）由神经网络架构决定。

     

1.1.2 参数学习算法

1. 假设训练集为：

   

   其中 表示第 个图， 表示第 个图的顶点集合， 表示第 个图的边集合， 表示第 个图的第 个顶点， 表示顶点 的监督信息target ， 为图 中的标记样本。

   • 训练集的所有图 也可以合并为一张大图，其中大图内部存在孤立的子区域（各个子图）。因此上述框架可以简化为：

     

     其中 表示大图， 表示 “顶点-目标” pair 对的集合。这种表述方式不仅简单而且实用，它直接捕获了某些仅包含单个图的问题的本质。

   • 对于 graph-focused 任务可以引入一个特殊的顶点，该顶点和任务目标相关。只有该顶点包含监督信息，即 。

   • 对于node-focused 任务，每个顶点都可以包含监督信息。

   假设采用平方误差，则训练集的损失函数为：

   

   也可以在损失函数中增加罚项从而对模型施加约束。

2. 我们可以基于梯度下降算法来求解该最优化问题，求解方法由以下几步组成：

   • 通过下面的迭代公式求解求解 ，直到时间 ：

     

     其解接近 的不动点： 。

     注意：这一步要求 是一个压缩映射，从而保证方程能够收敛到一个不动点。

   • 求解梯度 。

     这一步可以利用 GNN 中发生的扩散过程以非常高效的方式进行。这种扩散过程与 RNN 中发生的扩散过程非常相似，而后者是基于backpropagation-through-time: BPTT 算法计算梯度的。

     BPTT 是在展开图上执行传统的反向传播算法。 首先计算时间步 的损失函数，以及损失函数在每个时间步 相对于 和 的梯度。最终 由所有时间步的梯度之和得到。

     BPTT 要求存储每个单元在每个时间步 的状态 ，当 非常大时内存需求太大。为解决该问题，论文基于 Almeida-Pineda 算法提出了一个非常高效的处理方式：由于我们假设状态向量最终收敛到不动点 ，因此我们假设对于任意 都有 。因此 BPTT 算法仅需要存储 即可。

     下面两个定理表明：这种简单直观方法的合理性。

     • 定理：如果全局转移函数 和全局输出函数 对于状态 和参数 都是连续可微的，则 对于参数 也是连续可微的。

       其证明见原始论文。值得注意的是，对于一般动力学系统而言该结论不成立。对于这些动力学系统而言，参数的微小变化会迫使其从一个固定点转移到另一个固定点。而 GNN 中的 可微的原因是由于 是收缩映射。

     • 定理：如果全局转移函数 和全局输出函数 对于状态 和参数 都是连续可微的，定义 为：

       

       则序列 以指数级收敛到一个向量 ，且收敛结果和初始状态 无关。

       更进一步有：

       

       其中 为GNN 的不动点， 为上述收敛的向量。

       证明见论文原文。其中：

       • 第一项表示输出函数 对于梯度的贡献。反向传播的梯度在通过 的 layer 时计算这一项。

       • 第二项表示转移函数 对于梯度的贡献。反向传播的梯度在通过 的 layer 时计算这一项。

         可以证明：

         

         即： 等价于 的累加。

         证明过程：

         

         其中最外层的 表示矩阵的转置，内层的 表示矩阵的幂。

         考虑到收敛结果和初始状态 无关，因此假设：

         

         并且当 时有 ，以及 ，则有：

         

         考虑到：

         

         因此有：

         

   • 通过梯度来更新参数 。

3. GNN 参数学习算法包含三个部分：

   • FORWARD前向计算部分：前向计算部分用于计算状态向量 ，即寻找不动点。
   • BACKWARD 反向计算部分：反向计算部分用于计算梯度 。
   • MAIN 部分：该部分用户求解参数。该部分更新权重 直到满足迭代的停止标准。

4. FORWARD 部分：

   • 输入：

     • 图
     • 当前参数
     • 迭代停止条件

   • 输出：不动点

   • 算法步骤：

     • 随机初始化 ，令

     • 循环迭代，直到满足 。迭代步骤为：

       • 计算 ：
       • 令
     • 返回

5. BACKWARD 部分：

   • 输入：

     • 图
     • 不动点
     • 当前参数
     • 迭代停止条件

   • 输出：

   • 算法步骤：

     • 定义：

       

     • 随机初始化 ，令

     • 循环迭代，直到满足 。迭代步骤为：

       • 更新 ：
       • 令

     • 计算梯度：

       

     • 返回梯度

6. Main 部分：

   • 输入：

     • 图
     • 学习率

   • 输出：模型参数

   • 算法步骤：

     • 随机初始化参数

     • 通过前向计算过程计算状态：

     • 循环迭代，直到满足停止条件。循环步骤为：

       • 通过反向计算过程计算梯度：
       • 更新参数：
       • 通过新的参数计算状态：
     • 返回参数

7. 目前 GNN 只能通过梯度下降算法求解，非梯度下降算法目前还未解决，这是未来研究的方向。

8. 实际上编码网络仅仅类似于静态的前馈神经网络，但是编码网络的layer 层数是动态确定的，并且网络权重根据输入图的拓扑结构来共享。因此为静态网络设计的二阶学习算法、剪枝算法、以及逐层学习算法无法直接应用于 GNN 。

1.1.3 转移函数和输出函数

1. 局部输出函数 的实现没有任何约束。通常在 GNN 中， 采用一个多层前馈神经网络来实现。

2. 局部转移函数 在 GNN 中起着关键作用，它决定了不动点的存在性和唯一性。GNN 的基本假设是：全局转移函数 是收缩映射。

   论文给出了两种满足该约束的 的实现，它们都是基于nonpositional form，positional form 也可以类似地实现。

3. nonpositional linear GNN 线性 GNN：

   

   其中 和矩阵 分别由两个前馈神经网络的输出来定义，这两个前馈神经网络的参数对应于 GNN 的参数。更准确的说：

   • 转移神经网络 transition network 是一个前馈神经网络，它用于生成 。

     设该神经网络为一个映射 ，则定义：

     

     其中：

     • 是由 的 个元素进行重新排列得到的矩阵。
     • 为缩放系数， 用于对矩阵 进行缩放。

   • 约束神经网络forcing network 是另一个前馈神经网络，它用于生成 。

     设该神经网络为一个映射 ，则定义：

     

   假设有： ，即 。事实上如果转移神经网络的输出神经元采用有界的激活函数（如双曲正切），则很容易满足该假设。

   根据 有：

   

   其中：

   • 是由所有的 拼接而来， 是由所有的 拼接而来：

     

   • 是一个分块矩阵，每一块为 ：

     

     其中：

     • 如果 是 的邻居顶点，则有
     • 如果 不是 的邻居顶点，则由

   由于 和 不依赖于状态 （它们仅仅依赖于图的结构和顶点标签信息、边标签信息），因此有：

   

   则有：

   

   因此对于任意的参数 ， 都是约束映射。

4. nonpositional nonlinear GNN 非线性 GNN： 通过一个多层前馈神经网络来实现。考虑到 必须是一个约束映射，因此我们在损失函数中增加罚项：

   

   其中罚项 定义为：

   

   超参数 定义了针对 的约束。

1.2 模型分析

1.2.1 RNN

1. 事实上，GNN 是其它已知模型的扩展，特别地，RNN 是 GNN 的特例。当满足以下条件时，GNN 退化为 RNN：

   • 输入为有向无环图。
   • 的输入为 ，其中 为顶点 的子结点的集合。
   • 一个超级源点 ，从该源点可以到达其它所有顶点。该源点通常对应于 graph-focused 任务的输出 。
2. 实现 的神经网络形式包括：多层前馈神经网络、cascade correlation、自组织映射 self-orgnizing map。在 RNN 中，编码网络采用多层前馈神经网络。这个简化了状态向量的计算。

1.2.2 随机游走

1. 当选择 为线性函数时，GNN 模型还捕获了图上的随机游走过程。

   定义顶点的状态 为一个实数，其定义为：

   

   其中 表示顶点 的父节点集合； 为归一化系数，满足：

   

2. 事实上 定义了一个随机游走生成器：

   • 表示当前位于顶点 时，随机转移到下一个顶点 的概率。
   • 表示当系统稳定时，随机游走生成器位于顶点 的概率。

3. 当所有的 拼接成向量 ，则有：

   

   其中：

   

   可以很容易的验证 。

   马尔可夫理论认为：如果存在 使得矩阵 的所有元素都是非零的，则 就是一个收缩映射。

   因此假设存在 使得矩阵 的所有元素都是非零的，则图上的随机游走是 GNN 的一个特例，其中 的参数 是一个常量随机矩阵，而不是由神经网络产生的矩阵。

1.2.3 计算复杂度

1. 我们关心三种类型的 GNN 模型：positional GNN ，其中 和 通过前馈神经网络来实现；nonpositional linear GNN；nonpositional nonlinear GNN 。

   训练过程中一些复杂运算的计算复杂度见下表。为方便表述，我们假设训练集仅包含一张图。这种简化不影响结论，因为训练集所有的图总是可以合并为一张大图。另外，复杂度通过浮点预算量来衡量。

   具体推导见论文。其中：

   • instruction 表示具体的运算指令；positional/non-linear/linear 分别给出了三类 GNN 模型在对应运算指令的计算复杂度；execs 给出了迭代的次数。

   • 下图中的 就是损失函数 ， 就是 ， 就是 ， 就是 。这是因为原始论文采用了不同的符号。

   • 为罚项。设 ，则有：

     

     其中：

     • 表示矩阵 的分块 的第 行第 列
     • 表示矩阵 的第 列
     • 

   • 定义 为一个矩阵，其元素为 ，则 为：对所有的顶点 ，满足 的顶点 的数量的均值。通常它是一个很小的数值。

   • 和 分别表示前向计算 和反向计算 梯度的计算复杂度。

   • 表示隐层神经元的数量，即隐层维度。如 表示函数 的实现网络的隐层神经元数量。

   • 表示迭代的 epoch 数量， 表示平均每个epoch 的反向迭代次数(BACKWARD 过程中的循环迭代次数)， 表示平均每个epoch 的前向迭代次数（FORWARD 过程中的循环迭代次数）。

   

2. 当 GNN 模型训练完成之后，其推断速度也很快。

   • 对于positional GNN，其推断的计算复杂度为：
   • 对于 nonpositional nonliear GNN，其推断的计算复杂度为：
   • 对于 nonpositional linear GNN，其推断的计算复杂度为：

3. 推断阶段的主要时间消耗在计算状态 的重复计算中，每次迭代的计算代价和输入图的维度（如边的数量）成线性关系，和前馈神经网络的隐层维度成线性关系，和状态向量的维度成线性关系。

   • 线性 GNN 是一个例外。线性 GNN 的单次迭代成本是状态维度的二次关系。
   • 状态向量的收敛速度取决于具体的问题。但是 Banach 定理可以确保它是以指数级速度收敛。实验表明：通常5 到 15 次迭代足以逼近不动点。

4. 在 positional GNN 中转移函数需要执行 次，在 nonpositional nonliear GNN 中转移函数需要执行 次。虽然边的数量 通常远大于顶点数量 ，但是positional GNN 和 nonpositional nonlinear GNN 的推断计算复杂度是相近的，这是因为 的网络通常要比 的网络更复杂。

   • 在 positional GNN 中，实现 的神经网络有 个神经元，其中 为所有顶点的最大邻居数量。因为 的输入必须确保能够容纳最多的邻居。
   • 在 nonpositonal nonliear GNN 中，实现 的神经网络有 个神经元。

5. 在 nonpositonal linear GNN 中，转移函数就是一个简单的矩阵乘法，因此这部分的计算复杂度为 而不是 。

   通常线性 GNN 比非线性 GNN 速度推断速度更快，但是前者的效果更差。

6. GNN 的训练阶段要比推断阶段消耗更多时间，主要在于需要在多个epoch 中重复执行 forward 和 backward 过程。

   实验表明：forward 阶段和 backward 阶段的时间代价都差不多。类似 forward阶段的时间主要消耗在重复计算 ，backward 阶段的时间主要消耗在重复计算 。前述定理可以确保 是指数级收敛的，并且实验表明 通常很小。

7. 训练过程中，每个 epoch 的计算代价可以由上表中所有指令的计算复杂度的加权和得到，权重为指令对应的迭代次数。

   • 所有指令的计算复杂度基本上都是输入图的维度（如：边的数量）的线性函数，也是前馈神经网络隐单元维度的线性函数，也是状态维度 的线性函数。

     有几个例外，如计算 的计算复杂度都是 的平方关系。

   • 最耗时的指令是 nonpositional nonlinear GNN 中计算 ，其计算复杂度为 。

     • 实验表明，通常 是一个很小的数字。在大多数 epoch 中 ，因为雅可比矩阵 并未违反施加的约束；另一些情况中， 通常在 1~5 之间。

       因此对于较小的状态维度 ，计算 的复杂度较低。

     • 理论上，如果 非常大则可能导致 。如果同时还有 ，则这将导致计算 非常慢。但是论文表示未在实验中观察到何种情况。

1.2.4 不动点

1. GNN 的核心是不动点理论，通过顶点的消息传播使得整张图的每个顶点的状态收敛，然后在收敛的状态基础上预测。

   这里存在两个局限：

   • GNN 将顶点之间的边仅仅视为一种消息传播手段，并未区分边的功能。

   • 基于不动点的收敛会导致顶点之间的状态存在较多的消息共享，从而导致顶点状态之间过于光滑 over smooth ，这将使得顶点之间缺少区分度。

     如下图所示，每个像素点和它的上下左右、以及斜上下左右八个像素点相邻。初始时刻蓝色没有信息量，绿色、黄色、红色各有一部分信息。

     开始时刻，不同像素点的区分非常明显；在不动点的收敛过程中，所有像素点都趋向于一致，最终整个系统的信息分布比较均匀。最终，虽然每个像素点都感知到了全局信息，但是我们已经无法根据每个像素点的最终状态来区分它们。

     

1.3 实验

1. 根据 RNN 的已有经验，nonpositional 转移函数效果要优于 positional 转移函数，因此这里测试了 nonpositional linear GNN 和 nonpositional nonlinear GNN 。

   所有GNN 中涉及到的函数，如 nonpositional linear GNN 中的 ，以及 nonpositional nonlinear GNN 中的 都采用三层的前馈神经网络来实现，并使用 sigmoid 激活函数。

2. 数据集划分为训练集、验证集和测试集。

   • 如果原始数据仅包含一张大图 ，则训练集、验证集、测试集分别包含 的不同顶点。
   • 如果原始数据包含多个图 ，则每张图整个被划分到训练集、验证集、测试集之一。

   所有模型都随机执行五次并报告在测试集上指标的均值。每次执行时都随机生成训练集：以一定的概率 随机连接每一对顶点，直到图的连接性满足指定条件。

   • 对于分类问题， 为一个标量，取值范围为 。模型的评估指标为预测准确率：如果 则分类正确；否则分类不正确。

   • 对于回归问题， 为一个标量，取值范围为 。模型的评估指标为相对误差：

     

   在每轮实验中，训练最多 5000 个 epoch，每隔 20 个 epoch 就在验证集上执行一次评估。然后选择验证集损失最小的模型作为最佳模型，从而在测试集上评估。

1.3.1 子图匹配问题

1. 子图匹配问题：在更大的图 中寻找给定的子图 。即，需要学习一个函数 ：如果顶点 属于图 中的一个和 同构的子图，则 ；否则 。

   如下图所示，图 都包含子图 。顶点内的数字表示顶点的标签信息向量 （这里是一个标量）。最终学到的函数 为：如果为黑色顶点则 ，否则 。

   

2. 子图匹配问题有很多实际应用，如：目标定位、化合物检测。子图匹配问题是评估图算法的基准测试。实验表明 GNN 模型可以处理该任务。

   • 一方面 GNN 模型解决子图匹配问题的结果可能无法与该领域的专用方法相比，后者的速度更快、准确率更高。
   • 另一方面 GNN 模型是一种通用算法，可以在不经修改的情况下处理子图匹配问题的各自扩展。如：同时检测多个子图、子图的结构和标签信息向量带有噪音、待检测的目标图 是未知的且仅已知它的几个顶点。

3. 数据集：由 600 个随机图组成（边的连接概率为 ），平均划分为训练集、验证集、测试集。在每轮实验中，随机生成一个子图 ，将子图 插入到数据集的每个图中。因此每隔图 至少包含了 的一份拷贝。

   • 每个顶点包含整数标签，取值范围从 [0,10]。
   • 我们使用一个一个均值为0、标准差为 0.25 的高斯噪声添加到标签上，结果导致数据集中每个图对应的 的拷贝都不同。
   • 为了生成正确的监督目标 ，我们使用一个暴力搜索算法从每个图 中搜索 。

4. GNN 配置：

   • 所有实验中，状态向量的维度
   • 所有实验中，GNN 的所有神经网络的隐层为三层，隐层维度为 5 。

   为评估子图匹配任务中，标签信息和图结构的相对重要性，我们还应用了前馈神经网络FNN 。FNN 的隐层为三层、隐层维度为 20 、输入层维度为1、输出层维度为 1 。因此 FNN 仅仅使用标签信息 来预测监督目标 ，它并没有利用图的结构。

5. 实验结果如下图所示，其中 NL 表示 nonpositional nonlinear GNN，L 表示 nonpositional linear GNN ，FNN 表示前馈神经网络。

   结论：

   • 正负顶点的比例影响了所有方法的效果。

     • 当 接近 时，几乎所有顶点都是正样本，所有方法预测的准确率都较高。
     • 当 只有 的一半时，正负顶点比较均匀，次数所有方法预测的准确率都较低。

   • 子图规模 影响了所有方法的结果。

     因为标签只能有 11 种不同取值，当 很小时，子图的大多数顶点都可以仅仅凭借其标签来识别。因此 越小预测准确率越高，即使是在 时。

   • GNN 总是优于 FNN，这表明 GNN 可以同时利用标签内容和图的拓扑结构。

   • 非线性 GNN 略优于线性 GNN，这可能是因为非线性 GNN 实现了更为通用的模型，它的假设空间更大。

   

6. 为评估GNN 的计算复杂度和准确性，我们评估了不同顶点数、不同边数、不同隐层维度、不同状态向量维度的效果。

   在基准情况下：训练集包含10 个随机图，每个图包含20 个顶点和 40 条边；GNN 隐层维度为5，状态向量维度为 2 。

   GNN 训练 1000 个 epoch 并报告十次实验的平均结果。如预期的一样，梯度计算中需要的 CPU 时间随着顶点数量、边的数量、隐层维度呈线性增长，随着状态向量维度呈二次增长。

   • 下图为顶点数量增加时，梯度计算花费的CPU 时间。实线表示非线性GNN，虚线表示线性 GNN 。

     

   • 下图为状态向量维度增加时，梯度计算花费的 CPU 时间。实线表示非线性GNN，虚线表示线性 GNN 。

     

7. 非线性 GNN 中，梯度和状态向量维度的二次关系取决于计算雅可比矩阵 以及梯度 的时间代价。下图给出了计算梯度过程中的总时间代价。

   • 线条 -o- 给出了计算 和 的时间代价
   • 线条 -*- 给出了计算雅可比矩阵 的时间代价
   • 线条 -x- 给出了计算 的时间代价
   • 点线 ...和给出了剩下的前向计算的时间代价
   • 虚线 ---给出了剩下的反向计算的时间代价
   • 实线表示剩下的计算梯度的时间代价

   可以看到： 的计算复杂度虽然是状态向量维度的二次关系，但是实际上影响较小。实际上该项的计算复杂度依赖于参数 ：对所有的顶点 ，满足 的顶点 的数量的均值。通常它是一个很小的数值。

   

   下图给出每个epoch 中 的顶点 的数量的直方图。可以看到 的顶点 的数量通常为零，且从未超过4 。

   另外下图也给出计算稳定状态 和计算梯度（如计算 ）所需要的平均迭代次数的直方图，可以看到这些值通常也很小。

   

1.3.2 Mutagenesis问题

1. Mutagenesis 数据集：一个小型数据集，经常作为关系学习和 inductive logic programming 中的基准。它包含 230 种硝基芳香族化合物的数据，这些化合物是很多工业化学反应中的常见中间副产品。

   任务目标是学习识别 mutagenic 诱变化合物。我们将对数诱变系数 log mutagenicity 的阈值设为0，因此这个任务是一个二类分类问题。

   数据集中的每个分子都被转换为一张图：

   • 顶点表示原子、边表示原子键 atom-bond：AB 。平均的顶点数量大约为 26 。

   • 边和顶点的标签信息包括原子键 AB、原子类型、原子能量状态，以及其它全局特征。全局特征包括：

     • chemical measurement化学度量 C： 包括 lowest unoccupied molecule orbital， the water/octanol partition coefficient 。
     • precoded structural 预编码结构属性 PS 。

     另外原子键可以用于定义官能团 functional groups:FG 。

   • 在每个图中存在一个监督顶点：分子描述中的第一个原子。如果分子为诱变的，则该顶点的期望输出为1；否则该顶点的期望输出为 -1 。

   • 在这 230 个分子中，有 188 个适合线性回归分析，这部分分子被称作回归友好 regression friendly；剩下的 42 个分子称作回归不友好 regression unfriendly 。

   

2. GNN 在诱变化合物问题上的结果如下表所示。我们采用十折交叉验证进行评估：将数据集随机拆分为十份，重复实验十次，每次使用不同的部分作为测试集，剩余部分作为训练集。我们运行5 次十折交叉，并取其均值。

   在回归友好分子上的效果：

   

   在回归不友好分子上的效果：

   

   在所有分子上的效果：

   

   结论：

   • GNN 在回归不友好分子和所有分子上的效果都达到最佳，在回归友好分子上的效果达到了最新的技术水平。
   • 大多数方法在应用于整个数据集时，相对于回归不友好分子部分显示出更高的准确率。但是GNN 与此相反。这表明 GNN 可以捕获有利于解决问题，但是在回归友好分子、回归不友好分子这两部分中分布不均的模式特征。

1.3.3 Web PageRank

1. 受到谷歌的 PageRank 启发，这里我们的目标是学习一个网页排名。网页 的排名得分 定义为：

   

   其中：

   • 为顶点 的出度 out-degree
   • 为阻尼因子 damping factor
   • 为顶点 的父顶点集合

   图 以 随机生成，包含 5000 个顶点。训练集、验证集、测试集由图的不同顶点组成，其中 50 个顶点作为训练集、50 个顶点作为验证集、剩下顶点作为测试集。

   每个顶点 对应于一个二维标签 ，其中 表示顶点 是否属于两个给定的主题： 表示顶点 同时属于这两个主题； 表示顶点 仅仅属于第一个主题； 表示顶点 仅仅属于第二个主题； 表示顶点 不属于任何主题。

   需要拟合的目标target 为：

   

   其中 表示每个顶点的PageRank 得分组成的向量。

2. 这里我们使用线性 GNN 模型，因为线性 GNN 模型很自然的类似于 PageRank 线性模型。

   • 转移网络和 forcing 网络都使用三层前馈神经网络，隐层维度为5
   • 状态向量维度为
   • 输出函数为： 。其中 为三层前馈神经网络，隐层维度为 5 。

3. 下图给出了 GNN 模型的结果。其中图 (a) 给出了仅属于一个主题的结果，图 (b) 给出了其它网页的结果。

   实线表示目标 ，点线表示 GNN 模型的输出。横轴表示测试集的顶点数量，纵轴表示目标得分 。顶点按照 得分进行升序排列。

   

   下图给出学习过程中的误差。实线为训练集的误差，虚线是验证集的误差。注意：两条曲线总是非常接近，并且验证集的误差在 2400 个 epoch 之后仍在减少。这表明尽管训练集由 5000 个顶点中的 50 个组成，GNN 仍然未经历过拟合。