图神经网络入门详解

本文基本是对A Gentle Introduction to Graph Neural Networks这篇文章的翻译理解。
（注意：原文中有很多可交互的动画，更有启发性。本文对原文中的有些图像进行了调整，方便初学者理解）

（这部分大都来自于这篇参考文献）
曾有学者将本次人工智能浪潮的兴起归因于三个条件，分别是：
（1）计算资源的快速发展（如GPU）
（2）大量训练数据的可用性
（3）深度学习从欧氏空间数据中提取潜在特征的有效性
尽管传统的深度学习方法被应用在提取欧氏空间数据的特征方面取得了巨大的成功，但许多实际应用场景中的数据是从非欧式空间生成的，传统的深度学习方法在处理非欧式空间数据上的表现却仍难以使人满意。
常见的欧几里得结构化数据主要包含：
（1）1D：声音，时间序列等；
（2）2D：图像等；
（3）3D：视频，高光谱图像等。
常见的非欧几里得结构化数据有：
（1）1D：社交网络(如Facebook，Twitter)等；
（2）2D：生物网络(基因，分子，大脑连接)等；
（3）3D：基础设施网络(如能源，交通，互联网，通信等。

例如，在电子商务中，一个基于图（Graph）的学习系统能够利用用户和产品之间的交互来做出非常准确的推荐，但图的复杂性使得现有的深度学习算法在处理时面临着巨大的挑战。这是因为图是不规则的，每个图都有一个大小可变的无序节点，图中的每个节点都有不同数量的相邻节点，导致一些重要的操作（例如卷积）在图像（Image）上很容易计算，但不再适合直接用于图。此外，现有深度学习算法的一个核心假设是数据样本之间彼此独立。然而，对于图来说，情况并非如此，图中的每个数据样本（节点）都会有边与图中其他实数据样本（节点）相关，这些信息可用于捕获实例之间的相互依赖关系。

近年来，人们对深度学习方法在图上的扩展越来越感兴趣。在多方因素的成功推动下，研究人员借鉴了卷积网络、循环网络和深度自动编码器的思想，定义和设计了用于处理图数据的神经网络结构，由此一个新的研究热点——图神经网络（Graph Neural Networks，GNN）。

什么是图？图（graph）是一系列实体（nodes）之间的关系（edges）。

黄色的是节点或称顶点，其属性包括节点标识、邻居数量等；
蓝色的是边或称链接，其属性包括边的标识、边的权重等；
红色线框包围的就是整张图，或称全局，该全局属性包括节点数量、图中的最长路径等特征。
其中，根据边的方向性还有两种情形，有向图和无向图：

社交网络作为图

图graph结构最简单明了的一种真实应用场景就是社交网络。
社交网络是用来研究人在机构、组织等集体中的行为模式的工具。我们可以通过将个人建模为节点、将人与人之间的关系建模为边来构建表示社交网络的图。
比如如下是莎士比亚的戏剧《奥赛罗》中的社交网络的图表达：

一种可视化图的连通性的方法是通过其邻接矩阵。如果人与人之间有关系，则在该矩阵中填充数值：

引文网络作为图

科学家在发表论文时经常引用其他科学家的工作。我们可以将这些引文网络可视化为一个图，其中每篇论文都是一个节点，每个有向边是一篇论文和另一篇论文之间的引用。此外，我们可以将每篇论文的信息添加到每个节点中，例如摘要的词嵌入。

分子作为图

分子是物质的基石，由3D空间中的原子和电子构成。所有粒子都在相互作用，但是当一对原子彼此保持稳定的距离时，我们说它们共享一个共价键。不同的原子对和键有不同的距离（例如单键、双键）。将这个3D对象描述为图是一种非常方便和常见的抽象，其中节点是原子，边是共价键。
如下是咖啡因因子的3D表示，及将它建模为图。

以上三例的数据都是异构的，由其所建的图graph中的节点的邻居数量是可变的。下面将展示两种可能认为无法建模为图的数据类型：图像和文本。这两类的数据就非常规整，表现在其邻居数量是固定的，但是它们仍然可以建模为图这一种数据结构。

图像作为图

通常将图像视为具有图像通道的矩形网格，并将它们表示为数组（例如，244x244x3 浮点数）。
另一种方式就是将图像视为具有规则结构的图，其中每个像素代表一个节点，并通过边连接到相邻像素。每个非边界像素正好有 8 个邻居，每个节点存储的信息是一个 3 维向量，表示像素的 RGB 值。如下面的 5x5 笑脸图像：

在邻接矩阵中，我们对25个节点进行排序，并形成一个 nnodes×nnodes 的矩阵，如果两个节点共享一条边，则在矩阵中填充数值，如下：

文本作为图

首先将文本进行“数字化”：比如对每个字符character、单词word或token都关联一个索引，然后文本就可以表示为一系列的索引（这种方式是文本在循环神经网络RNN 中经常表示的方式）。
这将创建一个简单的有向图，其中每个索引都是一个节点，并通过一条边连接到它后面的节点。如下图所示：

当然，在实践中，这通常不是文本和图像的编码方式：这种图graph的表达是冗余的，因为所有图像和所有文本都具有非常规则的结构。例如，图像在其邻接矩阵中具有带状结构，这是因为所有节点（像素）都在一个规则网格中相互连接。文本的邻接矩阵只是一条对角线，因为每个单词只连接到前一个单词和下一个单词。

在计算机视觉中，我们有时想标记视觉场景中的对象。然后可以通过将这些对象视为节点，将它们的关系视为边来构建图。
机器学习模型，编程代码和数学方程也可以表述为图，其中变量是节点，边是将这些变量作为输入和输出的操作。术语“数据流图”dataflow graph就是这个意思。

图能干什么

图上的预测任务一般分为三种类型：图级graph-level、节点级node-level和边级edge-level。
在图级任务中，我们预测整个图的单个属性。对于节点级任务，我们预测图中每个节点的一些属性。对于边级任务，我们希望预测图中边的属性或存在。

在图级任务中，我们的目标是预测整个图的属性。例如，对于表示为图的分子，我们可能想要预测该分子的气味，或者它是否会与与疾病有关的受体结合。
比如下面例子，就是判断哪些分子结构有两个环。

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

节点级任务

节点级任务与预测图中每个节点的身份或角色有关。
节点级预测问题的一个经典示例是 Zach 的空手道俱乐部。该数据集是一个单一的社交网络图，整个图由在政治分歧后宣誓效忠两个空手道俱乐部之一的个人练习者组成。故事是这样的，Hi 先生（讲师）和 John H（管理员）之间的不和导致了空手道俱乐部的分裂。节点代表个人空手道练习者，边代表这些成员之间在空手道之外的互动。预测问题是对给定成员在发生争执后是变得忠诚于 Mr. Hi 还是 John H 进行分类。在这种情况下，此分类标签与节点到讲师或管理员之间的距离高度相关。

（在左边我们有问题的初始条件，在右边我们有一个可能的解决方案，其中每个节点都基于联盟进行了分类。该数据集可用于其他图问题，如无监督学习。）

按照图像类比，节点级预测问题类似于图像分割，我们试图标记图像中每个像素的作用。对于文本，类似的任务是预测句子中每个单词的词性（例如名词、动词、副词等）。

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

（在上面的 (b) 中，原始图像 (a) 被分割为五个实体：两个格斗者、裁判、观众和垫子。(C) 显示了这些实体之间的关系。）

（左侧是根据之前的视觉场景构建的初始图，右侧是根据模型的输出对某些连接进行修剪后得到的该图可能的边标记。）

在机器学习中使用图的挑战

那么，我们如何用神经网络解决这些不同的图任务呢？第一步是考虑我们将如何表示图以与神经网络兼容。
机器学习模型通常采用矩形或网格状阵列作为输入。因此，如何以与深度学习兼容的格式表示它们并不是很直观。图有多达四种类型的信息可能想要用来进行预测：节点、边、全局上下文和连通性。前三个比较简单：比如对于节点，我们可以通过为每个节点分配一个索引i从而组成一个节点特征矩阵N，然后在N中存储特征nodei。虽然这些矩阵具有可变数量的实例，但处理矩阵不需要任何特殊的技巧。
然而，表示图的连通性更为复杂。也许最明显的选择是使用邻接矩阵，因为它很容易张量化。然而，这种表示有一些缺点。
如下是一个示例数据集表：

从示例数据集表中，我们看到图中的节点数量可能达到数百万，每个节点的边数可能变化很大。通常，这会导致非常稀疏的邻接矩阵，这是空间效率低下的。
另一个问题是，有很多邻接矩阵可以编码相同的连通性，并不能保证这些不同的矩阵在深度神经网络中会产生相同的结果（也就是说，它们不是排列不变的）。
例如，前面的奥赛罗图可以用如下这两个邻接矩阵等价地描述。它也可以用节点的所有其他可能的排列来描述。

更直观一点，下面的这个小图由四个节点组成，可以表示它的邻接矩阵如下：

可以看出，对于这么简单的一个小图，可以表示同样信息的邻接矩阵就很多了，更不必说有更多节点的奥赛罗图。

表示稀疏矩阵的一种优雅且节省内存的方法是邻接列表。它把节点ni和节点nj之间的边ek的连通性表达为邻接表的第k个元素中的元组(i,j)。由于通常情况下边的数量远低于邻接矩阵的元素数量（nnodes2)，因此可以避免在图的断开部分（即没有边的部分）进行计算和存储。
举一个例子：

