GNN系统学习：简单图论、环境配置、PyG中图与图数据集的表示和使用

Reference

datawhale开源学习资料

开篇

1.1 为什么要在图上进行深度学习？

在过去的深度学习应用中，我们接触的数据形式主要是这四种：矩阵、张量、序列（sequence）和时间序列（time series）。然而来自现实世界应用的数据更多地是图的结构，如社交网络、交通网络、蛋白质与蛋白质相互作用网络、知识图谱和大脑网络等。
在这里插入图片描述

此外，大量的现实世界的问题可以作为图上的一组小的计算任务来解决。推断节点属性、检测异常节点（如垃圾邮件发送者）、识别与疾病相关的基因、向病人推荐药物等，都可以概括为节点分类问题。推荐、药物副作用预测、药物与目标的相互作用识别和知识图谱的完成（knowledge graph completion）等，本质上都是边预测问题。

同一图的节点存在连接关系，这表明节点不是独立的。然而，传统的机器学习技术假设样本是独立且同分布的，因此传统机器学习方法不适用于图计算任务。图机器学习研究如何构建节点表征，节点表征要求同时包含节点自身的信息和节点邻接的信息，从而我们可以在节点表征上应用传统的分类技术实现节点分类。图机器学习成功的关键在于如何为节点构建表征。深度学习已经被证明在表征学习中具有强大的能力，它大大推动了计算机视觉、语音识别和自然语言处理等各个领域的发展。因此，将深度学习与图连接起来，利用神经网络来学习节点表征，将带来前所未有的机会。

然而，如何将神经网络应用于图，这一问题面临着巨大的挑战。首先，传统的深度学习是为规则且结构化的数据设计的，图像、文本、语音和时间序列等都是规则且结构化的数据。但图是不规则的，节点是无序的，节点可以有不同的邻居节点。其次，规则数据的结构信息是简单的，而图的结构信息是复杂的，特别是在考虑到各种类型的复杂图，它们的节点和边可以关联丰富的信息，这些丰富的信息无法被传统的深度学习方法捕获。

以往的深度学习技术是为规则且结构化的数据设计的，无法直接用于图数据。应用于图数据的神经网络，要求：

适用于不同度的节点；
节点表征的计算与邻接节点的排序无关；
不但能够根据节点信息、邻接节点的信息和边的信息计算节点表征，还能根据图拓扑结构计算节点表征。下面的图片展示了一个需要根据图拓扑结构计算节点表征的例子。图片中展示了两个图，它们同样有俩黄、俩蓝、俩绿，共6个节点，因此它们的节点信息相同；假设边两端节点的信息为边的信息，那么这两个图有一样的边，即它们的边信息相同。但这两个图是不一样的图，它们的拓扑结构不一样。

1.2 此组队学习涵盖的话题

此组队学习由五个话题组成，每一话题都包含理论部分与实践部分：

话题一：

我们将首先学习简单图论知识、了解常规的图预测任务（见第2节）；
然后学习基于PyG包的图数据的表示与使用（见第3节）。

话题二：

我们将首先学习实现图神经网络的通用范式，即消息传递范式；
其次学习PyG中的消息传递（MessagePassing）基类的属性、方法和运行流程；
最后学习如何自定义一个消息传递图神经网络（见第4节）。

话题三：

图计算应用中最基础的任务是节点表征（Node Representation）学习。
我们将以GCN和GAT（两个最为经典的图神经网络）为例，学习基于图神经网络的节点表征学习的一般过程；并且通过MLP、GCN和GAT三者在节点分类任务中的比较，学习图神经网络为什么强于普通的MLP神经网络，以及GCN和GAT的差别（见第5节）。
此外，我们还将学习如何构造一个数据全部存于内存的数据集类（见第6-1节)；
并学习基于节点表征学习的图节点预测任务和边预测任务的实践（见第6-2节）。

话题四：

我们将首先分析在超大图上进行节点表征学习面临着的挑战**；
接着学习应对挑战的一种解决方案；
最后学习超大图节点预测任务的实践（见第7节）。

话题五：

