机器学习周报-GNN模型学习

摘要，

本周阅读了The graph neural network model这篇论文，论文提出了一种新的神经网络模型–图神经网络（graph neural network，GNN）模型，该模型扩展了已有的神经网络方法，使之适用于处理以图论表示的数据。该GNN模型可以直接处理大多数实用的图形类型，非循环的、循环的、有向的和无向的。通过看文章和相关资料的学习，对GNN的基本概念，相关流程以及GNN算法的实现原理和过程有了基本的认识。

Abstract

This week, I read the paper titled “The Graph Neural Network Model.” The paper introduces a novel neural network model known as the Graph Neural Network (GNN). This model extends existing neural network methodologies to make them applicable for processing data represented in graph form. The GNN model is capable of directly handling a wide variety of practical graph types, including acyclic, cyclic, directed, and undirected graphs. Through the study of the paper and supplementary materials, I have gained a fundamental understanding of the basic concepts of GNN, its related processes, as well as the principles and procedures behind the implementation of GNN algorithms.

1 GNN介绍

GNN 可以理解为是由 Graph（图) + Nerual Networks 组合而成的

1. 图神经网络（Graph Neural Network，GNN）是一类用于处理图结构数据的深度学习模型。图结构数据中的实体以节点的形式表示，实体之间的关系以边的形式表示。GNN的目标是从图结构数据中学习有用的表示，并利用这些表示进行各种任务，例如节点分类、图分类、链接预测等。
2. 图神经网络的核心思想是通过消息传递机制（message-passing mechanism）来聚合节点的邻居信息，并更新节点的特征表示。这个过程通常会进行多轮迭代，以便捕获图中更远距离的信息。最终，每个节点的特征表示将包含其邻居和更远节点的信息。
3. 图神经网络的基本组成部分包括：
   节点特征矩阵：用于表示图中每个节点的初始特征。
   邻接矩阵：用于表示图中节点之间的连接关系。
   图卷积层：用于聚合邻居节点的信息并更新节点特征。
   输出层：根据任务需求设计的输出层，用于输出预测结果。

基本组件

• 节点表示：每个节点初始的特征向量可通过特征工程获取，通常包括用户的基本信息、行为特征等。
• 消息传递机制：定义如何从邻居节点汇聚信息，包含聚合函数和更新函数。常见的聚合函数有求和、平均和最大池化等。
• 损失函数：根据具体任务设置，如节点分类、边预测等。选择合适的损失函数能够提高模型的性能。

GNN的强大之处在于其能够有效处理非结构化数据，捕捉图中的局部和全局结构，从而在多种任务中实现优越的性能。

相对于传统的神经网络模型，GNN在处理图数据时有一些优势：

1. 能够学习到节点和边之间的复杂关系。与传统神经网络只能处理类似向量或矩阵的数据不同，GNN天然地适用于处理有复杂关系的数据，如社交网络、蛋白质结构中残基之间的关系等。
2. 具有很强的泛化性能。不同于传统的机器学习方法，GNN可以在没有预训练的情况下进行端到端的学习和推理。这意味着GNN可以更好地适应广泛的数据和任务，并且可以避免过度拟合。
3. 涉及节点和边的信息量非常大，对于节点和边上存在多种属性或者情境信息的任务，在GNN中可以很自然地将这些信息进行整合。这些属性可以来自节点和边的语义信息、拓扑信息、上下文信息和其他相关信息。
4. 强大的可扩展性：GNN已经在多个领域实现预测性能的颠覆，但其最大优势是可扩展性。 我们可以在GNN中添加更多的参数并训练它们以适用于特定的问题

2 GNN流程

通过一个简单的例子，简单对GNN流程有个初步的了解

如图表示各节点之间的关系，(x,x,x,x)表示各节点的初始特征

2.1 聚合

核心思路：将邻居的信息结合到自己身上，作为自己特征的补充

