【图神经网络1】入门笔记：A Gentle Introduction to Graph Neural Networks解读

这篇文章是学习图神经网络过程中的笔记，内容主要来自这篇博客，是一个翻译总结和个人的体会，感兴趣的朋友可以参考原文，里面有很多互动式的动画。

什么是图（Graph）

图是一种数据结构，他主要表达表示实体（entity，也就是图的节点node）之间的关系（relationship，也就是图的边edge）。这里说的图（Graph）并不是图片的图（Image），后者应该被叫做像素图，本质上是空间里的像素矩阵，当然，像素图也可以被理解为特殊情况下（每个像素为节点，连接方式固定）的Graph。

每个节点，边，以及图的整体都有相应的embedding，这里说的embedding相当于描述特征的向量，也可以叫做attribute

图里的边可以被分为有向边和无向边，一条无向边相当于两条有向边。

作为数据结构的图（Examples）

所谓数据结构就是我们整理数据的方法，数据结构里往往隐含了数据的特点，生活中有一些数据天然符合图的数据特点。

Images as graphs

将图像视为Graph的方法是：每个像素代表一个节点，并通过边与相邻像素相连。每个像素与 8 个节点相连，每个节点存储的信息是一个三维向量，代表像素的 RGB 值。

可以用领接矩阵描述一幅图，在一个 5x5 笑脸图像中，一共有 25 个像素节点，因此形成25x25的矩阵，如果两个节点相连，则所在值为1，否则为0。

Text as graphs

文本可以视为字符、单词的序列，将每个字符或词汇看作一个节点，按顺序连接，就形成了一个简单的有向图。

Molecules as graphs

分子是物质的组成部分，由三维空间中的原子和电子构成。所有粒子都在相互作用，但当一对原子彼此保持稳定距离时，我们就说它们共享共价键。不同的原子对和键有不同的距离（如单键、双键）。将这种三维物体描述为图是一种非常方便和常见的抽象方法，图中的节点是原子，边是共价键。

Social networks as graphs

社交网络是研究人、机构和组织集体行为模式的工具。我们可以通过将个人建模为节点，将他们之间的关系建模为边，从而建立一个代表人群的图。

Citation networks as graphs

科学家在发表论文时经常会引用其他科学家的研究成果。我们可以将这些引用网络可视化为一个图，其中每篇论文都是一个节点，每条有向边都是一篇论文与另一篇论文之间的引用。此外，我们还可以在每个节点中添加有关每篇论文的信息，如摘要的单词嵌入。

Other examples

在计算机视觉中，我们有时需要标记视觉场景中的物体。然后，我们可以将这些对象视为节点，将它们之间的关系视为边，从而构建图。

机器学习模型、编程代码和数学公式也可以用图来表示，其中变量是节点，边是将这些变量作为输入和输出的操作。

现实世界中不同数据类型的图形结构可能会有很大差异——有些图形的节点很多，但节点之间的连接却很少，反之亦然。图形数据集在节点、边的数量以及节点的连接性方面可能会有很大的不同（包括给定数据集内部以及数据集之间）。

图解决什么问题（Tasks）

我们已经描述了一些图的示例，但我们想在这些数据上执行什么任务呢？图的预测任务一般有三种类型：图级、节点级和边级。在图层面的任务中，我们预测整个图的单一属性。在节点级任务中，我们要预测图中每个节点的某些属性。在边级任务中，我们要预测图中边缘的属性或存在。

Graph-level task

在图级任务中，我们的目标是预测整个图形的属性。例如，对于以图表示的分子，我们可能想要预测该分子的气味，或者预测它是否会与某种疾病的受体结合。

这类似于 MNIST 和 CIFAR 的图像分类问题，我们希望将标签与整幅图像关联起来。对于文本，类似的问题是情感分析，我们希望一次性识别整个句子的情绪或情感。

Node-level task

节点级任务涉及预测图中每个节点的身份或角色。

扎克的空手道俱乐部是节点级预测问题的一个典型例子。（An Information Flow Model for Conflict and Fission in Small Groups） 该数据集是一个单一的社交网络图，由在政治分裂后宣誓效忠于两个空手道俱乐部之一的个人组成。故事讲述的是，Hi 先生（教练）和 John H（管理员）之间的不和导致了空手道俱乐部的分裂。节点代表空手道练习者个人，边代表这些成员之间在空手道之外的互动。预测问题是对某个成员在不和之后是忠于 Hi 先生还是忠于 John H 进行分类。在这种情况下，节点与教练或管理员之间的距离与这一标签高度相关。

