在这篇博文中，我们介绍了图机器学习的基础知识。
我们首先研究了图是什么，为什么要使用图，以及如何最好地表示它们。然后简要介绍了人们在图上学习的方法，从前神经方法（同时探索图特征）到通常称为图神经网络的方法。最后，我们瞥见了用于图的Transformer。
图
什么是图？
本质上，图是通过关系链接的项目的描述。
图的示例包括社交网络（Twitter、Mastodon、任何将论文和作者链接起来的引用网络）、分子、知识图（如UML图、百科全书和带有页面之间超链接的任何网站）、以其句法树表示的句子、任何三维网格等等！因此，可以说图无处不在。
图的项目（或网络）称为其节点（或顶点），它们之间的连接称为边（或链接）。例如，在社交网络中，节点是用户，边是它们之间的连接；在分子中，节点是原子，边是它们之间的化学键。
- 具有类型节点或类型边的图称为异构图（例如：引用网络中的项目可以是论文或作者，具有类型节点；XML图中的关系是有类型的，具有类型边）。它不能仅通过其拓扑结构来表示，它需要额外的信息。本文重点介绍同质图。
- 图也可以是有向的（如关注者网络，A关注B并不意味着B关注A）或无向的（如分子，原子之间的关系是双向的）。边可以连接不同的节点或一个节点本身（自连接），但不是所有节点都需要连接。
如果要使用您的数据，您必须首先考虑其最佳描述方式（同质/异构、有向/无向等）。
图有什么用途？
让我们看一下我们可以在图上做哪些可能的任务。
在图级别上，主要任务包括：
- 图生成，在药物发现中用于生成新的合理分子。
- 图演化（给定一个图，预测它随时间的演化），在物理学中用于预测系统的演化。
- 图级别的预测（从图中进行分类或回归任务），例如预测分子的毒性。
在节点级别上，通常是节点属性预测。例如，Alphafold使用节点属性预测来预测给定分子的整体图的情况下，原子的三维坐标，从而预测分子在三维空间中的折叠方式，这是一个困难的生物化学问题。
在边级别上，可以是边属性预测或缺失边预测。边属性预测有助于药物副作用预测，可以根据一对药物预测不良副作用。缺失边预测在推荐系统中用于预测图中两个节点是否相关。
还可以在子图级别上进行社区检测或子图属性预测。社交网络使用社区检测来确定人们的联系方式。子图属性预测可以在行程系统（例如Google Maps）中找到，用于预测预计到达时间。
在这些任务上工作可以通过两种方式完成。
当您想要预测特定图的演化时，您可以在遍历设置中进行工作，其中所有内容（训练、验证和测试）都在同一个图上完成。如果这是您的设置，请注意！从单个图创建训练/评估/测试数据集并不简单。然而，大部分工作都是使用不同的图进行的（分开的训练/评估/测试拆分），这被称为归纳设置。
我们如何表示图？
用于处理和操作图的常见表示方法有：
- 作为所有边的集合（可能补充有所有节点的集合）
- 或作为所有节点之间的邻接矩阵。邻接矩阵是一个方阵（大小为节点数*节点数），指示哪些节点直接连接到其他节点（其中(A_{ij} = 1)表示(n_i)和(n_j)相连，否则为0）。注意：大多数图并不密集连接，因此具有稀疏邻接矩阵，这可能会使计算更加困难。
然而，尽管这些表示似乎很熟悉，但不要被欺骗！
图形与ML中常用的典型对象非常不同，因为它们的拓扑比“序列”（如文本和音频）或“有序网格”（例如图像和视频）更复杂：即使它们可以表示为列表或矩阵，它们的表示不应被视为有序对象！
但是这是什么意思？如果你有一个句子并打乱它的单词，你会得到一个新的句子。如果你有一张图片并重新排列它的列，你会得到一张新的图片。
对于图来说这并不适用：如果你打乱它的边列表或邻接矩阵的列，它仍然是同一个图。（我们稍后会更正式地解释这一点，请查找排列不变性）。
通过ML进行图形表示
使用机器学习处理图形的通常流程是首先为您感兴趣的项（节点、边缘或完整图形，具体取决于您的任务）生成有意义的表示，然后使用这些表示来训练目标任务的预测器。我们希望（与其他模态一样）约束对象的数学表示，以便相似的对象在数学上接近。然而，在图形ML中，这种相似性很难严格定义：例如，当两个节点具有相同的标签或相同的邻居时，它们是否更相似？
注意：在接下来的几节中，我们将专注于生成节点表示。一旦您拥有节点级表示，就有可能获得边缘或图级信息。对于边缘级别的信息，您可以连接节点对表示或进行点积。对于图级信息，可以对所有节点级表示的连接张量进行全局池化（平均值、求和等）。然而，这将使图形变得平滑并丢失信息-递归分层池化可能更有意义，或者添加一个虚拟节点，该节点与图中的所有其他节点相连，并使用其表示作为整体图形表示。
神经网络之前的方法
只使用设计的特征
在神经网络之前，图形及其感兴趣的项可以以特定任务的方式组合特征进行表示。现在，这些特征仍然用于数据增强和半监督学习，尽管存在更复杂的特征生成方法；根据任务的不同，如何最好地将它们提供给网络可能是至关重要的。
节点级特征可以提供关于重要性（该节点对图形的重要程度）和/或基于结构的信息（该节点周围的图形形状是什么），并且可以组合使用。
节点中心度测量图形中节点的重要性。它可以通过递归计算每个节点邻居的中心度之和，或通过节点之间的最短距离测量等方式计算得出。节点度数是其直接邻居的数量。节点聚类系数测量节点邻居之间的连接程度。图形度向量计算以给定节点为根的不同图形的数量，其中图形是您可以使用给定数量的连接节点创建的所有小图（例如，使用三个连接节点，您可以有两个边的线或三个边的三角形）。
边级特征通过提供有关节点的连接性的更详细信息来补充表示，包括两个节点之间的最短距离、它们的共同邻居和它们的Katz指数（即两个节点之间可能的最大长度的行走次数-它可以直接从邻接矩阵中计算得出）。
图级特征包含有关图形相似性和特异性的高级信息。总的图形计数虽然计算成本较高，但提供有关子图形的形状的信息。核方法通过不同的“节点包”方法（类似于词袋）来度量图形之间的相似性。
基于遍历的方法
基于遍历的方法使用从节点i到节点j的随机遍历访问概率来定义相似性度量；这些方法结合了局部和全局信息。Node2Vec，例如，模拟图形中节点之间的随机遍历，然后使用跳字模型处理这些遍历，就像我们在句子中处理单词一样，以计算嵌入。这些方法也可以用于加速Page Rank方法的计算，该方法为每个节点分配重要性分数（基于其与其他节点的连接性，例如通过随机遍历的访问频率来评估）。
然而，这些方法存在一些限制：它们无法为新节点获取嵌入，不能很好地捕捉节点之间的结构相似性，并且无法使用添加的特征。
图神经网络
神经网络可以对未见数据进行泛化。鉴于我们先前提到的表示约束，一个好的神经网络在处理图时应该具备哪些特点呢？
它应该：
- 是置换不变的：
- 方程：f（P（G））= f（G），其中f是网络，P是置换函数，G是图
- 解释：通过网络后，图及其置换的表示应该是相同的
- 是置换等变的：
- 方程：P（f（G））= f（P（G）），其中f是网络，P是置换函数，G是图
- 解释：在将节点传递给网络之前对它们进行置换应该等同于对它们的表示进行置换
典型的神经网络，如循环神经网络（RNN）或卷积神经网络（CNN），不是置换不变的。因此，引入了一种新的架构，即图神经网络（Graph Neural Network）（最初作为一种基于状态的机器）。
GNN由连续的层组成。GNN层将节点表示表示为其在前一层的邻居和自身的表示的组合（聚合），通常还包括激活函数以添加一些非线性。
与其他模型的比较：卷积神经网络可以被视为具有固定邻居大小（通过滑动窗口）和顺序（不是置换等变的）的GNN。没有位置嵌入的Transformer可以被视为一个在完全连接的输入图上的GNN。
聚合和消息传递
有许多方法可以从邻居节点中聚合消息，例如求和、平均等。以下是一些按照这一思想开展的值得注意的工作：
- 图卷积网络（Graph Convolutional Networks）对节点的规范化表示进行平均聚合（大多数GNN实际上都是GCNs）；
- 图注意力网络（Graph Attention Networks）学习基于其重要性对不同邻居进行加权（类似于Transformer）；
- GraphSAGE在聚合邻居信息之前在不同跳数上对邻居进行采样，并使用最大池化进行多步聚合；
- 图同构网络（Graph Isomorphism Networks）通过将MLP应用于邻居节点表示的总和来进行表示聚合。
选择聚合方式：一些聚合技术（尤其是均值/最大池化）在创建能够细分具有不同邻居的节点的表示时可能会遇到失败情况（例如，通过均值池化，表示为1,1,-1,-1的4个节点的邻域平均为0，与表示为-1,0,1的3个节点的邻域没有区别）。
GNN形状和过度平滑问题
在每个新的层中，节点表示将包括越来越多的节点。
通过第一层，一个节点是其直接邻居的聚合。通过第二层，它仍然是其直接邻居的聚合，但这一次，它们的表示包括其自己的邻居（来自第一层）。经过n层后，所有节点的表示将成为距离n处的所有邻居的聚合，因此，如果图的直径小于n，则表示将成为整个图的聚合！
如果您的网络有太多层，每个节点都有可能成为整个图的聚合（并且节点表示会收敛为所有节点相同的表示）。这被称为过度平滑问题。
可以通过以下方式解决这个问题：
- 将GNN缩放为层数足够小，以避免将每个节点近似为整个网络（通过首先分析图的直径和形状）
- 增加层的复杂性
- 添加非消息传递层来处理消息（例如简单的MLPs）
- 添加跳连接。
过度平滑问题是图机器学习中的一个重要研究领域，因为它阻碍了GNN的扩展，就像在其他模态中已经展示的Transformer一样。
图形转换器
去除位置编码层的Transformer是置换不变的，并且Transformer已被证明具有良好的可扩展性，因此最近人们开始将Transformer适应于图形（调研）。大多数方法侧重于通过寻找最佳特征和表示位置信息的最佳方式以及调整注意力来适应这些新数据的最佳方式来表示图形。
以下是一些在编写时在Stanford的Open Graph Benchmark中获得最先进结果或接近最先进结果的有趣方法：
- 图形转换器用于图形到序列学习（Cai和Lam，2020）引入了图形编码器，将节点表示为其嵌入和位置嵌入的连接，将节点关系表示为它们之间的最短路径，并在关系增强的自注意力中组合两者。
- 使用谱注意力重新思考图形转换器（Kreuzer等人，2021）引入了谱注意力网络（SAN）。这些网络将节点特征与学习的位置编码（从拉普拉斯特征向量/值计算）结合起来，作为关键和查询用于注意力，注意力值为边特征。
- GRPE：用于图形转换器的相对位置编码（Park等人，2021）引入了图形相对位置编码转换器。它通过将图级位置编码与节点信息相结合，将边级位置编码与节点信息相结合，并在注意力中将两者相结合来表示图形。
- 全局自注意力作为图形卷积的替代方法（Hussain等人，2021）引入了边缘增强Transformer。该架构将节点和边缘分别嵌入，并在修改后的注意力中聚合它们。
- Transformer在图形表示中真的表现不好吗（Ying等人，2021）介绍了Microsoft的Graphormer，它在OGB发布时获得了第一名。该架构将节点特征用作注意力中的查询/键/值，并将它们的表示与中心性、空间性和边缘编码的组合一起求和。
最新的方法是纯Transformer是强大的图形学习器（Kim等人，2022），它引入了TokenGT。该方法将输入图形表示为节点和边嵌入的序列（加上正交节点标识符和可训练类型标识符），没有位置嵌入，并将此序列提供给Transformer作为输入。它非常简单，但很聪明！
有点不同的是，通用、强大、可扩展的图形转换器的配方（Rampášek等人，2022）介绍了一个名为GraphGPS的框架，而不是模型。它允许将消息传递网络与线性（长程）Transformer结合起来轻松创建混合网络。该框架还包含了几个计算位置和结构编码（节点、图、边级别）、特征增强、随机游走等的工具。
将Transformer用于图形仍然是一个刚起步的领域，但前景看好，因为它可以缓解GNN的一些限制，例如在更大/更密集的图形上进行扩展，或者增加模型大小而不过度平滑。
如果您想深入研究，可以参考以下一些课程：
- 学术格式
- 斯坦福的图形机器学习
- 麦吉尔的图形表示学习
- 视频格式
- 几何深度学习课程
- 书籍
- 图形表示学习*，Hamilton
- 调研
- 图神经网络研究指南
- 研究方向
- 2023年的图形机器学习总结了2023年的图形机器学习的可能有趣方向。
用于图形的好用库包括PyGeometric或Deep Graph Library（用于图形机器学习）和NetworkX（用于更一般地操作图形）。
如果您需要质量基准，您可以查看：
- OGB，开放图形基准：参考图形基准数据集，用于不同的任务和数据规模。
- GNN基准：用于基准测试图形机器学习网络及其表达能力的库和数据集。相关论文特别研究了从统计角度来看哪些数据集是相关的，它们允许评估哪些图形属性以及哪些数据集不应再用作基准。
- 长程图形基准：最新的（2022年11月）基准，研究长程图形信息
- 图形表示学习基准分类法：发表于2022年图形学习会议上的论文，分析和整理现有的基准数据集
更多数据集，请参见：
- Paper with code图任务排行榜：公开数据集和基准的排行榜-注意，此排行榜上的所有基准都可能已经不再相关
- TU数据集：公开可用数据集的汇编，现已按类别和特征排序。这些数据集大部分也可以使用PyG加载，并且其中一部分已经移植到Datasets
- SNAP数据集：斯坦福大型网络数据集合：
- MoleculeNet数据集
- 关系数据集存储库
外部图片归属
缩略图中的表情符号来自Openmoji（CC-BY-SA 4.0），Graphlets图案来自《使用图形度分布进行生物网络比较》（Pržulj, 2007）。