Graph and GNN——图的表示与图神经网络的介绍与应用

Hi，大家好，我是半亩花海。细数日子已然有很长一段时间没有更新博客了，不是在忙东忙西，就是在玩这玩那，在家摆，在学校gap，无敌了。言归正传，今天暂且先进一步探索并整理一部分图神经网络（GNN）的图的表示与图神经网络部分。

一、图的表示

（一）图的概念与形式

1. 聚合

2. 更新、循环

（二）图数据的任务

1. 图层面（分类/回归）

2. 边层面（分类/回归）

3. 节点层面（分类/回归）

二、图神经网络（GNN）

（一）图神经网络的概念

（二）图神经网络的工作流程

（三）图神经网络的数据集

参考文章

一、图的表示

（一）图的概念与形式

在开始讨论图神经网络之前，首先考虑如何表示图。在数学上，图 G 定义为一组节点/顶点 V 和一组边/链接 E，构成 G =（V，E） 的二元组，且每条边都连接着两个顶点。

如上示例图所示，顶点是 V = 1, 2, 3, 4，边是 E =（1, 2）、（2, 3）、（2, 4）、（3, 4）。为了简单起见，这里假设图是无向的，因此并未添加像（2, 1）、（3, 2）、（4, 3）这样的镜像对。

而在实际应用中，顶点和边通常可以具有特定的属性特征，也可以是有向边。那么，如何用一种有效的方法来表示图呢？通常有两种方案：

邻接矩阵：表示顶点之间相邻关系的矩阵。
邻接表：存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。

假设上图中的每个节点的特征分别为： $F_{1},F_{2}, F_{3}, F_{4}$ 。

1. 聚合

节点3的邻居信息： $N = W_{1}F_{2} + W_{2}F_{4}$ ，其中 $W_{1}, W_{2}$ 表示可训练参数，这些参数也可以手动设置。
节点3的信息： $\sigma(W \cdot F_3 + \alpha \cdot N)$ ，其中 $\sigma$ 是激活函数， $W$ 是可训练参数。

同理，节点1、2、4以同样的方式聚合信息。

第一次聚合：节点3可以包含节点2、3、4的信息。
第二次聚合：节点3可以包含节点1、2、3、4的信息，因为节点2会在第一次聚合后包含节点1的信息。

2. 更新、循环

多次聚合、得到Loss，更新参数、循环训练。

（二）图数据的任务

1. 图层面（分类/回归）

例：分子是天然的图，原子是节点，化学键是边。现在要做一个分类，有一个苯环的分子分一类，两个苯环的分子分一类。这是图分类任务。

2. 边层面（分类/回归）

例：UFO拳击赛上，首先通过语义分割把台上的人和环境分离开来。赛场上的人都是节点，现在要做一个预测，预测的是这些人之间的关系，是对抗关系？还是观众watch的关系？还是裁判watch的关系？这是边分类任务。

3. 节点层面（分类/回归）

例：假设一个跆拳道俱乐部里有A、B两个教练，所有的会员都是节点。有一天A、B两个跆拳道教练决裂，那么各个学员是愿意和A在一个阵营还是愿意和B在一个阵营？这是节点分类任务。

二、图神经网络（GNN）

（一）图神经网络的概念

图神经网络（Graph Neural Network, GNN）是一种深度学习模型，专门用于处理图结构数据。它能够捕捉节点的邻域结构信息，广泛应用于各种领域，如社交网络分析、生物信息学、推荐系统等。

GNN的核心思想是通过节点间的连接关系来传递和更新信息。基本的GNN模型包括递归图神经网络（Recursive GNN, RecGNN）和卷积图神经网络（Convolutional GNN, ConvGNN）。RecGNN通过递归地应用相同的参数集来提取节点的高级表示，而ConvGNN则通过图卷积层来学习节点特征的高级表示。

GNN可以针对不同类型的任务进行输出，包括节点级输出（如节点分类和回归任务）、边级输出（如边分类和链接预测任务）以及图级输出（如图分类任务）。在训练GNN时，可以根据任务和数据标签的可用性采用不同的训练策略，包括半监督学习、监督学习和无监督学习。

（二）图神经网络的工作流程

GNN是对图上的所有属性进行的一个可以优化的变换，它的输入是一个图，输出也是个图。它只对属性向量（即上文所述的V、E、G）进行变换，但它不会改变图的连接性（即哪些点互相连接经过GNN后是不会变的）。在获取优化后的属性向量之后，再根据实际的任务，后接全连接神经网络，进行分类和回归。大家可以把图神经网络看做是一个图数据的在三个维度的特征提取器。