根据图像类比，节点级预测问题类似于图像分割，我们试图标记图像中每个像素的角色。对于文本，类似的任务是预测句子中每个单词的语音部分（如名词、动词、副词等）。

Edge-level task

边级预测的一个例子是图像场景理解。除了识别图像中的物体，深度学习模型还可用于预测它们之间的关系。我们可以将其表述为边级分类：给定代表图像中物体的节点，我们希望预测这些节点中哪些共享一条边缘，或者这条边缘的值是多少。如果我们希望发现实体之间的联系，我们可以考虑完全连接的图，并根据预测值修剪边，从而得到一个稀疏的图。

机器学习中使用图的挑战（Challenges）

我们该如何利用神经网络解决这些不同的图形任务呢？首先，我们要考虑如何表示图形才能与神经网络兼容。

机器学习模型通常将矩形或网格状阵列作为输入。因此，如何用一种与深度学习兼容的格式来表示它们并不直观。图中有多达四种我们可能需要用来进行预测的信息：节点、边、全局上下文和连接性。前三种信息相对简单：例如，对于节点，我们可以为每个节点分配一个索引 i，并在矩阵 N 中存储节点 i 的特征，从而形成节点特征矩阵 N （num_node * dim_node）。虽然这些矩阵的示例数量不固定，但无需任何特殊技术即可处理。

邻接矩阵（adjacency matrices）

然而，表示图形的连通性则更为复杂。也许最明显的选择是使用邻接矩阵，因为它很容易张量化（tensorisable）。不过，这种表示方法也有一些缺点。从示例数据集表中，我们可以看到图中的节点数可能达到数百万的数量级，而每个节点的边数可能变化很大。这通常会导致邻接矩阵非常稀疏，空间效率低下。

另一个问题是，有许多邻接矩阵可以编码相同的连通性，而且无法保证这些不同的矩阵会在深度神经网络中产生相同的结果，也就是说，这些矩阵不具有排列不变性（permutation invariant）。

表示同一图形的两个邻接矩阵：

邻接表（adjacency lists）

用邻接表来表示稀疏矩阵是一种既优雅又节省内存的方法。它以邻接表条目中的元组 (i,j) 来描述节点 n_i 和 n_j 之间边 e_k 的连接性。由于边的数量远低于邻接矩阵的条目数（n_nodes^2），因此我们避免了对图中断开部分的计算和存储。

需要注意的是，图中每个节点/边/全局使用的是标量值，但大多数实际的张量表示法都是每个图形属性使用向量。我们将使用大小为 [nnodes,nodedim] 的节点张量(Tensor)，而不是大小为 [nnodes] 的节点张量。其他图形属性也是如此。

用图神经网络处理图数据（GNN）

最简单的GNN（The simplest GNN）

在图的节点/边/整体上使用多层感知器 (MLP)构成最简单的GNN Layer，对于每个节点向量，我们应用 MLP，并得到一个学习到的节点向量。我们对每条边进行同样的学习，学习每条边的嵌入，同时也对全局上下文向量进行同样的学习，学习整个图的单一嵌入。

简单 GNN 的单层。图形是输入，每个分量（V,E,U）由 MLP 更新，生成新的图形。每个函数下标表示 GNN 模型第 n 层不同图形属性的函数。

与神经网络模块或层一样，我们可以将这些 GNN 层堆叠在一起。

由于 GNN 不会更新输入图的连接性，因此我们可以用与输入图相同的邻接表和相同数量的特征向量来描述 GNN 的输出图。但是，由于 GNN 更新了每个节点、边和全局上下文表示，因此输出图具有更新的Embedding。

通过池化汇集信息

如果任务是对节点进行二元预测，而图中已经包含节点信息，那么方法就很简单--对每个节点Embedding应用线性分类器。

然而，事情并不总是那么简单。例如，图中的信息可能存储在边中，但节点中没有信息，但仍需要对节点进行预测。我们需要一种方法来收集边上的信息，并将其提供给节点进行预测。我们可以通过汇集来实现这一目的。池化分两步进行：