我们将首先学习基于图神经网络的图表征学习的一般过程（见第8节）；
接着学习样本按需获取的数据集类的构造方法（见第9-1节）；
最后学习基于图表征学习的图预测任务的实践（见第9-2节）。

除了话题四和话题五都依赖于话题三之外，其余话题都依赖于该话题自身的前一话题。

图结构数据

2.1 图的表示

定义一（图）

一个图被记为 $\mathcal{G}=\left\{\mathcal{V}, \mathcal{E}\right\}$ ，其中 $\mathcal{V} = \left\{v_{1}, \ldots, v_{N}\right\}$ 是数量为 $N=|\mathcal{V}|$ 的节点的集合， $\mathcal{E}=\left\{e_{1}, \ldots, e_{M}\right\}$ 是数量为 $M$ 的边的集合。
图用节点表示实体（entities ），用边表示实体间的关系（relations）。
节点和边的信息可以是类别型的（categorical），类别型数据的取值只能是哪一类别。一般称类别型的信息为标签（label）。
节点和边的信息可以是数值型的（numeric），数值型数据的取值范围为实数。一般称数值型的信息为属性（attribute）。
在图的计算任务中，我们认为，节点一定含有信息（至少含有节点的度的信息），边可能含有信息。

定义二（图的邻接矩阵）

给定一个图 $\mathcal{G}=\left\{\mathcal{V}, \mathcal{E}\right\}$ ，其对应的邻接矩阵被记为 $\mathbf{A} \in \left\{0,1\right\}^{N \times N}$ 。 $\mathbf{A}_{i, j}=1$ 表示存在从节点 $v_i$ 到 $v_j$ 的边，反之表示不存在从节点 $v_i$ 到 $v_j$ 的边。
在无向图中，从节点 $v_i$ 到 $v_j$ 的边存在，意味着从节点 $v_j$ 到 $v_i$ 的边也存在。因而无向图的邻接矩阵是对称的。
在无权图中，各条边的权重被认为是等价的，即认为各条边的权重为 $1$ 。
对于有权图，其对应的邻接矩阵通常被记为 $\mathbf{W} \in \mathbb{R}^{N \times N}$ ，其中 $\mathbf{W}_{i, j}=w_{ij}$ 表示从节点 $v_i$ 到 $v_j$ 的边的权重。若边不存在时，边的权重为 $0$ 。

2.2 图的属性

定义三（节点的度，degree）

对于有向有权图，节点 $v_i$ 的出度（out degree）等于从 $v_i$ 出发的边的权重之和，节点 $v_i$ 的入度（in degree）等于从连向 $v_i$ 的边的权重之和。
无向图是有向图的特殊情况，节点的出度与入度相等。
无权图是有权图的特殊情况，各边的权重为 $1$ ，那么节点 $v_i$ 的出度（out degree）等于从 $v_i$ 出发的边的数量，节点 $v_i$ 的入度（in degree）等于从连向 $v_i$ 的边的数量。
节点 $v_i$ 的度记为 $d(v_i)$ ，入度记为 $d_{in}(v_i)$ ，出度记为 $d_{out}(v_i)$ 。

定义四（邻接节点，neighbors）

节点 $v_i$ 的邻接节点为与节点 $v_i$ 直接相连的节点，其被记为 $\mathcal{N(v_i)}$ 。
节点 $v_i$ 的 $k$ 跳远的邻接节点（neighbors with k-hop）指的是到节点 $v_i$ 要走 $k$ 步的节点（一个节点的 $2$ 跳远的邻接节点包含了自身）。

定义五（行走，walk）

$walk(v_1,v_2)=(v_1,e_6,e_5,e_4,e_1,v_2)$ ，这是一次“行走”，它是一次从节点 $v_1$ 出发，依次经过边 $e_6,e_5,e_4,e_1$ ，最终到达节点 $v_2$ 的“行走”。
下图所示为 $walk(v_1, v_2) = (v_1, e_6,e_5,e_4,e_1,v_2)$ ，其中红色数字标识了边的访问序号。
在“行走”中，节点是允许重复的。

定理六