可以看出，整个图graph中有8个节点和7个边。
Nodes列表里给出了8个节点的属性，取值只有两个0和1；Edges列表里给出了7个边的属性，取值为1或2；临界列表里则给出了这些边由哪两个节点形成，比如Edges里的倒数第二条边就是连接的7号节点和4号节点。Global给出了整个图的标识，这里标识为0。

需要注意的是，该图中每个节点/边/全局的属性都是标量，即都只有一个值，但大多数真实的图中的属性都是向量（或称特征向量或嵌入）。比如对于一个节点，上例中节点列表是[nnodes]，但真实情况大概率是这样的形状[nnodes,nodedim]。对于边的属性、全局属性也同理。

上述这种对于图的描述方式具有排列不变性。

图神经网络

图神经网络GNN是对图的所有属性（节点、边、全局上下文）进行优化的变换，它保留了图的对称性（置换不变性）。这里使用 Gilmer 等人提出的“消息传递神经网络”框架构建 GNN。
GNN 采用“图入图出”架构，这意味着这些模型类型接受图作为输入，将信息加载到其节点、边和全局上下文中，并逐步转换这些嵌入，而不会改变输入图的连通性。

最简单的GNN

一个最简单的 GNN架构如下：

该GNN在图的每个组件上使用单独的多层感知器 (MLP)（或其他可微模型），我们称之为 GNN 层。比如，对于每个节点向量，我们应用 MLP 并返回一个学习到的节点向量；对每条边做同样的事情，学习每条边的嵌入（或称新的特征向量）；以及全局上下文向量，为整个图学习一个嵌入。（在该架构中学习了所有图属性（节点、边、全局）的新嵌入，但尚未使用图的连通性。）
然后将这些GNN层堆叠在一起。
因为 GNN 不会更新输入图的连通性，所以我们可以用与输入图相同的邻接表和相同数量的特征向量来描述 GNN 的输出图。但是，输出图更新了嵌入，因为 GNN 更新了每个节点、边和全局上下文表示。

