本文次要波及图机器学习的基础知识。
咱们首先学习什么是图，为什么应用图，以及如何最佳地示意图。而后，咱们简要介绍大家如何在图数据上学习，从神经网络以前的办法 (同时咱们会摸索图特色) 到当初广为人知的图神经网络 (Graph Neural Network，GNN)。最初，咱们将一窥图数据上的 Transformers 世界。
什么是图？
实质上来讲，图形容了由关系相互链接起来的实体。
事实中有很多图的例子，包含社交网络 (如推特，长毛象，以及任何链接论文和作者的援用网络)、分子、常识图谱 (如 UML 图，百科全书，以及那些页面之间有超链接的网站)、被示意成句法树的句子、3D 网格等等。因而，能够毫不夸大地讲，图无处不在。
图 (或网络) 中的实体称为 节点 (或顶点)，它们之间的连贯称为 边 (或链接)。举个例子，在社交网络中，节点是用户，而边是他 (她) 们之间的连贯关系；在分子中，节点是原子，而边是它们之间的分子键。
- 能够存在不止一种类型的节点或边的图称为 异构图 (heterogeneous graph) (例子：援用网络的节点有论文和作者两种类型，含有多种关系类型的 XML 图的边是多类型的)。异构图不能仅由其拓扑构造来表征，它须要额定的信息。本文次要探讨同构图 (homogeneous graph)。
- 图还能够是 有向 (directed) 的 (如一个关注网络中，A 关注了 B，但 B 能够不关注 A) 或者是 无向 (undirected) 的 (如一个分子中，原子间的关系是双向的)。边能够连贯不同的节点，也能够本人连贯本人 (自连边，self-edges)，但不是所有的节点都必须有连贯。
如果你想应用本人的数据，首先你必须思考如何最佳地刻画它 (同构 / 异构，有向 / 无向等)。
图有什么用处？
咱们一起看看在图上咱们能够做哪些工作吧。
在 图层面，次要的工作有：
- 图生成，可在药物发现工作中用于生成新的可能的药物分子，
- 图演变 (给定一个图，预测它会如何随工夫演变)，可在物理学中用于预测零碎的演变，
- 图层面预测 (基于图的分类或回归工作)，如预测分子毒性。
在 节点层面，通常用于预测节点属性。举个例子，Alphafold 应用节点属性预测办法，在给定分子总体图的条件下预测原子的 3D 坐标，并由此预测分子在 3D 空间中如何折叠，这是个比拟难的生物化学问题。
在 边层面，咱们能够做边属性预测或缺失边预测。边属性预测可用于在给定药物对 (pair) 的条件下预测药物的不良副作用。缺失边预测被用于在举荐零碎中预测图中的两个节点是否相干。
另一种可能的工作是在 子图层面 的，可用于社区检测或子图属性预测。社交网络用社区检测确定人们之间如何连贯。咱们能够在行程零碎 (如 Google Maps) 中发现子图属性预测的身影，它被用于预测达到工夫。
实现这些工作有两种形式。
当你想要预测特定图的演变时，你工作在 直推 (transductive) 模式，直推模式中所有的训练、验证和推理都是基于同一张图。如果这是你的设置，要多加小心！在同一张图上创立训练 / 评估 / 测试集可不容易。 然而，很多工作其实是工作在不同的图上的 (不同的训练 / 评估 / 测试集划分)，咱们称之为 演绎 (inductive) 模式。
如何示意图？
罕用的示意图以用于后续解决和操作的办法有 2 种：
- 示意成所有边的汇合 (很有可能也会加上所有节点的汇合用以补充)。
- 或示意成所有节点间的邻接矩阵。邻接矩阵是一个 $node\_size \times node\_size$ 大小的方阵，它指明图上哪些节点间是间接相连的 (若 $n\_i$ 和 $n\_j$ 相连则 $A_{ij} = 1$，否则为 0)。
留神：少数图的边连贯并不浓密，因而它们的邻接矩阵是稠密的，这个会让计算变得艰难。
尽管这些示意看上去很相熟，但可别被骗了！
图与机器学习中应用的典型对象大不相同，因为它们的拓扑构造比序列 (如文本或音频) 或有序网格 (如图像和视频) 简单得多：即便它们能够被示意成链表或者矩阵，但它们并不能被当作有序对象来解决。
这到底意味着什么呢？如果你有一个句子，你替换了这个句子的词序，你就发明了一个新句子。如果你有一张图像，而后你重排了这个图像的列，你就发明了一张新图像。
但图并不会如此。如果你重排了图的边列表或者邻接矩阵的列，图还是同一个图 (一个更正式的叫法是置换不变性 (permutation invariance) )。
基于机器学习的图示意
应用机器学习解决图的个别流程是：首先为你感兴趣的对象 (依据你的工作，能够是节点、边或是全图) 生成一个有意义的示意，而后应用它们训练一个指标工作的预测器。与其余模态数据一样，咱们想要对这些对象的数学示意施加一些束缚，使得类似的对象在数学上是相近的。然而，这种相似性在图机器学习上很难严格定义，举个例子，具备雷同标签的两个节点和具备雷同街坊的两个节点哪两个更类似？
留神：在随后的局部，咱们将聚焦于如何生成节点的示意。一旦你有了节点层面的示意，就有可能取得边或图层面的信息。你能够通过把边所连贯的两个节点的示意串联起来或者做一个点积来失去边层面的信息。至于图层面的信息，能够通过对图上所有节点的示意串联起来的张量做一个全局池化 (均匀，求和等) 来取得。当然，这么做会平滑掉或失落掉整图上的一些信息，应用迭代的分层池化可能更正当，或者减少一个连贯到图上所有其余节点的虚构节点，而后应用它的示意作为整图的示意。
神经网络以前的办法
只应用手工设计特色
在神经网络呈现之前，图以及图中的感兴趣项能够被示意成特色的组合，这些特色组合是针对特定工作的。只管当初存在 更简单的特色生成办法，这些特色依然被用于数据加强和 半监督学习。这时，你次要的工作是依据指标工作，找到最佳的用于后续网络训练的特色。
节点层面特色 能够提供对于其重要性 (该节点对于图有多重要？) 以及 / 或结构性 (节点四周的图的形态如何？) 信息，两者能够联合。
节点 核心性 (centrality) 度量图中节点的重要性。它能够递归计算，即一直对每个节点的邻节点的核心性求和直到收敛，也能够通过计算节点间的最短距离来取得，等等。节点的 度 (degree) 度量节点的间接街坊的数量。聚类系数 (clustering coefficient) 度量一个节点的邻节点之间相互连接的水平。图元度向量 (Graphlets degree vectors，GDV) 计算给定根节点的不同图元的数目，这里图元是指给定数目的连通节点可创立的所有迷你图 (如：3 个连通节点能够生成一个有两条边的线，或者一个 3 条边的三角形)。
边层面特色带来了对于节点间连通性的更多细节信息，无效地补充了图的示意，有：两节点间的 最短距离 (shortest distance)，它们的公共街坊 (common neighbours)，以及它们的 卡兹指数 (Katz index) (示意两节点间从所有长度小于某个值的门路的数目，它能够由邻接矩阵间接算得)。
图层面特色 蕴含了对于图相似性和规格的高层信息。总 图元数 只管计算上很低廉，但提供了对于子图形态的信息。 核办法 通过不同的“节点袋 (bag of nodes)”(相似于词袋 (bag of words) ) 办法度量图之间的相似性。
基于游走的办法
基于游走的办法 应用在随机游走时从节点 j 拜访节点 i 的可能性来定义相似矩阵；这些办法联合了部分和全局的信息。举个例子，Node2Vec 模仿图中节点间的随机游走，把这些游走门路建模成跳字 (skip-gram)，这与咱们解决句子中的词很类似，而后计算嵌入。基于随机游走的办法也可被用于减速 Page Rank 办法，帮忙计算每个节点的重要性得分 (举个例子：如果重要性得分是基于每个节点与其余节点的连通度的话，咱们能够用随机游走拜访到每个节点的频率来模仿这个连通度)。
然而，这些办法也有限度：它们不能失去新的节点的嵌入向量，不能很好地捕捉节点间的构造相似性，也应用不了新退出的特色。
图神经网络
神经网络可泛化至未见数据。咱们在上文曾经提到了一些图示意的束缚，那么一个好的神经网络应该有哪些个性呢？
它应该：
-
满足置换不变性：
- 等式：，这里 f 是神经网络，P 是置换函数，G 是图。
- 解释：置换后的图和原图通过同样的神经网络后，其示意应该是雷同的。
-
满足置换等价性
- 公式：，同样 f 是神经网络，P 是置换函数，G 是图。
- 解释：先置换图再传给神经网络和对神经网络的输入图示意进行置换是等价的。
典型的神经网络，如循环神经网络 (RNN) 或卷积神经网络 (CNN) 并不是置换不变的。因而，图神经网络 (Graph Neural Network, GNN) 作为新的架构被引入来解决这一问题 (最后是作为状态机应用)。
一个 GNN 由间断的层组成。一个 GNN 层通过 消息传递 (message passing) 过程把一个节点示意成其邻节点及其本身示意的组合 (聚合 (aggregation))，而后通常咱们还会应用一个激活函数去减少一些非线性。
与其余模型相比：CNN 能够看作一个邻域 (即滑动窗口) 大小和程序固定的 GNN，也就是说 CNN 不是置换等价的。一个没有地位嵌入 (positional embedding) 的 Transformer 模型能够被看作一个工作在全连贯的输出图上的 GNN。
聚合与消息传递
多种形式可用于聚合邻节点的音讯，举例来讲，有求和，取均匀等。一些值得关注的工作有：
- 图卷积网络 对指标节点的所有邻节点的归一化示意取均匀来做聚合 (大多数 GNN 其实是 GCN)；
- 图注意力网络 会学习如何依据邻节点的重要性不同来加权聚合邻节点 (与 transformer 模型想法类似)；
- GraphSAGE 先在不同的跳数上进行邻节点采样，而后基于采样的子图分多步用最大池化 (max pooling) 办法聚合信息；
- 图同构网络 先计算对邻节点的示意求和，而后再送入一个 MLP 来计算最终的聚合信息。
抉择聚合办法：一些聚合技术 (尤其是均值池化和最大池化) 在遇到在邻节点上仅有些微差异的类似节点的状况下可能会失败 (举个例子：采纳均值池化，一个节点有 4 个邻节点，别离示意为 1，1，-1，-1，取均值后变成 0；而另一个节点有 3 个邻节点，别离示意为 – 1，0，1，取均值后也是 0。两者就无奈辨别了。)。
GNN 的形态和过平滑问题
每加一个新层，节点示意中就会蕴含越来越多的节点信息。
一个节点，在第一层，只会聚合它的间接邻节点的信息。到第二层，它们依然只聚合间接邻节点信息，但这次，他们的间接邻节点的示意曾经蕴含了它们各自的邻节点信息 (从第一层取得)。通过 n 层后，所有节点的示意变成了它们间隔为 n 的所有邻节点的聚合。如果全图的直径小于 n 的话，就是聚合了全图的信息！
如果你的网络层数过多，就有每个节点都聚合了全图所有节点信息的危险 (并且所有节点的示意都收敛至雷同的值)，这被称为过平滑问题 (the oversmoothing problem)。
这能够通过如下形式来解决：
- 在设计 GNN 的层数时，要首先剖析图的直径和形态，层数不能过大，以确保每个节点不聚合全图的信息
- 减少层的复杂性
- 减少非消息传递层来解决音讯 (如简略的 MLP 层)
- 减少跳跃连贯 (skip-connections)
过平滑问题是图机器学习的重要钻研畛域，因为它阻止了 GNN 的变大，而在其余模态数据上 Transformers 之类的模型曾经证实了把模型变大是有很好的成果的。
图 Transformers
没有地位嵌入 (positional encoding) 层的 Transformer 模型是置换不变的，再加上 Transformer 模型已被证实扩展性很好，因而最近大家开始看如何革新 Transformer 使之适应图数据 (综述)。少数办法聚焦于如何最佳示意图，如找到最好的特色、最好的示意地位信息的办法以及如何扭转注意力以适应这一新的数据。
这里咱们收集了一些有意思的工作，截至本文写作时为止，这些工作在现有的最难的测试基准之一 斯坦福凋谢图测试基准 (Open Graph Benchmark, OGB) 上获得了最高程度或靠近最高程度的后果：
- Graph Transformer for Graph-to-Sequence Learning (Cai and Lam, 2020) 介绍了一个图编码器，它把节点示意为它自身的嵌入和地位嵌入的级联，节点间关系示意为它们间的最短门路，而后用一个关系加强的自注意力机制把两者联合起来。
- Rethinking Graph Transformers with Spectral Attention (Kreuzer et al, 2021) 介绍了谱注意力网络 (Spectral Attention Networks, SANs)。它把节点特色和学习到的地位编码 (从拉普拉斯特征值和特征向量中计算失去) 联合起来，把这些作为注意力的键 (keys) 和查问 (queries)，而后把边特色作为注意力的值 (values)。
- GRPE: Relative Positional Encoding for Graph Transformer (Park et al, 2021) 介绍了图绝对地位编码 Transformer。它先在图层面的地位编码中联合节点信息，在边层面的地位编码中也联合节点信息，而后在注意力机制中进一步把两者联合起来。
- Global Self-Attention as a Replacement for Graph Convolution (Hussain et al, 2021) 介绍了边加强 Transformer。该架构别离对节点和边进行嵌入，并通过一个批改过的注意力机制聚合它们。
- Do Transformers Really Perform Badly for Graph Representation (Ying et al, 2021) 介绍了微软的 Graphormer, 该模型在面世时博得了 OGB 第一名。这个架构应用节点特色作为注意力的查问 / 键 / 值 (Q/K/V)，而后在注意力机制中把这些示意与核心性，空间和边编码信息通过求和的形式联合起来。
最新的工作是 Pure Transformers are Powerful Graph Learners (Kim et al, 2022)，它引入了 TokenGT。这一办法把输出图示意为一个节点和边嵌入的序列 (并用正交节点标识 (orthonormal node identifiers) 和可训练的类型标识 (type identifiers) 加强它)，而不应用地位嵌入，最初把这个序列输出给 Tranformer 模型。超级简略，但很聪慧！
稍有不同的是，Recipe for a General, Powerful, Scalable Graph Transformer (Rampášek et al, 2022) 引入的不是某个模型，而是一个框架，称为 GraphGPS。它容许把消息传递网络和线性 (长程的) transformer 模型联合起来轻松地创立一个混合网络。这个框架还蕴含了不少工具，用于计算地位编码和构造编码 (节点、图、边层面的)、特色加强、随机游走等等。
在图数据上应用 transformer 模型还是一个十分初生的畛域，然而它看上去很有前途，因为它能够加重 GNN 的一些限度，如扩大到更大 / 更浓密的图，抑或是减少模型尺寸而不用放心过平滑问题。
更进阶的资源
如果你想钻研得更深刻，能够看看这些课程：
-
学院课程模式
- 斯坦福大学图机器学习
- 麦吉尔大学图示意学习
-
视频模式
- 几何深度学习课程
-
相干书籍
- 图示意学习 *，汉密尔顿著
不错的解决图数据的库有
PyGeometric (用于图机器学习) 以及 NetworkX (用于更通用的图操作)。
如果你须要品质好的测试基准，你能够试试看：
- OGB, 凋谢图测试基准 (the Open Graph Benchmark)：一个可用于不同的工作和数据规模的参考图测试基准数据集。
- Benchmarking GNNs: 用于测试图机器学习网络和他们的表现力的库以及数据集。相干论文顺便从统计角度钻研了哪些数据集是相干的，它们可被用于评估图的哪些个性，以及哪些图不应该再被用作测试基准。
- 长程图测试基准 (Long Range Graph Benchmark): 最新的 (2022 年 10 月份) 测试基准，次要关注长程的图信息。
- Taxonomy of Benchmarks in Graph Representation Learning: 发表于 2022 年 Learning on Graphs 会议，剖析并对现有的测试基准数据集进行了排序。
如果想要更多的数据集，能够看看:
- Paper with code 图工作排行榜:
公开数据集和测试基准的排行榜，请留神，不是所有本排行榜上的测试基准都依然合适。 - TU 数据集: 公开可用的数据集的合辑，当初以类别和特色排序。大多数数据集能够用 PyG 加载，而且其中一些曾经被集成进 PyG 的 Datsets。
-
SNAP 数据集 (Stanford Large Network Dataset Collection):
- MoleculeNet 数据集
- 关系数据集仓库
内部图像起源
缩略图中的 Emoji 表情来自于 Openmoji (CC-BY-SA 4.0)，图元的图片来自于 Biological network comparison using graphlet degree distribution (Pržulj, 2007)。
英文原文: https://huggingface.co/blog/intro-graphml
译者: Matrix Yao (姚伟峰)