Question

1. 数据可以在许多应用领域中自然地用图结构graph structure 来表达，包括蛋白质组织学proteomics 、图像分析、场景描述、软件工程、自然语言处理。最简单的图结构包括单节点single node、序列sequence。但是在一些应用中，信息被组织成更复杂的图结构，如树、无环图、带环图。传统上，数据关系探索一直是归纳式逻辑编程inductive logic programming 的社区中许多研究的主题。最近，数据关系探索data relationships exploitation这个研究主题已经朝着不同的方向发展，这也是因为统计statistics和神经网络中的相关概念在这些领域中的应用。

   在机器学习中，结构化数据通常与（有监督的或者无监督的）learning 的目标相关联，例如一个函数$\tau$$ \tau $ 将一个图$\mathbf{G}$$ \mathbf G $ 和该图的一个节点$n$$ n $ 映射为一个实数向量$\tau (\mathbf{G},v)\in {\mathbb{R}}^m$$ \tau(\mathbf G,v) \in \mathbb R^m $ ，其中$m$$ m $ 为向量的维度。在本文中，图领域的应用application 通常可以分为两大类，分别称作 graph-focused 应用、node-focused 应用 。

   • 在 graph-focused 应用中，函数$\tau$$ \tau $ 独立于节点$n$$ n $ ，并且在图结构的数据集上实现分类器或回归器。

     此时每个图具有一个 representation，并且每个图具有一个 target。

     例如，可以用一个图$\mathbf{G}$$ \mathbf G $ 来建模一种化合物，图的节点代表原子（或者化学基团）、边代表将原子连接起来的化学键。如下图所示。这个函数$\tau (\mathbf{G})$$ \tau(\mathbf G) $ 可用于估计化合物引起某种疾病的概率。

     

     在下图中，图片由区域邻接图region adjacency graph 来表达，其中节点表示均匀图片强度的区域，边代表这些区域的邻接关系。在这种情况下，可以根据图片的内容通过$\tau (\mathbf{G})$$ \tau(\mathbf G) $ 将图片分为不同的类别，如城堡、汽车、人等等。

     

   • 在 node-focused 应用中，函数$\tau$$ \tau $ 取决于节点$n$$ n $ ，因此分类（或回归）取决于每个节点的属性。

     此时每个节点具有一个 representation，并且每个节点具有一个 target 。

     例如目标检测 application 包括检查图片中是否包含给定的对象，如果是，则定位给定对象的位置。这个问题可以通过一个函数$\tau$$ \tau $ 来解决，该函数根据区域邻接图是否属于目标对象，从而对区域邻接图进行节点分类。例如，下图中的黑色节点，如果对应于城堡则$\tau$$ \tau $ 输出为 1、否则$\tau$$ \tau $ 输出为 0 。

     

     另一个例子来自于网页分类。web 可以通过一个图来表达，其中节点代表网页，边代表网页之间的超链接，如下图所示。可以利用 web connectivity 以及网页内容来实现多种目的purposes,，如页面的主题分类。

     

   传统的机器学习 application 通过使用预处理 preprocessing 阶段来处理图结构化数据graph structured data ，该阶段将图结构化信息映射到更简单的 representation，如实值向量。换句话讲，预处理步骤首先将图结构化数据 "挤压squash" 为实数向量，然后使用 list-based 数据处理技术来处理 preprocessed的数据。然而，在预处理阶段，一些重要的信息（如每个节点的拓扑依赖性 topological dependency）可能会丢失，并且最终结果可能以不可预知的方式unpredictable manner 取决于预处理算法的细节。

   最近，有各种方法试图在预处理阶段尽可能地保留数据的图结构特性，其思想是：使用图节点之间的拓扑关系对底层的图结构化数据进行编码，以便在数据正式处理步骤（即预处理步骤之后的模型处理阶段）中融合图结构化信息。这组技术包括 recursive neural network: RNN、马尔科夫链Markov chain: MC，并且通常可以同时应用于 graph-focused 问题和 node-focused 问题。论文 《The Graph Neural Network Model》提出的方法扩展了这两种方法（即 RNN 和马尔科夫链），因为该方法可以直接处理图结构化信息。

   • 现有的 RNN 是以有向无环图directed acyclic graph 作为输入的神经网络模型。该方法估计函数${\phi }_{\mathbf{w}}$$ \varphi_{\mathbf w} $ 的参数$\mathbf{w}$$ \mathbf w $ ，其中函数${\phi }_{\mathbf{w}}$$ \varphi_{\mathbf w} $ 将图映射到实值向量。该方法也可以用于 node-focused application 中，此时，图必须经过预处理阶段。类似地，采用预处理阶段之后，我们可以处理某些类型的带环图。RNN 已被应用于多个问题，包括逻辑术语分类 logical term classification、化合物分类、logo 识别、网页评分、人脸定位 face localization。

     RNN 也与支持向量机有关，其中支持向量机采用特殊的 kernel 对图结构化数据进行操作，其中：

     • diffusion kernel 是基于热扩散方程heat diffusion equation 。
     • 《Marginalized kernels between labeled graphs》和 《Extensions of marginalized graph kernels》 中提出的 kernel 利用了图随机游走生成的向量。
     • 《Convolution kernels for natural language》、《Kernels for structured natural language data》、《Convolution kernels with feature selection for natural language processing tasks》 中设计的 kernel 使用了一种计算两棵树的公共子结构数量的方法。

     事实上，类似于支持向量机方法，RNN 自动将输入的图编码为内部 representation。然而，在 RNN 中内部编码是模型自动学到的，而在支持向量机中内部编码是由用户手动设计的。

   • 另一方面，马尔科夫链模型可以建模事件之间的因果关系，其中因果关系由图来表达。最近，针对特定种类马尔科夫链模型的随机游走理论已成功应用于网页排名ranking 算法的实现。互联网搜索引擎使用排名算法来衡量网页的相对重要性。这类度量值通常与其它页面特征一起被搜索引擎所利用，从而对用户 query 返回的 URL 进行排序。人们已经进行了一些尝试来扩展这些具有学习能力的模型，以便可以从训练样本中学习模型参数。这些模型能够泛化结果从而对集合中的所有网页进行评分。更一般地，人们已经提出了几种其它统计方法，这些方法假设数据集由模式 pattern、以及模式之间的关系 relationship 组成。这些技术包括：随机场random field、贝叶斯网络、统计关系学习、transductive learning、用于图处理的半监督方法。

   在论文 《The Graph Neural Network Model》 中，作者提出了一种有监督的神经网络模型，该模型同时适用于 graph-focused application 和 node-focused application。该模型将这两个现有模型（即 RNN 和马尔科夫链）统一到一个通用框架中。论文将这种新颖的神经网络模型称作图神经网络 graph neural network: GNN 。论文将证明 GNN 是 RNN 和随机游走模型的扩展，并且保留了它们的特性 characteristics 。

   • GNN 模型扩展了 RNN，因为 GNN 可以处理更通用的图，包括带环图、有向图、无向图，并且无需任何预处理步骤即可处理 node-focused application 。
   • GNN 方法通过引入 learning 算法、以及扩大可建模过程的种类从而扩展了随机游走理论。

   GNN 基于信息扩散机制 information diffusion mechanism。图由一组单元unit 来处理，每个单元对应于图上的一个节点，这些节点根据图的连通性进行链接。这些单元更新它们的状态并交换信息，直到它们到达稳定的平衡stable equilibrium 。然后，基于单元的状态unit state 计算每个节点的输出。扩散机制是受约束constrained 的，从而确保始终存在唯一的稳定平衡。

   这种实现机制已经在细胞神经网络、Hopfield 神经网络中使用。在那些神经网络模型中，连通性是根据预定义的图来指定的，网络连接本质上是循环 recurrent 的，神经元状态是通过松弛relaxation 到平衡点equilibrium point 来计算的。GNN 与那些神经网络不同之处在于：GNN 可以处理更加通用的图，并且采用更通用的扩散机制。

   在论文 《The Graph Neural Network Model》 中，作者将介绍一种学习算法，该算法在一组给定的训练样本上估计 GNN 模型的参数。此外，参数估计算法的计算代价需要被考虑。还值得一提的是，《Computation capabilities of graph neural networks》 已经证明了 GNN 展示出一种普遍的逼近特性，并且在不严厉的条件下，GNN 可以逼近图上大多数实际有用的函数$\phi$$ \varphi $ 。

1.1 模型

1. 定义图$\mathbf{G}=(\mathbf{N},\mathbf{E})$$ \mathbf G=(\mathbf N,\mathbf E) $ ，其中$\mathbf{N}$$ \mathbf N $ 为节点集合、$\mathbf{E}$$ \mathbf E $ 为边集合。边可以为有向边，也可以为无向边。对于节点$n\in \mathbf{N}$$ n\in \mathbf N $ ，定义$\text{ne}[n]$$ \text{ne}[n] $ 为其邻接节点集合（即，邻域），定义$\text{co}[n]$$ \text{co}[n] $ 为包含节点$n$$ n $ 的边的集合。

   节点和边可能含有额外的信息，这些信息统称为标签信息（它和监督学习中的标记label 不是一个概念），并以实值向量的形式来表示。

   • 定义节点$n$$ n $ 的标签为${\overrightarrow{l}}_n\in {\mathbb{R}}^{d_N}$$ \vec l_n\in \mathbb R^{d_N} $ ，定义边$(n_1,n_2)$$ (n_1,n_2) $ 的标签为${\overrightarrow{l}}_{n_1,n_2}\in {\mathbb{R}}^{d_E}$$ \vec l_{n_1,n_2} \in \mathbb R^{d_E} $ ，其中$d_N$$ d_N $ 为节点标签的维度、$d_E$$ d_E $ 为边标签的维度。
   • 定义$\overrightarrow{l}$$ \vec l $ 为图中所有标签向量（包括所有节点标签向量、所有边标签向量）拼接得到的all 标签向量。
   • 标签向量的符号遵循更一般的scheme：如果$\overrightarrow{\mathbf{y}}$$ \mathbf{\vec y} $ 是图$\mathbf{G}$$ \mathbf G $ 中的某种类型的标签向量（如节点标签向量或边标签向量），$\mathbf{S}$$ \mathbf S $ 为图$\mathbf{G}$$ \mathbf G $ 中的某个集合（如节点集合或边集合），则${\overrightarrow{\mathbf{y}}}_{\mathbf{S}}$$ \mathbf{\vec y}_\mathbf S $ 为根据集合$\mathbf{S}$$ \mathbf S $ 获得的标签向量。例如${\overrightarrow{l}}_{\text{ne}[n]}$$ \vec l_{\text{ne}[n]} $ 包含节点$n$$ n $ 的邻域节点的所有节点标签。

   注意，这里的符号定义与大多数论文的符号定义不同。

2. 节点标签通常包含节点的特征，边标签通常包含节点之间关系的特征。如下图中：节点标签可能代表区块的属性，如：面积、周长、颜色的平均强度。边标签可能代表区块region 之间的相对位置，如：重心之间的距离、轴线之间的角度。我们未对边作出任何假设，有向边和无向边都是允许的。但是，当不同类型的边共同存在于同一个图$\mathbf{G}$$ \mathbf G $ 中时，就需要区分它们。这可以通过在每条边上添加适当的标签来轻松地实现，此时，不同类型的边具有不同的标签。

   

3. 图$\mathbf{G}$$ \mathbf G $ 可以是 positional 的、或者是 nonpositional 的。nonpositional graph 是前面所讲的那些图。positional graph 与之不同，节点$n$$ n $ 的每个邻居都被分配一个 unique 的整数标识符，从而指示每个邻居的逻辑位置logical position 。 形式上，对于positional graph 中的每个节点，存在一个映射函数${\nu }_n:\text{ne}[n]\to \{1,2,\cdots ,|\mathbf{N}|\}$$ \nu_n:\text{ne}[n]\rightarrow \{1,2,\cdots,|\mathbf N|\} $ ，它为节点$n$$ n $ 的每个邻居节点$u$$ u $ 分配了一个位置 position${\nu }_n(u)$$ \nu_n(u) $ 。注意，邻居的位置可以用于隐式地存储有用的信息。例如，考虑区块邻接图region adjacency graph（如上图所示） ：可以用${\nu }_n$$ \nu_n $ 来表示区块的相对空间位置，例如，${\nu }_n$$ \nu_n $ 可能会按照顺时针的排序约定来枚举节点$n$$ n $ 的邻居。

   注意，位置信息可以通过对邻居节点分配位置编号来显式地给出，也可以通过对邻居节点进行排序从而隐式地给出。

