GNN

一、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. 定义图 $G=( V, E)$，其中 $V$ 为顶点集合、$E$ 为边集合。边可以为有向边，也可以为无向边。

   对于顶点 $v$ ，定义 $\mathcal N_v$ 为其邻接顶点集合，定义 $\mathcal E_v$ 为包含顶点 $v$ 的边的集合。

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

   • 标签信息以实值向量来表示，定义顶点 $v$ 的标签为 $\vec l _v \in \mathbb R^{n_v}$ ，定义边 $(v_1,v_2)$ 的标签为 $\vec l_{v_1,v_2} \in \mathbb R^{n_E}$，其中 $n_v$ 为顶点标签的维度、$n_E$ 为边标签的维度。

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

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

     

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

   • $\mathbf{\vec x}_v$ 是顶点 $v$ 对应对象的 representation，可用于产生顶点 $v$ 的输出 $\mathbf{\vec o}_v \in \mathbb R^m$ 。

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

     $$\mathbf{\vec x}_v = f_w( {\vec l}_v, {\vec l}_{\mathcal E_v}, \mathbf{\vec x}_{\mathcal N_v}, {\vec l}_{\mathcal N_v})$$

     其中：

     • $\vec l_v$ 为顶点 $v$ 的标签信息向量。
     • $\vec l_{\mathcal E_v}$ 为包含顶点 $v$ 的所有边的标签信息向量拼接的向量。
     • $\mathbf{\vec x}_{\mathcal N_v}$ 为顶点 $v$ 的所有邻居的状态向量拼接的向量。
     • ${\vec l}_{\mathcal N_v}$ 为顶点 $v$ 的所有邻居的标签信息向量拼接的向量。

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

     $$\mathbf{\vec o}_v = g_w(\mathbf{\vec x}_v, {\vec l}_v)$$

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

   • 可以移除 ${\vec l}_{\mathcal N_v}$，因为 $\mathbf{\vec x}_{\mathcal N_v}$ 中已经包含了邻居顶点的信息。
   • 邻域不仅可以包含顶点 $v$ 的直接链接的顶点，还可以包含顶点 $v$ 的二跳、三跳的顶点。

5. 上述定义仅仅针对无向图，也可以通过改造 $f_w$ 来支持有向图。我们引入一个变量 $d_l, l \in \mathcal E_v$：如果边 $l$ 的终点为 $v$ 则 $d_l = 1$；如果边 $l$ 的起点为 $v$ 则 $d_l = 0$。则有：

   $$\mathbf{\vec x}_v = f_w( {\vec l}_v, {\vec l}_{\mathcal E_v}, \mathbf {\vec d}_{\mathcal E_v}, \mathbf{\vec x}_{\mathcal N_v}, {\vec l}_{\mathcal N_v})$$

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

   $$\mathbf{\vec x}_v = f_{w_{k_v}}^{k_v}({\vec l}_v, {\vec l}_{\mathcal E_v},\mathbf{\vec x}_{\mathcal N_v}, {\vec l}_{\mathcal N_v})\\ \mathbf{\vec o}_v = g_{w_{k_v}}^{k_v}(\mathbf{\vec x}_v,{\vec l}_v)$$

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

7. 令 $\mathbf{\vec x}, \mathbf{\vec o},\vec l,\vec l_V$ 分别代表所有顶点状态向量的拼接、所有顶点输出向量的拼接、所有标签（包含顶点标签以及边的标签）向量的拼接、所有顶点标签向量的拼接：

   $$\mathbf{\vec x} = \begin{bmatrix} \mathbf{\vec x} _1\\ \mathbf{\vec x} _2\\ \vdots\\ \mathbf{\vec x} _{|V|} \end{bmatrix} ,\quad \mathbf{\vec o} = \begin{bmatrix} \mathbf{\vec o} _1\\ \mathbf{\vec o} _2\\ \vdots\\ \mathbf{\vec o} _{|V|} \end{bmatrix} ,\quad \vec l = \begin{bmatrix} \vec l_1\\ \vec l_2\\ \vdots\\ \vec l_{|V|}\\ \vec l_{1,2}\\ \vec l_{1,3}\\ \vdots\\ \vec l_{1,|V|}\\ \vdots\\ \vec l_{|V|,|V|-1} \end{bmatrix} ,\quad \vec l_V = \begin{bmatrix} \vec l_1\\ \vec l_2\\ \vdots\\ \vec l_{|V|} \end{bmatrix}$$

   则有：

   $$\mathbf{\vec x} = F_w(\mathbf{\vec x}, {\vec l})\\ \mathbf{\vec o} = G_w(\mathbf{\vec x}, {\vec l}_V)$$

   其中：

   • $F_w$ 称作全局转移函数 global transition fucntion，它由 $|V|$ 个 $f_w$ 组成。
   • $G_w$ 称作全局输出函数 global output function ，它由 $|V|$ 个 $g_w$ 组成。

   令图和顶点的 pair 对的集合为 $\mathcal D = \mathcal G\times \mathcal V$，其中 $\mathcal G$ 为所有图的集合，$\mathcal V$ 为这些图中所有顶点的集合。全局转移函数和全局输出函数定义了一个映射 $\varphi_w: \mathcal D \rightarrow \mathbb R^m$ ，它以一个图作为输入，然后对每个顶点 $v$ 返回一个输出 $\mathbf{\vec o}_v$ 。