有一图，其邻接矩阵为 $A$ , $A^n$ 为邻接矩阵的 $n$ 次方，那么 $\mathbf{A}^{n}[i,j]$ 等于从节点 $v_i$ 到节点 $v_j$ 的长度为 $n$ 的行走的个数。（也就是，以节点 $v_i$ 为起点，节点 $v_j$ 为终点，长度为 $n$ 的节点访问方案的数量，节点访问中可以兜圈子重复访问一些节点）

定义七（路径，path）

“路径”是节点不可重复的“行走”。

定义八（子图，subgraph）

有一图 $\mathcal{G}=\left\{\mathcal{V}, \mathcal{E}\right\}$ ，另有一图 $\mathcal{G}^{\prime}=\left\{\mathcal{V}^{\prime}, \mathcal{E}^{\prime}\right\}$ ，其中 $\mathcal{V}^{\prime} \in \mathcal{V}$ ， $\mathcal{E}^{\prime} \in \mathcal{E}$ 并且 $\mathcal{V}^{\prime}$ 不包含 $\mathcal{E}^{\prime}$ 中未出现过的节点，那么 $\mathcal{G}^{\prime}$ 是 $\mathcal{G}$ 的子图。

定义九（连通分量，connected component）

给定图 $\mathcal{G}^{\prime}=\left\{\mathcal{V}, \mathcal{E}\right\}$ 是图 $\mathcal{G}=\left\{\mathcal{V}, \mathcal{E}\right\}$ 的子图。记属于图 $\mathcal{G}$ 但不属于 $\mathcal{G}^{\prime}$ 图的节点集合记为 $\mathcal{V}/\mathcal{V}^{\prime}$ 。如果属于 $\mathcal{V}^{\prime}$ 的任意节点对之间存在至少一条路径，但不存在一条边连接属于 $\mathcal{V}^{\prime}$ 的节点与属于 $\mathcal{V}/\mathcal{V}^{\prime}$ 的节点，那么图 $\mathcal{G}^{\prime}$ 是图 $\mathcal{G}$ 的连通分量。

在这里插入图片描述

左右两边子图都是整图的连通分量。

定义十（连通图，connected graph）

当一个图只包含一个连通分量，即其自身，那么该图是一个连通图。

定义十一（最短路径，shortest path）

$v_s, v_t \in \mathcal{V}$ 是图 $\mathcal{G}=\left\{\mathcal{V}, \mathcal{E}\right\}$ 上的一对节点，节点对 $v_{s}, v_{t} \in \mathcal{V}$ 之间所有路径的集合记为 $\mathcal{P}_{\mathrm{st}}$ 。节点对 $v_{s}, v_{t}$ 之间的最短路径 $p_{\mathrm{s} t}^{\mathrm{sp}}$ 为 $\mathcal{P}_{\mathrm{st}}$ 中长度最短的一条路径，其形式化定义为 $p_{\mathrm{s} t}^{\mathrm{sp}}=\arg \min \limits_{p \in \mathcal{P}_{\mathrm{st}}}|p|$ 其中， $p$ 表示 $\mathcal{P}_{\mathrm{st}}$ 中的一条路径， $∣ p ∣$ 是路径 $p$ 的长度。

定义十二（直径，diameter）：

给定一个连通图 $\mathcal{G}={\mathcal{V}, \mathcal{E}}$ ，其直径为其所有节点对之间的最短路径的最大值，形式化定义为
$\operatorname{diameter}(\mathcal{G})=\max {v{s}, v_{t} \in \mathcal{V}} \min {p \in \mathcal{P}{s t}}|p|$

定义十三（拉普拉斯矩阵，Laplacian Matrix）：

给定一个图 $\mathcal{G}=\left\{\mathcal{V}, \mathcal{E}\right\}$ ，其邻接矩阵为 $A$ ，其拉普拉斯矩阵定义为 $\mathbf{L=D-A}$ ，其中 $\mathbf{D=diag(d(v_1), \cdots, d(v_N))}$ 。

定义十四（对称归一化的拉普拉斯矩阵，Symmetric normalized Laplacian）：