4. 本文考虑的领域是 (graph, node) pair 的集合$\mathcal{D}=\mathcal{G}\times \mathcal{N}$$ \mathcal D = \mathcal G\times \mathcal N $ ，其中$\mathcal{G}=\{{\mathbf{G}}_1,\cdots \}$$ \mathcal G=\{\mathbf G_1,\cdots\} $ 为 graph 的集合，$\mathcal{N}=\{{\mathbf{N}}_1,\cdots \}$$ \mathcal N=\{\mathbf N_1,\cdots\} $ 为这些 graph 的节点集合的集合，即：

   $$\mathcal{L}=\{({\mathbf{G}}_i,n_{i,j},{\mathbf{t}}_{i,j})\mid {\mathbf{G}}_i=({\mathbf{N}}_i,{\mathbf{E}}_i)\in \mathcal{G},n_{i,j}\in {\mathbf{N}}_i,{\mathbf{t}}_{i,j}\in {\mathbb{R}}^m,1\le i\le p,1\le j\le q_i\}$$

   其中：${\mathbf{G}}_i$$ \mathbf G_i $ 表示第$i$$ i $ 个图，$n_{i,j}$$ n_{i,j} $ 表示图${\mathbf{G}}_i$$ \mathbf G_i $ 的第$j$$ j $ 个节点，${\mathbf{t}}_{i,j}$$ \mathbf t_{i,j} $ 表示节点$n_{i,j}$$ n_{i,j} $ 的desired target （可能为向量也可能为标量），$p\le |\mathcal{G}|$$ p\le |\mathcal G| $ ，$q_i\le |{\mathbf{N}}_i|$$ q_i\le |\mathbf N_i| $ 。

   有趣的是，$\mathcal{D}$$ \mathcal D $ 中所有的图都可以组合成一个 unique 的、断开的大图，因此可以将$\mathcal{D}$$ \mathcal D $ 视为一个 pair$\mathcal{L}=(\mathbf{G},\mathcal{T})$$ \mathcal L = (\mathbf G,\mathcal T) $ ，其中：$\mathbf{G}=(\mathbf{N},\mathbf{E})$$ \mathbf G=(\mathbf N,\mathbf E) $ 为包含所有节点和所有边的大图，$\mathcal{T}=\{(n_i,{\mathbf{t}}_i)\mid n_i\in \mathbf{N},{\mathbf{t}}_i\in {\mathcal{R}}^m,1\le i\le q\}$$ \mathcal T = \left\{\left(n_i,\mathbf t_i\right)\mid n_i\in \mathbf N,\mathbf t_i\in \mathcal R^m,1\le i\le q\right\} $ 。值得一提的是，这个紧凑的定义不仅因为它简单易用，而且它还直接捕捉到了一些问题的本质，其中领域domain 仅由一个图组成，如大部分的 web 网络（如下图所示）。

   

1.1.1 思想

1. 我们所提出方法的直观想法是：图中的节点代表对象或概念，而边代表它们之间的关系。每个概念自然地由它的特征和相关的概念来定义。因此，我们可以可以将一个状态向量state vector${\overrightarrow{\mathbf{x}}}_n\in {\mathcal{R}}^s$$ \mathbf{\vec x}_n\in \mathcal R^s $ 关联到每个节点$n$$ n $ 上，其中${\overrightarrow{\mathbf{x}}}_n$$ \mathbf{\vec x}_n $ 基于节点$n$$ n $ 的邻域信息来构建（如下图所示），$s$$ s $ 为状态向量的维度。状态向量${\overrightarrow{\mathbf{x}}}_n$$ \mathbf{\vec x}_n $ 包含由$n$$ n $ 表示的概念的 representation，并可用于产生输出${\overrightarrow{\mathbf{o}}}_n$$ \mathbf{\vec o}_n $ （即，这个概念能决定什么）。

   令$f_{\mathbf{w}}(\cdot )$$ f_{\mathbf w}(\cdot) $ 为一个参数化parametric的函数，称之为局部转移函数 local transition function ，用于表示节点对其邻域的依赖性。令$g_{\mathbf{w}}(\cdot )$$ g_{\mathbf w}(\cdot) $ 为另一个参数化的函数，称之为局部输出函数 local output function，用于描述如何产生输出。那么${\overrightarrow{\mathbf{x}}}_n$$ \mathbf{\vec x}_n $ 和${\overrightarrow{\mathbf{o}}}_n$$ \mathbf{\vec o}_n $ 的定义如下：

   $$\begin{array}{c}{\overrightarrow{\mathbf{x}}}_n=f_{\mathbf{w}}({\overrightarrow{l}}_n,{\overrightarrow{l}}_{\text{co}[n]},{\overrightarrow{\mathbf{x}}}_{\text{ne}[n]},{\overrightarrow{l}}_{\text{ne}[n]})\\ {\overrightarrow{\mathbf{o}}}_n=g_{\mathbf{w}}({\overrightarrow{\mathbf{x}}}_n,{\overrightarrow{l}}_n)\end{array}$$

   其中：

   • ${\overrightarrow{l}}_n$$ \vec l_n $ 为节点$n$$ n $ 的标签信息向量。
   • ${\overrightarrow{l}}_{\text{co}[n]}$$ \vec l_{\text{co}[n]} $ 为包含节点$n$$ n $ 的所有边的标签信息向量拼接的向量。
   • ${\overrightarrow{\mathbf{x}}}_{\text{ne}[n]}$$ \mathbf{\vec x}_{\text{ne}[n]} $ 为节点$n$$ n $ 的所有邻居的状态向量拼接的向量。
   • ${\overrightarrow{l}}_{\text{ne}[n]}$$ {\vec l}_{\text{ne}[n]} $ 为节点$n$$ n $ 的所有邻居的标签信息向量拼接的向量。

   注意：这里有递归定义，其中节点$n$$ n $ 的状态向量${\overrightarrow{\mathbf{x}}}_n$$ \mathbf{\vec x}_n $ 依赖于其邻居的状态向量集合${\overrightarrow{\mathbf{x}}}_{\text{ne}[n]}$$ \mathbf{\vec x}_{\text{ne}[n]} $ 。而邻居的状态向量又依赖于邻居的邻居的状态向量集合。

   注意：这里的邻域依赖性使得计算状态向量所依赖的节点规模迅速膨胀。假设平均邻域大小为 10 个节点，如果最多依赖于 5 阶邻域，那么计算每个状态向量需要依赖于 5 阶邻域内的 10 万个邻域节点。

   备注：

   • 备注一：可以采用不同的邻域概念。例如，人们可能希望删除标签${\overrightarrow{l}}_{\text{ne}[n]}$$ \vec l_{\text{ne}[n]} $ ，因为${\overrightarrow{l}}_{\text{ne}[n]}$$ \vec l_{\text{ne}[n]} $ 的信息可能隐含在${\overrightarrow{\mathbf{x}}}_{\text{ne}[n]}$$ \mathbf{\vec x}_{\text{ne}[n]} $ 中。此外，邻域可能包含距$n$$ n $ 2-hop 或者多个 hop 的节点。

   • 备注二：上式用于无向图。在处理有向图时，函数$f_{\mathbf{w}}(\cdot )$$ f_{\mathbf w}(\cdot) $ 也可以接受链接的方向作为输入。我们引入一个变量$d_e,\mathit{e}\in \text{co}[n]$$ d_e, \mathit e \in \text{co}[n] $ ：如果边$e$$ e $ 的终点为$n$$ n $ 则$d_e=1$$ d_e = 1 $ ，如果边$e$$ e $ 的起点为$n$$ n $ 则$d_e=0$$ d_e = 0 $ 。则有：

     $${\overrightarrow{\mathbf{x}}}_n=f_{\mathbf{w}}({\overrightarrow{l}}_n,{\overrightarrow{l}}_{\text{co}[n]},{\mathbf{d}}_{\text{co}[n]},{\overrightarrow{\mathbf{x}}}_{\text{ne}[n]},{\overrightarrow{l}}_{\text{ne}[n]})$$

     本文中为了保持符号紧凑，我们使用无向图的形式。然而，除非特殊说明，否则本文中提出的所有结果也适用于有向图、以及混合有向与无向的图。

   • 备注三：通常而言，转移函数$f_{\mathbf{w}}(\cdot )$$ f_{\mathbf w}(\cdot) $ 和输出函数$g_{\mathbf{w}}(\cdot )$$ g_{\mathbf w}(\cdot) $ 以及它们的参数parameters 可能都依赖于节点$n$$ n $ 。但是在一些场景中，节点分为不同类型，并且不同类型的节点有不同的转移函数、输出函数、以及它们的参数。假设节点$n$$ n $ 的类别为$k_n$$ k_n $ ，转移函数为$f_{\mathbf{w}}^{k_n}(\cdot )$$ f_{\mathbf w}^{k_n}(\cdot) $ ，输出函数为$g_{\mathbf{w}}^{k_n}(\cdot )$$ g_{\mathbf w}^{k_n}(\cdot) $ ，对应参数为${\mathbf{w}}_{k_n}$$ \mathbf w_{k_n} $ ，则有：

     $$\begin{array}{c}{\overrightarrow{\mathbf{x}}}_n=f_{{\mathbf{w}}_{k_n}}^{k_n}({\overrightarrow{l}}_n,{\overrightarrow{l}}_{\text{co}[n]},{\overrightarrow{\mathbf{x}}}_{\text{ne}[n]},{\overrightarrow{l}}_{\text{ne}[n]})\\ {\overrightarrow{\mathbf{o}}}_n=g_{{\mathbf{w}}_{k_n}}^{k_n}({\overrightarrow{\mathbf{x}}}_n,{\overrightarrow{l}}_n)\end{array}$$

     然而为了简单起见，我们对所有节点共享相同的转移函数和输出函数（包括它们的参数）。

     如果没有参数共享则模型的容量太大导致难以训练且很容易过拟合。

   

2. 令$\overrightarrow{\mathbf{x}},\overrightarrow{\mathbf{o}},\overrightarrow{l},{\overrightarrow{l}}_{\mathbf{N}}$$ \mathbf{\vec x}, \mathbf{\vec o},\vec l,\vec l_{\mathbf N} $ 分别代表所有节点状态向量的拼接、所有节点输出向量的拼接、所有标签（包含节点标签以及边的标签）向量的拼接、所有节点标签向量的拼接（例如，$\overrightarrow{\mathbf{x}}={[{\overrightarrow{\mathbf{x}}}_1^{\mathrm{\top }},\cdots ,{\overrightarrow{\mathbf{x}}}_{|\mathbf{N}|}^{\mathrm{\top }}]}^{\mathrm{\top }}$$ \mathbf{\vec x}=\left[\mathbf{\vec x}_1^\top,\cdots,\mathbf{\vec x}_{|\mathbf N|}^\top\right]^\top $ ），则有：

   $$\begin{array}{c}\overrightarrow{\mathbf{x}}=F_{\mathbf{w}}(\overrightarrow{\mathbf{x}},\overrightarrow{l})\\ \overrightarrow{\mathbf{o}}=G_{\mathbf{w}}(\overrightarrow{\mathbf{x}},{\overrightarrow{l}}_{\mathbf{N}})\end{array}$$

   其中：

   • $F_{\mathbf{w}}(\cdot )$$ F_{\mathbf w}(\cdot) $ 称作全局转移函数 global transition fucntion，它由$|\mathbf{N}|$$ |\mathbf N| $ 个$f_{\mathbf{w}}(\cdot )$$ f_{\mathbf w}(\cdot) $ 组成。
   • $G_{\mathbf{w}}(\cdot )$$ G_{\mathbf w}(\cdot) $ 称作全局输出函数 global output function ，它由$|\mathbf{N}|$$ |\mathbf N| $ 个$g_{\mathbf{w}}(\cdot )$$ g_{\mathbf w}(\cdot) $ 组成。

   令图和节点的 pair 对的集合为$\mathcal{D}=\mathcal{G}\times \mathcal{N}$$ \mathcal D = \mathcal G\times \mathcal N $ ，其中$\mathcal{G}=\{{\mathbf{G}}_1,\cdots \}$$ \mathcal G=\{\mathbf G_1,\cdots\} $ 为所有图的集合，$\mathbf{N}=\{{\mathbf{N}}_1,\cdots \}$$ \mathbf N=\{\mathbf N_1,\cdots\} $ 为这些图中所有节点的集合。全局转移函数和全局输出函数定义了一个映射${\phi }_{\mathbf{w}}:\mathcal{D}\to {\mathcal{R}}^m$$ \varphi_{\mathbf w}: \mathcal D \rightarrow \mathcal R^m $ ，它以一个图作为输入，然后对每个节点$n$$ n $ 返回一个输出${\overrightarrow{\mathbf{o}}}_n$$ \mathbf{\vec o}_n $ 。

   Banach 不动点理论 fixed point theorem 为上述方程解的存在性和唯一性提供了理论依据。根据 Banach 不动点理论，当$F_{\mathbf{w}}(\cdot )$$ F_{\mathbf w}(\cdot) $ 满足以下条件时，方程$\overrightarrow{\mathbf{x}}=F_{\mathbf{w}}(\overrightarrow{\mathbf{x}},\overrightarrow{l})$$ \mathbf{\vec x} = F_{\mathbf w}\left(\mathbf{\vec x}, {\vec l}\right) $ 存在唯一解：$F_{\mathbf{w}}(\cdot )$$ F_{\mathbf w}(\cdot) $ 是一个收缩映射 contraction map 。即存在$\mu ,0\le \mu <1$$ \mu, 0\le\mu\lt 1 $ ，使得对任意$\overrightarrow{\mathbf{x}},\overrightarrow{\mathbf{y}}$$ \mathbf{\vec x}, \mathbf{\vec y} $ 都有：

   $$\Vert F_{\mathbf{w}}(\overrightarrow{\mathbf{x}},\overrightarrow{l})-F_{\mathbf{w}}(\overrightarrow{\mathbf{y}},\overrightarrow{l})\Vert \le \mu \Vert \overrightarrow{\mathbf{x}}-\overrightarrow{\mathbf{y}}\Vert$$

   其中$||\cdot ||$$ ||\cdot|| $ 表示向量范数。

   本文中我们假设$F_{\mathbf{w}}(\cdot )$$ F_{\mathbf w}(\cdot) $ 是一个收缩映射。实际上在 GNN 模型中，这个条件是通过适当的选择转移函数来实现的。