1. 对于要汇集的每个项目，收集它们的Embedding，并将它们连接成一个矩阵。

2. 通常通过求和操作（Aggregate function，也可以是平均/求最大）对收集到的Embedding进行汇总。

因此，如果我们只有边级特征，并试图预测节点类别，我们可以使用池化技术将信息路由（或传递）到需要的地方。模型看起来是这样的

如果我们只有节点级特征，并试图预测边的类别，那么模型看起来就像这样：

如果我们只有节点级特征，但需要预测全局属性，我们就需要将所有可用的节点信息收集在一起，然后进行聚合。这与 CNN 中的全局平均池化层类似。边缘也可以采用同样的方法：

一个端到端分类任务的 GNN 模型：

在这个最简单的 GNN 结构中，我们在 GNN 层内完全没有使用图的连通性。每个节点、每条边以及全局上下文都是独立处理的。我们只在汇集预测信息时使用连接性。

信息传递（Passing messages）

我们可以使用消息传递，让相邻节点或边交换信息，并影响彼此更新的Embedding。

消息传递分为三个步骤：

1. 对于图中的每个节点，收集所有相邻节点的Embedding。

2. 通过聚合函数（如 sum）汇总所有信息。

3. 所有汇集的信息将通过一个更新函数（通常是一个神经网络）进行传递。

这让人联想到卷积：从本质上讲，信息传递和卷积都是汇总和处理元素邻域信息以更新元素值的操作。在图中，元素是一个节点，而在图像中，元素是一个像素。然而，图中相邻节点的数量可以是可变的，这与图像中每个像素都有固定数量的相邻元素不同。

通过将消息传递 GNN 层堆叠在一起，一个节点最终可以包含来自整个图的信息：经过三层之后，一个节点就可以获得距离它三步远的节点的信息。

我们的数据集并不总是包含所有类型的信息（节点、边缘和全局上下文）。当我们想对节点进行预测，但我们的数据集只有边缘信息时，我们在上文展示了如何使用池化将信息从边缘路由到节点，但仅限于模型的最后预测步骤(Last layer)。我们可以在 GNN 层内使用消息传递在节点和边缘之间共享信息。

然而，图中存储的节点和边信息的大小和形状不一定相同，因此如何将它们结合起来并不明确。一种方法是学习从边缘空间到节点空间的线性映射。另一种方法是在更新函数之前将它们拼接concat起来。

在构建 GNN 时，更新哪些图属性以及更新的顺序是一个设计决策。我们可以选择是先更新节点嵌入，再更新边嵌入，也可以相反。我们还可以以 "编织 "的方式进行更新。

迄今为止，我们所描述的网络存在一个缺陷：图中相距较远的节点可能永远无法有效地相互传递信息，即使我们多次应用消息传递也是如此。对于一个节点，如果我们有 k 层，信息最多只能传播 k 步。如果预测任务依赖于相距甚远的节点或节点组，这就会成为一个问题。一种解决方案是让所有节点都能相互传递信息。遗憾的是，对于大型图而言，这种方法的计算成本很快就会变得很高。

解决这一问题的方法之一是使用图的全局表示（U），有时也称为主节点或上下文向量。这个全局上下文向量与网络中的所有其他节点和边相连，可以作为它们之间传递信息的桥梁，为整个图建立一个表征。这就为图形创建了比学习到的信息更丰富、更复杂的表征。

为了得到新的节点特征，我们利用所有这些可能的信息源，我们可以简单地将它们拼接起来。此外，我们还可以通过线性映射将它们映射到同一空间，然后将它们Sum到一起，或者应用一个特征调制层[22]，这可以被视为一种featurize-wise attention mechanism。

实验（Empirical guide）

Leffingwell 气味数据集 [23] [24]，该数据集由带有相关气味感知（标签）的分子组成。预测分子结构（图）与其气味的关系。为了简化问题，我们只考虑每个分子的二分类标签，即分子图是否具有专业调香师所标注的 "刺激性 "气味

将每个分子表示为一个图，其中原子是节点，包含其原子特征（碳、氮、氧、氟）的编码，而键是边，包含其键类型（单键、双键、三键或芳香键）的编码。

我们可以调节GNN层数，信息聚合方式，Embedding维度来观察模型效果。

性能 vs. 可训练参数