给定一个图 $\mathcal{G}={\mathcal{V}, \mathcal{E}}$ ，其邻接矩阵为 $A$ ，其规范化的拉普拉斯矩阵定义为
$\mathbf{L}=\mathbf{D}^{-\frac{1}{2}}(\mathbf{D}-\mathbf{A})\mathbf{D}^{-\frac{1}{2}}=\mathbf{I}-\mathbf{D}^{-\frac{1}{2}}\mathbf{A}\mathbf{D}^{-\frac{1}{2}}$

2.3 图的种类

同质图（Homogeneous Graph）：只有一种类型的节点和一种类型的边的图。
异质图（Heterogeneous Graph）：存在多种类型的节点和多种类型的边的图。

在这里插入图片描述

二部图（Bipartite Graphs）：节点分为两类，只有不同类的节点之间存在边。

2.4 图结构数据上的机器学习

节点预测：预测节点的类别或某类属性的取值
例子：对是否是潜在客户分类、对游戏玩家的消费能力做预测
边预测：预测两个节点间是否存在链接
例子：Knowledge graph completion、好友推荐、商品推荐
图的预测：对不同的图进行分类或预测图的属性
例子：分子属性预测
节点聚类：检测节点是否形成一个社区
例子：社交圈检测
其他任务
图生成：例如药物发现
图演变：例如物理模拟
……

环境配置与PyG中图与图数据集的表示和使用

3.1 PyG引言

PyTorch Geometric (PyG) 是面向几何深度学习的PyTorch的扩展库，几何深度学习指的是应用于图和其他不规则、非结构化数据的深度学习。

基于PyG库，我们可以轻松地根据数据生成一个图对象，然后很方便的使用它；我们也可以容易地为一个图数据集构造一个数据集类，然后很方便的将它用于神经网络。

通过此节的实践内容，我们将

首先学习程序运行环境的配置。
接着学习PyG中图数据的表示及其使用，即学习PyG中Data类。
最后学习PyG中图数据集的表示及其使用，即学习PyG中Dataset类。

3.2 环境配置

安装正确版本的pytorch和cudatoolkit（Cudatoolkit的目的是为开发人员提供方便操作GPU的工具和库，避免他们需要重复编写底层功能），此处安装1.8.1版本的pytorch和11.1版本的cudatoolkit

conda install pytorch torchvision torchaudio cudatoolkit=11.1 -c pytorch -c nvidia

确认是否正确安装，正确的安装应出现下方的结果

$ python -c "import torch; print(torch.__version__)"
# 1.8.1
$ python -c "import torch; print(torch.version.cuda)"
# 11.1

在一个torch版本为1.9.0的上：

1.9.0+cpu
None

在一个torch版本为2.4.1+cu121的上：

2.4.1+cu121
12.1

安装正确版本的PyG

pip install torch-scatter -f https://pytorch-geometric.com/whl/torch-1.8.0+cu111.html
pip install torch-sparse -f https://pytorch-geometric.com/whl/torch-1.8.0+cu111.html
pip install torch-cluster -f https://pytorch-geometric.com/whl/torch-1.8.0+cu111.html
pip install torch-spline-conv -f https://pytorch-geometric.com/whl/torch-1.8.0+cu111.html
pip install torch-geometric

# 通用形式
pip install torch-scatter -f https://pytorch-geometric.com/whl/torch-${TORCH}+${CUDA}.html
pip install torch-sparse -f https://pytorch-geometric.com/whl/torch-${TORCH}+${CUDA}.html
pip install torch-cluster -f https://pytorch-geometric.com/whl/torch-${TORCH}+${CUDA}.html
pip install torch-spline-conv -f https://pytorch-geometric.com/whl/torch-${TORCH}+${CUDA}.html
pip install torch-geometric

# 电脑安装
pip install torch-scatter -f https://pytorch-geometric.com/whl/torch-1.8.0+cpu.html
pip install torch-sparse -f https://pytorch-geometric.com/whl/torch-1.8.0+cpu.html
pip install torch-cluster -f https://pytorch-geometric.com/whl/torch-1.8.0+cpu.html
pip install torch-spline-conv -f https://pytorch-geometric.com/whl/torch-1.8.0+cpu.html
pip install torch-geometric