• 假设现在需要判断A节点的分类，但有时单看A节点自己的特征无法确定其属于哪个类别，从图中可以看出，A节点和B、C、D都有关系，这时B、C、D的特征就可以从一定程度上决定A的类别。
• 以A节点为例，邻居信息N = a$\ast$(2,2,2,2,2) + b$\ast$(3,3,3,3,3) + c$\ast$(4,4,4,4,4)，其中a,b,c是边的权重，假如b对a很重要，则a的值就可以设置的高一些，假如c对a不是很重要，则c的值就可以设置的低一些。邻居信息N可以理解为对A的特征信息的一个补足

2.2 更新

一次GNN操作：

• A节点的总特征，就是自己的特征 加$\alpha$倍的邻居信息N，再乘权重W，再经过一个激活函数，最终得到的是经过一层GNN操作之后A的最终信息。
• A的最终的特征=$\sigma (w((1,1,1,1)+\alpha \ast N))$
  其中$\sigma$是激活函数（relu,sigmoid等），w是模型需要训练的参数

2.3 循环

• 经过一次聚合后：A中有B,C,D的信息；B中有A,C的信息；C中有A,B,D,E的信息；D中有A,C的信息；E中有C的信息；第二次聚合之后以此类推。GNN层数越多，GNN的“感受野”越大，每个点考虑其他点的信息越多，考虑越全面.
• 以A节点为例，此时A聚合C的时候，由于C中有上一层聚合得到的E的信息，所以这时A获得了二阶邻居E的特征。

通过聚合更新，我们能够得到每个节点的表达，也就是特征feature，此时：节点分类就可以直接拿去分类，计算loss，优化权重W；关联预测则将两个节点的特征拼接起来，做分类，计算loss，做优化。
归根到底，GNN就是一个提取特征的方法

利用networkx简单生成一个无向图

import networkx as nx
import numpy as np
import matplotlib.pyplot as plt
import pandas as pd

G = nx.Graph()
node_features = [[2, 3], [4, 7], [3, 7], [4, 5], [5, 5]]
edges = [(1, 2), (1, 3), (2, 4), (2, 5), (1, 3), (3, 5), (3, 4)]
edge_features = [[1, 3], [4, 1], [1, 5], [5, 3], [5, 6], [5, 4], [4, 3]]
colors = []
edge_colors = []

# add nodes
for i in range(1, len(node_features) + 1):
    G.add_node(i, feature=str(i) + ':(' + str(node_features[i-1][0]) + ',' + str(node_features[i-1][1]) + ')')
    colors.append('#DCBB8A')

# add edges
for i in range(1, len(edge_features) + 1):
    G.add_edge(edges[i-1][0], edges[i-1][1], feature='(' + str(edge_features[i-1][0]) + ',' + str(edge_features[i-1][1]) + ')')
    edge_colors.append('#3CA9C4')

# draw
fig, ax = plt.subplots()
pos = nx.spring_layout(G)
nx.draw(G, pos=pos, node_size=2000, node_color=colors, edge_color='black')
node_labels = nx.get_node_attributes(G, 'feature')
nx.draw_networkx_labels(G, pos=pos, labels=node_labels, font_color='r', font_size=14)
edge_labels = nx.get_edge_attributes(G, 'feature')
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels, font_size=14, font_color='#7E8877')
ax.set_facecolor('deepskyblue')
ax.axis('off')
fig.set_facecolor('deepskyblue')
plt.show()

如下图所示：

其中，每一个节点都有自己的一些特征，比如在社交网络中，每个节点（用户）有性别以及年龄等特征

5个节点的特征向量依次为：

 [2, 6], [3, 5], [6, 7], [4, 6], [7, 8]

同样，6条边的特征向量为：

[1, 3], [4, 1], [1, 5], [5, 3], [5, 6], [5, 4]

根据上述相关概念和符号，该图中：

1. 节点特征向量$l_n$，如$l_1=(2,6)$
2. 边特征向量$l_{(n1,n2)}$表示边(n1,n2)的特征向量，如$l_{(1,2)}=(1,3)$

特征向量实际上也就是节点或者边的标签，这个是图本身的属性，一直保持不变。

