论文笔记：Graphical-based learning environments for pattern recognition
大多数应用程序都使用预处理阶段来处理图结构数据，预处理阶段将图结构信息映射为更简单的表示，比如实数向量。但是，在预处理阶段，节点n上信息的拓扑依赖性等重要信息可能会丢失，最终结果则会不可避免的受到预处理信息丢失的影响。因此，有一些提出的方法首先避免了图数据的预处理，然后使用基于列表的数据处理技术处理预处理数据，而不是特别关注数据的底层图结构性质（这里也没太理解）。换句话说，这些最近的方法试图在数据处理步骤中结合图形结构信息。在关注图的方法中，这是通过递归神经网络来完成的（即上一篇论文中提到的），而在关注节点的方法中，这通常是通过使用随机游走技术(random walk)来完成的。
本文提出了一种新的神经网络模型，它既适用于图的应用，也适用于节点的应用。
符号声明和预备知识
Labels这里指的应该是特征的意思。
本文提出的图神经网络是基于不动点定理和压缩映射的。
- 不动点：存在X使得X=g(x)，该X称为不动点。不定点存在的充分条件是，函数g是压缩映射。
- 压缩映射：函数g：Rd->Rd可微，且存在大于0小于1的e使得g关于X的雅可比矩阵（偏导矩阵）的一范数小于e。此时g是压缩映射，且序列x(t)=g(x(t-1))将收敛于不动点。
一种新的神经网络模型
该方法的直观思想是，图节点代表对象或概念，边代表它们之间的关系。因此，可以给节点n定义一个状态xn，一个s维的向量，它的值与自身的特征，邻居节点的特征还有与连接节点之间的边的特征有关，这个也比较好理解。ln和xn的区别就在于，ln是节点自身的特征（比如一个引文网络中节点是一篇文章，特征就可以是它的字数，关键字什么的），而xn是节点结合了它在图中的拓扑信息的特征，利于其在当前图中的分类任务。如下图：
用公式1表示xn（无向图，后面也都是以无向图为例，因为无向图的结论可以很方便的转到有向图上）：
其中w是F函数的参数，这里的邻居是1步之内的，更一般的我们可以考虑xn取决于n步之内的邻居节点。
对于每个节点，代表其类别的向量On,一个m维的向量，取决于xn和ln。用公式2表示：
将所有的特征L和状态x都压缩到一起，得到下面的公式：
上式包含了r个Fw的实例
注意到公式一的解xn是Fw函数的不动点。因此我们需要精心设计Fw使其为压缩映射使得公式一有唯一解（为什么是唯一解？）
实际上，函数Fw和Ow将由特定的静态神经网络模型来实现。总结下来就是，公式1和公式2给每个节点定义了一个输出向量，可以表示为fw(G,n)=Ow。因此学习任务变成了：调整Ow和Fw的参数w，使输出Ow逼近训练集中的数据。在实际应用中，学习问题可以通过最小化二次误差函数来实现：
由于Fw的输入数量不是固定的，而是取决于每个节点的邻居数量，因此Fw的实现可能比较困难，特别是在节点连通性变化较大的情况下。因此，用公式3代替式(1)可能是有用的：
为了实现由式(1)和(2)正式定义的模型，必须解决以下问题：
- 求解公式1
- 一种基于训练数据集的优化Fw和Ow参数的学习算法
- Fw和Ow函数的设计使得Fw是压缩映射。
求解公式1
给定xn任意初始值集合，按以下公式4迭代一定次数直到xn收敛（Fw是压缩映射时必收敛），此时Xn的收敛值就是要求的解，具体如何存储数据就不详细记了。
其中t指代第t次迭代。用于实现F和O的神经网络称为编码网络(encoding network)。
训练算法
我们提出的学习算法分为两个阶段:
- 根据上面迭代的方法求出xn
- ∂ew(T)∂w被计算，权重w根据梯度下降策略更新。
梯度反向传播过程中，通过时间反向传播需要存储单元的每个实例的状态。当图形和T - t0较大时，所需的内存可能相当大。由于系统已经到达一个稳定点，我们可以假设当t≥t0时，x(t)= x(t0)，因此只存储x(t0)就可以进行时间反向传播。
与递归神经网络和随机游动进行比较
这一节向我们给出了几个结论：首先本文的GNN是递归神经网络的一个拓展。（未细读）
然后，图上的随机游动就是本文模型的一个实例，是它的线性版本。Fw是一个线性函数。
其中wn,i是代表随机游走从n到节点的概率。且概率和为1。将Xn组合成一个向量，则上式可以表示为：
W的1范数等于1。可以证明Fw是一个压缩映射
Fw和Ow的实现
Ow是简单的前馈神经网络，而fw需要设计神经网络使其为压缩映射函数。
未读
后记
这篇论文是比较经典的，原作者也写了很多版本。
- The graph neural network model
- Graph neural networks for ranking web pages
- A new model for earning in raph domains