# 服务器安装
pip install torch-scatter -f https://pytorch-geometric.com/whl/torch-1.7.0+cu101.html
pip install torch-sparse -f https://pytorch-geometric.com/whl/torch-1.7.0+cu101.html
pip install torch-cluster -f https://pytorch-geometric.com/whl/torch-1.7.0+cu101.html
pip install torch-spline-conv -f https://pytorch-geometric.com/whl/torch-1.7.0+cu101.html
pip install torch-geometric

其他版本的安装方法以及安装过程中出现的大部分问题的解决方案可以在 Installation of of PyTorch Geometric 页面找到。

3.3 Data类——PyG中图的表示及其使用

3.3.1 Data对象的创建

A. 通过构造函数

Data类的构造函数：

class Data(object):

    def __init__(self, x=None, edge_index=None, edge_attr=None, y=None, **kwargs):
    r"""
    Args:
        x (Tensor, optional): 节点属性矩阵，大小为`[num_nodes, num_node_features]`
        edge_index (LongTensor, optional): 边索引矩阵，大小为`[2, num_edges]`，第0行可称为头（head）节点、源（source）节点、邻接节点，第1行可称为尾（tail）节点、目标（target）节点、中心节点
        edge_attr (Tensor, optional): 边属性矩阵，大小为`[num_edges, num_edge_features]`
        y (Tensor, optional): 节点或图的标签，任意大小（，其实也可以是边的标签）
	
    """
    self.x = x
    self.edge_index = edge_index
    self.edge_attr = edge_attr
    self.y = y

    for key, item in kwargs.items():
        if key == 'num_nodes':
            self.__num_nodes__ = item
        else:
            self[key] = item

edge_index的每一列定义一条边，其中第一行为边起始节点的索引，第二行为边结束节点的索引。这种表示方法被称为COO格式（coordinate format），通常用于表示稀疏矩阵。
PyG 不是用稠密矩阵 $\mathbf{A} \in \left\{ 0, 1 \right\}^{|\mathcal{V}| \times |\mathcal{V}|}$ 来持有邻接矩阵的信息，而是用仅存储邻接矩阵 $\mathbf{A}$ 中非 $0$ 元素的稀疏矩阵来表示图。

通常，一个图至少包含x, edge_index, edge_attr, y, num_nodes5个属性，当图包含其他属性时，我们可以通过指定额外的参数使Data对象包含其他的属性：

graph = Data(x=x, edge_index=edge_index, edge_attr=edge_attr, y=y, num_nodes=num_nodes, other_attr=other_attr)

B. 转dict对象为Data对象

我们也可以将一个dict对象转换为一个Data对象：

graph_dict = {
    'x': x,
    'edge_index': edge_index,
    'edge_attr': edge_attr,
    'y': y,
    'num_nodes': num_nodes,
    'other_attr': other_attr
}
graph_data = Data.from_dict(graph_dict)

from_dict是一个类方法：

@classmethod
def from_dict(cls, dictionary):
    r"""Creates a data object from a python dictionary."""
    data = cls()
    for key, item in dictionary.items():
        data[key] = item

    return data

注意：graph_dict中属性值的类型与大小的要求与Data类的构造函数的要求相同。

3.3.2 Data对象转换成其他类型数据

我们可以将Data对象转换为dict对象：

def to_dict(self):
    return {key: item for key, item in self}

或转换为namedtuple：

def to_namedtuple(self):
    keys = self.keys
    DataTuple = collections.namedtuple('DataTuple', keys)
    return DataTuple(*[self[key] for key in keys])

获取Data对象属性

x = graph_data[‘x’]

设置Data对象属性

graph_data[‘x’] = x

获取Data对象包含的属性的关键字

graph_data.keys()

对边排序并移除重复的边

graph_data.coalesce()

3.3.3 Data对象的其他性质

我们通过观察PyG中内置的一个图来查看Data对象的性质：

from torch_geometric.datasets import KarateClub

dataset = KarateClub()
data = dataset[0]  # Get the first graph object.
print(data)
print('==============================================================')