通过汇集信息进行 GNN 预测

上面已经构建了一个简单的 GNN，但是如何在上述任何任务中进行预测呢？
这里考虑一个二元分类的情况（但这个框架可以很容易地扩展到多类或回归的情况）。如果任务是对节点进行二元预测，并且图形已经包含节点信息，则该方法很简单——对于每个节点嵌入，应用线性分类器。

然而，事情并不总是那么简单。例如，我们可能将图中的信息存储在边中，但节点中没有信息，但仍需要对节点进行预测。可以想象一个社交网络，我们希望匿名化用户数据（节点），不使用这些用户信息，而仅使用关系数据（边）来达到我们的预测目的。这种场景的一个实例就是之前在空手道俱乐部示例中，仅使用人与人之间的会面次数，而不使用任何具体的人的信息，来确定效忠于Mr. Hi还是John H.。
此时就需要一种从边收集信息并将它们提供给节点进行预测的方法。我们可以通过池化（或称汇集pooling）来做到这一点。池化分两步进行：
（1）对于要汇集的每个项目，收集它们的每个嵌入并将它们连接成一个矩阵。
（2）然后聚合收集到的嵌入，通常通过求和运算来实现。

用字母ρ表示池化操作，然后用pEn→Vn表示从边上收集信息到节点上。