3. 上述公式能够同时处理位置图positional graph和非位置图nonpositional graph 。

   • 对于位置图，$f_{\mathbf{w}}(\cdot )$$ f_{\mathbf w}(\cdot) $ 必须接收每个邻域节点的位置作为额外的输入。实际中我们可以根据邻居的位置进行排序，然后对${\overrightarrow{l}}_{\text{co}[n]},{\overrightarrow{\mathbf{x}}}_{\text{ne}[n]},{\overrightarrow{l}}_{\text{ne}[n]}$$ \vec l_{\text{co}[n]}, \mathbf{\vec x}_{\text{ne}[n]}, \vec l_{\text{ne}[n]} $ 按照排序之后的顺序进行拼接。如果在某些位置处的邻居不存在，则需要填充 null 值。例如：

     $${\overrightarrow{\mathbf{x}}}_{\text{ne}[n]}={[{\overrightarrow{\mathbf{y}}}_1^{\mathrm{\top }},\cdots ,{\overrightarrow{\mathbf{y}}}_M^{\mathrm{\top }}]}^{\mathrm{\top }}$$

     其中：

     • $M=\underset{n,u}{max}{\nu }_n(u)$$ M = \max_{n,u}\nu_n(u) $ 为所有节点的最大邻居数。

     • ${\overrightarrow{\mathbf{y}}}_i$$ \mathbf{\vec y}_i $ 为第$i$$ i $ 个位置邻居的状态向量：

       $$\begin{array}{c}{\overrightarrow{\mathbf{y}}}_i=\{\begin{array}{ll}{\overrightarrow{\mathbf{x}}}_u& \text{if}(i={\nu }_n(u))\\ {\overrightarrow{\mathbf{x}}}_0& \text{else}\end{array}\end{array}$$

       即：如果$u$$ u $ 为节点$n$$ n $ 的第$i$$ i $ 个邻居节点，则${\overrightarrow{\mathbf{y}}}_i={\overrightarrow{\mathbf{x}}}_u$$ \mathbf{\vec y}_i = \mathbf{\vec x}_u $ ；如果节点$n$$ n $ 没有第$i$$ i $ 个邻居节点，则${\overrightarrow{\mathbf{y}}}_i$$ \mathbf{\vec y}_i $ 为null 值${\overrightarrow{\mathbf{x}}}_0$$ \mathbf{\vec x}_0 $ 。

   • 对于位置无关的图，我们可以将$f_{\mathbf{w}}(\cdot )$$ f_{\mathbf w}(\cdot) $ 替换为：

     $${\overrightarrow{\mathbf{x}}}_n=\sum _{u\in \text{ne}[n]}{h}_{\mathbf{w}}({\overrightarrow{l}}_n,{\overrightarrow{l}}_{(n,u)},{\overrightarrow{\mathbf{x}}}_u,{\overrightarrow{l}}_u)$$

     其中$h_{\mathbf{w}}(\cdot )$$ h_{\mathbf w}(\cdot) $ 为待学习的函数，它和邻居节点的数量和位置无关。这种形式被称作 nonpositional form，而原始形式被称作 positional form。

     注意，这里对邻居节点采用 sum 聚合。也可以采用 max 聚合或者 attention 聚合。

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

   • 求解以下方程的算法：

     $$\begin{array}{c}{\overrightarrow{\mathbf{x}}}_n=f_{\mathbf{w}}({\overrightarrow{l}}_n,{\overrightarrow{l}}_{\text{co}[n]},{\overrightarrow{\mathbf{x}}}_{\text{ne}[n]},{\overrightarrow{l}}_{\text{ne}[n]})\\ {\overrightarrow{\mathbf{o}}}_n=g_{\mathbf{w}}({\overrightarrow{\mathbf{x}}}_n,{\overrightarrow{l}}_n)\end{array}$$

   • 从训练集中学习$f_{\mathbf{w}}(\cdot )$$ f_{\mathbf w}(\cdot) $ 和$g_{\mathbf{w}}(\cdot )$$ g_{\mathbf w}(\cdot) $ 参数的学习算法。

   • $f_{\mathbf{w}}(\cdot )$$ f_{\mathbf w}(\cdot) $ 和$g_{\mathbf{w}}(\cdot )$$ g_{\mathbf w}(\cdot) $ 的实现方式，即：解空间。

1.1.2 方程求解算法

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

   $$\overrightarrow{\mathbf{x}}(t+1)=F_{\mathbf{w}}(\overrightarrow{\mathbf{x}}(t),\overrightarrow{l})$$

   其中$\overrightarrow{\mathbf{x}}(t)$$ \mathbf{\vec x}(t) $ 表示状态$\overrightarrow{\mathbf{x}}$$ \mathbf{\vec x} $ 的第$t$$ t $ 次迭代值。

   对于任意初始值$\overrightarrow{\mathbf{x}}(0)$$ \mathbf{\vec x}(0) $ ，上式指数级收敛到方程$\overrightarrow{\mathbf{x}}=F_{\mathbf{w}}(\overrightarrow{\mathbf{x}},\overrightarrow{l})$$ \mathbf{\vec x} = F_{\mathbf w}\left(\mathbf{\vec x}, {\vec l}\right) $ ​ 的解。我们将$\overrightarrow{\mathbf{x}}(t)$$ \mathbf{\vec x}(t) $ 视为状态向量，它由转移函数$F_{\mathbf{w}}(\cdot )$$ F_{\mathbf w}(\cdot) $ 来更新。因此输出向量${\overrightarrow{\mathbf{o}}}_n(t)$$ \mathbf{\vec o}_n(t) $ 和状态向量${\overrightarrow{\mathbf{x}}}_n(t)$$ \mathbf{\vec x}_n(t) $ 的更新方程为：

   $$\begin{array}{c}{\overrightarrow{\mathbf{x}}}_n(t+1)=f_{\mathbf{w}}({\overrightarrow{l}}_n,{\overrightarrow{l}}_{\text{co}[n]},{\overrightarrow{\mathbf{x}}}_{\text{ne}[n]}(t),{\overrightarrow{l}}_{\text{ne}[n]})\\ {\overrightarrow{\mathbf{o}}}_n(t)=g_{\mathbf{w}}({\overrightarrow{\mathbf{x}}}_n(t),{\overrightarrow{l}}_n),n\in \mathbf{N}\end{array}$$

   这可以解释为由很多处理单元unit 组成的神经网络，每个处理单元通过$f_{\mathbf{w}}(\cdot )$$ f_{\mathbf w}(\cdot) $ 计算其状态，并通过$g_{\mathbf{w}}(\cdot )$$ g_{\mathbf w}(\cdot) $ 计算其输出。这个神经网络被称作编码网络 encoding network，它类似于 RNN 的编码网络。在编码网络中，每个单元根据邻居单元的状态、当前节点的信息、邻居节点的信息、边的信息，通过$f_{\mathbf{w}}(\cdot )$$ f_{\mathbf w}(\cdot) $ 计算下一个时刻的状态${\overrightarrow{\mathbf{x}}}_n(t+1)$$ \mathbf{\vec x}_n(t+1) $ 。

2. 当$f_{\mathbf{w}}(\cdot )$$ f_{\mathbf w}(\cdot) $ 和$g_{\mathbf{w}}(\cdot )$$ g_{\mathbf w}(\cdot) $ 通过前馈神经网络实现时，编码网络就成为 RNN ，其中神经元之间的连接可以分为内部连接internal connection 和外部连接external connection ：内部连接由实现处理单元的神经网络架构（如前馈神经网络）决定，外部连接由图的边来决定。

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

   内部连接决定$f_{\mathbf{w}}(\cdot )$$ f_\mathbf w(\cdot) $ 如何更新状态${\overrightarrow{\mathbf{x}}}_n(t)$$ \mathbf{\vec x}_n(t) $ ，外部连接决定节点之间的依赖关系。

   

1.1.3 参数学习算法

1. 假设训练集为：

   $$\begin{array}{c}\mathcal{L}=\{({\mathbf{G}}_i,n_{i,j},{\mathbf{t}}_{i,j})\mid {\mathbf{G}}_i=({\mathbf{N}}_i,{\mathbf{E}}_i)\in \mathcal{G},n_{i,j}\in {\mathbf{N}}_i,{\mathbf{t}}_{i,j}\in {\mathbb{R}}^m,1\le i\le p,1\le j\le q_i\}\\ p\le |\mathcal{G}|,q_i\le |{\mathbf{N}}_i|\end{array}$$

   其中：${\mathbf{G}}_i$$ \mathbf G_i $ 表示第$i$$ i $ 个图，${\mathbf{N}}_i$$ \mathbf N_i $ 表示第$i$$ i $ 个图的节点集合，${\mathbf{E}}_i$$ \mathbf E_i $ 表示第$i$$ i $ 个图的边集合，$n_{i,j}$$ n_{i,j} $ 表示第$i$$ i $ 个图的第$j$$ j $ 个节点，${\mathbf{t}}_{i,j}$$ \mathbf t_{i,j} $ 表示节点$n_{i,j}$$ n_{i,j} $ 的监督信息target （可能为标量可能为向量），$q_i$$ q_i $ 为图${\mathbf{G}}_i$$ \mathbf G_i $ 中的标记样本数量，$p$$ p $ 为数据集中图的数量。

   • 对于 graph-focused 任务，可以引入一个和任务目标相关的、特殊的节点，只有该节点包含监督信息，即$q_i=1$$ q_i = 1 $ 。
   • 对于node-focused 任务，每个节点都可以包含监督信息。

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

   $$e_{\mathbf{w}}=\sum _{i=1}^p\sum _{j=1}^{q_i}{\Vert {\mathbf{t}}_{i,j}-{\phi }_{\mathbf{w}}({\mathbf{G}}_i,n_{i,j})\Vert }_2^2$$

   其中${\phi }_{\mathbf{w}}(\cdot )$$ \varphi_\mathbf{w}(\cdot) $ 为近似函数 approximate function` 。

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

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

   • 通过下面的迭代公式求解求解${\overrightarrow{\mathbf{x}}}_n(t)$$ \mathbf{\vec x}_n(t) $ ，直到时间$T$$ T $ ：

     $$\begin{array}{c}{\overrightarrow{\mathbf{x}}}_n(t+1)=f_{\mathbf{w}}({\overrightarrow{l}}_n,{\overrightarrow{l}}_{\text{co}[n]},{\overrightarrow{\mathbf{x}}}_{\text{ne}[n]}(t),{\overrightarrow{l}}_{\text{ne}[n]})\\ {\overrightarrow{\mathbf{o}}}_n(t)=g_{\mathbf{w}}({\overrightarrow{\mathbf{x}}}_n(t),{\overrightarrow{l}}_n),n\in \mathbf{N}\end{array}$$

     其解接近$\overrightarrow{\mathbf{x}}=F_{\mathbf{w}}(\overrightarrow{\mathbf{x}},\overrightarrow{l})$$ \mathbf{\vec x} = F_{\mathbf w}\left(\mathbf{\vec x}, {\vec l}\right) $ 的不动点${\overrightarrow{\mathbf{x}}}^{\ast }$$ \mathbf{\vec x}^* $ ，即：$\overrightarrow{\mathbf{x}}(T)\simeq {\overrightarrow{\mathbf{x}}}^{\ast }$$ \mathbf{\vec x}(T) \simeq \mathbf{\vec x}^* $ 。

     注意：这一步要求$F_{\mathbf{w}}(\cdot )$$ F_{\mathbf w}(\cdot) $ 是一个压缩映射，从而保证方程能够收敛到一个不动点。

   • 求解梯度${\mathrm{\nabla }}_{\mathbf{w}}{e}_{\mathbf{w}}$$ \nabla_{\mathbf{ w}} e_{\mathbf w} $ 。

   • 通过梯度来更新参数$\mathbf{w}$$ \mathbf w $ 。

3. 梯度${\mathrm{\nabla }}_{\mathbf{w}}{e}_{\mathbf{w}}$$ \nabla_{\mathbf{ w}} e_{\mathbf w} $ 的计算可以利用 GNN 中发生的扩散过程diffusion process以非常高效的方式进行。这种扩散过程与 RNN 中发生的扩散过程非常相似，而后者是基于backpropagation-through-time: BPTT 算法计算梯度的。在这种情况下，编码网络从时刻$T$$ T $ 展开unfold 到初始时刻$t_0$$ t_0 $ 。展开图如上图所示，每一层对应于一个时刻，并且包含编码网络中所有单元unit$f_{\mathbf{w}}(\cdot )$$ f_{\mathbf w}(\cdot) $ 的副本。连续两层之间按照图的连通性进行链接。对应于时刻$T$$ T $ 的最后一层也包括单元$g_{\mathbf{w}}(\cdot )$$ g_{\mathbf w}(\cdot) $ 并计算网络的输出。

   BPTT 是在展开图上执行传统的反向传播算法。 首先计算时间步$T$$ T $ 的损失函数，以及损失函数在每个时间步$t$$ t $ 相对于$f_{\mathbf{w}}(\cdot )$$ f_{\mathbf w}(\cdot) $ 和$g_{\mathbf{w}}(\cdot )$$ g_{\mathbf w}(\cdot) $ 的梯度。最终${\mathrm{\nabla }}_{\mathbf{w}}{e}_{\mathbf{w}}(T)$$ \nabla_{\mathbf{ w}} e_{\mathbf w}(T) $ 由所有时间步的梯度之和得到。然而，BPTT 要求存储每个单元在每个时间步$t$$ t $ 的状态$\overrightarrow{\mathbf{x}}(t)$$ \mathbf {\vec x}(t) $ ，当$T-t_0$$ T-t_0 $ 非常大时内存需求太大。为解决该问题，我们基于 Almeida-Pineda 算法提出了一个非常高效的处理方式：由于我们假设状态向量$\overrightarrow{\mathbf{x}}(t)$$ \mathbf{\vec x}(t) $ 最终收敛到不动点${\overrightarrow{\mathbf{x}}}^{\ast }$$ \mathbf{\vec x}^* $ ，因此我们假设对于任意$t\ge t_0$$ t\ge t_0 $ 都有$\overrightarrow{\mathbf{x}}(t)={\overrightarrow{\mathbf{x}}}^{\ast }$$ \mathbf{\vec x}(t) = \mathbf{\vec x}^* $ 。因此 BPTT 算法仅需要存储${\overrightarrow{\mathbf{x}}}^{\ast }$$ \mathbf{\vec x}^* $ 即可。

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

   • 定理（可微性Differentiability）：如果全局转移函数$F_{\mathbf{w}}(\overrightarrow{\mathbf{x}},\overrightarrow{l})$$ F_{\mathbf w}\left(\mathbf{\vec x}, {\vec l}\right) $ 和全局输出函数$G_{\mathbf{w}}(\overrightarrow{\mathbf{x}},{\overrightarrow{l}}_{\mathbf{N}})$$ G_{\mathbf w}\left(\mathbf{\vec x}, {\vec l}_\mathbf N\right) $ 对于状态$\overrightarrow{\mathbf{x}}$$ \mathbf{\vec x} $ 和参数$\mathbf{w}$$ \mathbf{w} $ 都是连续可微的，则${\phi }_{\mathbf{w}}$$ \varphi_{\mathbf w} $ 对于参数$\mathbf{w}$$ \mathbf{w} $ 也是连续可微的。

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

   • 定理：如果全局转移函数$F_{\mathbf{w}}(\overrightarrow{\mathbf{x}},\overrightarrow{l})$$ F_{\mathbf w}\left(\mathbf{\vec x}, {\vec l}\right) $ 和全局输出函数$G_{\mathbf{w}}(\overrightarrow{\mathbf{x}},{\overrightarrow{l}}_{\mathbf{N}})$$ G_{\mathbf w}\left(\mathbf{\vec x}, {\vec l}_\mathbf N\right) $ 对于状态$\overrightarrow{\mathbf{x}}$$ \mathbf{\vec x} $ 和参数$\mathbf{w}$$ \mathbf{w} $ 都是连续可微的，定义$\overrightarrow{\mathbf{z}}(t)\in {\mathcal{R}}^s$$ \mathbf{\vec z}(t) \in \mathcal R^s $ 为：

     $$\overrightarrow{\mathbf{z}}(t)={\left(\frac{\partial F_{\mathbf{w}}(\overrightarrow{\mathbf{x}},\overrightarrow{l})}{\partial \overrightarrow{\mathbf{x}}}\right)}^{\mathrm{\top }}\overrightarrow{\mathbf{z}}(t+1)+{\left(\frac{\partial G_{\mathbf{w}}(\overrightarrow{\mathbf{x}},{\overrightarrow{l}}_{\mathbf{N}})}{\partial \overrightarrow{\mathbf{x}}}\right)}^{\mathrm{\top }}{\mathrm{\nabla }}_{\overrightarrow{\mathbf{o}}}{e}_{\mathbf{w}}(t)$$

     则序列$\overrightarrow{\mathbf{z}}(T),\overrightarrow{\mathbf{z}}(T-1),\cdots$$ \mathbf{\vec z}(T),\mathbf{\vec z}(T-1),\cdots $ 以指数级收敛到一个向量${\overrightarrow{\mathbf{z}}}^{\ast }=\underset{t\to -\mathrm{\infty }}{lim}\overrightarrow{\mathbf{z}}(t)$$ \mathbf{\vec z}^* = \lim_{t\rightarrow -\infty} \mathbf{\vec z}(t) $ ，且收敛结果和初始状态$\overrightarrow{\mathbf{z}}(T)$$ \mathbf{\vec z}(T) $ 无关。

     更进一步有：

     $${\mathrm{\nabla }}_{\mathbf{w}}{e}_{\mathbf{w}}={\left(\frac{\partial G_{\mathbf{w}}({\overrightarrow{\mathbf{x}}}^{\ast },{\overrightarrow{l}}_{\mathbf{N}})}{\partial \mathbf{w}}\right)}^{\mathrm{\top }}{\mathrm{\nabla }}_{\overrightarrow{\mathbf{o}}}{e}_{\mathbf{w}}+{\left(\frac{\partial F_{\mathbf{w}}({\overrightarrow{\mathbf{x}}}^{\ast },\overrightarrow{l})}{\partial \mathbf{w}}\right)}^{\mathrm{\top }}{\overrightarrow{\mathbf{z}}}^{\ast }$$

     其中${\overrightarrow{\mathbf{x}}}^{\ast }$$ \mathbf{\vec x}^* $ 为GNN 的不动点，${\overrightarrow{\mathbf{z}}}^{\ast }$$ \mathbf{\vec z}^* $ 为上述收敛的向量。

     证明见论文原文。

     第一项表示输出函数$G_{\mathbf{w}}(\cdot )$$ G_{\mathbf w}(\cdot) $ 对于梯度的贡献，反向传播的梯度在通过$g_{\mathbf{w}}(\cdot )$$ g_{\mathbf w}(\cdot) $ 的 layer 时计算这一项。第二项表示转移函数$F_{\mathbf{w}}(\cdot )$$ F_{\mathbf w}(\cdot) $ 对于梯度的贡献，反向传播的梯度在通过$f_{\mathbf{w}}(\cdot )$$ f_{\mathbf w}(\cdot) $ 的 layer 时计算这一项。

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

   • FORWARD前向计算部分：前向计算部分用于计算状态向量${\overrightarrow{\mathbf{x}}}^{\ast }$$ \mathbf{\vec x}^* $ ，即寻找不动点。该部分迭代直到$\Vert \overrightarrow{\mathbf{x}}(t)-\overrightarrow{\mathbf{x}}(t-1)\Vert$$ \left\|\mathbf{\vec x}(t) - \mathbf{\vec x}(t-1)\right\| $ 小于给定的阈值。
   • BACKWARD 反向计算部分：反向计算部分用于计算梯度${\mathrm{\nabla }}_{\mathbf{w}}{e}_{\mathbf{w}}$$ \nabla_{\mathbf{w}} e_{\mathbf w} $ 。该部分迭代直到$\Vert \overrightarrow{\mathbf{z}}(t-1)-\overrightarrow{\mathbf{z}}(t)\Vert$$ \left\|\mathbf{\vec z}(t-1) - \mathbf{\vec z}(t)\right\| $ 小于给定的阈值。
   • MAIN 部分：该部分用于求解参数。该部分更新权重$\mathbf{w}$$ \mathbf{w} $ 直到满足迭代的停止标准。

5. FORWARD 部分：

   • 输入：图$\mathbf{G}=(\mathbf{N},\mathbf{E})$$ \mathbf G = (\mathbf N,\mathbf E) $ ，当前参数$\mathbf{w}$$ \mathbf{w} $ ，迭代停止条件${ϵ}_f$$ \epsilon_f $

   • 输出：不动点${\overrightarrow{\mathbf{x}}}^{\ast }$$ \mathbf{\vec x}^* $

   • 算法步骤：

     • 随机初始化$\overrightarrow{\mathbf{x}}(0)$$ \mathbf{\vec x}(0) $ ，令$t=0$$ t=0 $ 。

     • 循环迭代，直到满足$\Vert \overrightarrow{\mathbf{x}}(t)-\overrightarrow{\mathbf{x}}(t-1)\Vert \le {ϵ}_f$$ \left\|\mathbf{\vec x}(t) - \mathbf{\vec x}(t-1)\right\|\le \epsilon_f $ 。迭代步骤为：

       • 计算$\overrightarrow{\mathbf{x}}(t+1)$$ \mathbf{\vec x}(t+1) $ ：$\overrightarrow{\mathbf{x}}(t+1)=F_{\mathbf{w}}(\overrightarrow{\mathbf{x}}(t),\overrightarrow{l})$$ \mathbf{\vec x}(t+1) = F_{\mathbf w}\left(\mathbf{\vec x}(t),\vec l\right) $ 。
       • 令$t=t+1$$ t = t+1 $ 。

     • 返回${\overrightarrow{\mathbf{x}}}^{\ast }(t)$$ \mathbf{\vec x}^*(t) $ 。

6. BACKWARD 部分：

   • 输入：图$\mathbf{G}=(\mathbf{N},\mathbf{E})$$ \mathbf G=(\mathbf N,\mathbf E) $ ，不动点${\overrightarrow{\mathbf{x}}}^{\ast }$$ \mathbf{\vec x}^* $ ，当前参数$\mathbf{w}$$ \mathbf{w} $ ，迭代停止条件${ϵ}_b$$ \epsilon_b $

   • 输出：梯度${\mathrm{\nabla }}_{\mathbf{w}}{e}_{\mathbf{w}}$$ \nabla_{\mathbf{w}}e_{\mathbf w} $

   • 算法步骤：

     • 定义：

       $$\overrightarrow{\mathbf{o}}=G_{\mathbf{w}}({\overrightarrow{\mathbf{x}}}^{\ast },{\overrightarrow{l}}_{\mathbf{N}})\mathbf{A}={\left(\frac{\partial F_{\mathbf{w}}({\overrightarrow{\mathbf{x}}}^{\ast },\overrightarrow{l})}{\partial \overrightarrow{\mathbf{x}}}\right)}^{\mathrm{\top }},\overrightarrow{\mathbf{b}}={\left(\frac{G_{\mathbf{w}}({\overrightarrow{\mathbf{x}}}^{\ast },{\overrightarrow{l}}_{\mathbf{N}})}{\partial \overrightarrow{\mathbf{x}}}\right)}^{\mathrm{\top }}{\mathrm{\nabla }}_{\overrightarrow{\mathbf{o}}}{e}_{\mathbf{w}}$$

     • 随机初始化$\overrightarrow{\mathbf{z}}(T)$$ \mathbf{\vec z}(T) $ ，令$t=T$$ t = T $ 。

     • 循环迭代，直到满足$\Vert \overrightarrow{\mathbf{z}}(t-1)-\overrightarrow{\mathbf{z}}(t)\Vert \le {ϵ}_b$$ \left\|\mathbf{\vec z}(t-1) - \mathbf{\vec z}(t)\right\|\le \epsilon_b $ 从而得到收敛的${\overrightarrow{\mathbf{z}}}^{\ast }$$ \mathbf{\vec z}^* $ 。迭代步骤为：

       • 更新$\overrightarrow{\mathbf{z}}(t)$$ \mathbf{\vec z}(t) $ ：$\overrightarrow{\mathbf{z}}(t)=\mathbf{A}\overrightarrow{\mathbf{z}}(t+1)+\overrightarrow{\mathbf{b}}$$ \mathbf{\vec z}(t) = \mathbf A\mathbf{\vec z}(t+1) + \mathbf{\vec b} $ 。
       • 令$t=t-1$$ t = t - 1 $ 。

     • 计算梯度：

       $${\mathrm{\nabla }}_{\mathbf{w}}{e}_{\mathbf{w}}={\left(\frac{\partial G_{\mathbf{w}}({\overrightarrow{\mathbf{x}}}^{\ast },{\overrightarrow{l}}_{\mathbf{N}})}{\partial \mathbf{w}}\right)}^{\mathrm{\top }}{\mathrm{\nabla }}_{\overrightarrow{\mathbf{o}}}{e}_{\mathbf{w}}+{\left(\frac{\partial F_{\mathbf{w}}({\overrightarrow{\mathbf{x}}}^{\ast },\overrightarrow{l})}{\partial \mathbf{w}}\right)}^{\mathrm{\top }}{\overrightarrow{\mathbf{z}}}^{\ast }$$

     • 返回梯度${\mathrm{\nabla }}_{\mathbf{w}}{e}_{\mathbf{w}}$$ \nabla_{\mathbf{w}}e_{\mathbf w} $ 。

7. Main 部分：

   • 输入：图$\mathbf{G}=(\mathbf{N},\mathbf{E})$$ \mathbf G=(\mathbf N,\mathbf E) $ ，学习率$\lambda$$ \lambda $

   • 输出：模型参数$\mathbf{w}$$ \mathbf{w} $

   • 算法步骤：

     • 随机初始化参数$\mathbf{w}$$ \mathbf{w} $ 。

     • 通过前向计算过程计算状态：${\overrightarrow{\mathbf{x}}}^{\ast }=\text{Forward}(\mathbf{w})$$ \mathbf{\vec x}^* = \text{Forward}(\mathbf{w}) $ 。

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

       • 通过反向计算过程计算梯度：${\mathrm{\nabla }}_{\mathbf{w}}{e}_{\mathbf{w}}=\text{Backward}({\overrightarrow{\mathbf{x}}}^{\ast },\mathbf{w})$$ \nabla_{\mathbf{w}} e_{\mathbf w} = \text{Backward}\left(\mathbf{\vec x}^*,\mathbf{w}\right) $
       • 更新参数：$\mathbf{w}=\mathbf{w}-\lambda {\mathrm{\nabla }}_{\mathbf{w}}{e}_{\mathbf{w}}$$ \mathbf{w} = \mathbf{w} - \lambda \nabla_{\mathbf{w}} e_{\mathbf w} $ 。
       • 通过新的参数计算状态：${\overrightarrow{\mathbf{x}}}^{\ast }=\text{Forward}(\mathbf{w})$$ \mathbf{\vec x}^* = \text{Forward}(\mathbf{w}) $ 。

     • 返回参数$\mathbf{w}$$ \mathbf{w} $ 。

8. Main 部分采用预定义的学习率$\lambda$$ \lambda $ ，但是也可以使用基于梯度下降的一些通用策略，例如使用带动量的梯度更新 、或者自适应学习率的方案。另一方面，目前 GNN 只能通过梯度下降算法求解，非梯度下降算法目前还未解决，这是未来研究的方向。

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

1.1.4 转移函数和输出函数

1. 局部输出函数$g_{\mathbf{w}}(\cdot )$$ g_{\mathbf w}(\cdot) $ 的实现没有任何约束。通常在 GNN 中，$g_{\mathbf{w}}(\cdot )$$ g_{\mathbf w}(\cdot) $ 采用一个多层前馈神经网络来实现。

   另一方面，局部转移函数$f_{\mathbf{w}}(\cdot )$$ f_{\mathbf w}(\cdot) $ 在 GNN 中起着关键作用，它决定了不动点的存在性和唯一性。GNN 的基本假设是：全局转移函数$F_{\mathbf{w}}(\cdot )$$ F_{\mathbf w}(\cdot) $ 是收缩映射。接下来，我们给出了两种满足该约束的$f_{\mathbf{w}}(\cdot )$$ f_{\mathbf w}(\cdot) $ 的实现，它们都是基于nonpositional form，positional form 也可以类似地实现。

2. nonpositional linear GNN 线性 GNN：

   $$h_{\mathbf{w}}({\overrightarrow{l}}_n,{\overrightarrow{l}}_{(n,u)},{\overrightarrow{\mathbf{x}}}_u,{\overrightarrow{l}}_u)={\mathbf{A}}_{n,u}{\overrightarrow{\mathbf{x}}}_u+{\overrightarrow{\mathbf{b}}}_n$$

   其中${\overrightarrow{\mathbf{b}}}_n\in {\mathcal{R}}^s$$ \mathbf{\vec b}_n\in \mathcal R^s $ 和矩阵${\mathbf{A}}_{n,u}\in {\mathcal{R}}^{s\times s}$$ \mathbf A_{n,u}\in \mathcal R^{s\times s} $ 分别由两个前馈神经网络的输出来定义，这两个前馈神经网络的参数对应于 GNN 的参数。更准确的说：

   • 转移网络 transition network 是一个前馈神经网络，它用于生成${\mathbf{A}}_{n,u}$$ \mathbf A_{n,u} $ 。

     设该神经网络为一个映射${\varphi }_{\mathbf{w}}:{\mathcal{R}}^{2d_N+d_E}\to {\mathcal{R}}^{s^2}$$ \phi_{\mathbf w}:\mathcal R^{2d_N+d_E} \rightarrow \mathcal R^{s^2} $ ，则定义：

     $${\mathbf{A}}_{n,u}=\frac{\mu }{s\times |\text{ne}[u]|}\mathbf{B}$$

     其中：

     • $\mathbf{B}\in {\mathcal{R}}^{s\times s}$$ \mathbf B\in \mathcal R^{s\times s} $ 是由${\varphi }_{\mathbf{w}}({\overrightarrow{l}}_n,{\overrightarrow{l}}_{n,u},{\overrightarrow{l}}_u)$$ \phi_{\mathbf w}\left(\vec l_n,\vec l_{n,u},\vec l_u\right) $ 的$s^2$$ s^2 $ 个元素进行重新排列得到的矩阵。
     • $\mu \in (0,1)$$ \mu\in (0,1) $ 为缩放系数，$\frac{\mu }{s\times |\text{ne}[u]|}$$ \frac{\mu}{s\times |\text{ne}[u]|} $ 用于对矩阵$\mathbf{B}$$ \mathbf B $ 进行缩放。

     因此${\mathbf{A}}_{n,u}$$ \mathbf A_{n,u} $ 是对转移网络输出的重排方阵$\mathbf{B}$$ \mathbf B $ 进行缩放得到。

     这里的转移矩阵${\mathbf{A}}_{n,u}$$ \mathbf A_{n,u} $ 是神经网络的输出，而不是待学习的权重参数。这是因为可以选择输出函数（如 tanh），使得神经网络的输出满足某些性质，从而使得$F_{\mathbf{w}}(\cdot )$$ F_\mathbf w(\cdot) $ 为收缩映射。

   • 约束网络forcing network 是另一个前馈神经网络，它用于生成${\overrightarrow{\mathbf{b}}}_n$$ \mathbf{\vec b}_n $ 。

     设该神经网络为一个映射${\rho }_{\mathbf{w}}:{\mathcal{R}}^{d_N}\to {\mathcal{R}}^s$$ \rho_{\mathbf w}: \mathcal R^{d_N} \rightarrow \mathcal R^s $ ，则定义：

     $${\overrightarrow{\mathbf{b}}}_n={\rho }_{\mathbf{w}}\left({\overrightarrow{l}}_n\right)$$

     因此，${\overrightarrow{\mathbf{b}}}_n$$ \mathbf{\vec b}_n $ 为约束网络的输出构成的向量。

     这里${\overrightarrow{\mathbf{b}}}_n$$ \mathbf{\vec b}_n $ 仅依赖于节点$n$$ n $ 本身的标签信息。

   假设有：${\Vert {\varphi }_{\mathbf{w}}({\overrightarrow{l}}_n,{\overrightarrow{l}}_{n,u},{\overrightarrow{l}}_u)\Vert }_1\le s$$ \left\|\phi_{\mathbf w}(\vec l_n,\vec l_{n,u},\vec l_u)\right\|_1 \le s $ ，即$|\mathbf{B}{|}_1\le s$$ |\mathbf B|_1 \le s $ 。事实上如果转移网络的输出神经元采用有界的激活函数（如tanh 激活函数），则很容易满足该假设。根据$h_{\mathbf{w}}({\overrightarrow{l}}_n,{\overrightarrow{l}}_{(n,u)},{\overrightarrow{\mathbf{x}}}_u,{\overrightarrow{l}}_u)={\mathbf{A}}_{n,u}{\overrightarrow{\mathbf{x}}}_u+{\overrightarrow{\mathbf{b}}}_n$$ h_{\mathbf w} \left({\vec l}_n,{\vec l}_{(n,u)}, \mathbf{\vec x}_{u},{\vec l}_{u}\right) = \mathbf A_{n,u} \mathbf{\vec x}_u + \mathbf{\vec b}_n $ 有：

   $$F_{\mathbf{w}}(\overrightarrow{\mathbf{x}},\overrightarrow{l})=\mathbf{A}\overrightarrow{\mathbf{x}}+\overrightarrow{\mathbf{b}}$$

   其中：

   • $\overrightarrow{\mathbf{b}}$$ \mathbf{\vec b} $ 是由所有的${\overrightarrow{\mathbf{b}}}_n$$ \mathbf{\vec b}_n $ 拼接而来，$\overrightarrow{\mathbf{x}}$$ \mathbf{\vec x} $ 是由所有的${\overrightarrow{\mathbf{x}}}_n$$ \mathbf{\vec x}_n $ 拼接而来：

     $$\overrightarrow{\mathbf{b}}={[{\overrightarrow{\mathbf{b}}}_1^{\mathrm{\top }},\cdots ,{\overrightarrow{\mathbf{b}}}_{|\mathbf{N}|}^{\mathrm{\top }}]}^{\mathrm{\top }}\overrightarrow{\mathbf{x}}={[{\overrightarrow{\mathbf{x}}}_1^{\mathrm{\top }},\cdots ,{\overrightarrow{\mathbf{x}}}_{|\mathbf{N}|}^{\mathrm{\top }}]}^{\mathrm{\top }}$$

   • $\mathbf{A}$$ \mathbf A $ 是一个分块矩阵，每一块为${\overline{\mathbf{A}}}_{n,u}$$ \bar{\mathbf A}_{n,u} $ ：

     $$\begin{array}{c}\mathbf{A}=\left[\begin{array}{cccc}{\overline{\mathbf{A}}}_{1,1}& {\overline{\mathbf{A}}}_{1,2}& \cdots & {\overline{\mathbf{A}}}_{1,|\mathbf{N}|}\\ {\overline{\mathbf{A}}}_{2,1}& {\overline{\mathbf{A}}}_{2,2}& \cdots & {\overline{\mathbf{A}}}_{2,|\mathbf{N}|}\\ ⋮& ⋮& \ddots & ⋮\\ {\overline{\mathbf{A}}}_{|\mathbf{N}|,1}& {\overline{\mathbf{A}}}_{|\mathbf{N}|,2}& \cdots & {\overline{\mathbf{A}}}_{|\mathbf{N}|,|\mathbf{N}|}\end{array}\right]\end{array}$$

     其中：

     • 如果$u$$ u $ 是$n$$ n $ 的邻居节点，则有${\overline{\mathbf{A}}}_{n,u}={\mathbf{A}}_{n,u}$$ \bar{\mathbf A}_{n,u} = \mathbf A_{n,u} $ 。
     • 如果$u$$ u $ 不是$n$$ n $ 的邻居节点，则由${\overline{\mathbf{A}}}_{n,u}=\mathbf{0}$$ \bar{\mathbf A}_{n,u} = \mathbf 0 $ 。

   由于${\overrightarrow{\mathbf{b}}}_n$$ \mathbf{\vec b}_n $ 和${\mathbf{A}}_{n,u}$$ \mathbf A_{n,u} $ 不依赖于状态$\overrightarrow{\mathbf{x}}$$ \mathbf{\vec x} $ （它们仅仅依赖于图的结构和节点标签信息、边标签信息），因此有：

   $$\frac{\partial F_{\mathbf{w}}(\overrightarrow{\mathbf{x}},\overrightarrow{l})}{\partial \overrightarrow{\mathbf{x}}}=\mathbf{A}$$

   则有：

   $${\Vert \frac{\partial F_{\mathbf{w}}(\overrightarrow{\mathbf{x}},\overrightarrow{l})}{\partial \overrightarrow{\mathbf{x}}}\Vert }_1=||\mathbf{A}|{|}_1\le \underset{u\in \mathbf{N}}{max}(\sum _{n\in \text{ne}[u]}||{\mathbf{A}}_{n,u}|{|}_1)\le \underset{u\in \mathbf{N}}{max}(\frac{\mu }{s\times |\text{ne}[u]|}\times \sum _{n\in \text{ne}[u]}||\mathbf{B}|{|}_1)\le \mu$$

   因此对于任意的参数$\mathbf{w}$$ \mathbf{w} $ ，$F_{\mathbf{w}}(\cdot )$$ F_{\mathbf w}(\cdot) $ 都是收缩映射。

3. nonpositional nonlinear GNN 非线性 GNN：$h_{\mathbf{w}}({\overrightarrow{l}}_n,{\overrightarrow{l}}_{(n,u)},{\overrightarrow{\mathbf{x}}}_u,{\overrightarrow{l}}_u)$$ h_{\mathbf w} \left({\vec l}_n,{\vec l}_{(n,u)}, \mathbf{\vec x}_{u},{\vec l}_{u}\right) $ 通过一个多层前馈神经网络来实现。由于三层神经网络是通用的函数逼近器，可以逼近任何所需的函数。但是，并非所有的参数$\mathbf{w}$$ \mathbf w $ 都可以使用，因为必须保证对应的转移函数$F_{\mathbf{w}}(\cdot )$$ F_{\mathbf w}(\cdot) $ 是收缩映射。这可以通过在损失函数中增加罚项来实现：

   $$\begin{array}{c}{e}_{\mathbf{w}}=\sum _{i=1}^p\sum _{j=1}^{q_i}{\Vert {\mathbf{t}}_{i,j}-{\phi }_{\mathbf{w}}({\mathbf{G}}_i,n_{i,j})\Vert }_2^2+\beta L\left({\Vert \mathbf{A}\Vert }_1\right)\\ \mathbf{A}=\frac{\partial F_{\mathbf{w}}(\overrightarrow{\mathbf{x}},\overrightarrow{l})}{\partial \overrightarrow{\mathbf{x}}}\end{array}$$

   注意，这里针对关于$\overrightarrow{\mathbf{x}}$$ \mathbf{\vec x} $ 的雅克比矩阵进行约束，而不是针对$\mathbf{w}$$ \mathbf w $ 的大小进行约束。

   其中：$\mathbf{A}$$ \mathbf A $ 为$F_{\mathbf{w}}(\cdot )$$ F_\mathbf w(\cdot) $ 关于$\overrightarrow{\mathbf{x}}$$ \mathbf{\vec x} $ 的雅克比矩阵；罚项$L(\cdot )$$ L(\cdot) $ 定义为：

   $$\begin{array}{c}L(y)=\{\begin{array}{ll}(y-\mu {)}^2& ,\text{if}y>\mu \\ 0& ,\text{else}\end{array}\end{array}$$

   超参数$\mu \in (0,1)$$ \mu \in (0,1) $ 定义了针对$F_{\mathbf{w}}(\cdot )$$ F_{\mathbf w}(\cdot) $ 的约束。

   更一般地，罚项可以是关于$\mathbf{w}$$ \mathbf w $ 可微的任何表达式，只需要关于雅克比范数${\Vert \mathbf{A}\Vert }_1$$ \left\|\mathbf A\right\|_1 $ 单调递增。例如，在我们的实验中，我们使用罚项$p_{\mathbf{w}}=L(\parallel \mathbf{A}{\parallel }_1)=\sum _{i=1}^{s}L\left({\Vert {\mathbf{A}}^i\Vert }_1\right)$$ p_{\mathbf w} =L(\|\mathbf A\|_1)= \sum_{i=1}^s L\left(\left\|\mathbf A^i\right\|_1\right) $ ，其中${\mathbf{A}}^i$$ \mathbf A^i $ 为$\mathbf{A}$$ \mathbf A $ 的第$i$$ i $ 列。实际上这个罚项是$L\left(\underset{i}{max}{\Vert {\mathbf{A}}^i\Vert }_1\right)$$ L\left(\max_i\left\|\mathbf A^i\right\|_1\right) $ 的一个近似。

1.2 模型分析

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

   • 输入图为有向无环图（例如最简单的有向的、线性的链式图）。
   • $f_{\mathbf{w}}(\cdot )$$ f_{\mathbf w}(\cdot) $ 的输入为${\overrightarrow{l}}_n,{\overrightarrow{\mathbf{x}}}_{\text{ch}[n]}$$ \vec l_n, \mathbf{\vec x}_{\text{ch}[n]} $ ，其中$\text{ch}[n]$$ \text{ch}[n] $ 为节点$n$$ n $ 的子结点的集合。
   • 一个超级源点$\text{sn}$$ \text{sn} $ ，从该源点可以到达其它所有节点。该源点通常对应于 graph-focused 任务的输出${\overrightarrow{\mathbf{o}}}_{\text{sn}}$$ \mathbf{\vec o}_\text{sn} $ 。

   实现$f_{\mathbf{w}}(\cdot ),g_{\mathbf{w}}(\cdot )$$ f_{\mathbf w}(\cdot),g_{\mathbf w}(\cdot) $ 的神经网络形式包括：多层前馈神经网络、cascade correlation、自组织映射 self-orgnizing map。在 RNN 中，编码网络采用多层前馈神经网络。这个简化了状态向量的计算。

2. GNN 和随机游走：当选择$f_{\mathbf{w}}(\cdot )$$ f_{\mathbf w}(\cdot) $ 为线性函数时，GNN 模型还捕获了图上的随机游走过程。

   定义节点的状态${\overrightarrow{\mathbf{x}}}_n$$ \mathbf{\vec x}_n $ 为一个实数，其定义为：

   $$x_n=\sum _{i\in \text{pa}[n]}{a}_{n,i}\times x_i$$

   其中：$\text{pa}[n]$$ \text{pa}[n] $ 表示节点$n$$ n $ 的父节点集合；$a_{n,i}$$ a_{n,i} $ 为归一化系数，满足：

   $$a_{n,i}\ge 0,\sum _{i\in \text{pa}[n]}{a}_{n,i}=1$$

   事实上$x_n=\sum _{i\in \text{pa}[n]}{a}_{n,i}\times x_i$$ x_n = \sum_{i\in \text{pa}[n]} a_{n,i}\times x_i $ 定义了一个随机游走生成器：

   • $a_{n,i}$$ a_{n,i} $ 表示当前位于节点$n$$ n $ 时，随机转移到下一个节点$i$$ i $ 的概率。
   • $x_n$$ x_n $ 表示当系统稳定时，随机游走生成器位于节点$n$$ n $ 的概率。

   当所有的$x_n$$ x_n $ 拼接成向量$\overrightarrow{\mathbf{x}}$$ \mathbf{\vec x} $ ，则有：

   $$\begin{array}{c}\overrightarrow{\mathbf{x}}=\mathbf{A}\overrightarrow{\mathbf{x}}\\ \overrightarrow{\mathbf{x}}=\left[\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_{|\mathbf{N}|}\end{array}\right]\mathbf{A}=\left[\begin{array}{cccc}{\overline{a}}_{1,1}& {\overline{a}}_{1,2}& \cdots & {\overline{a}}_{1,|\mathbf{N}|}\\ {\overline{a}}_{2,1}& {\overline{a}}_{2,2}& \cdots & {\overline{a}}_{2,|\mathbf{N}|}\\ ⋮& ⋮& \ddots & ⋮\\ {\overline{a}}_{|\mathbf{N}|,1}& {\overline{a}}_{|\mathbf{N}|,2}& \cdots & {\overline{a}}_{|\mathbf{N}|,|\mathbf{N}|}\end{array}\right]\end{array}$$

   其中：

   $$\begin{array}{c}{\overline{a}}_{n,i}=\{\begin{array}{ll}{a}_{n,i}& ,\text{if}(i\in \text{pa}[n])\\ 0& ,\text{else}\end{array}\end{array}$$

   可以很容易的验证$||\mathbf{A}|{|}_1=1$$ ||\mathbf A||_1 = 1 $ 。

   马尔可夫理论认为：如果存在$t$$ t $ 使得矩阵${\mathbf{A}}^t$$ \mathbf A^t $ 的所有元素都是非零的，则$x_n=\sum _{i\in \text{pa}[n]}{a}_{n,i}\times x_i$$ x_n = \sum_{i\in \text{pa}[n]} a_{n,i}\times x_i $ 就是一个收缩映射。

   因此假设存在$t$$ t $ 使得矩阵${\mathbf{A}}^t$$ \mathbf A^t $ 的所有元素都是非零的，则图上的随机游走是 GNN 的一个特例，其中$F_{\mathbf{w}}(\cdot )$$ F_{\mathbf w}(\cdot) $ 的参数$\mathbf{A}$$ \mathbf A $ 是一个常量随机矩阵constant stochastic matrix ，而不是由神经网络产生的矩阵。

   当输入图为无向图时，将$\text{pa}[n]$$ \text{pa}[n] $ 替换为邻域$\text{ne}[n]$$ \text{ne}[n] $ ，则结论仍然成立。

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

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

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

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

   

1.3 计算复杂度

1. 我们关心三种类型的 GNN 模型：positional GNN （其中$f_{\mathbf{w}}(\cdot )$$ f_{\mathbf w}(\cdot) $ 和$g_{\mathbf{w}}(\cdot )$$ g_{\mathbf w}(\cdot) $ 通过前馈神经网络来实现）、nonpositional linear GNN、nonpositional nonlinear GNN 。

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

   具体推导见论文。其中：

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

   • $\text{hi}$$ \text{hi} $ 表示隐层神经元的数量，即隐层维度。如${\text{hi}}_f$$ \text{hi}_f $ 表示函数$f_{\mathbf{w}}(\cdot )$$ f_\mathbf w(\cdot) $ 的实现网络的隐层神经元数量。

   • ${\text{it}}_l$$ \text{it}_l $ 表示迭代的 epoch 数量，${\text{it}}_b$$ \text{it}_b $ 表示平均每个epoch 的反向迭代次数(BACKWARD 过程中的循环迭代次数)，${\text{it}}_f$$ \text{it}_f $ 表示平均每个epoch 的前向迭代次数（FORWARD 过程中的循环迭代次数）。

   • ${\overrightarrow{C}}_f$$ \overrightarrow C_f $ 和${\overleftarrow{C}}_f$$ \overleftarrow C_f $ 分别表示前向计算$f_{\mathbf{w}}(\cdot )$$ f_\mathbf w(\cdot) $ 和反向计算$f_{\mathbf{w}}(\cdot )$$ f_\mathbf w(\cdot) $ 梯度的计算复杂度。

   • 令雅克比矩阵$\mathbf{A}=\frac{\partial F_{\mathbf{w}}(\overrightarrow{\mathbf{x}},\overrightarrow{l})}{\partial \overrightarrow{\mathbf{x}}}$$ {\mathbf A}= \frac{\partial F_{\mathbf w}\left(\mathbf{\vec x},\vec l\right)}{\partial \mathbf{\vec x}} $ ，则罚项$p_{\mathbf{w}}$$ p_\mathbf w $ 为：

     $$p_{\mathbf{w}}=\sum _{j=1}^{s}L\left({\Vert {\mathbf{A}}^j\Vert }_1\right)=\sum _{u\in \mathbf{N}}\sum _{j=1}^{s}L(\sum _{(n,u)\in \mathbf{E}}\sum _{i=1}^s\left|{\mathbf{A}}_{i,j}^{n,u}\right|-\mu )=\sum _{u\in \mathbf{N}}\sum _{j=1}^s{\alpha }_{u,j}$$

     其中：${\mathbf{A}}_{i,j}^{n,u}$$ \mathbf A^{n,u}_{i,j} $ 表示矩阵$\mathbf{A}$$ \mathbf A $ 的分块${\mathbf{A}}^{n,u}$$ \mathbf A^{n,u} $ 的第$i$$ i $ 行第$j$$ j $ 列，${\mathbf{A}}^j$$ \mathbf{ A}^j $ 表示矩阵$\mathbf{A}$$ \mathbf A $ 的第$j$$ j $ 列，${\alpha }_{u,j}=L(\sum _{(n,u)\in \mathbf{E}}\sum _{i=1}^s\left|{\mathbf{A}}_{i,j}^{n,u}\right|-\mu )$$ \alpha_{u,j}=L\left(\sum_{(n,u)\in \mathbf E}\sum_{i=1}^s \left|\mathbf A_{i,j}^{n,u}\right|-\mu\right ) $ 。

   • 定义${\mathbf{R}}^{n,u}$$ \mathbf R^{n,u} $ 为一个矩阵，其元素为${\mathbf{R}}_{i,j}^{n,u}={\alpha }_{u,j}\times \text{sgn}\left({\mathbf{A}}_{i,j}^{n,u}\right)$$ \mathbf R^{n,u}_{i,j} = \alpha_{u,j}\times \text{sgn}\left(\mathbf A^{n,u}_{i,j}\right) $ ，则$t_{\mathbf{R}}$$ t_\mathbf R $ 为：对所有的节点$n$$ n $ ，满足${\mathbf{R}}^{n,u}\ne \mathbf{0}$$ \mathbf R^{n,u} \ne \mathbf 0 $ 的节点$u$$ u $ 的数量的均值。通常它是一个很小的数值。

   

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

   • 对于positional GNN，其推断的计算复杂度为：$O(|\mathbf{N}|{\overrightarrow{C}}_g+{\text{it}}_f|\mathbf{N}|{\overrightarrow{C}}_f)$$ O(|\mathbf N|\overrightarrow C_g + \text{it}_f|\mathbf N|\overrightarrow C_f) $ 。
   • 对于 nonpositional nonliear GNN，其推断的计算复杂度为：$O(|\mathbf{N}|{\overrightarrow{C}}_g+{\text{it}}_f|\mathbf{E}|{\overrightarrow{C}}_h)$$ O(|\mathbf N|\overrightarrow C_g +\text{it}_f|\mathbf E|\overrightarrow C_h) $ 。
   • 对于 nonpositional linear GNN，其推断的计算复杂度为：$O(|\mathbf{N}|{\overrightarrow{C}}_g+{\text{it}}_f|\mathbf{E}|s^2+|\mathbf{N}|{\overrightarrow{C}}_{\rho }+|\mathbf{E}|{\overrightarrow{C}}_{\varphi })$$ O(|\mathbf N|\overrightarrow C_g+\text{it}_f|\mathbf E|s^2+|\mathbf N|\overrightarrow C_\rho+|\mathbf E|\overrightarrow C_\phi) $ 。

   推断阶段的主要时间消耗在计算状态$\overrightarrow{\mathbf{x}}$$ \mathbf{\vec x} $ 的重复计算中，每次迭代的计算代价和输入图的维度（如边的数量）成线性关系，和前馈神经网络的隐层维度成线性关系，和状态向量的维度成线性关系。线性 GNN 是一个例外。线性 GNN 的单次迭代成本是状态维度的二次关系。

   状态向量的收敛速度取决于具体的问题。但是 Banach 定理可以确保它是以指数级速度收敛。实验表明：通常5 到 15 次迭代足以逼近不动点。

3. 在 positional GNN 中转移函数需要执行${\text{it}}_f|\mathbf{N}|$$ \text{it}_f|\mathbf N| $ 次，在 nonpositional nonliear GNN 中转移函数需要执行${\text{it}}_f|\mathbf{E}|$$ \text{it}_f|\mathbf E| $ 次。虽然边的数量$|\mathbf{E}|$$ |\mathbf E| $ 通常远大于节点数量$|\mathbf{N}|$$ |\mathbf N| $ ，但是positional GNN 和 nonpositional nonlinear GNN 的推断计算复杂度是相近的，这是因为 positional GNN 中的$f_{\mathbf{w}}(\cdot )$$ f_{\mathbf w}(\cdot) $ 网络通常要比 nonpositional nonliear GNN 中的$h_{\mathbf{w}}(\cdot )$$ h_{\mathbf w}(\cdot) $ 网络更复杂。

   • 在 positional GNN 中，实现$f_{\mathbf{w}}(\cdot )$$ f_{\mathbf w}(\cdot) $ 的神经网络有$M\times (s+d_E)$$ M\times (s + d_E) $ 个神经元，其中$M$$ M $ 为所有节点的最大邻居数量。
   • 在 nonpositonal nonliear GNN 中，实现$h_{\mathbf{w}}(\cdot )$$ h_{\mathbf w}(\cdot) $ 的神经网络有$(s+d_E)$$ (s+d_E) $ 个神经元。

   只有在节点的邻居数量高度可变的图中才能注意到明显的差异，因为$f_{\mathbf{w}}(\cdot )$$ f_{\mathbf w}(\cdot) $ 的输入必须确保能够容纳最多的邻居，并且在应用$f_{\mathbf{w}}(\cdot )$$ f_{\mathbf w}(\cdot) $ 时许多输入可能仍然未使用（很多输入填充为 null ）。

4. 另一方面，观察到在 linear GNN 中，每次迭代仅使用一次 FNN，因此每次迭代的复杂度为$O(s^2|\mathbf{E}|)$$ O(s^2|\mathbf E|) $ 而不是$O(|\mathbf{E}|{\overrightarrow{C}}_h)$$ O(|\mathbf E|\overrightarrow C_h) $ 。

   注意到，当$h_{\mathbf{w}}(\cdot )$$ h_{\mathbf w}(\cdot) $ 由具有${\text{hi}}_h$$ \text{hi}_h $ 隐层神经元的三层 FNN 实现时，${\overrightarrow{C}}_h=O((s+d_E+2d_N)\times {\text{hi}}_h)=O(s\times {\text{hi}}_h)$$ \overrightarrow C_h = O((s+d_E+2d_N)\times \text{hi}_h) = O(s\times \text{hi}_h) $ 成立。在实际情况下，${\text{hi}}_h$$ \text{hi}_h $ 通常大于$s$$ s $ ，因此线性模型比非线性模型更快。正如实验所证实的那样，这种优势通常被更差的效果所抵消。

5. GNN 的训练阶段要比推断阶段消耗更多时间，主要在于需要在多个epoch 中重复执行 forward 和 backward 过程。实验表明：forward 阶段和 backward 阶段的时间代价都差不多。

   • forward阶段的时间主要消耗在重复计算$\overrightarrow{\mathbf{x}}(t)$$ \mathbf{\vec x}(t) $ 。
   • 类似于 forward 阶段，backward 阶段的时间主要消耗在重复计算$\overrightarrow{\mathbf{z}}(t)$$ \mathbf{\vec z}(t) $ 。前述定理可以确保$\overrightarrow{\mathbf{z}}(t)$$ \mathbf{\vec z}(t) $ 是指数级收敛的，并且实验表明${\text{it}}_b$$ \text{it}_b $ 通常很小。

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

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

     有几个例外，如计算$\overrightarrow{\mathbf{z}}(t)={\mathbf{A}}^{\mathrm{\top }}\overrightarrow{\mathbf{z}}(t+1)+\overrightarrow{\mathbf{b}},\mathbf{A}=\frac{F_{\mathbf{w}}(\overrightarrow{\mathbf{x}},\overrightarrow{l})}{\partial \overrightarrow{\mathbf{x}}},{\mathrm{\nabla }}_{\mathbf{w}}{p}_{\mathbf{w}}$$ \mathbf{\vec z}(t) = \mathbf A^\top \mathbf{\vec z}(t+1) + \mathbf{\vec b}, \mathbf A = \frac{F_{\mathbf w}\left(\mathbf{\vec x},\vec l\right)}{\partial \mathbf{\vec x}}, \nabla_{\mathbf{w}}p_{\mathbf w} $ 的计算复杂度都是$s$$ s $ 的平方关系。

   • 最耗时的指令是 nonpositional nonlinear GNN 中计算${\mathrm{\nabla }}_{\mathbf{w}}{p}_{\mathbf{w}}$$ \nabla_{\mathbf{w}}p_{\mathbf w} $ ，其计算复杂度为$t_{\mathbf{R}}\times max(s^2\times {\text{hi}}_h,{\overleftarrow{C}}_h)$$ t_\mathbf R\times \max(s^2\times \text{hi}_h,\overleftarrow C_h) $ 。

     实验表明，通常$t_{\mathbf{R}}$$ t_\mathbf R $ 是一个很小的数字。在大多数 epoch 中$t_{\mathbf{R}}=0$$ t_\mathbf R=0 $ ，因为雅可比矩阵$\mathbf{A}$$ \mathbf A $ 并未违反施加的约束。另一些情况中，$t_{\mathbf{R}}$$ t_\mathbf R $ 通常在 1~5 之间。因此对于较小的状态维度$s$$ s $ ，计算${\mathrm{\nabla }}_{\mathbf{w}}{p}_{\mathbf{w}}$$ \nabla_{\mathbf{w}}p_{\mathbf w} $ 的复杂度较低。

     理论上，如果$s$$ s $ 非常大则可能导致$s^2\times {\text{hi}}_h\gg {\overleftarrow{C}}_h$$ s^2\times \text{hi}_h \gg \overleftarrow C_h $ 。如果同时还有$t_{\mathbf{R}}\gg 0$$ t_\mathbf R\gg 0 $ ，则这将导致计算${\mathrm{\nabla }}_{\mathbf{w}}{p}_{\mathbf{w}}$$ \nabla_{\mathbf{w}}p_{\mathbf w} $ 非常慢。但是值得一提的是，我们的实验中从未观察到这种情况。

1.4 实验

1. 这里我们展示了在一组简单问题上获得的实验结果，这些问题是为了研究 GNN 模型的特性，并证明该方法可以应用于相关领域的相关应用。这些问题包括：子图匹配、诱变mutagenesis、网页排名，因为这些问题特别适合挖掘模型的属性并且与重要的现实应用相关。值得一提的是，GNN 模型已经成功应用于更大的应用，包括图像分类、图像中的物体定位、网页排名web page ranking 、关系学习relational learning、XML 分类。

2. 除非另有说明，以下事实适用于每个实验。

   • 根据 RNN 的已有经验，nonpositional 转移函数效果要优于 positional 转移函数，因此这里测试了 nonpositional linear GNN 和 nonpositional nonlinear GNN 。
   • 所有GNN 中涉及到的函数，如 nonpositional linear GNN 中的$g_{\mathbf{w}}(\cdot ),{\varphi }_{\mathbf{w}}(\cdot ),{\rho }_{\mathbf{w}}(\cdot )$$ g_{\mathbf w}(\cdot),\phi_{\mathbf w}(\cdot),\rho_{\mathbf w}(\cdot) $ ，以及 nonpositional nonlinear GNN 中的$g_{\mathbf{w}}(\cdot ),h_{\mathbf{w}}(\cdot )$$ g_{\mathbf w}(\cdot),h_{\mathbf w}(\cdot) $ 都采用三层的前馈神经网络来实现，并使用 sigmoid 激活函数。
   • 报告的结果是五次不同运行的均值。在每次运行中，数据集是由以下过程构建的随机图的集合：每对节点之间以一定的概率$\delta$$ \delta $ 随机连接，直到构建的随机图满足指定条件。

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

   • 如果原始数据仅包含一张大图$\mathbf{G}$$ \mathbf G $ ，则训练集、验证集、测试集分别包含$\mathbf{G}$$ \mathbf G $ 的不同节点。
   • 如果原始数据包含多个图${\mathbf{G}}_i$$ \mathbf G_i $ ，则每张图整个被划分到训练集、验证集、测试集之一。

   在每次试验中，训练最多执行 5000 个 epoch，每 20 个 epoch 在验证集上评估 GNN 。在验证集上实现最低损失函数的 GNN 被认为是最佳模型，并应用于测试集。

   测试集性能评估指标为分类准确率或回归相对误差。

   • 对于分类问题，${\mathbf{t}}_{i,j}$$ \mathbf t_{i,j} $ 为一个标量，取值范围为$\{+1,-1\}$$ \{+1,-1\} $ 。模型的评估指标为预测准确率：如果$t_{i,j}\times {\phi }_{\mathbf{w}}({\mathbf{G}}_i,n_{i,j})>0$$ t_{i,j}\times \varphi_{\mathbf w}(\mathbf G_i,n_{i,j}) \gt 0 $ 则分类正确；否则分类不正确。

   • 对于回归问题，${\mathbf{t}}_{i,j}$$ \mathbf t_{i,j} $ 为一个标量，取值范围为$\mathcal{R}$$ \mathcal R $ 。模型的评估指标为相对误差：

     $$\left|\frac{t_{i,j}-{\phi }_{\mathbf{w}}({\mathbf{G}}_i,n_{i,j})}{t_{i,j}}\right|$$

4. 算法在 Matlab 7 上实现，在配备了 2-GHz PowerPC 处理器的 Power Mac G5 上进行。

1.4.1 子图匹配问题

1. 子图匹配subgraph matching 问题：在更大的图$\mathbf{G}$$ \mathbf G $ 中寻找给定的子图$\mathbf{S}$$ \mathbf S $ 。即，需要学习一个函数$\tau$$ \tau $ ：如果节点$n_{i,j}$$ n_{i,j} $ 属于图${\mathbf{G}}_i$$ \mathbf G_i $ 中的一个和$\mathbf{S}$$ \mathbf S $ 同构的子图，则$\tau ({\mathbf{G}}_i,n_{i,j})=1$$ \tau(\mathbf G_i,n_{i,j}) = 1 $ ；否则$\tau ({\mathbf{G}}_i,n_{i,j})=-1$$ \tau(\mathbf G_i,n_{i,j}) = -1 $ 。

   如下图所示，图${\mathbf{G}}_1,{\mathbf{G}}_2$$ \mathbf G_1,\mathbf G_2 $ 都包含子图$\mathbf{S}$$ \mathbf S $ 。节点内的数字表示节点的标签信息向量${\overrightarrow{l}}_n$$ \vec l_n $ （这里是一个标量）。最终学到的函数$\tau$$ \tau $ 为：如果为黑色节点则$\tau ({\mathbf{G}}_i,n_{i,j})=1$$ \tau(\mathbf G_i,n_{i,j}) = 1 $ ，否则$\tau ({\mathbf{G}}_i,n_{i,j})=-1$$ \tau(\mathbf G_i,n_{i,j}) = -1 $ 。

   

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

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

2. 数据集：由 600 个随机图组成（边的连接概率为$\delta =0.2$$ \delta = 0.2 $ ），平均划分为训练集、验证集、测试集。在每轮实验中，随机生成一个子图$\mathbf{S}$$ \mathbf S $ ，将子图$\mathbf{S}$$ \mathbf S $ 插入到数据集的每个图中，因此每个图${\mathbf{G}}_i$$ \mathbf G_i $ 至少包含了$\mathbf{S}$$ \mathbf S $ 的一份拷贝。

   每个节点包含整数标签，取值范围从 [0,10]。我们使用一个均值为0、标准差为 0.25 的高斯噪声添加到标签上，结果导致数据集中每个图对应的$\mathbf{S}$$ \mathbf S $ 的拷贝都不同。

   注意添加噪声之后，节点的标签仍然为整数，因此需要四舍五入。

   为了生成正确的监督目标${\mathbf{t}}_{i,j}$$ \mathbf t_{i,j} $ ，我们使用一个暴力搜索算法从每个图${\mathbf{G}}_i$$ \mathbf G_i $ 中搜索$\mathbf{S}$$ \mathbf S $ 。

3. GNN 配置：

   • 所有实验中，状态向量的维度$s=5$$ s=5 $ 。
   • 所有实验中，GNN 的所有神经网络的隐层为三层，隐层维度为 5 。我们已经测试过更多的网络架构，结果是类似的。

   为评估子图匹配任务中，标签信息和子图连通性的相对重要性，我们还应用了前馈神经网络FNN 作为 baseline 。FNN 有一个输出单元、20 个隐单元、一个输入单元。 FNN 仅使用标签信息${\overrightarrow{l}}_{n_{i,j}}$$ \vec l_{n_{i,j}} $ 来预测监督目标${\mathbf{t}}_{i,j}$$ \mathbf t_{i,j} $ ，它并没有利用图的结构。

4. 实验结果如下图所示，其中 NL 表示 nonpositional nonlinear GNN，L 表示 nonpositional linear GNN ，FNN 表示前馈神经网络。评估指标为测试集准确率。

   结论：

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

     • 当$|\mathbf{S}|$$ |\mathbf S| $ 接近$|\mathbf{G}|$$ |\mathbf G| $ 时，几乎所有节点都是正样本，所有方法预测的准确率都较高。
     • 当$|\mathbf{S}|$$ |\mathbf S| $ 只有$|\mathbf{G}|$$ |\mathbf G| $ 的一半时，正负节点比较均匀，此时所有方法预测的准确率都较低。

     事实上，在后一种情况下，数据集是完全平衡的，并且更难以猜测正确的目标。

   • 子图规模$|\mathbf{S}|$$ |\mathbf S| $ 影响了所有方法的结果。

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

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

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

   • 最后，可以观察到 FNN 的总体平均误差比 GNN 增加大约 50% 。GNN 和 FNN 之间的相对错误率（衡量了拓扑结构的优势）随着$|\mathbf{S}|$$ |\mathbf S| $ 的增加而变小。

     实际上，GNN 使用信息扩散机制 information diffusion mechanism 来决定节点是否属于子图。当$\mathbf{S}$$ \mathbf S $ 较大时，必须扩散更多的信息，因此要学习的函数更复杂。

   

5. 为评估GNN 的计算复杂度和准确性，我们评估了不同节点数、不同边数、不同隐层维度、不同状态向量维度的效果。在基准情况下：训练集包含10 个随机图，每个图包含20 个节点和 40 条边；GNN 隐层维度为5，状态向量维度为 2 。

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

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

   

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

   

6. 非线性 GNN 中，梯度和状态向量维度的二次关系取决于计算雅可比矩阵$\mathbf{A}=\frac{\partial F_{\mathbf{w}}(\overrightarrow{\mathbf{x}},\overrightarrow{l})}{\partial \overrightarrow{\mathbf{x}}}$$ \mathbf A=\frac{\partial F_{\mathbf w}\left(\mathbf{\vec x},\vec l\right)}{\partial \mathbf{\vec x}} $ 以及梯度${\mathrm{\nabla }}_{\mathbf{w}}{p}_{\mathbf{w}}$$ \nabla_{\mathbf{w}} p_{\mathbf w} $ 的时间代价。下图给出了计算梯度过程中的总时间代价。

   线条 -o- 给出了计算$e_{\mathbf{w}}$$ e_{\mathbf w} $ 和${\mathrm{\nabla }}_{\mathbf{w}}{e}_{\mathbf{w}}$$ \nabla_{\mathbf{w}}e_{\mathbf w} $ 的时间代价；线条 -*- 给出了计算雅可比矩阵$\mathbf{A}$$ \mathbf A $ 的时间代价；线条 -x- 给出了计算${\mathrm{\nabla }}_{\mathbf{w}}{p}_{\mathbf{w}}$$ \nabla_{\mathbf{w}} p_{\mathbf w} $ 的时间代价；点线 ...和给出了剩下的前向计算的时间代价；虚线 ---给出了剩下的反向计算的时间代价；实线表示剩下的计算梯度的时间代价。

   可以看到：${\mathrm{\nabla }}_{\mathbf{w}}{p}_{\mathbf{w}}$$ \nabla_{\mathbf{w}} p_{\mathbf w} $ 的计算复杂度虽然是状态向量维度的二次关系，但是实际上影响较小。实际上该项的计算复杂度依赖于参数$t_{\mathbf{R}}$$ t_\mathbf R $ （对所有的节点$n$$ n $ ，满足${\mathbf{R}}^{n,u}\ne \mathbf{0}$$ \mathbf R^{n,u} \ne \mathbf 0 $ 的节点$u$$ u $ 的数量的均值），通常它是一个很小的数值。

   

   下图给出每个epoch 中${\mathbf{R}}^{n,u}\ne \mathbf{0}$$ \mathbf R^{n,u} \ne \mathbf 0 $ 的节点$u$$ u $ 的数量的直方图（黑色柱体）。可以看到${\mathbf{R}}^{n,u}$$ \mathbf R^{n,u} $ 的节点$u$$ u $ 的数量通常为零，且从未超过4 。另外下图也给出计算稳定状态${\overrightarrow{\mathbf{x}}}^{\ast }$$ \mathbf{\vec x}^* $ 和计算梯度（如计算${\overrightarrow{\mathbf{z}}}^{\ast }$$ \mathbf{\vec z}^* $ ）所需要的平均迭代次数的直方图，可以看到这些值通常也很小。

   下图给出的是迭代次数或$t_{\mathbf{R}}$$ t_\mathbf R $ 取值（x 轴）的分布（y 轴表示出现次数）。

   

1.4.2 Mutagenesis问题

1. Mutagenesis 数据集：一个小型数据集，经常作为关系学习relational learning 和 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 预编码结构属性 P\mathbf S 。

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

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

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

   

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

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

   

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

   

   在所有分子上的效果：

   

   结论：

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

1.4.3 Web PageRank

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

   $$p_n=d\times \frac{\sum _{u\in \text{pa}[n]}{p}_u}{o_n}+(1-d)$$

   其中：$o_n$$ o_n $ 为节点$n$$ n $ 的出度 out-degree ，$d\in [0,1]$$ d\in [0,1] $ 为阻尼因子 damping factor ，$\text{pa}[n]$$ \text{pa}[n] $ 为节点$n$$ n $ 的父节点集合。

   图$\mathbf{G}$$ \mathbf G $ 以$\delta =0.2$$ \delta = 0.2 $ 随机生成，包含 5000 个节点。训练集、验证集、测试集由图的不同节点组成，其中 50 个节点作为训练集、50 个节点作为验证集、剩下节点作为测试集。

   每个节点$n$$ n $ 对应于一个二维标签${\overrightarrow{l}}_n=[a_n,b_n]$$ \vec l_n = [a_n,b_n] $ ，其中$a_n\in \{0,1\},b_n\in \{0,1\}$$ a_n\in \{0,1\},b_n \in \{0,1\} $ 表示节点$n$$ n $ 是否属于两个给定的主题：

   • $[a_n,b_n]=[1,1]$$ [a_n,b_n]=[1,1] $ 表示节点$n$$ n $ 同时属于这两个主题。
   • $[a_n,b_n]=[1,0]$$ [a_n,b_n] = [1,0] $ 表示节点$n$$ n $ 仅仅属于第一个主题。
   • $[a_n,b_n]=[0,1]$$ [a_n,b_n]=[0,1] $ 表示节点$n$$ n $ 仅仅属于第二个主题。
   • $[a_n,b_n]=[0,0]$$ [a_n,b_n]=[0,0] $ 表示节点$n$$ n $ 不属于任何主题。

   需要拟合的目标target 为：

   $$\begin{array}{c}{t}_n=\{\begin{array}{ll}\frac{2p_n}{\sum _{j\in \mathbf{N}}|p_j|}& ,\text{if}(a_n\text{XOR}{b}_n)=1\\ \frac{p_n}{\sum _{j\in \mathbf{N}}|p_j|}& ,\text{otherwise}\end{array}\end{array}$$

2. 这里我们使用线性 GNN 模型，因为线性 GNN 模型很自然的类似于 PageRank 线性模型。转移网络和约束网络 forcing network 都使用三层前馈神经网络，隐层维度为5。状态向量维度为$s=1$$ s=1 $ （即，一个标量$x_n$$ x_n $ ）。

   输出函数为：$g_{\mathbf{w}}(x_n,{\overrightarrow{l}}_n)=x_n^{\prime }\times {\pi }_{\mathbf{w}}(x_n,{\overrightarrow{l}}_n)$$ g_{\mathbf w}\left(x_n,\vec l_n\right) = x_n^\prime \times \pi_{\mathbf w}\left(x_n,\vec l_n\right) $ 。其中：$x_n^{\prime }$$ x_n^\prime $ 为$x_n$$ x_n $ 的偏导数；${\pi }_{\mathbf{w}}$$ \pi_{\mathbf w} $ 为三层前馈神经网络，隐层维度为 5 。

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

   红色实线表示目标$t_n$$ t_n $ ，蓝色点线表示 GNN 模型的输出。横轴表示测试集的节点数量，纵轴表示目标得分$t_n$$ t_n $ 。节点按照$t_n$$ t_n $ 得分进行升序排列。该结果清晰地表明 GNN 在这个问题上表现得非常好。

   

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