参数数量越多，性能越高。但GNN 是一种参数效率很高的模型类型：即使参数数量很少（3k），我们也能找到性能很高的模型。

特征维度

维度越高的模型，其平均值和下限性能往往越好，但最大值却没有发现同样的趋势。一些表现最好的模型可以在较小的维度下找到

层数

虽然平均性能随着层数的增加而增加，但性能最好的模型不是三层或四层，而是两层。此外，性能下限随着层数的增加而降低。这种效应以前也观察到过，层数越多的 GNN 传播信息的距离越远，其节点表征有可能被多次连续迭代 "稀释"

聚合方式

求和比求均值的性能略有提高，但求最大值或求均值也能给出同样好的模型

信息传递方式

交流的图形属性越多，平均模型的性能就越好。我们的任务以全局表示为中心，因此明确学习这一属性也往往会提高性能。我们的节点表征似乎也比边缘表征更有用，这是有道理的，因为这些属性中加载了更多的信息

开放研究领域

其他种类的图 (多图, 超图, 超节点, 多级图)

我们可以定义更复杂的图来适应不同的任务。

例如，我们可以考虑多边图或多图[32]，其中一对节点可以共享多种类型的边。例如，在社交网络中，我们可以根据关系类型（熟人、朋友、家人）指定边的类型。通过为每种边缘类型设置不同类型的信息传递步骤，可以对 GNN 进行调整。我们还可以考虑嵌套图，例如一个节点代表一个图，也称为超节点图。例如，我们可以考虑一个分子网络，其中一个节点代表一个分子，如果我们有将一个分子转化为另一个分子的方法（反应），则两个分子之间共享一条边。

例如超图 [36]，在超图中，一条边可以连接多个节点，而不仅仅是两个节点。对于给定的图，我们可以通过识别节点群落并分配一条与群落中所有节点相连的超边来构建超图。

图的采样和批处理

训练神经网络通过对训练数据的mini batch计算随机梯度来更新网络参数。由于相邻节点和边的数量存在变化，这意味着我们无法设定恒定的batch大小，因此这种做法对图形来说是一个挑战。对图形进行分批处理的主要思路是创建保留较大图形基本属性的子图（采样），如何对图进行采样是一个尚未解决的研究课题

归纳偏差

当建立一个模型来解决特定类型数据的问题时，我们希望对模型进行专门化，以充分利用该数据的特性。如果能成功做到这一点，我们往往能看到更好的预测性能、更少的训练时间、更少的参数和更好的泛化效果。

例如，在对图像进行标注时，我们希望利用这样一个事实：无论狗是在图像的左上角还是右下角，它仍然是一只狗。因此，大多数图像模型都使用卷积，而卷积具有平移不变性。对于文本而言，标记的顺序非常重要，因此递归神经网络会按顺序处理数据。此外，一个标记的出现（如 "不是 "一词）会影响句子其余部分的意思，因此我们需要能 "关注 "文本其他部分的组件，而 BERT 和 GPT-3 等Transformer模型就能做到这一点。这些都是归纳偏差的一些例子，在这些例子中，我们发现了数据中的对称性或规律性，并添加了利用这些特性的建模组件。

在图的情况下，我们关心每个图的组成部分（边、节点、全局）是如何相互关联的，因此我们寻求具有关系归纳偏向的模型。 [19] 模型应保留实体间的显式关系（邻接矩阵）并保留图的对称性（置换不变性）。我们希望实体间的互动非常重要的问题能从图结构中受益。具体来说，这意味着在集合上设计转换：节点或边的操作顺序不重要，操作应适用于可变数量的输入。

汇集操作

汇集相邻节点和边的信息是任何功能强大的 GNN 架构的关键步骤。由于每个节点的邻居数量不固定，而且我们需要一种可微分的方法来汇集这些信息，因此我们希望使用一种平滑的汇集操作，这种操作不受节点排序和所提供节点数量的影响。

选择和设计最佳聚合运算是一个尚未解决的研究课题。 [44] 聚合运算的一个理想特性是相似的输入提供相似的聚合输出，反之亦然。一些非常简单的候选包络不变运算包括总和、平均值和最大值。方差等汇总统计也可以使用。所有这些运算都采用数量可变的输入，无论输入排序如何，都能提供相同的输出。