3 GNN算法原理

3.1 图神经网络（GNN）模型的基本概念和符号

1. 图的定义：
   $G(N,E)$表示一个图，其中N是节点（node）的集合， E是边（edge）的集合。

2. 邻居和连接
   $ne[n]：$表示节点n的邻居节点集合，即与n通过边相连的节点
   $co[n]：$表示以n为顶点的边的集合。

3. 标签
   $l_n\in R^{l_N}：$表示与节点$n$相关的标签，是一个实数向量。
   $l_{(n1,n2)}\in R^{l_E}：$表示与边（n1,n2）相关的标签，也是一个实数向量。
   $l：$表示通过将图中所有标签堆叠在一起得到的向量。

4. 标签的一般表示
   如果$y$是包含图中数据的向量，$S$是节点（或边）的子集，那么$y_s$表示中$y$中选择与$S$中节点（或边）相关的分量得到的向量
   $l_{ne[n]}：$表示包含节点$n$所有邻居标签的向量。

5. 图的类型
   非位置图(Nonpositional graphs)：没有为节点的邻居分配特定的逻辑位置。
   位置图(Positional graphs)：为每个节点$n$的邻居分配一个唯一的整数标识符,以指示其逻辑位置。形式上，对于位置图中的每个节点$n$,存在一个注入函数$v_n:ne[n]->1,....,|N|$,为n的每个邻居$u$分配一个位置$v_n(u)$

3.2 The model

局部转换函数（local transition function）$f_w$：表示节点对其邻域的依赖性
局部输出函数（local output function）$g_w$：描述如何产生输出

$$x_n=f_w(l_n,l_{co[n]},x_{ne[n]},l_{ne[n]})$$

$$o_n=g_w(x_n,l_n)$$

其中$x_n$表示节点n的状态，$l_n$表示节点n的标签，$l_{co[n]}$表示与节点n相连的边的标签，$x_{ne[n]}$表示节点n的邻居节点的状态向量，$l_{ne[n]}$表示节点n的邻居节点的标签向量

注1： 邻域概念的灵活性

作者指出，可以采用不同的邻域概念。例如，可以选择去除邻居节点的标签$l_{ne[n]}$,因为这些信息已经隐含在节点n的状态$x_{ne[n]}$中，此外，邻域可以包含距离节点n两个或更多链接的节点。
这表明GNN模型在设计时具有灵活性，可以根据具体应用场景的需求来定义邻域的范围。这种灵活性允许模型捕获不同距离的节点间的关系，从而更好地理解图结构。

注2： 对有向图的适应性

作者提到，虽然公式$f_w$和$g_w$是为无向图定制的，但在处理有向图时，函数$f_w$也可以接受表示弧方向的输入。
例如：对于每个弧$l\in co[n]$，可以引入一个变量$d_l$，如果弧指向节点n，则$d_l=1$；如果弧来自节点n，则$d_l=0$
这个备注强调了GNN模型不仅适用于无向图，也可以通过适当的调整来处理有向图。这种调整使得模型能够考虑边的方向性，这对于某些应用（如社交网络分析）是非常重要的。

注3：模型的通用性和简化

作者指出，转换函数和输出函数及其参数可能依赖于节点n,在这种情况下每种类型的节点$k_n$都有自己的转换函数$f^{k_n}$、输出函数$g^{k_n}$和参数集$w_{k_n}$，故公式$f_w$和$g_w$可以扩展为：$x_n=(f^{k_n}{)}_{w_{k_n}}(l_n,l_{co[n]},x_{ne[n]},l_{ne[n]})$和$o_n=（g^{k_n}{)}_{w_{k_n}}(x_n,l_n)$
这个备注说明了GNN模型可以根据不同节点类型采用不同的机制（实现）。这种设计允许模型更加通用，能够处理包含多种类型节点的复杂图。同时，为了简化分析，作者选择考虑所有节点共享相同实现的特定模型。这种简化有助于集中讨论模型的核心概念，而不被实现细节所分散。

