图形神经网络(GNN )一.背景图形神经网络的概念首先由Gori等人(2005 ) )提出，并由Scarselli等人(2009 ) ) 17 )进一步阐明。 这些初步研究通过循环神经架构传递邻域信息，迭代学习目标节点的表示，直到达到稳定的固定点。 该过程所需的计算量巨大，但最近为了解决这个课题进行了很多研究。 本文中，图神经网络表示了用于图数据的所有深度学习方法。
受卷积网络在计算机视觉领域取得巨大成功的启发，最近出现了很多重新定义图表数据卷积概念的方法。 这些方法属于图卷积网络(GCN )的范畴。 Bruna等人(2013 )提出了关于基于spectral graph theory )开发图卷积变化的图卷积网络的第一个重要研究。 自此，基于谱的图卷积网络不断改进、扩展、进步。 由于谱法通常难以同时处理整个图并扩展为并行或大规模的图，基于空间的图卷积网络开始迅速发展
二.图的概念和基础2.1图论介绍图论〔Graph Theory〕是数学的一个分支。 那个是以地图为研究对象的。 图论中的图是由几个给定的点和连接两点的线组成的图形。 此图形通常用于表达某事物之间的某种特定关系，用点表示事物，用连接点的线表示对应的两个事物之间存在这种关系。
世界上许多信息之间的联系可以用图像抽象的数学方式来表示，是表示网络之间关系的连接图。
2.2图论的基本研究对象-----图(Graph )是表示对象与对象关系的数学对象，是图论的基本研究对象。 在一个加权图中，如果两点不相邻，则邻接矩阵的相应位置为0，对于加权图(网)，相应位置为。
对于具有n个顶点的有向连通图，其边数必定多于n-1条。 从中选择n-1条边，使有向图仍然连接的话，由n个顶点和这个n-1条边(弧)构成的图被称为原来的有向图的生成树。
2.3定义图的二元组的定义图g是有序的二元组(v，e )，其中v称为顶集合(Vertices Set )，e称为边集合(Edges set )，e不与v相交。 它们也可以写成v(g )和v(g )。
的元素均为二元组，用(x，y )表示，其中x，yV。
三元组的定义图g指的是一个三元组(v，e，I )，这里v称为顶集合，e称为边集合，e和v不相交； I称为相关函数，I将e的每个元素映射到。 当e映射到(u，v )时，连接被称为边e的顶点u，v，但u，v被称为e的端点，u，v此时与e相邻。 另外，如果两边I，j有共同的顶点u，则I，j称为关于u邻接。
2.4分类有向图的每边确定一个方向，得到的图就称为有向图。 在有向图中，与一个节点相关联的边有边的输出和输入的区别。 相反，边没有方向的图称为无向图。
如果单个图任意两个顶点之间只有一条边(在有向图中两个顶点之间的每个方向上只有一条边)； 如果边的集中不包含环，则称为单图。
三、GNN (基于循环结构)理论基础------为了在不懂点理论的情况下理解GNN，有必要知道什么是不动点理论。
GNN的理论基础是不动点(the fixed point )理论，这里的不动点理论指的是巴拿赫不动点定理(Banach’s Fixed Point Theorem)。
3.1巴拿赫不动点定理定义了巴拿赫不动点定理，又称为压缩映射定理或压缩映射原理，是衡量空间理论的重要工具。 保证了度量空间恒自映射不动点的存在性和唯一性，并给出了求解这些不动点的构造方法。 这个定理以感动的可乐命名，他于1922年提出了这个定理。
定理的内容是将(x，d )作为非空的完备度量空间。 设T:XX为x上的压缩映射。 也就是说，对于所有x内的x和y，存在以下的非负实数q1
那么映射t在x内，且只有一个不动点x (即，Tx=x )。 此外，该不动点可以从x内的任何要素x0开始，通过对n=1、2、3、定义迭代序列xn=Txn-1来求出。 该序列收敛，极限为x。 以下不等式显示了收敛的速度。
等价于：
然后呢
有时将满足以上不等式的最小q称为利普希茨常数。
请注意，对所有不同的x和y都有d(tx，Ty ) d ) x，y )的要求。 一般来说，这并不足以保证不动点的存在。 例如，如果映射T: [1， [1，]，t ) x )=x 1/x，则没有不动点。 然而，如果空间x是充分的，这个弱假设也可以保证不动点的存在。
实际应用这个定理时，最难的部分通常是恰当地定义x，使得t实际上将元素从x映射到x。 换句话说，Tx总是x的一个元素。
在GNN上的操作首先，将以3358www.Sina.com/表示若干个F而得到的函数也称为全局更新函数，但是图中的所有节点的状态更新式可以写成如下。
不管是什么不动点定理，如果f为http://www.Sina.com/(contraction map )，则通过反复地收敛于某一定点，我们称为不动点
3.2什么是压缩映射？ 将定义(x，)作为距离空间，
T是X 到 X中的映射，如果存在数a (0<a<1)，使得对所有的x,y∈X都有ρ(Tx, Ty)≤a*ρ(x, y)，则称T是压缩映射，压缩映射也称为利普希茨映射。那么既然 f 是由 神经网络实现的，如何保证它是一个压缩映射呢？
3.3 用前馈神经网络实现 压缩映射一种实现方法可以是把每个邻居结点的特征、隐藏状态、每条相连边的特征以及结点本身的特征简单拼接在一起，在经过前馈神经网络后做一次简单的加和。
那我们如何保证 f 是个压缩映射呢，其实是通过限制 f 对 H 的偏导数矩阵的的惩罚项大小，这是通过一个对雅可比矩阵(Jacobian Matrix)的惩罚项(Penalty)来实现的。
（图片来自网络）
（图片来自网络）
从将图输入到GNN中到得到输出结果 主要可以分为两步：第一步是传播（propagation）过程，即节点表示随时间的更新过程；第二步是输出（output）过程，即根据最终的节点表示得到目标输出（如每个节点的类别）的过程。在这两步中，传播过程要更为重要，其设计也要受到一定的约束（要保证整个图上的状态映射是一个压缩映射（contraction map））。在展开图中，传播过程对应于从 到 的更新过程（注意， 并不是确定的，而是对应于整个图的状态到达不动点的时刻），不同时间步的连接则由图中的连接来决定（可以是有向的，也可以是无向的）。
传播过程 输出过程 GNN 的训练GNN的学习是通过Almeida-Pineda算法实现的。该算法的特点在于，首先通过传播过程使整个图收敛，然后在收敛解上计算相应的梯度。这样，我们就无需存储梯度计算过程所需的中间状态了。但是，必须保证整个图的映射是压缩的，以保证传播过程有一个收敛解。
实验结果表明GNN对于结构化数据的建模十分有效，但仍然存在着诸多的不足。
对于不动点隐藏状态的更新是十分低效的GNN在迭代的过程中用相同的参数，然而大多标准网络在不同的网络层数使用不同的参数在原始的GNN中存在着一些无法有效建模的边缘信息特征。例如，在知识图谱中边代表这关系类型，不同边缘的消息传递应该根据他们的类型有所不同。怎么样去学习边缘的隐藏状态也是一个重要的问题如果把重点放在节点的表示而不是图上，就不适合使用不动点，因为不动点上表示的分布会变得非常平滑，且每个节点的信息量也会减少。