没有哪种操作是一成不变的最佳选择。当节点的邻居数量变化很大，或者需要对局部邻域的特征进行归一化处理时，平均值操作可能会很有用。当你想突出本地邻域中的单个突出特征时，最大值运算可能会很有用。求和则在这两者之间取得了平衡，它提供了局部特征分布的快照，但由于没有进行归一化处理，因此也会突出异常值。在实践中，求和是常用的方法。

设计聚合操作是一个开放的研究课题，与集合的机器学习有交叉。 [45] 新方法（如主邻域聚合 [27]）通过串联多个聚合操作，并添加一个缩放函数，该函数取决于要聚合的实体的连接程度，从而将多个聚合操作考虑在内。同时，还可以设计特定领域的聚合操作。其中一个例子就是 "Tetrahedral Chirality"聚合操作[46]。

GCN是子图近似器

一种将包含一次邻节点运算的 k 层 GCN视为神经网络的方法是，将其视为对大小为 k 的子图的学习embedding进行操作的神经网络。

当专注于一个节点时，经过 k 层后，更新后的节点表征具有 k 距离内所有邻居的有限视角，本质上是一种子图表征。边的表示也是如此。

因此，GCN 收集大小为 k 的所有可能子图，并从一个节点或边的位置学习向量表示。可能的子图数量会以组合方式增长，因此，与在 GCN 中动态构建这些子图相比，从一开始就枚举这些子图是不可能的。

图的对偶

边预测和节点预测虽然看似不同，但往往可以归结为同一个问题：图 G 上的边预测任务可以表述为 G对偶 上的节点级预测。 为了得到 G 的对偶图，我们可以将节点转换为边（将边转换为节点） 要解决 G 的边缘分类问题，我们可以考虑在 G 的对偶图上进行图卷积（这与学习 G 的边缘表示法是一样的）。

图卷积是矩阵乘法，矩阵乘法是遍历图

邻接矩阵 点乘 节点特征矩阵 相当于用加法聚合传递信息

邻接矩阵的k次幂相当于，从i到j，长度为k的边的条数

我们可以将矩阵视为图，从而探索更深层次的联系。

图注意力网络

在图形属性之间传递信息的另一种方式是通过注意力。例如，当我们考虑一个节点与其 相邻节点的聚合时，我们也可以考虑使用加权总和。一种方法是考虑一种标量评分函数，根据Node pair分配权重。

在这种情况下，评分函数可以解释为一个衡量邻近节点与中心节点相关程度的函数。可以对权重进行归一化处理，例如使用softmax函数，将大部分权重集中在与任务相关的、与节点最相关的相邻节点上。这一概念是图注意网络（GAT）的基础。

其实Transformer模型可被视为具有注意力机制的 GNN [55] 。Transformer将多个元素（如字符token）建模为完全连接图中的节点，而attention则是为每个节点对分配边嵌入，用于计算注意力权重。两者的区别在于假定的实体间连接模式，GNN 假定的是稀疏模式，而Transformer模拟的是所有连接。

可解释性

我们可能会关心模型的可解释性，以便建立可信度、进行调试或科学发现。我们需要解释的图概念因上下文而异。

生成式模型

除了学习图形的预测模型外，我们可能还会关注图形生成模型的学习。有了生成模型，我们就可以通过从学习到的分布中采样或通过完成给定起点的图形来生成新的图形。一个相关的应用是在新药设计中，我们需要具有特定性质的新分子图作为治疗疾病的候选药物。

图形生成模型的一个主要挑战在于如何对图形的拓扑结构建模，因为图形的大小可能会有很大的变化，并且有 N^2 个节点。一种解决方案是直接使用自动编码器框架对邻接矩阵建模，就像对图像建模一样

另一种方法是迭代构建图形，即从图形开始，迭代地应用离散操作，如添加或减少节点和边。为了避免为离散操作估算梯度，我们可以使用策略梯度。这可以通过自动回归模型（如 RNN）[61] 或强化学习方案来实现。

总结

图形是一种强大而丰富的结构化数据类型，其优势和挑战与图像和文本截然不同。在本文中，我们概述了研究人员在构建基于神经网络的图形处理模型方面取得的一些阶段性成果。GNN 近年来取得的成功为解决各种新问题创造了巨大的机会，我们很高兴看到这一领域将带来什么。