论文中，作者提出了为实现GNN模型所需的关键组件：

1. a method to solve（公式）：$x_n=f_w(l_n,l_{co[n]},x_{ne[n]},l_{ne[n]})$和$o_n=g_w(x_n,l_n)$
2. a learning algorithm to adapt $f_w$ and $g_w$ ：用于调整模型参数以提高性能
3. an implementation of $f_w$ and $g_w$：具体实现$f_w$ 和 $g_w$，这通常涉及到选择合适的神经网络架构

3.3 Computation of the State

在GNN中，状态的计算是通过迭代更新每个节点的状态来实现的。这个过程基于巴拿赫不动点定理（Banach’s fixed point theorem），该定理不仅确保了方程解的存在性和唯一性

• 迭代方案（Iterative Scheme）
  状态更新：状态x(t+1)通过应用全局转换函数$F_w$到当前状态$x(t)$和图的标签l来计算的。$x(t+1)=F_w(x(t),l)$，其中x(t)表示在第t次迭代时的状态。

• 动态系统（Dynamical System）
  收敛性：这个动态系统对于任何初始值 x(0) 都会指数级快速收敛到方程的解。这意味着无论初始状态如何，系统都会快速稳定到一个固定点，即节点状态的最终表示。

• 雅可比迭代方法（Jacobi Iterative Method）
  非线性方程求解：这个迭代方案实际上是解决非线性方程的雅可比迭代方法。通过不断迭代更新节点状态，可以计算出节点的输出和状态。

• 编码网络（Encoding Network）
  1)网络表示：计算过程可以被解释为一个由单元组成的网络的表示，这些单元计算局部转换函数 $f_w$ 和局部输出函数 $g_w$。这样的网络被称为编码网络，它模拟了递归神经网络的行为。
  2)状态存储与更新：每个单元存储节点的当前状态 $x_n(t)$，并在激活时使用节点标签和邻居存储的信息来计算下一个状态 $x_n(t+1)$。
  3）输出生成：节点 n 的输出由另一个实现 $g_w$ 的单元生成。

• 网络结构（Network Architecture）
  当 $f_w$ 和 $g_w$ 由前馈神经网络实现时，编码网络成为一个循环神经网络，其中神经元之间的连接可以分为内部连接和外部连接。
  内部连接：由实现单元的神经网络架构决定。
  外部连接：依赖于被处理图的边，即节点的邻居关系。

3.4 The Learning Algorithm

学习算法的目标是通过调整模型参数来最小化损失函数，从而训练GNN模型，学习算法基于梯度下降策略，由以下步骤组成：

1. 状态迭代更新
   1)状态更新：节点的状态$x_n(t)$根据公式$$x_n(t+1)=f_w(l_n,l_{co[n]},x_{ne[n]}(t),l_{ne[n]})$$迭代更新，直到时间T达到方程$x(T)\approx x$的不动点解。
   2)迭代过程：这个过程通常涉及到使用局部转换函数$f_w$来更新每个节点的状态，这个函数考虑了节点的当前状态、邻居节点的状态以及相关的边信息。

2. 计算梯度
   梯度计算：一旦节点状态收敛到不动点，就计算损失函数相对于模型参数$w$的梯度$\frac{\partial e_w(T)}{\partial w}$,这个梯度表示了在当前参数设置下，损失函数如何随参数变化。

3. 更新权重
   参数更新：根据步骤2中计算得到的梯度，更新模型的权重 w。这个过程通常涉及到梯度下降或其变体，如随机梯度下降（SGD）或Adam优化器。
   通过更新权重，模型的预测输出更接近于训练数据集中的目标值，从而减少损失函数。

如图是GNN的三个关键概念：原始图、对应的编码网络（encoding network），以及通过展开编码网络得到的网络（unfolding network）

• 原始图：每个节点 $l_1,l_2,l_3,l_4$带有标签，边 $l_{(1,2)},l_{(2,3)},l_{(1,4)},l_{(4,3)}$ 也带有标签。
  节点的输出 $o_1(t),o_2(t),o_3(t),o_4(t)$ 依赖于节点的状态和边的信息。
