边上面的黑色尖头表示节点之间的关系类型，其可表明一个关系是双向的还是单向的。图有两种主要类型：有向图和无向图。在有向图中，节点之间的连接存在方向；而无向图的连接顺序并不重要。有向图既可以是单向的，也可以是双向的。

图可以表示很多事物——社交网络、分子等等。节点可以表示用户/产品/原子，而边表示它们之间的连接，比如关注/通常与相连接的产品同时购买/键。社交网络图可能看起来像是这样，其中节点是用户，边则是连接： 节点表示用户，边则表示两个实体之间的连接/关系。真实的社交网络图往往更加庞大和复杂！

通常使用 G = ( V , E ) G=(V, E) G=(V,E)来表示图，其中 V V V表示节点的集合、 E E E表示边的集合。对于两个相邻节点 u , v u, v u,v, 使用 e = ( u , v ) e=(u,v) e=(u,v)表示这两个节点之间的边。两个节点之间边既可能是有向，也可能无向。若有向，则称之有向图(Directed Graph), 反之，称之为无向图(Undirected Graph)。

在图神经网络中，常见的表示方法有邻接矩阵、度矩阵、拉普拉斯矩阵等。

邻接矩阵(Adjacency Matrix) 用于表示图中节点之间的关系，对于n个节点的简单图，有邻接矩阵 A ∈ R n × n A\in R^{n\times n} A∈Rn×n: A i j = { 1  if  ( v i , v j ) ∈ E and i ≠ j 0  else  A_{ij}=\begin{cases}1 & \text{ if } (v_i,v_j)\in E \text{and} i\ne j \\0 & \text{ else }\end{cases} Aij​={10​ if (vi​,vj​)∈Eandi=j else ​

度矩阵(Degree Matrix) 节点的度(Degree)表示与该节点相连的边的个数，记作d(v)。对于n个节点的简单图G=(V, E)，其度矩阵D为 D i i = d ( v ) D_{ii}=d(v) Dii​=d(v)，也是一个对角矩阵。

拉普拉斯矩阵 (Laplacian Matrix) 对于n个节点的简单图 G = ( V , E ) G=(V, E) G=(V,E)，其拉普拉斯矩阵定义为 L = D − A L=D-A L=D−A，其中 D D D、 A A A为上面提到过的度矩阵和邻接矩阵. 将其归一化后有 L s y m = D − 1 / 2 L D − 1 / 2 L^{sym}=D^{-1/2}LD^{-1/2} Lsym=D−1/2LD−1/2。

每个节点都有一组定义它的特征。在社交网络图的案例中，这些特征可以是年龄、性别、居住国家、政治倾向等。每条边连接的节点都可能具有相似的特征。这体现了这些节点之间的某种相关性或关系。

假设我们有一个图 G，其具有以下顶点和边： 为了简单起见，假设图节点的特征向量是当前节点的索引的one-hot编码。类似地，其标签（或类别）可设为节点的颜色（绿、红、黄）。那么这个图看起来会是这样： 节点的顺序其实并不重要。

注意：在实际运用中，尽量不要使用 one-hot 编码，因为节点的顺序可能会非常混乱。相反，应该使用可明显区分节点的特征，比如对社交网络而言，可选择年龄、性别、政治倾向等特征；对分子研究而言可选择可量化的化学性质。

现在，我们有节点的 one-hot 编码（或嵌入）了，接下来我们将神经网络引入这一混合信息中来实现对图的修改。所有的节点都可转化为循环单元（或其它任何神经网络架构，只是我这里使用的是循环单元）；所有的边都包含简单的前馈神经网络。那么看起来会是这样： 其中的信封符号只是每个节点的 one-hot 编码的向量（嵌入）。

一旦节点和边的转化完成，图就可在节点之间执行消息传递。这个过程也被称为「近邻聚合（Neighbourhood Aggregation）」，因为其涉及到围绕给定节点，通过有向边从周围节点推送消息（即嵌入）。

注意：有时候可为不同类型的边使用不同的神经网络，比如为单向边使用一种神经网络，为双向边使用另一种神经网络。这样仍然可以获取节点之间的空间关系。

就 GNN 而言，对于单个参考节点，近邻节点会通过边神经网络向参考节点上的循环单元传递它们的消息（嵌入）。参考循环单位的新嵌入更新，基于在循环嵌入和近邻节点嵌入的边神经网络输出的和上使用循环函数。我们把上面的红色节点放大看看，并对这一过程进行可视化： 紫色方块是一个应用于来自近邻节点的嵌入（白色信封）上的简单前馈神经网络；红色三角形是应用于当前嵌入（白色信封）和边神经网络输出（黑色信封）之和上的循环函数，以得到新的嵌入（最上面的白色信封）。

这个过程是在网络中的所有节点上并行执行的，因为 L+1 层的嵌入取决于 L 层的嵌入。因此，在实践中，我们并不需要从一个节点「移动」到另一节点就能执行消息传递。

注意：边神经网络输出（黑色信封）之和与输出的顺序无关。

正式地，图神经网络(GNN)最早由Marco Gori、Franco Scarselli等人提出，他们将神经网络方法拓展到了图数据计算领域。在Scarselli论文中典型的图如图1所示： 图1 典型的图神经网络

为了根据输入节点邻居信息更新节点状态，将局部转移函数 f f f定义为循环递归函数的形式, 每个节点以周围邻居节点和相连的边作为来源信息来更新自身的表达 h h h。为了得到节点的输出 o o o, 引入局部输出函数 g g g。因此，有以下定义： h n = f ( x n , x c o [ n ] , x n e [ n ] , h n e [ n ] ) ( 1 ) h_n=f(x_n, x_{co[n]}, x_{ne[n]}, h_{ne[n]}) \quad (1) hn​=f(xn​,xco[n]​,xne[n]​,hne[n]​)(1) o n = g ( h n , x n ) ( 2 ) o_n=g(h_n, x_n) \quad (2) on​=g(hn​,xn​)(2) 其中 x x x表示当前节点, h h h表示节点隐状态， n e [ n ] ne[n] ne[n]表示表示节点n的邻居节点集合， c o [ n ] co[n] co[n]表示节点n的邻接边的集合。以图1的L1节点为例， X 1 X1 X1是其输入特征, n e [ l 1 ] ne[l_1] ne[l1​]包含节点 l 2 , l 3 , l 4 , l 6 l_2, l_3, l_4, l_6 l2​,l3​,l4​,l6​, c o [ l 1 ] co[l_1] co[l1​]包含边 l ( 3 , 1 ) , l ( 1 , 4 ) , l ( 6 , 1 ) , l ( 1 , 2 ) l_{(3,1)}, l_{(1,4)}, l_{(6,1)}, l_{(1,2)} l(3,1)​,l(1,4)​,l(6,1)​,l(1,2)​。

将所有局部转移函数 f f f堆叠起来, 有： H = F ( H , X ) ( 3 ) H=F(H,X) \quad (3) H=F(H,X)(3) O = G ( H , X n ) ( 4 ) O=G(H,X_n) \quad (4) O=G(H,Xn​)(4)其中F是全局转移函数(Global Transition Function), G是全局输出函数(Global Output Function)。 根据巴拿赫不动点定理，假设公式(3)的F是压缩映射，那么不动点H的值就可以唯一确定，根据以下方式迭代求解: H t + 1 = F ( H t , X ) ( 5 ) H^{t+1}=F(H^t, X) \quad (5) Ht+1=F(Ht,X)(5)基于不动点定理，对于任意初始值，GNN会按照公式(5)收敛到公式(3)描述的解。

执行了几次近邻聚合/消息传递流程之后，每个节点的循环单元都会获得一组全新的嵌入。此外，经过多个时间步骤/多轮消息传递之后，节点对自己和近邻节点的信息（特征）也会有更好的了解。这会为整个图创建出更加准确的表征。

要进一步在该流程的更高层面上进行处理或者只是简单地表征该图，你可以将所有嵌入加到一起得到向量 H 来表示整个图。使用 H 比使用邻接矩阵更好，因为不管怎样对图进行扭转变形，这些矩阵都并不表征图的特征或独特性质——只是节点之间的边连接（这在某些情形下并不是很重要）。

总结一下，将所有节点循环单元的最终向量表征加到一起（当然，与顺序无关），然后使用所得到的向量作为其它工作过程的输入或简单地将其用于表征该图。这个步骤看起来如下图所示： 这是经过 n 次重复消息传递之后带有已完全更新的嵌入向量的最终图。可以将所有节点的表征加到一起得到 H。

GCN可谓是图神经网络的“开山之作”，它首次将图像处理中的卷积操作简单的用到图结构数据处理中来，并且给出了具体的推导，这里面涉及到复杂的谱图理论。2017年，Thomas N. Kipf等人提出GCN模型. 其结构如图2所示： 图2 Thomas N. Kipf等人提出GCN

假设需要构造一个两层的GCN，激活函数分别采用ReLU和Softmax，则整体的正向传播的公式如下所示： Z = f ( X , A ) = s o f t m a x ( A ^ ReLU ( A ^ X W ( 0 ) ) W ( 1 ) ) ( 6 ) Z=f(X,A)=softmax(\hat{A} \text{ReLU}(\hat{A}XW^{(0)})W^{(1)}) \quad (6) Z=f(X,A)=softmax(A^ReLU(A^XW(0))W(1))(6) A ^ = D ~ − 1 2 A ~ D ~ − 1 2 ( 7 ) \hat{A}=\tilde {D}^{-\frac{1}{2}} \tilde{A}\tilde {D}^{-\frac{1}{2}} \quad (7) A^=D~−21​A~D~−21​(7)

其中 W ( 0 ) W^{(0)} W(0)表示第一层的权重矩阵， W ( 1 ) W^{(1)} W(1)表示第二层的权重矩阵，X为节点特征， A ~ \tilde{A} A~等于邻接矩阵A和单位矩阵相加，\tilde{D}为 A A A的度矩阵。

从上面的正向传播公式和示意图来看，GCN好像跟基础GNN没什么区别。接下里给出GCN的传递公式(8)： H ( l + 1 ) = σ ( D ~ − 1 2 A ~ D ~ − 1 2 H ( l ) W ( l ) ) ( 8 ) H^{(l+1)}=\sigma (\tilde {D}^{-\frac{1}{2}}\tilde {A}\tilde {D}^{-\frac{1}{2}}H^{(l)}W^{(l)}) \quad (8) H(l+1)=σ(D~−21​A~D~−21​H(l)W(l))(8) 观察一下归一化的矩阵与特征向量矩阵的乘积： 这种聚合方式实际上就是在对邻接求和取平均。而 D ~ − 1 2 A ~ D ~ − 1 2 \tilde {D}^{-\frac{1}{2}}\tilde {A}\tilde {D}^{-\frac{1}{2}} D~−21​A~D~−21​这种归一化方式，将不再单单地对领域节特征点取平均，它不仅考虑了节点 i i i的度，也考虑了邻接节点 j j j的度，当邻居节点 j j j 度数较大时，它在聚合时贡献地会更少。这也比较好理解，存在B->A