GNN

一、GNN[2009]

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 }$$

     其中