• 编码网络：其中图的节点被替换为计算局部转换函数 $f_w$ 和局部输出函数 $g_w$ 的单元（用方块表示）。
• 展开网络：其中每一层对应一个时间点，并包含编码网络所有单元的副本。
  层与层之间的连接取决于编码网络的连接性，这反映了信息在图中的传播方式。

其中，图中的时间轴（time）从 T 到 T0，表示状态更新的迭代过程。
每个时间步长 T,T1,T2 对应于网络中的一层，展示了状态更新的过程。

3.5 GNN算法

主函数中：

1. 首先初始化参数$w$
2. 通过Forward计算出所有节点的收敛的状态向量：$x=Forward(w)$
3. 通过Backward计算：$\frac{\partial e_w}{\partial w}=Backward(x,w)$,利用梯度下降法更新参数w：$w=w-\lambda \cdot \frac{\partial e_w}{\partial w}$，后利用更新后的参数$w$重新对所有结点的状态进行更新：$x=Forward(w)$,重复以上过程。
4. 最后得到的$w$就是我们的GNN了

GNN的Forward描述如下：

1. 初始化所有结点的状态向量，此时t=0;
2. 利用压缩映射$F_w$对节点状态向量进行更新：$x(t+1)=F_w(x(t),l)$
   这里的$l$是$l_n,l_{co[n]},l_{ne[n]}$这三种信息向量的堆叠。
3. 如果更新后的结果达到了收敛条件，则停止更新，返回最终时刻所有节点的状态向量。

Backward

1. 输出计算
   $o=G_w(x,l_N)$首先，使用全局输出函数$G_w$计算图的输出$o$,这取决于当前的节点状态$x$和节点标签$l_N$

2. 雅可比矩阵和梯度计算
   1）$A=\frac{\partial F_w}{\partial x}(x,l)$计算全局转换函数$F_w$关于节点状态x的雅可比矩阵A,这表示状态更新的局部变化率。
   2）$b=\frac{\partial e_w}{\partial o}\cdot \frac{\partial G_w}{\partial x}(x,l_N)$计算损失函数$e_w$关于输出$o$的梯度$\frac{\partial e_w}{\partial o}$与输出函数$G_w$关于节点状态$x$的梯度$\frac{\partial G_w}{\partial x}$的乘积，得到损失函数关于节点状态的梯度$b$

3. 反向传播
   1)初始化$z(0)$和t=0：在开始反向传播之前，初始化用于存储中间梯度值的变量$z$和时间步长t
   2)反向迭代：通过迭代更新z(t)来反向传播梯度信息，其中$z(t)=z(t+1)\cdot A+b$表示在时间步t的梯度值，这是通过将前一时间步的梯度z(t+1)与雅可比矩阵A相乘，然年加上得到的。
   3)直到$|z(t-1)-z(t)|<={ϵ}_b$,这表明梯度已经收敛。

4. 权重梯度计算
   1)$c=\frac{\partial e_w}{\partial o}\cdot \frac{\partial G_w}{\partial w}(x,l_N)$：计算损失函数关于输出函数权重的梯度$c$
   2)$d=z(t)\cdot \frac{\partial F_w}{\partial w}(x,l)$：计算在最终时间步t的梯度$z(t)$与全局转换函数 $F_w$关于权重的梯度$\frac{\partial F_w}{\partial w}$的乘积，得到梯度 d。
   3)$\frac{\partial e_w}{\partial w}=c+d$：将c和d相加，得到总的权重梯度$\frac{\partial e_w}{\partial w}$

5. 返回梯度
   返回$\frac{\partial e_w}{\partial w}$：最后，返回计算得到的权重梯度，用于在主算法中更新模型参数。

总结

本周学习了GNN模型的相关知识和其算法内容，但是可能还有些要继续学习和改进的地方，后面的学习我会继续督促自己学习和改进。