这可能是比较早提出图神经网络模型的一篇文章，在这里摘录一些重点。
原文: The Graph Neural Network Model
Abstract and Introduction
很多关系型的数据需要用图论中的图结构来描述，例如分子模型、社交网络等。我们比较难用传统的神经网络来直接刻画这种结构关系，因此这篇文章提出了 Graph Neural Network 来扩展传统神经网络在图数据域的表达能力。具体来说，GNN 提供了一个映射函数 $\tau(\mathrm{G},n) \in \mathbb{R}^m$ 来把一个图 $G$ 以及其中的一个节点 $n$ 来嵌入到一个 $m$ 维的欧氏空间中。 在针对图整体(graph focused)的应用中， $\tau$ 并不关心节点 $n$， 只是对图结构整体做一个分类或者回归任务， 例如对无向图描述的分子结构， 我们可能想设计一个网络来判断它是否对某种疾病具有疗效。 而在针对节点(node focused)的应用中， 模型依赖于每个节点的具体属性。 例如说， 在目标检测中， 可以通过 $\tau$ 在区域邻接图上对节点进行标记， 进而通过标记结果选择检测出来的目标部分。
传统的机器学习方法在处理图数据的时候， 往往通过将图转化成更简单的表示， 如简单的向量， 但这个过程中可能会丢失拓扑结构之类的信息。 已有的一些方法通过预处理来处理无环图和一部分的有环图， 如 RNN、 马尔科夫链等。 这篇文章提出的方法扩展了已有方法， 得到了能比较好处理图结构的方法。
The Graph Neural Network Model
Notations
$N$ 表示节点集合。 $E$ 表示边集合。 $ne[n]$ 表示 $n$ 的邻居集合。 $co[n]$ 表示 $n$ 的邻边集合。 节点和边的标签信息记为 $l_n$ 和 $l_{(n_1,n_2)}$， 维度分别为 $l_N$ 和 $l_E$。 令 $l$ 表示堆叠所有标签得到的结果。 我们将图分为 Positional Graphs 和 Non-positional Graphs。 Positional Graph 中， 对于节点 $n$ 的邻居是存有排列信息的。 例如在区域邻接图上， 可以有一个函数 $v_n$ 描述了 $n$ 邻居的逆时针顺序。
我们研究的问题定义在域 $\mathcal{D} = \mathcal{G} \times \mathcal{N}$ 上。 其中 $\mathcal{G}$ 是一系列图的集合， 而 $\mathcal{N}$ 是节点的集合。 一组训练集的形式如同 $\mathcal{L} = \left\{ (G_i, n_{i,j}, t_{i,j}) | G_i = (N_i, E_i) \in \mathcal{G}; n_{i,j} \in N_i; t_{i,j} \in \mathbb{R}^m\right\}$。 其中下标 $i,j$ 描述了第几个图的第几个有标注节点。 我们可以进一步把这些图视作一个大的不连通图的不同部分， 这样也可以写作 $\mathcal{L} = (G, \mathcal{T})$， 其中 $G$ 是整个大图而 $\mathcal{T}$包含了所有被标注的节点-标签对 $(n_i, t_i)$。
The Model
感性地来说， 可以认为图中的节点表示概念（或者实体）， 而边表示它们之间的关系。 一个概念应该由它自身的特征以及相关概念所定义。 我们对每个节点 $n$ 定义 $x_n \in \mathbb{R}^s$ 表示它的状态函数， 这由它自身的标签、邻居的标签、邻边标签、邻居的状态决定。即 $x_n = f_w(l_n, l_{co[n]}, l_{ne[n]}, x_{ne[n]})$。 其中 $f_w$ 被称为局部转化函数(local transition function)， 由参数 $w$ 控制。 在具体的任务中， 我们可能需要输出一些定制化的信息， 如节点分类的结果， 这通过另一个函数 $g_w$ 得到， $g_w$ 被称为局部输出函数(local output function)。 总之， 状态 $x$ 和输出 $o$ 如下定义：
将所有的 $x_n$ 和 $o_n$ 合并到一个向量里，可以得到简化的形式。其中 $l_N$ 表示节点的标签。 $F_w$ 和 $G_w$ 被称为全局转化/输出函数。
可以看到这个方程组中， 我们希望得到的 $x$ 是方程 $x = F_w(x, l)$ 的一个不动点。 由 Banach 不动点定理， 当 $F_w$ 是一个压缩映射的时候， 即存在 $0 < \mu < 1$， 使得对于任意 $x, y$， 我们有 $\parallel F_w(x, l) - F_w(y, l) \parallel$， 那我们可以通过迭代来以指数级收敛的速度找到这个不动点。 稍后我们可以证明， 可以通过适当的实现来满足压缩映射的要求。
我们尝试用神经网络去实现 $f_w$ 和 $g_w$。
Learning Algorithm
之前提到过， 训练集的形式是 $\mathcal{L} = \left\{ (G_i, n_{i,j}, t_{i,j}) | G_i = (N_i, E_i) \in \mathcal{G}; n_{i,j} \in N_i; t_{i,j} \in \mathbb{R}^m\right\}$。 对于 graph-focusd 的任务， 我们仅在图中选择一个点作为标注节点。 我们希望最小化代价函数：
训练过程如下：
- 迭代 $T$ 轮近似得到 $x$ 的不动点 $x(T) \approx x$。
- 计算 $\frac{\partial{e_w}}{\partial{w}}$， 梯度下降优化参数。
Theorem 1: Differentiability
在 $F_w$ 和 $G_w$ 可微， 且迭代求解不动点的动力系统稳态确定的情况下， 证明 $\varphi(G,n)$ 也可微。
令 $\Theta(x,w) = x - F_w(x,l)$， 由假设， $\Theta$ 关于 $x$ 和 $w$ 均可微。 $\frac{\partial{\Theta}}{\partial{x}}(x, w) = I_{|s|} - \frac{\partial{F_w}}{\partial{x}}(x, w)$。 由于 $F_w$ 是一个压缩映射， 存在一个 $0 \le \mu \lt 1$ 使得 $\parallel \frac{\partial{F_w}}{\partial{x}}(x, w) \parallel \le \mu$（考虑矩阵诱导范数的定义：最多能将一个向量的范数放缩多少倍， 再考虑压缩映射的定义， 是任意向量经过映射后的范数是原先的至多 $\mu$ 倍， 而 Jacobi 矩阵定义了在邻域内的缩放比例， 则这个结论显然）， 原文说， 这说明 $\parallel \frac{\partial{\Theta}}{\partial{x}}(x, w) \parallel \gt (1 - \mu)$。 我觉得这里的符号可能有所混淆， 应该是一个类似于诱导范数的定义， 但是取的是放缩比例的最小值， 即 $\min_{u \not = 0}\frac{\parallel \frac{\partial{\Theta}}{\partial{x}}(x, w)u \parallel}{\parallel u \parallel} \gt (1 - \mu)$。 这样就可以得出 $\frac{\partial{\Theta}}{\partial{x}}(x, w)$ 的行列式非 $0$ （否则直接取特征值 $0$ 对应的特征向量，就可以得到 $0$ 的放缩比例）。
根据隐函数定理， 和压缩映射的性质， 我们在任意的 $w$ 处有可微函数 $\Psi(w)$ 使得 $\Theta(\Psi(w), w) = 0$， 即 $\Psi(w) = F_w(\Psi(w), l)$。 因此这个不动点是关于 $w$ 可微的。 而 $\varphi(G, n)$ 不过是在外面再套了一层输出函数， 依然是可微的。
Theorem 2: Backpropagation
其中， $z=\lim_{t \rightarrow -\infty}z(t)$：