8. 图结构的数据可以是位置相关的 positional 或者是位置无关的 non-positional 。前面描述的都是位置无关的，位置相关的有所不同：需要为顶点 $v$ 的每个邻居分配唯一的整数标识符来指示其位置。即：对于顶点 $v$ 的邻域 $\mathcal N_v$，存在一个映射函数 $\nu_v: \mathcal N_v \rightarrow \{1,2,\cdots,|\mathcal N_v|\}$ ，使得顶点 $v$ 的每个邻居 $u \in \mathcal N_v$ 都有一个位置 $\nu_v(u)$ 。

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

     

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

     实际中我们可以根据邻居的位置进行排序，然后对 $\vec l_{\mathcal E_v}, \mathbf{\vec x}_{\mathcal N_v}, \vec l_{\mathcal N_v}$ 按照排序之后的顺序进行拼接。如果在某些位置处的邻居不存在，则需要填充 null 值。

     如：

     $$\mathbf {\vec x}_{\mathcal N_v} = \begin{bmatrix} \mathbf{\vec y}_1\\ \mathbf{\vec y}_2\\ \vdots\\ \mathbf{\vec y}_M \end{bmatrix}$$

     其中：

     • $M = \max_{v,u}\nu_v(u)$ 为所有顶点的最大邻居数。

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

       $$\mathbf{\vec y}_i = \begin{cases} \mathbf{\vec x}_u &\text{if}(i=\nu_v(u))\\ \mathbf{\vec x}_0&\text{else} \end{cases}$$

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

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

     $$\mathbf{\vec x}_v = \sum_{u\in \mathcal N_v}h_{w} ({\vec l}_v,{\vec l}_{(u,v)}, \mathbf{\vec x}_{u},{\vec l}_{u})$$

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

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

   • 求解以下方程的算法：

     $$\mathbf{\vec x}_v = f_w( {\vec l}_v, {\vec l}_{\mathcal E_v}, \mathbf{\vec x}_{\mathcal N_v}, {\vec l}_{\mathcal N_v})\\ \mathbf{\vec o}_v = g_w(\mathbf{\vec x}_v, {\vec l}_v)$$

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

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

1.1.1 方程求解算法

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

   $$||F_w(\mathbf{\vec x}, {\vec l}) - F_w(\mathbf{\vec y}, {\vec l})|| \le \mu ||\mathbf{\vec x} - \mathbf{\vec y}||$$

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

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

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

   $$\mathbf{\vec x}(t+1) = F_w(\mathbf{\vec x}(t), {\vec l})$$

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

   • 对于任意初始值 $\mathbf{\vec x}(0)$ ，上式指数级收敛到方程 $\mathbf{\vec x} = F_w(\mathbf{\vec x}, {\vec l})$ 的解。

   • 我们将 $\mathbf{\vec x}(t)$ 视为状态向量，它由转移函数 $F_w$ 来更新。因此输出向量 $\mathbf{\vec o}_v(t)$ 和状态向量 $\mathbf{\vec x}(t)$ 的更新方程为：

     $$\mathbf{\vec x}_v(t+1) = f_w({\vec l}_v,{\vec l}_{\mathcal E_v}, \mathbf{\vec x}_{\mathcal N_v}(t), {\vec l}_{\mathcal N_v})\\ \mathbf{\vec o}_v(t) = g_w(\mathbf{\vec x}_v(t), {\vec l}_v),\quad v\in V$$

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

     在编码网络中，每个单元根据邻居单元的状态、当前顶点的信息、邻居顶点的信息、边的信息，通过 $f_w$ 计算下一个时刻的状态 $\mathbf{\vec x}_v(t+1)$ 。

     注意：这里没有根据 $\mathbf{\vec x}_v(t+1)$ 没有考虑 $\mathbf{\vec x}_v(t)$ ，也就是没有自环。

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

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

     

