图机器学习入门

在这篇博文中，我们将介绍图机器学习的基础知识。

我们首先研究什么是图，它们为什么被使用，以及如何最好地表示它们。然后，我们简要介绍人们如何在图上学习，从前神经网络方法（同时探索图特征）到通常所说的图神经网络。最后，我们窥探一下图 Transformer 的世界。

图

什么是图？

从本质上讲，图是对通过关系连接的项目的描述。

图的例子包括社交网络（Twitter、Mastodon、任何连接论文和作者的引文网络）、分子、知识图谱（如 UML 图、百科全书以及任何页面之间有超链接的网站）、以句法树表示的句子、任何 3D 网格等等！因此，说图无处不在并非夸张。

图（或网络）中的项目称为其 *节点* (或顶点)，它们的连接称为其 *边* (或链接)。例如，在社交网络中，节点是用户，边是他们之间的连接；在分子中，节点是原子，边是它们的分子键。

• 具有类型化节点或类型化边的图称为 **异构图** (heterogeneous) (例如：引文网络中的项目可以是论文或作者，因此具有类型化的节点；而 XML 图中的关系是类型化的，因此具有类型化的边)。它不能仅通过其拓扑结构来表示，还需要额外的信息。本文侧重于同构图。
• 图也可以是 **有向的** (directed) (比如关注者网络，A 关注 B 并不意味着 B 关注 A) 或 **无向的** (undirected) (比如分子，原子之间的关系是双向的)。边可以连接不同的节点或一个节点自身 (自环)，但并非所有节点都需要连接。

如果你想使用你的数据，你必须首先考虑其最佳的特征描述 (同构/异构，有向/无向，等等)。

图有什么用？

让我们来看一些可以在图上执行的任务。

在 **图级别**，主要任务是

• 图生成，用于药物发现以生成新的可能分子，
• 图演化 (给定一个图，预测其随时间的演变)，用于物理学中预测系统的演变，
• 图级别预测 (从图进行的分类或回归任务)，例如预测分子的毒性。

在 **节点级别**，通常是节点属性预测。例如，Alphafold 使用节点属性预测来预测给定分子整体图的原子三维坐标，从而预测分子如何在三维空间中折叠，这是一个困难的生物化学问题。

在 **边级别**，可以是边属性预测或缺失边预测。边属性预测有助于药物副作用预测，即在给定一对药物的情况下预测不良副作用。缺失边预测用于推荐系统中，以预测图中两个节点是否相关。

也可以在 **子图级别** 进行社区检测或子图属性预测。社交网络使用社区检测来确定人们是如何连接的。子图属性预测可以在行程规划系统 (如 Google Maps) 中找到，用于预测预计到达时间。

处理这些任务可以有两种方式。

当你想预测特定图的演变时，你工作在 **直推式** (transductive) 设置中，其中所有操作 (训练、验证和测试) 都在同一个图上完成。*如果这是你的设置，请小心！从单个图创建训练/评估/测试数据集并非易事。* 然而，很多工作是使用不同的图 (独立的训练/评估/测试集) 完成的，这被称为 **归纳式** (inductive) 设置。

我们如何表示图？

表示一个图以进行处理和操作的常见方法有

• 表示为其所有边的集合 (可能辅以其所有节点的集合)
• 或者表示为其所有节点之间的邻接矩阵。邻接矩阵是一个方阵 (大小为节点数 * 节点数)，它指示哪些节点直接连接到其他节点 (如果 (n_i) 和 (n_j) 连接，则 (A_{ij} = 1)，否则为 0)。*注意：大多数图都不是密集连接的，因此具有稀疏邻接矩阵，这可能使计算更加困难。*

然而，尽管这些表示方法看起来很熟悉，但不要被迷惑！

图与机器学习中使用的典型对象非常不同，因为它们的拓扑结构比单纯的“序列”(如文本和音频) 或“有序网格”(如图像和视频) 更复杂：即使它们可以表示为列表或矩阵，它们的表示也不应被视为有序对象！