因此，如果我们只有边上的特征，并且想尝试预测节点的二元分类信息，那可以使用池化将信息路由（或传递）到需要去的地方。
该模型如下。

反过来，如果我们只有节点级特征，并试图预测边上的二元分类信息（这种场景的一个例子比如上面的边级任务，节点就是图像实体，想预测这些实体是否共享关系，即二元边）。此时模型看起来像这样。

如果我们只有节点级别的特征，并且需要预测一个全局的二进制属性，此时需要将所有可用的节点信息收集在一起并聚合它们。这类似于CNN 中的全局平均池化层。边缘到全局的信息也可以这样做。
（这是预测分子特性的常见场景。例如，我们有原子信息及其连通性，我们想知道一个分子的毒性（有毒/无毒），或者它是否有特定的气味（玫瑰/非玫瑰））

在上面例子中，分类模型c可以很容易地替换为任何可微模型，或使用广义线性模型来做多分类问题。

上面构建了一个简单的 GNN 模型，并通过在图的不同部分之间路由信息来进行二元预测。这种池化技术将作为构建更复杂 GNN 模型的基石。如果我们有新的图属性，只需要定义如何将信息从一个属性传递到另一个属性即可。
请注意，在这个最简单的 GNN 公式中，没有在 GNN 层内部使用图的连通性。每个节点都是独立处理的，每个边以及全局上下文也是如此。我们只是在汇集信息进行预测时使用连通性。

在图的各个部分之间传递消息

如上所述，我们仅在最后预测时使用了池化来汇聚消息。自然地，我们可以通过在 GNN 层之间使用池化来进行更复杂的预测，以使中间学习的嵌入（或称特征向量）知道图的连通性。
我们可以使用消息传递来做到这一点，其中相邻的节点或边交换信息，并影响彼此更新后的嵌入。
消息传递分三步进行：
（1）对于图中的每个节点，收集所有相邻节点嵌入（或消息）；
（2）通过聚合函数（如 sum）聚合所有消息；
（3）所有汇集的消息都通过一个更新函数，该函数通常是一个可学习的神经网络。
（第二步和第三步顺序可以调整，即先更新再聚合，这种方式也具有置换不变性）

整个过程如下所示：

正如池化可以应用于节点或边一样，消息传递可以发生在节点或边之间。
这些步骤是利用图形连通性的关键。我们将在 GNN 层中构建更精细的消息传递变体，从而产生具有增加表现力和能力的 GNN 模型。

这一系列操作，当应用一次时，就是消息传递 GNN 层的最简单形式。
这跟图像处理中的标准卷积操作类似：本质上，消息传递和卷积是聚合和处理元素邻居的信息以更新元素值的操作。在图中，元素是一个节点，而在图像中，元素是一个像素。然而，图中相邻节点的数量可以是可变的，这与每个像素具有一组固定数量相邻元素的图像不同。
通过将传递 GNN 层的消息堆叠在一起，一个节点最终可以合并来自整个图的信息：在三层之后，一个节点拥有距离它三步远的节点的信息。（这跟图像中的感受野类似）

于是，前面最简单的GNN架构图可以增加上面这一部分内容，即包含新的节点消息源，形成一个更复杂的GNN架构：

学习边的表示

我们的数据集并不总是包含所有类型的信息（节点、边和全局上下文）。当我们想对节点进行预测，但我们的数据集只有边信息时，我们在上面展示了如何使用池化将信息从边路由到节点，但仅限于模型的最后预测步骤。我们可以使用消息传递在 GNN 层内的节点和边之间共享信息。
我们可以以与之前使用相邻节点信息相同的方式合并来自相邻边的信息，首先将边信息池化，用更新函数对其进行转换，然后存储它。
但是，图中存储的节点和边信息不一定具有相同的大小或形状，因此如何将它们组合起来还不是很清楚。一种方法是学习从边空间到节点空间的线性映射，反之亦然。或者，可以在更新函数之前将它们连接在一起。模型如下：

构建GNN时一个需要设计的地方在于：更新哪些图属性以及更新它们的顺序。我们可以选择是在缘嵌入之前更新节点嵌入，或者以相反的顺序。
该领域仍在活跃研究中，目前有多种解决方案。例如，我们可以以“编织”方式进行更新：