1.1.2 参数学习算法

1. 假设训练集为：

   $$\mathcal L = \{(G_i,v_{i,j},\mathbf{\vec t}_{i,j})\mid G_i=(V_i,E_i)\in \mathcal G, v_{i,j}\in V_i,\mathbf{\vec 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 |V_i|$$

   其中 $G_i$ 表示第 $i$ 个图，$V_i$ 表示第 $i$ 个图的顶点集合，$E_i$ 表示第 $i$ 个图的边集合，$v_{i,j}$ 表示第 $i$ 个图的第 $j$ 个顶点，$\mathbf{\vec t}_{i,j}$ 表示顶点 $v_{i,j}$ 的监督信息target ，$q_i$ 为图 $G_i$ 中的标记样本。

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

     $$\mathcal L = (G,\mathcal T)$$

     其中 $G=(V,E)$ 表示大图，$\mathcal T = \{(v_i,\mathbf{\vec t}_i)\mid v_i\in V, \mathbf{\vec t}_i\in \mathbb R^m, 1\le i\le q\}$ 表示 “顶点-目标” pair 对的集合。这种表述方式不仅简单而且实用，它直接捕获了某些仅包含单个图的问题的本质。

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

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

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

   $$\mathcal L_w = \sum_{i=1}^p\sum_{j=1}^{q_i}||\mathbf{\vec t}_{i,j} - \varphi_w(G_i,v_{i,j})||_2^2$$

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

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

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

     $$\mathbf{\vec x}_v(t+1) = f_w({\vec l}_v,{\vec l}_{\mathcal E_v}, \mathbf{\vec x}_{\mathcal N_v}(t), {\vec l}_{\mathcal N_v})\\ \mathbf{\vec o}_v(t) = g_w(\mathbf{\vec x}_v(t), {\vec l}_v),\quad v\in V$$

     其解接近 $\mathbf{\vec x} = F_w(\mathbf{\vec x}, {\vec l})$ 的不动点：$\mathbf{\vec x}(T) \simeq \mathbf{\vec x}$ 。

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

   • 求解梯度 $\nabla_{\mathbf{\vec w}} \mathcal L_w$ 。

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

     BPTT 是在展开图上执行传统的反向传播算法。 首先计算时间步 $T$ 的损失函数，以及损失函数在每个时间步 $t$ 相对于 $f_w$ 和 $g_w$ 的梯度。最终 $\nabla_{\mathbf{\vec w}} \mathcal L_w(T)$ 由所有时间步的梯度之和得到。

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

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

     • 定理：如果全局转移函数 $F_w(\mathbf{\vec x}, {\vec l})$ 和全局输出函数 $G_w(\mathbf{\vec x}, {\vec l}_V)$ 对于状态 $\mathbf{\vec x}$ 和参数 $\mathbf{\vec w}$ 都是连续可微的，则 $\varphi_w$ 对于参数 $\mathbf{\vec w}$ 也是连续可微的。

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

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

       $$\mathbf{\vec z}(t) = \left(\frac{\partial F_w(\mathbf{\vec x},\vec l) }{\partial \mathbf{\vec x}}\right)^T\mathbf{\vec z}(t+1)+ \left(\frac{\partial G_w(\mathbf{\vec x},\vec l_V)}{\partial \mathbf{\vec x}}\right)^T\nabla_{\mathbf {\vec o}}\mathcal L_w(t)$$

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

       更进一步有：

       $$\nabla_{\mathbf{\vec w}} \mathcal L_w = \left(\frac{\partial G_w(\mathbf{\vec x},\vec l_V)}{\partial \mathbf{\vec w}}\right)^T\nabla_{\mathbf {\vec o}}\mathcal L_w + \left(\frac{\partial F_w(\mathbf{\vec x},\vec l)}{\partial \mathbf{\vec w}}\right)^T \mathbf{\vec z}$$

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

       证明见论文原文。其中：

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

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

         可以证明：

         $$\mathbf{\vec z}(t) = \sum_{i=T}^t\frac{\partial \mathcal L_w(T)}{\partial \mathbf{\vec x}(i)}$$

         即： $\mathbf{\vec z}(t)$ 等价于 $\frac{\partial \mathcal L_w(T)}{\partial \mathbf{\vec x}(i)}$ 的累加。

         证明过程：

         $$\mathbf{\vec z}(t) = \left(\frac{\partial F_w(\mathbf{\vec x},\vec l) }{\partial \mathbf{\vec x}}\right)^T\mathbf{\vec z}(t+1)+ \left(\frac{\partial G_w(\mathbf{\vec x},\vec l_V)}{\partial \mathbf{\vec x}}\right)^T\nabla_{\mathbf {\vec o}}\mathcal L_w(t)\\ = \left(\left(\frac{\partial F_w(\mathbf{\vec x},\vec l) }{\partial \mathbf{\vec x}}\right)^{T-t}\right)^T\mathbf{\vec z}(T) + \sum_{i=0}^{T-t-1} \left(\left(\frac{\partial F_w(\mathbf{\vec x},\vec l) }{\partial \mathbf{\vec x}}\right)^{i}\right)^T\left(\frac{\partial G_w(\mathbf{\vec x},\vec l_V)}{\partial \mathbf{\vec x}}\right)^T\nabla_{\mathbf {\vec o}}\mathcal L_w(t)$$

         其中最外层的 $()^T$ 表示矩阵的转置，内层的 $()^i$ 表示矩阵的幂。

         考虑到收敛结果和初始状态 $\mathbf{\vec z}(T)$ 无关，因此假设：

         $$\mathbf{\vec z}(T) = \left(\frac{\partial G_w(\mathbf{\vec x}(T),\vec l_V)}{\partial \mathbf{\vec x}(T)}\right)^T\nabla_{\mathbf {\vec o}}\mathcal L_w(T)$$

         并且当 $t_0 \le t \le T$ 时有 $\mathbf{\vec x}(t) = \mathbf{\vec x}$ ，以及 $\mathcal L_w(t) = \mathcal L_w(T)$，则有：

         $$\mathbf{\vec z}(t) = \sum_{i=0}^{T-t}\left(\left(\frac{\partial F_w(\mathbf{\vec x},\vec l) }{\partial \mathbf{\vec x}}\right)^{i}\right)^T\left(\frac{\partial G_w(\mathbf{\vec x},\vec l_V)}{\partial \mathbf{\vec x}}\right)^T\nabla_{\mathbf {\vec o}}\mathcal L_w(t)\\ = \sum_{i=0}^{T-t}\left(\prod_{j=1}^i\left(\frac{\partial F_w(\mathbf{\vec x}(T-j),\vec l) }{\partial \mathbf{\vec x}(T-j)}\right)^T\right)\left(\frac{\partial G_w(\mathbf{\vec x}(T),\vec l_V)}{\partial \mathbf{\vec x}(T)}\right)^T\nabla_{\mathbf {\vec o}}\mathcal L_w(T)$$

         考虑到：

         $$\frac{\partial \mathcal L_w(T)}{\partial \mathbf{\vec x}(T-i)} = \left(\frac{\partial \mathbf{\vec o}(T)}{\partial \mathbf{\vec x}(T-i)}\right)^T \frac{\partial \mathcal L_w(T)}{\partial \mathbf{\vec o}(T)}\\ = \left(\frac{\partial \mathbf{\vec x}(T)}{\partial \mathbf{\vec x}(T-i)}\right)^T\left(\frac{\partial G_w(\mathbf{\vec x}(T),\vec l_V)}{\partial \mathbf{\vec x}(T)}\right)^T\nabla_{\mathbf {\vec o}}\mathcal L_w(T)\\ = \left(\prod_{j=1}^i\left(\frac{\partial F_w(\mathbf{\vec x}(T-j),\vec l) }{\partial \mathbf{\vec x}(T-j)}\right)^T\right)\left(\frac{\partial G_w(\mathbf{\vec x}(T),\vec l_V)}{\partial \mathbf{\vec x}(T)}\right)^T\nabla_{\mathbf {\vec o}}\mathcal L_w(T)$$

         因此有：

         $$\mathbf{\vec z}(t) = \sum_{i=0}^{T-t} \frac{\partial \mathcal L_w(T)}{\partial \mathbf{\vec x}(T-i)} = \sum_{i=T}^t\frac{\partial \mathcal L_w(T)}{\partial \mathbf{\vec x}(i)}$$

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

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

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

4. FORWARD 部分：

   • 输入：

     • 图 $G = (V,E)$
     • 当前参数 $\mathbf{\vec w}$
     • 迭代停止条件 $\epsilon_f$

   • 输出：不动点 $\mathbf{\vec x}$

   • 算法步骤：

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

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

       • 计算 $\mathbf{\vec x}(t+1)$： $\mathbf{\vec x}(t+1) = F_w(\mathbf{\vec x}(t),l)$
       • 令 $t = t+1$

     • 返回 $\mathbf{\vec x}(t)$

5. BACKWARD 部分：

   • 输入：

     • 图 $G=(V,E)$
     • 不动点 $\mathbf{\vec x}$
     • 当前参数 $\mathbf{\vec w}$
     • 迭代停止条件 $\epsilon_b$

   • 输出：

   • 算法步骤：

     • 定义：

       $$\mathbf{\vec o} = G_w(\mathbf{\vec x},\vec l_V)\quad \mathbf A = \left(\frac{\partial F_w(\mathbf{\vec x},\vec l)}{\partial \mathbf{\vec x}}\right)^T\\ \mathbf{\vec b} =\left(\frac{G_w(\mathbf{\vec x},\vec l_V)}{\partial \mathbf{\vec x}}\right)^T\nabla_{\mathbf{\vec o}}\mathcal L_w$$

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

     • 循环迭代，直到满足 $||\mathbf{\vec z}(t-1) - \mathbf{\vec z}(t)||\le \epsilon_b$。迭代步骤为：

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

     • 计算梯度：

       $$\nabla_{\mathbf{\vec w}} \mathcal L_w = \left(\frac{\partial G_w(\mathbf{\vec x},\vec l_V)}{\partial \mathbf{\vec w}}\right)^T\nabla_{\mathbf {\vec o}}\mathcal L_w + \left(\frac{\partial F_w(\mathbf{\vec x},\vec l)}{\partial \mathbf{\vec w}}\right)^T \mathbf{\vec z}(t)$$

     • 返回梯度 $\nabla_{\mathbf{\vec w}}\mathcal L_w$

6. Main 部分：

   • 输入：

     • 图 $G=(V,E )$
     • 学习率 $\lambda$

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

   • 算法步骤：

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

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

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

       • 通过反向计算过程计算梯度：$\nabla_{\mathbf{\vec w}} \mathcal L_w = \text{Backward}(\mathbf{\vec x},\mathbf{\vec w})$
       • 更新参数：$\mathbf{\vec w} = \mathbf{\vec w} - \lambda \nabla_{\mathbf{\vec w}} \mathcal L_w$
       • 通过新的参数计算状态：$\mathbf{\vec x} = \text{Forward}(\mathbf{\vec w})$

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

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

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

1.1.3 转移函数和输出函数

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

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

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

3. nonpositional linear GNN 线性 GNN：

   $$h_{w} ({\vec l}_v,{\vec l}_{(u,v)}, \mathbf{\vec x}_{u},{\vec l}_{u}) = \mathbf A_{v,u} \mathbf{\vec x}_u + \mathbf{\vec b}_v$$

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

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

     设该神经网络为一个映射 $\phi_w:\mathbb R^{2n_V+n_E} \rightarrow \mathbb R^{s^2}$，则定义：

     $$\mathbf A_{v,u} = \frac{\mu}{s\times |\mathcal N_u|}\mathbf B$$

     其中：

     • $\mathbf B$ 是由 $\phi_w(\vec l_v,\vec l_{v,u},\vec l_u)$ 的 $s^2$ 个元素进行重新排列得到的矩阵。
     • $\mu\in (0,1)$ 为缩放系数，$\frac{\mu}{s\times |\mathcal N_u|}$ 用于对矩阵 $\mathbf B$ 进行缩放。

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

     设该神经网络为一个映射 $\rho_w: \mathbb R^{n_V} \rightarrow \mathbb R^s$，则定义：

     $$\mathbf{\vec b}_v = \rho_w(\vec l_v)$$

   假设有：$||\phi_w(\vec l_v,\vec l_{v,u},\vec l_u)||_1 \le s$ ，即 $|\mathbf B|_1 \le s$。事实上如果转移神经网络的输出神经元采用有界的激活函数（如双曲正切），则很容易满足该假设。

   根据 $h_{w} ({\vec l}_v,{\vec l}_{(u,v)}, \mathbf{\vec x}_{u},{\vec l}_{u}) = \mathbf A_{v,u} \mathbf{\vec x}_u + \mathbf{\vec b}_v$ 有：