但这是什么意思呢？如果你有一个句子并打乱其单词，你会创造一个新句子。如果你有一张图片并重新排列其列，你会创造一张新图片。

对于图来说，情况并非如此：如果你打乱其边列表或其邻接矩阵的列，它仍然是同一个图。(我们稍后会更正式地解释这一点，请查找置换不变性)。

通过机器学习进行图表示

使用机器学习处理图的通常过程是，首先为你的感兴趣项目 (节点、边或整个图，取决于你的任务) 生成一个有意义的表示，然后用这些表示来训练一个针对你目标任务的预测器。我们希望 (像在其他模态中一样) 约束对象的数学表示，使相似的对象在数学上是接近的。然而，这种相似性在图机器学习中很难严格定义：例如，两个节点在具有相同标签或相同邻居时更相似？

注意：*在接下来的部分中，我们将专注于生成节点表示。一旦你有了节点级别的表示，就可以获得边或图级别的信息。对于边级别的信息，你可以连接节点对的表示或进行点积。对于图级别的信息，可以对所有节点级别表示的连接张量进行全局池化 (平均、求和等)。但这会平滑并丢失图上的信息——递归的层次化池化可能更有意义，或者添加一个连接到图中所有其他节点的虚拟节点，并使用其表示作为整个图的表示。*

前神经网络方法

简单使用工程特征

在神经网络出现之前，图及其感兴趣的项目可以以任务特定的方式表示为特征的组合。现在，这些特征仍然用于数据增强和半监督学习，尽管存在更复杂的特征生成方法；根据你的任务，找到如何最好地将它们提供给你的网络可能至关重要。

**节点级别** 特征可以提供关于重要性 (这个节点对图有多重要？) 和/或基于结构 (节点周围的图的形状是什么？) 的信息，并且可以组合使用。

节点的 **中心性** (centrality) 衡量节点在图中的重要性。它可以通过递归地对每个节点的邻居的中心性求和直到收敛，或者例如通过节点之间的最短距离度量来计算。节点的 **度** (degree) 是它直接邻居的数量。**聚类系数** (clustering coefficient) 衡量节点邻居之间的连接程度。**小图度向量** (Graphlets degree vectors) 计算以给定节点为根的不同小图的数量，其中小图是你可以用给定数量的连接节点创建的所有迷你图 (用三个连接的节点，你可以有一条带两条边的线，或者一个带三条边的三角形)。

**边级别** 特征用关于节点连接性的更详细信息来补充表示，包括两个节点之间的 **最短距离**、它们的 **共同邻居** 以及它们的 **Katz 指数** (这是两个节点之间长度不超过某个值的可能游走次数 - 它可以直接从邻接矩阵计算)。

**图级别特征** 包含关于图相似性和特殊性的高级信息。总的 **小图计数** (graphlet counts)，虽然计算成本高，但提供了关于子图形状的信息。**核方法** (Kernel methods) 通过不同的“节点袋”方法 (类似于词袋) 来衡量图之间的相似性。

基于游走的方法

**基于游走的方法** 使用在随机游走中从节点 i 访问节点 j 的概率来定义相似性度量；这些方法结合了局部和全局信息。**Node2Vec**，例如，模拟图节点之间的随机游走，然后用 skip-gram 处理这些游走，很像我们处理句子中的词语，来计算嵌入。这些方法也可以用来加速**页面排名方法**的计算，该方法为每个节点分配一个重要性分数 (例如，基于其与其他节点的连接性，评估为随机游走访问的频率)。

然而，这些方法有其局限性：它们无法为新节点获得嵌入，无法精细地捕捉节点之间的结构相似性，也无法使用附加特征。

图神经网络

神经网络可以泛化到未见过的数据。考虑到我们之前提到的表示约束，一个好的用于处理图的神经网络应该是什么样的？

它应该