添加全局表示

到目前为止，上面描述的网络存在一个缺陷：图中彼此相距很远的节点可能永远无法有效地相互传输信息，即使我们多次应用消息传递。对于一个节点，如果我们有 k 层，信息最多将传播 k 步。对于预测任务依赖于相距很远的节点或节点组的情况，这可能是一个问题。
一种解决方案是让所有节点都能够相互传递信息。不幸的是，对于大图来说，这很快就会变得计算成本很高（尽管称为“虚拟边”的方法已被用于分子等小图）。
该问题的一种解决方案是使用图 (U) 的全局表示，该图有时称为主节点master node或上下文向量。这个全局上下文向量连接到网络中的所有其他节点和边，并可以作为它们之间的桥梁来传递信息，从而为整个图构建一个表示。这创建了一个更丰富、更复杂的而不是通过其他方式学习的图表示。

上述架构称为Graph Nets。

此时，可以发现，所有的图属性都学习了表示，因此我们可以在池化过程中通过调节我们感兴趣的属性的信息来使用它们。例如，对于一个节点，我们可以考虑来自相邻节点、所连接的边和全局信息的信息。为了在所有这些可能的信息源上调整新节点嵌入，我们可以简单地将它们连接起来。此外，我们还可以通过线性映射将它们映射到相同的空间并添加它们或应用特征调制层，这可以被认为是一种特征化的注意力机制。

GNN游乐场

上面给出了GNN的各种架构和组件，到底在实践中怎么用呢？
作者直接给出了一个在线DEMO，即GNN游乐场，该游乐场基于tensorflow.js构建，用户在上面可以自由地玩耍和配置，从而探索上面不同的组件和架构如何用于GNN中。
整个DEMO展示了一个带有小分子图的图级预测任务。使用 Leffingwell 气味数据集，它由具有相关气味感知（标签）的分子组成。
预测分子结构（图）与其气味的关系是一个跨越化学、物理、神经科学和机器学习的百年历史问题。为了简化问题，只考虑每个分子的一个二元标签，根据专业调香师的标签，对分子图是否闻起来“刺鼻”进行分类。如果一个分子具有强烈、醒目的气味，我们就说它具有“刺鼻”气味。例如，可能含有烯丙醇分子的大蒜和芥末就具有这种性质。胡椒酮分子，通常用于薄荷味糖果，也被描述为具有刺鼻的气味。
这里将每个分子表示为一个图，其中原子是包含对其原子身份（碳、氮、氧、氟）进行独热编码的节点，而键是包含对其键类型（单、双、三重或芳香）进行独热编码的边。
针对这个问题的通用建模模板是使用GNN层序列构建，然后接一个用于分类的 sigmoid 激活函数。
整个GNN模型有多个超参数可供调节：
（1）GNN 层数，也称为深度；
（2）更新时每个属性的维度。更新函数是一个 1 层 MLP，其具有 relu 激活函数和用于激活归一化的标准化层；
（3）池化中使用的聚合函数：max、mean 或 sum；
（4）更新的图形属性或消息传递的样式：节点、边和全局表示。我们通过布尔切换（开或关）来控制这些。基线模型是一个与图无关的 GNN（关闭所有消息传递），它将最后的所有数据聚合到一个全局属性中。打开所有的消息传递函数就会形成一个 Graph Nets 架构（即上面添加了全局表示的GNN架构）。

为了更好地理解 GNN 如何学习图的任务优化表示，作者还查看了 GNN 的倒数第二层激活。这些“图嵌入”是 GNN 模型在预测之前的输出。由于使用广义线性模型进行预测，因此线性映射足以让用户了解如何围绕决策边界学习表示。但由于这些是高维向量，所以通过主成分分析 (PCA) 将它们简化为 2D。一个完美的模型可以很容易地将这个决策边界显示出来，但由于这里压缩了维度并且模型也不完美，因此这个边界可能很难看到。（如下截图有点那个边界的意思了）

游乐场的截图如下：

A Gentle Introduction to Graph Neural Networks
图神经网络（Graph Neural Networks，GNN）综述
GNN 系列：Graph 基础知识介绍