# 获取图的一些信息
print(f'Number of nodes: {data.num_nodes}') # 节点数量
print(f'Number of edges: {data.num_edges}') # 边数量
print(f'Number of node features: {data.num_node_features}') # 节点属性的维度
print(f'Number of node features: {data.num_features}') # 同样是节点属性的维度
print(f'Number of edge features: {data.num_edge_features}') # 边属性的维度
print(f'Average node degree: {data.num_edges / data.num_nodes:.2f}') # 平均节点度
print(f'if edge indices are ordered and do not contain duplicate entries.: {data.is_coalesced()}') # 是否边是有序的同时不含有重复的边
print(f'Number of training nodes: {data.train_mask.sum()}') # 用作训练集的节点
print(f'Training node label rate: {int(data.train_mask.sum()) / data.num_nodes:.2f}') # 用作训练集的节点数占比
print(f'Contains isolated nodes: {data.contains_isolated_nodes()}') # 此图是否包含孤立的节点
print(f'Contains self-loops: {data.contains_self_loops()}')  # 此图是否包含自环的边
print(f'Is undirected: {data.is_undirected()}')  # 此图是否是无向图

3.4 Dataset类——PyG中图数据集的表示及其使用

PyG内置了大量常用的基准数据集，接下来我们以PyG内置的Planetoid数据集为例，来学习PyG中图数据集的表示及使用。

Planetoid数据集类的官方文档为torch_geometric.datasets.Planetoid。

3.4.1 生成数据集对象并分析数据集

如下方代码所示，在PyG中生成一个数据集是简单直接的。在第一次生成PyG内置的数据集时，程序首先下载原始文件，然后将原始文件处理成包含Data对象的Dataset对象并保存到文件。

from torch_geometric.datasets import Planetoid

dataset = Planetoid(root='/dataset/Cora', name='Cora')
# Cora()

len(dataset)
# 1 该数据集只有一个图

dataset.num_classes
# 7

dataset.num_node_features
# 1433

3.4.2 分析数据集中样本

可以看到该数据集只有一个图，包含7个分类任务，节点的属性为1433维度。

data = dataset[0]
# Data(edge_index=[2, 10556], test_mask=[2708],
#         train_mask=[2708], val_mask=[2708], x=[2708, 1433], y=[2708])

data.is_undirected()
# True

data.train_mask.sum().item()
# 140

data.val_mask.sum().item()
# 500

data.test_mask.sum().item()
# 1000

现在我们看到该数据集包含的唯一的图，有2708个节点，节点特征为1433维，有10556条边，有140个用作训练集的节点，有500个用作验证集的节点，有1000个用作测试集的节点。

A: 为什么节点数为 2708，但训练、验证、测试节点的总和为 1650？
Q: 在 PyG 中，数据集中并不是所有节点都被分配到训练、验证或测试集。剩余的 1058 个节点（2708 - 1650 = 1058）通常没有标签，也就不参与监督训练、验证或测试。在实际应用中，尤其是图神经网络中，这是一个常见情况，因为图中的部分节点可能并不具有标签，而是作为上下文信息参与训练。

A: train_mask、val_mask 和 test_mask 的维度解释
Q: 在 PyG 中，train_mask、val_mask 和 test_mask 是长度为 2708 的布尔张量，而不是单纯地包含分配的节点数量。每个布尔张量表示该节点是否属于相应的集合：
train_mask[i] 为 True 表示节点 i 属于训练集。
val_mask[i] 为 True 表示节点 i 属于验证集。
test_mask[i] 为 True 表示节点 i 属于测试集。
这样，每个节点的位置都固定地映射到训练、验证、测试集中某一类别或不属于任何类别。这种方式便于处理节点信息，并方便后续将特定集合的节点从图数据中分割出来。

3.4.3 数据集的使用

假设我们定义好了一个图神经网络模型，其名为Net。在下方的代码中，我们展示了节点分类图数据集在训练过程中的使用。

model = Net().to(device)
data = dataset[0].to(device)
optimizer = torch.optim.Adam(model.parameters(), lr=0.01, weight_decay=5e-4)

model.train()
for epoch in range(200):
    optimizer.zero_grad()
    out = model(data)
    loss = F.nll_loss(out[data.train_mask], data.y[data.train_mask])
    loss.backward()
    optimizer.step()