• 是置换不变的
  • 方程： $f(P(G))=f(G)$ 其中 f 是网络，P 是置换函数，G 是图
  • 解释：一个图及其置换的表示在经过网络后应该是相同的
• 是置换等变的
  • 方程： $P(f(G))=f(P(G))$ 其中 f 是网络，P 是置换函数，G 是图
  • 解释：在将节点传递给网络之前对其进行置换，应等同于对其表示进行置换

典型的神经网络，如 RNN 或 CNN，不是置换不变的。因此，一种新的架构，即图神经网络 (GNN)，被引入 (最初是作为一种基于状态的机器)。

GNN 由连续的层组成。一个 GNN 层将一个节点表示为其邻居和自身在前一层表示的组合 (**聚合**)，加上通常的激活函数以增加非线性 (**消息传递**)。

**与其他模型的比较**：一个 CNN 可以被看作是一个具有固定邻居大小 (通过滑动窗口) 和顺序 (它不是置换等变的) 的 GNN。一个没有位置嵌入的 Transformer 可以被看作是一个在全连接输入图上的 GNN。

聚合与消息传递

有很多方法可以聚合来自邻居节点的消息，例如求和、求平均。一些遵循这一思想的著名工作包括：

• 图卷积网络 (Graph Convolutional Networks) 对节点的邻居的归一化表示进行平均 (大多数 GNN 实际上是 GCN)；
• 图注意力网络 (Graph Attention Networks) 学习根据不同邻居的重要性来加权它们 (类似于 transformer)；
• GraphSAGE 在聚合信息之前，在不同的跳数上采样邻居，然后通过最大池化分多步聚合它们的信息。
• 图同构网络 (Graph Isomorphism Networks) 通过对邻居节点表示的和应用一个 MLP 来聚合表示。

**选择聚合方式**：某些聚合技术 (特别是均值/最大池化) 在为具有不同相似节点邻域的节点创建精细区分的表示时可能会遇到失败案例 (例如：通过均值池化，一个有 4 个节点的邻域，表示为 1,1,-1,-1，平均为 0，与一个只有 3 个节点表示为 -1, 0, 1 的邻域没有区别)。

GNN 的形状和过平滑问题

在每个新层中，节点表示包含越来越多的节点。

一个节点，通过第一层，是其直接邻居的聚合。通过第二层，它仍然是其直接邻居的聚合，但这次，它们的表示包括了它们自己的邻居 (来自第一层)。经过 n 层后，所有节点的表示变成了它们距离 n 的所有邻居的聚合，因此，如果图的直径小于 n，则变成了整个图的聚合！

如果你的网络层数太多，就有可能每个节点都成为整个图的聚合 (并且所有节点的表示都收敛到同一个值)。这被称为 **过平滑问题** (oversmoothing problem)

这可以通过以下方式解决：

• 调整 GNN 的层数，使其足够小，以避免将每个节点近似为整个网络 (通过首先分析图的直径和形状)
• 增加层的复杂性
• 添加非消息传递层来处理消息 (例如简单的 MLP)
• 添加跳跃连接 (skip-connections)。

过平滑问题是图机器学习中的一个重要研究领域，因为它阻止了 GNN 像 Transformer 在其他模态中那样进行扩展。

图 Transformer

一个没有位置编码层的 Transformer 是置换不变的，而且 Transformer 以其良好的扩展性而闻名，因此最近人们开始研究将 Transformer 应用于图 (综述)。大多数方法都专注于通过寻找最佳特征和表示位置信息的最佳方式来表示图，并改变注意力机制以适应这种新数据。

以下是一些有趣的方法，它们在撰写本文时在最难的可用基准之一——斯坦福开放图基准上取得了 SOTA 或接近 SOTA 的结果：

• 用于图到序列学习的图 Transformer (Cai 和 Lam, 2020) 引入了一个图编码器，它将节点表示为它们的嵌入和位置嵌入的拼接，节点关系表示为它们之间的最短路径，并在关系增强的自注意力中将两者结合起来。
• 用谱注意力重新思考图 Transformer (Kreuzer 等人, 2021) 引入了谱注意力网络 (SANs)。这些网络将节点特征与学习到的位置编码 (从拉普拉斯特征向量/值计算) 相结合，用作注意力中的键和查询，注意力值则是边特征。
• GRPE：图 Transformer 的相对位置编码 (Park 等人, 2021) 引入了图相对位置编码 Transformer。它通过将图级别的位置编码与节点信息相结合，将边级别的位置编码与节点信息相结合，并在注意力中将两者结合来表示图。
• 全局自注意力作为图卷积的替代 (Hussain 等人, 2021) 引入了边增强 Transformer。这种架构分别嵌入节点和边，并在修改后的注意力中将它们聚合起来。
• Transformer 在图表示上真的表现不佳吗 (Ying 等人, 2021) 介绍了微软的 **Graphormer**，它在发布时在 OGB 上获得了第一名。这种架构在注意力中使用节点特征作为查询/键/值，并在注意力机制中将它们的表示与中心性、空间和边编码的组合相加。

最新的方法是 纯 Transformer 是强大的图学习器 (Kim 等人, 2022)，它引入了 **TokenGT**。这种方法将输入图表示为节点和边嵌入的序列 (增加了正交节点标识符和可训练类型标识符)，没有位置嵌入，并将此序列作为输入提供给 Transformer。它非常简单，但很巧妙！

有点不同的是，通用、强大、可扩展的图 Transformer 的配方 (Rampášek 等人, 2022) 介绍的不是一个模型，而是一个框架，名为 **GraphGPS**。它允许将消息传递网络与线性 (长程) transformer 相结合，以轻松创建混合网络。该框架还包含多种工具来计算位置和结构编码 (节点、图、边级别)、特征增强、随机游走等。

将 transformer 用于图仍然是一个处于起步阶段的领域，但它看起来很有前途，因为它可能缓解 GNN 的一些局限性，例如扩展到更大/更密集的图，或在不过平滑的情况下增加模型大小。

更多资源

如果你想深入研究，可以看看这些课程：

• 学术形式
  • 斯坦福的图机器学习
  • 麦吉尔大学的图表示学习
• 视频形式
  • 几何深度学习课程
• 书籍
  • 《图表示学习》，Hamilton
• 综述
  • 图神经网络学习指南
• 研究方向
  • 2023 年的图机器学习 总结了 2023 年图机器学习可能有趣的方向。

处理图的好库有 PyGeometric 或 深度图库 (用于图机器学习) 和 NetworkX (用于更通用的图操作)。

如果你需要高质量的基准，可以查看：

• OGB，开放图基准：参考的图基准数据集，适用于不同任务和数据规模。
• GNN 基准测试：用于对图机器学习网络及其表达能力进行基准测试的库和数据集。相关论文特别研究了哪些数据集从统计角度来看是相关的，它们允许评估哪些图属性，以及哪些数据集不应再用作基准。
• 长程图基准：最近 (2022年11月) 的基准，着眼于长程图信息
• 图表示学习中基准的分类法：发表在 2022 年图学习会议上的论文，分析并分类了现有的基准数据集

更多数据集，请参阅：

• 带代码论文的图任务排行榜：公共数据集和基准的排行榜 - 小心，这个排行榜上的并非所有基准都仍然相关
• TU 数据集：公开可用数据集的汇编，现在按类别和特征排序。这些数据集中的大多数也可以用 PyG 加载，并且其中一些已被移植到 Datasets
• SNAP 数据集：斯坦福大型网络数据集集合:
• MoleculeNet 数据集
• 关系数据集仓库

外部图片来源

缩略图中的表情符号来自 Openmoji (CC-BY-SA 4.0)，小图 (Graphlets) 的图来自 *使用小图度分布进行生物网络比较* (Pržulj, 2007)。