A Gentle Introduction to Deep Learning for Graphs 图深度学习的温和介绍
论文：A Gentle Introduction to Deep Learning for Graphs
作者：Davide Bacciua, Federico Erricaa, Alessio Michelia, Marco Poddaa
意大利比萨大学计算机科学系
来源：Machine Learning (cs.LG)
论文链接：
https://arxiv.org/pdf/1912.12693.pdf
摘要
图形数据的自适应处理是一个长期存在的研究主题，近来已被整合为深度学习社区的主要兴趣主题。相关研究的数量和广度迅速增加是以缺乏知识的系统化和对早期文献的关注为代价的。这篇文章主要是想作为图的深度学习领域的教程。相对于对最新文献的阐释，它主张对主要概念和体系结构方面进行一致且渐进的介绍，读者可参考其中的可用调查。本文从上至下对问题进行了介绍，介绍了一种基于局部和迭代方法来进行结构化信息处理的图形表示学习的广义公式。它介绍了基本的构建基块，可以将其组合起来设计出新颖而有效的图形神经模型。通过对有趣的研究挑战和在该领域中的应用的讨论来补充方法论的论述。
**关键字：**图的深度学习，图神经网络，结构化数据学习，教程
1.简介图形是表示各种人工和自然交互过程产生的不同性质数据的强大工具。图数据具有组成性质（是原子信息片段的复合）以及关系性质，因为定义其结构的链接表示链接的实体之间的某种形式的关系。图表允许通过链接方向和标签来表示大量的关联:例如离散关系类型、化学性质和分子键的强度。但最重要的是，图形无处不在。在化学和材料科学中，它们代表化合物的分子结构，蛋白质相互作用和药物相互作用网络，生物和生物化学关联。在社会科学中，网络被广泛用于代表人们的关系，而推荐系统则使用复杂的购买行为。
此类数据的丰富性以及大型存储库的可用性不断提高，引起了人们对能够以自适应方式处理图形的深度学习模型的兴趣激增。与这一总体目标相关的方法论和实践挑战是下面几个。首先，图形的学习模型应该能够适应在大小和拓扑结构上不同的样本。除此之外，关于节点标识和跨多个样本排序的信息很少可用。同时，图是离散的对象，这对可微性有一定的限制，而图的组合性质又阻碍了穷举搜索方法的应用。最后，最一般的图类允许出现循环，这是消息传递和节点访问的复杂性来源。换句话说，处理图形数据在表现形式和计算复杂度方面，以及在矢量数据学习方面，都带来了前所未有的挑战。因此，这是一个很好的开发和测试新的神经网络方法的领域。
尽管最近深度学习社区掀起了一阵热潮，但用于图的神经网络领域已有悠久而巩固的历史，它起源于90年代初，涉及树状结构数据的递归神经网络（RecNN）的开创性工作（请参阅[ [98、32、9]及其中的参考文献）。 RecNN方法后来在自然语言处理应用程序的上下文中重新发现[99，97]。同样，它从有向无环图开始逐渐扩展到更复杂和更丰富的结构[75]，为此，它已经得到了通用逼近的保证[44]。递归处理结构还被概率论所利用，首先作为一个纯理论模型[32]，然后更实际地通过有效的近似分布[6]。
递归模型共享一个(神经)状态转换系统的思想，该系统遍历结构以计算其嵌入。将这种方法扩展到一般图(循环/非循环、有向/无向)的主要问题是循环的处理，因为在神经递归单元中定义的状态变量之间存在相互依赖关系。最早解决这个问题的模型是Graph Neural Network (GNN)[89]和Neural Network for Graphs (NN4G)[74]。GNN模型是基于一个类似于RecNN的状态转换系统，但是它允许在状态计算中循环。相反，NN4G提出了一种想法，即可以通过利用架构中先前层的表示来管理相互依赖关系。通过这种方式，NN4G用多层架构打破了图数据循环中的递归依赖关系。这些模型为图形处理的两种主要方法奠定了基础，即递归(GNN)方法和前馈(NN4G)方法，从而开创了这一领域。特别是后者现在已经成为主流的方法，在graph convolutional (neural) networks的统称下。(以在2015年前后重新引入上述概念的方法命名[59,42])。
本文从这一历史角度出发，对图的神经网络领域进行了简要介绍，在现代术语中也称为图的深度学习。本文旨在作为具有教程性质的论文，赞成对主要概念和构建块进行有充分依据的，一致的和渐进的介绍，以组装图的神经体系结构。因此，它的目的不是要对有关该主题的最新出版作品进行阐述。这种教程方法的动机是多方面的。一方面，近年来关于图形深度学习的著作激增，这是以一定程度的遗忘(如果不是缺乏适当的引用的话)为代价的，这种遗忘是开创性和综合性著作的结果。因此，存在重新发现已知结果和模型的风险。另一方面，社区开始注意到图的深度学习模型评估中令人不安的趋势[93,25]，这需要更多的有原则地对待这个话题。最后，文献[7,15,38,43,111,112,126,127]中开始出现一定数量的调查论文，而对方法的介绍似乎比较缓慢。
本教程采用自顶向下的方法，同时对主要概念和思想的引入保持一个清晰的历史视角。为此，在第2节中，我们首先提供了图形表示学习问题的一个通用公式，介绍并激发了我们将在本文其余部分中遵循的体系结构路线图。我们将特别关注处理信息的局部和迭代处理的方法，因为这些方法更符合神经网络的操作机制。在这方面，我们将较少关注基于谱图方法的全局方法(即假设单个固定邻接矩阵)。然后，在第3节中，我们将介绍可以组装和组合的基本构建块，以创建现代的图数据深度学习体系结构。在本文中，我们将介绍图卷积的概念，如局部邻域聚合函数、注意力的使用、在图上定义的抽样和池操作符，最后我们将讨论计算整个结构嵌入的聚合函数。在第4节中，我们将继续讨论图表示学习中的主要学习任务，以及相关的成本函数和相关的归纳偏差的描述。论文的最后一部分是对其他相关方法和任务的综述(第5部分)，并讨论了有趣的研究挑战(第6部分)和应用(第7部分)。
2. 高级概述我们首先从图的深度学习的高级概述开始。为此，我们首先总结必要的数学符号。然后，讨论文学作品中绝大多数借用的动机和主要思想。
图1:
形式上，图g=(Vg,Eg,Xg,Ag)g=\left(\mathcal{V}_{g}, \mathcal{E}_{g}, \mathcal{X}_{g}, \mathcal{A}_{g}\right)g=(Vg,Eg,Xg,Ag)是由一组顶点Vg\mathcal{V}_{g}Vg(也称为节点)和一组连接两个节点Eg={(u,v)∣u,v∈Vg}\mathcal{E}_{g}=\left\{(u, v) | u, v \in \mathcal{V}_{g}\right\}Eg={(u,v)∣u,v∈Vg}的有向边(或弧)定义的。我们对无向弧进行建模，即， (u,v)=(v,u)(u, v)=(v, u)(u,v)=(v,u)形式的弧，有两个方向相反的弧。为了方便，我们有时会使用一对(Vg,Eg)\left(\mathcal{V}_{g}, \mathcal{E}_{g}\right)(Vg,Eg)的另一种表示形式，即g的邻接矩阵，定义为A∈{0,1}∣Vq∣×∣Vs∣\mathbf{A} \in\{0,1\}^{\left|V_{q}\right| \times\left|V_{s}\right|}A∈{0,1}∣Vq∣×∣Vs∣。
节点可以与特征向量xv∈Xg⊆Rd\mathbf{x}_{v} \in \mathcal{X}_{g} \subseteq \mathbb{R}^{d}xv∈Xg⊆Rd相关联。同样,有向边可以有自己的特征向量auv∈Ag⊆Rd′\mathbf{a}_{u v} \in \mathcal{A}_{g} \subseteq \mathbb{R}^{d^{\prime}}auv∈Ag⊆Rd′。在监督学习应用程序中，我们可能希望预测单个节点、一条边或整个图的输出，其ground truth标签分别称为yv,yuvy_{v}, y_{u v}yv,yuv和ygy_{g}yg。当从上下文中清除时，我们将省略下标g以避免冗长的表示法。
ground truth：在机器学习里面理解为真值、真实的有效值或者是标准的答案。
在机器学习中，术语”ground truth”指的是用于有监督训练的训练集的分类准确性，主要用于统计模型中验证或推翻某种研究假设。术语也指收集准确客观的数据用于验证的过程。
如果定义了节点上的总顺序，则图形是有序的，否则就是无序的。同样，如果存在从每条边到一组自然数的双射映射，则图是有位置的，否则就是无位置的。在本文的其余部分，我们将假设无序和非位置图。
节点vvv的邻域定义为以有向弧连接到vvv的节点集合，即，Nv={u∈Vg∣(u,v)∈Eg}。Nv\mathcal{N}_{v}=\left\{u \in \mathcal{V}_{g} |(u, v) \in \mathcal{E}_{g}\right\}。 \mathcal{N}_{v}Nv={u∈Vg∣(u,v)∈Eg}。Nv关闭，如果它总是包括u和开放，否则。如果弧标A的域是离散的、有限的，即， A={c1,…,cm}\mathcal{A}=\left\{c_{1}, \ldots, c_{m}\right\}A={c1,…,cm}，我们用弧标签ckc_{k}ck as Nvck={u∈Nv∣auv=ck}\mathcal{N}_{v}^{c_{k}}=\left\{u \in \mathcal{N}_{v} | \mathbf{a}_{u v}=c_{k}\right\}Nvck={u∈Nv∣auv=ck}定义vvv的邻居子集。图1描述了一个具有无向和有向弧的图(1a)，以及它可以表示为机器学习模型输入的方式(1b)。相反，节点v1v1v1的(开放)邻域如图1c所示。
在下面几节中,我们将使用符号ℓ\ellℓ表示一个通用的层/迭代步骤层/迭代步骤层/迭代步骤的机制，通过它，信息可以在整个图中传播。此外，我们用hvℓ\mathbf{h}_{v}^{\ell}hvℓ表示在ℓ\ellℓ层的节点vvv的隐藏状态向量，即节点的内部表示，而hgℓ\mathbf{h}_{g}^{\ell}hgℓ表示在ℓ\ellℓ层与整个图ggg相关的表示。重要的是，我们使用上下文一词来标识直接或间接影响特定节点表示形式hvℓ\mathbf{h}_{v}^{\ell}hvℓ的节点集。
让我们也介绍一个定义在集合上的函数的通用符号，这是至关重要的，因为我们假设了无序邻域。在整个工作中，我们将使用字母Ψ\PsiΨ表示置换不变函数，即具有以下属性的函数：Ψ(Z)=Ψ(π(Z))\Psi(Z)=\Psi(\pi(Z))Ψ(Z)=Ψ(π(Z))，其中Z是泛型集合，而π(⋅)\pi(\cdot)π(⋅)是任意值排列运算符。类似地定义了多集合上的置换不变函数。置换不变函数的示例是集合中所有元素的总和，均值和乘积。当集合是可数的（这是我们在实践中期望的）时，可以通过以下[123]近似任何置换不变函数：
Ψ(Z)≈ϕ(∑z∈Zψ(z))\Psi(Z) \approx \phi\left(\sum_{z \in Z} \psi(z)\right)Ψ(Z)≈ϕ(z∈Z∑ψ(z))
其中ϕ\phiϕ和ψψψ是任意的函数。
邻域是集合上的一种基础的拓扑结构。有邻域公理（邻域公理是现代数学拓扑结构的基础概念）、开邻域和闭邻域、去心邻域等的研究著作。
邻域是一个特殊的区间，以点a为中心点任何开区间称为点a的邻域，记作U(a)。
拓扑结构
拓扑空间是一个集合X{\displaystyle X}X和其上定义的拓扑结构τ{\displaystyle \tau }τ 组成的二元组(X,τ){\displaystyle (X,\tau )}(X,τ)。X{\displaystyle X}X的元素 x{\displaystyle x}x通常称为拓扑空间 (X,τ){\displaystyle (X,\tau )}(X,τ)的点。而拓扑结构τ{\displaystyle \tau }τ一词涵盖了开集，闭集，邻域，开核，闭包，导集，滤子等若干概念。从这些概念出发，可以给拓扑空间(X,τ){\displaystyle (X,\tau )}(X,τ)作出若干种等价的定义。在教科书中最常见的定义是从开集开始的。
而这里的拓扑结构我觉得直接理解为无向图即可。
图2：所有图学习方法共享的全局图。 DGN获取输入图并生成节点表示hv∀v∈Vg\mathbf{h}_{v} \forall v \in \mathcal{V}_{g}hv∀v∈Vg。可以将这样的表示形式聚合起来以形成单个图形表示形式hg\mathbf{h}_{g}hg。
由于模型能够自动地从原始数据中提取相关特征来解决问题，因此表示学习在研究领域引起了广泛的兴趣。在这方面，卷积神经网络[61]可能是这种平面数据方法的最佳代表。由于结构化域允许表示比平面数据更清晰的信息，因此考虑实体之间的现有关系至关重要。换句话说，需要对结构进行自适应处理才能最大限度地利用这些附加信息。注意，在图的特定情况下，不能对图的大小或拓扑结构做出任何假设;因此，为了确保它们的普遍适用性，图数据处理方法必须在没有已知的和固定的因果关系的情况下设计。，该机制允许施加适当的顺序来处理图形组件)。
自适应就是在处理和分析过程中，根据处理数据的数据特征自动调整处理方法、处理顺序、处理参数、边界条件或约束条件，使其与所处理数据的统计分布特征、结构特征相适应，以取得最佳的处理效果的过程。
自适应过程是一个不断逼近目标的过程，它所遵循的途径以数学模型表示，称为自适应算法。通常采用基于梯度的算法，其中最小均方误差算法(即LMS算法)尤为常用。
不管我们关心的训练目标是什么，几乎所有用于图的深度学习方法最终都会产生节点表示（状态）hv,∀v∈Vg\mathbf{h}_{v}, \forall v \in \mathcal{V}_{g}hv,∀v∈Vg。在[32]中，这个过程被称为执行图的同构转换。这些表示是并行访问图节点的结果;也就是说，在没有任何特定节点或划分的情况下遍历图。图2所示的整体机制非常有用，因为它允许处理节点、边和图相关的任务;例如，图7表示可以很容易地通过将其节点表示聚合在一起来计算。因此，研究人员和实践者的工作围绕着从图中自动提取相关特征的深度学习模型的定义展开。在本教程中，我们将这些模型称为深图网络(DGNs)。一方面，这个通用术语的目的是消除术语图神经网络(Graph Neural Net- work, GNN)和图卷积网络(Graph Convolutional Network, GCN)之间的歧义，图神经网络(Graph Neural Net- work, GNN)指的是[89]，而图卷积网络(Graph Convolutional Network, GCN)指的是[59]。这两个术语在文献中经常被用来表示操作在图数据上的整个类神经网络，在从业者中产生了歧义和混淆。另一方面，我们也使用它作为一个说明性分类的基础(如图3所示)，它将作为本节和后续部分讨论的路线图。
为了进一步阐明我们对术语的使用，这里DGN指的是产生最终内部节点表示hv\mathbf{h}_{v}hv的体系结构的子集。可以通过将每一层计算得到的所有内部表示连接起来（进行级联），也可以通过获取最后一层生成的内部表示来获得。因此，术语DGN不包括全局节点聚合机制，也不包括最终分类器或回归器。通过这种方式，我们在体系结构上保持了一个模块化的视图，并且我们可以将任何DGN与一个通过使用最终的内部节点表示作为输入来解决任务的预测器相结合。
我们将DGNs分为三类:深度神经图网络(DNGNs)，其中包括受神经结构启发的模型;以图的概率模型为代表的深度贝叶斯图网络;还有深度生成图网络(DGGNs)，它包括利用神经模型和概率模型的图的生成方法。这种分类法绝不是方法的严格划分;实际上，我们在本教程中所关注的所有方法都是基于局部关系和迭代处理来将节点上下文分散到整个图中，而不考虑它们的神经或概率性质。
图3：我们将详细讨论的体系结构路线图。
从任意图的总体中学习提出了两个基本问题:第一，对一般图的拓扑结构不作任何假设;第二，结构可能包含循环。现在我们讨论这两点，重点介绍文献中采用的最常见的解决方案。
具有可变拓扑的图。首先，我们需要一种无缝处理大小和形状均变化的图形信息的方法。在文献中，这已经通过构建在节点级别而不是图级别本地工作的模型来解决[98]。换句话说，模型只关心节点及其附近的关系。这回想起卷积模型中图像的局部处理，在该模型中，焦点集中在单个像素及其有限邻居（无论如何定义）上。这种平稳性假设可以极大地减少模型所需的参数数量，因为它们可在所有节点上重复使用（类似于卷积滤波器在像素上的重复使用方式）。此外，它有效且高效地结合了数据集中所有节点和图形的“经验”，以学习单个功能。同时，平稳性假设要求引入一些机制，这些机制也可以从图的全局结构中学习，我们将在下一节中讨论这些机制。
尽管有这些优点，但仅进行局部处理并不能解决可变邻域形状的图的问题。在非位置图的情况下会出现此问题，在这种情况下，没有一致的方式来排序邻域中的节点。在这种情况下，一种常见的解决方案是使用对每个节点的邻居集起作用的置换不变函数。
图4：显示了深度为3的网络在无向图中的上下文传播，其中波浪箭头表示上下文流。具体来说，我们通过从右到左查看图，重点关注最后一层节点 uuu 的上下文。很容易看出，节点 uuu 在 ℓ=2\ell=2ℓ=2 时的上下文取决于其唯一邻居 vvv 在 ℓ=1\ell=1ℓ=1 时的上下文，后者又取决于节点 uuu 在 ℓ=0\ell=0ℓ=0（包括u）处的表示形式。因此，图的几乎所有节点都给出了 uuu 的上下文。添加一点个人的理解，这里是否就是说，在考虑 u 和 v 的关系的时候，u 可以通过 v 考虑v 的领域节点的信息。
图包含循环图包含循环图包含循环。图的自适应局部处理意味着任何节点的中间状态都是其邻居状态的函数。因此，如果一个图包含一个循环，则需要处理节点状态之间的相互因果关系。解决这个问题的方法是假设一个迭代方案，即hvℓ+1\mathbf{h}_{v}^{\ell+1}hvℓ+1是通过在上一次迭代中计算出的邻居状态定义的。这样，我们就可以近似出属于一个循环的节点之间的相互依赖关系。正如我们将看到的，这样的迭代定义可以很好地并入深层架构。
2.5、语境扩散的三种机制本节介绍了上下文扩散，它可以说是局部图学习方法中最重要的概念。顾名思义，上下文扩散的目标是在整个图上传播信息。在更广泛环境中为节点提供与其有关的知识，而不是仅限于其直接邻域。这对于节点的更好的表达是很有必要的。
图4描述了通过迭代和局部方法扩散上下文的方式，其中我们显示了节点 u 在迭代 ℓ=2\ell=2ℓ=2 时对图具有的“视图”。首先，我们观察到 u 的邻域。是由节点 v 给出的，因此 u 接收的所有上下文信息都必须经过v。如果从右向左看图片，则根据hv1\mathbf{h}_{v}^{1}hv1定义的hu2\mathbf{h}_{u}^{2}hu2，v∈Nuv \in \mathcal{N}_{u}v∈Nu，这又是通过聚合三个不同颜色的节点（其中一个是u本身）来计算的。因此，通过迭代计算相邻特征的局部聚合，我们能够间接地向 u 提供有关图中更远的节点的信息。很容易看出迭代次数为3的时候，即 ℓ=3\ell=3ℓ=3 时，足以增加上下文以包括图中的所有节点。换句话说，深度学习技术不仅对自动特征提取有用，而且对上下文扩散也起作用。上下文扩散的正式的描述在[74]中给出。
根据不同的上下文扩散机制，我们可以将大多数深度图学习模型划分为递归、前馈和构造方法。我们现在讨论它们是如何工作的以及它们之间的区别。
循环架构循环架构循环架构。该系列模型将节点信息的迭代处理实现为动态系统。这个家族中最受欢迎的两个代表是图神经网络[89]和图回波状态网络[35]。两种方法都依赖于施加收缩动力学来确保迭代过程的收敛。前者在（监督的）损失函数中施加了这样的约束，而后者则从（未经训练的）储层动力学的收缩性继承了收敛性。门控图神经网络[63]是循环体系结构的另一个示例，与[89]不同，迭代次数是先验固定的，无论是否达到收敛。在[69]中引入了一种基于集体推理的迭代方法，该方法不依赖任何特定的收敛标准。
这一系列模型通过建模节点状态相互依存关系，以迭代的方式来处理图循环。在这些情况下，我们可以将图4的符号 ℓ\ellℓ 解释为递归状态转换函数的“迭代步骤”，用来计算每一个节点的状态。
前馈架构前馈架构前馈架构。与递归模型不同的是，前馈模型没有利用递归单元在同一层上的迭代扩散机制，而是将多层叠加起来，以构成每一步学习的局部上下文。结果，由循环引起的相互依赖通过不同的参数化层进行管理，不需要约束来确保编码过程的收敛。为了与图4进行对比(这里对应的是一个层的索引)，这种组合性会影响每个节点的上下文，上下文随着网络深度的增加而增加，直到包含整个图[74]。
毫不奇怪，这种上下文扩散与CNNs的局部接受域有密切的相似性，这种相似性随着架构中添加更多层而增加。CNNs的不同之处在于，图没有固定的结构，因为邻居的大小可能不同，而且很少给出节点排序。特别是CNNs的局部接受域可以看作是图数据中一个节点的上下文，而平面数据上的卷积算子则回忆起图数据中节点的无序并行访问(即使参数化技术不同)。这就是图卷积层图卷积层图卷积层这一术语在文献中经常使用的原因。
前馈模型系列因其简单、高效、适用于多种不同的任务而广受欢迎。但是，图的深层网络与其他深层神经网络同样面临与梯度相关的问题，尤其是与整个架构中的“端到端”学习过程相关时。
建设性架构建设性架构建设性架构。我们确定的最后一个族可以看作是前馈模型的特例，其中的训练是逐层进行的。建设性架构的主要好处是，深层网络不会因设计而导致消失/爆炸梯度问题，因此上下文可以更有效的在节点之间传播。在有监督的情况下，这种构造技术甚至可以自动确定完成一项任务所需的层数[26,72]。就像在图4中解释的那样，在图形模型中，该特性也与当前问题所需的上下文相关，因此，无需先验确定它，如[74]所示，其中层的深度和上下文形状已得到正式证明。此外，建设性模型的一个重要特征是它们以“分而治之”的方式解决问题，将任务逐步拆分为更简单的子任务（从而放宽了“端到端”方法）。每一层都有助于解决子问题，随后的层使用此结果逐步解决全局任务。
在这些建设性的方法中，我们提到了图数据的神经网络(NN4G)74，而最近的一种概率变体是上下文图数据马尔科夫模型(CGMM)[3]。
3.构建块现在我们将注意力转向局部图学习模型的主要组成部分。这些构建块施加的体系结构偏差决定了模型可以计算的表示形式。本节的目的不是给出最全面，最笼统的表述，而在此表述下可以对所有模型进行形式化。相反，它的目的是展示许多体系结构共有的主要组成部分，以及如何将这些组成一个有效的图形学习模型。
3.1、邻域（邻居）聚集局部图处理的核心是对邻居进行模型聚合以计算隐藏节点表示的方法。我们将遵循图是非位置的普遍假设，因此我们需要使用置换不变函数来实现聚合。为了便于注释，我们将假设在节点 v 上运行的任何函数都可以访问其特征向量 xv\mathbf{x}_{v}xv 以及入射弧特征向量集{auv∣u∈Nv}\left\{\mathbf{a}_{u v} | u \in \mathcal{N}_{v}\right\}{auv∣u∈Nv}。
以其最一般的形式，可以表示节点 v 在层/步骤ℓ+1\ell+1ℓ+1处的邻域聚合如下：
hvℓ+1=ϕℓ+1(hvℓ,Ψ({ψℓ+1(huℓ)∣u∈Nv}))−−−−−−−(1) \mathbf{h}_{v}^{\ell+1}=\phi^{\ell+1}\left(\mathbf{h}_{v}^{\ell}, \Psi\left(\left\{\psi^{\ell+1}\left(\mathbf{h}_{u}^{\ell}\right) | u \in \mathcal{N}_{v}\right\}\right)\right) -------(1) hvℓ+1=ϕℓ+1(hvℓ,Ψ({ψℓ+1(huℓ)∣u∈Nv}))−−−−−−−(1)
其中Nv\mathcal{N}_{v}Nv可以打开或关闭。在大多数情况下，ℓ=0\ell=0ℓ=0 的基本情况对应于不依赖于结构信息的节点特征xv\mathbf{x}_{v}xv的可能的非线性变换。
重要的是要意识到上述公式包括神经和贝叶斯DGN。例如，上面介绍的邻域聚合方案的一个流行的具体实例是图卷积网络[59]，它是DNGN，其执行聚合的过程如下：
hvℓ+1=σ(Wℓ+1∑u∈N(v)Luvhuℓ)
\mathbf{h}_{v}^{\ell+1}=\sigma\left(\mathbf{W}^{\ell+1} \sum_{u \in \mathcal{N}(v)} \mathbf{L}_{u v} \mathbf{h}_{u}^{\ell}\right)
hvℓ+1=σ⎝⎛Wℓ+1u∈N(v)∑Luvhuℓ⎠⎞
其中LLL是归一化图拉普拉斯算子，WWW是权重矩阵，σσσ是和sigmoid差不多的非线性激活函数。
处理图形边缘。前面提到的一般的邻域聚合方案要求弧是不带属性的，或者包含相同的信息。这种假设通常不成立，因为图中的弧通常包含有关关系性质的附加信息。这些信息可以是离散的(例如，在一个分子中连接两个原子的化学键的类型)，也可以是连续的(例如，原子间的节点距离)。因此，我们需要利用弧标签来丰富节点表示的机制。如果A\mathcal{A}A是有限且离散的，我们可以重新定义公式1，以说明不同的弧标签。如下：
hvℓ+1=ϕℓ+1(hvℓ,∑ck∈A(Ψ({ψℓ+1(huℓ)∣u∈Nvck})∗wk))−−−−−−−（2） \mathbf{h}_{v}^{\ell+1}=\phi^{\ell+1}\left(\mathbf{h}_{v}^{\ell}, \sum_{c_{k} \in \mathcal{A}}\left(\Psi\left(\left\{\psi^{\ell+1}\left(\mathbf{h}_{u}^{\ell}\right) | u \in \mathcal{N}_{v}^{c_{k}}\right\}\right) * w_{k}\right)\right)-------（2） hvℓ+1=ϕℓ+1(hvℓ,ck∈A∑(Ψ({ψℓ+1(huℓ)∣u∈Nvck})∗wk))−−−−−−−（2）
其中wk\boldsymbol{w}_{\boldsymbol{k}}wk是一个可学习的参数，权衡带有标签auv=ck\mathbf{a}_{u v}=c_{k}auv=ck的弧的贡献。该公式表示在共享相同弧标记的邻居之间的内部聚集，以及每个可能的弧标记上的外部总和。这样，可以分别了解每个弧形标签的作用。 NN4G [74]和R-GCN [90]实现了等式。明确地参见图2，而CGMM [3]使用开关父母近似[88]来达到相同的目标。与连续弧标签一起使用的更通用的解决方案是重新公式化公式 1作为
hvℓ+1=ϕℓ+1(hvℓ,Ψ({eℓ+1(auv)Tψℓ+1(huℓ)∣u∈Nv}))−−−−−−−（3）
\mathbf{h}_{v}^{\ell+1}=\phi^{\ell+1}\left(\mathbf{h}_{v}^{\ell}, \Psi\left(\left\{e^{\ell+1}\left(\mathbf{a}_{u v}\right)^{T} \psi^{\ell+1}\left(\mathbf{h}_{u}^{\ell}\right) | u \in \mathcal{N}_{v}\right\}\right)\right)-------（3）
hvℓ+1=ϕℓ+1(hvℓ,Ψ({eℓ+1(auv)Tψℓ+1(huℓ)∣u∈Nv}))−−−−−−−（3）
其中eee可以是任何函数。请注意，我们是如何在邻域(居)聚集中显式引入对弧auv\mathbf{a}_{u v}auv的依赖性的：这将根据每个邻居(可能是多维的)弧标记对其贡献进行加权，而不管它是连续的还是离散的。例如，在[38]中，eee被实现为输出权重矩阵的神经网络。
注意注意注意 注意机制[101]为神经层输入的每个部分分配一个相关性分数，并且它们在与语言相关的任务中得到了普及。当输入为图结构时，我们可以注意聚合函数。这导致邻居的加权平均值，其中各个权重是节点 v 及其邻居u∈Nvu \in \mathcal{N}_{v}u∈Nv的函数。更正式地讲，我们用以下列方式扩展了等式1的卷积：
hvℓ+1=ϕℓ+1(hvℓ,Ψ({αuvℓ+1∗ψℓ+1(huℓ)∣u∈Nv}))−−−−−−(4)
\mathbf{h}_{v}^{\ell+1}=\phi^{\ell+1}\left(\mathbf{h}_{v}^{\ell}, \Psi\left(\left\{\alpha_{u v}^{\ell+1} * \psi^{\ell+1}\left(\mathbf{h}_{u}^{\ell}\right) | u \in \mathcal{N}_{v}\right\}\right)\right)------(4)
hvℓ+1=ϕℓ+1(hvℓ,Ψ({αuvℓ+1∗ψℓ+1(huℓ)∣u∈Nv}))−−−−−−(4)
其中αuvℓ+1∈R\alpha_{u v}^{\ell+1} \in \mathbb{R}αuvℓ+1∈R是与u∈Nvu \in \mathcal{N}_{v}u∈Nv相关的注意力得分。通常，此分数与边缘信息无关，因此，边缘处理和注意力是两种截然不同的技术。实际上，图注意力网络（GAT）[102]对其邻居施加注意，但它没有考虑边缘信息。为了计算注意力得分，GAT计算注意力系数wuvw_{uv}wuv如下：
wuvℓ=a(Wℓhuℓ,Wℓhvℓ)
w_{u v}^{\ell}=a\left(\mathbf{W}^{\ell} \mathbf{h}_{u}^{\ell}, \mathbf{W}^{\ell} \mathbf{h}_{v}^{\ell}\right)
wuvℓ=a(Wℓhuℓ,Wℓhvℓ)
其中 aaa 是共享注意力函数，WWW 是图层权重。注意力系数衡量当前节点 vvv 与它的每个邻居 uuu 之间的某种形式的相似性。此外，GAT将关注函数a实现为：
a(Wℓhuℓ,Wℓhvℓ)= LeakyReLU ((bℓ)T[Wℓhuℓ,Wℓhvℓ])
a\left(\mathbf{W}^{\ell} \mathbf{h}_{u}^{\ell}, \mathbf{W}^{\ell} \mathbf{h}_{v}^{\ell}\right)=\text { LeakyReLU }\left(\left(\mathbf{b}^{\ell}\right)^{T}\left[\mathbf{W}^{\ell} \mathbf{h}_{u}^{\ell}, \mathbf{W}^{\ell} \mathbf{h}_{v}^{\ell}\right]\right)
a(Wℓhuℓ,Wℓhvℓ)= LeakyReLU ((bℓ)T[Wℓhuℓ,Wℓhvℓ])
其中bℓb^{\ell}bℓ是可学习的参数，[⋅,⋅][\cdot, \cdot][⋅,⋅]表示连接，而LeakyReLU是[68]中提出的非线性激活函数。根据注意力系数，可以通过将它们传递给softmax函数来获得注意力得分：
αuvℓ=exp(wuvℓ)∑u′∈Nvexp(wu′vℓ)\alpha_{u v}^{\ell}=\frac{\exp \left(w_{u v}^{\ell}\right)}{\sum_{u^{\prime} \in \mathcal{N}_{v}} \exp \left(w_{u^{\prime} v}^{\ell}\right)}αuvℓ=∑u′∈Nvexp(wu′vℓ)exp(wuvℓ)
GAT将该注意方案概括为多头注意，其中将多个注意机制的结果连接在一起或取平均。
图5：采样技术通过选择邻居的一个子集[18]或图形中的一个子集[42]来计算hvℓ+1h_{\mathbf{v}}^{\ell+1}hvℓ+1，从而影响邻域聚集过程。在这里，红色节点已被随机从节点 vvv 的邻域聚合中排除，并且上下文仅通过波浪箭头流动。
采样采样采样。当图较大且密集时，由于边的数量在∣Vg∣\left|\mathcal{V}_{g}\right|∣Vg∣基础上变为二次方，因此无法对每个节点的所有邻居执行聚合。因此，需要替代策略来减少计算负担，并且邻域采样是其中之一。在这种情况下，仅使用邻居的随机子集来计算hvℓ+1\mathrm{h}_{v}^{\ell+1}hvℓ+1。当子集大小固定时，我们还获得了每个图的聚合成本的上限。图5描述了通用采样策略如何在节点级别起作用。在对邻居进行抽样的模型中，我们提到了FastGCN [18]和GraphSAGE [42]。具体地，FastGCN通过重要性采样在每层 ℓ\ellℓ 上采样 ttt 个节点，从而减小了梯度估计器的方差。与FastGCN不同，GraphSAGE考虑邻域函数 N:∣Vg∣→2∣Vg∣\mathcal{N}:\left|\mathcal{V}_{g}\right| \rightarrow 2^{\left|\mathcal{V}_{g}\right|}N:∣Vg∣→2∣Vg∣ 将每个节点与给定图中的节点的任何（固定）子集相关联。在实践中，GraphSAGE可以对多个距离的节点进行采样并将其视为节点v的直接邻居。因此，该技术不是在本地学习，而是利用更广泛且异构的邻域，以潜在的性能提升来换取额外（但有界）的计算成本。
3.2、池化与CNN处理图像类似，可以定义图池化操作符来重新生成经过DGN层的图的维数。图池化主要用于三个目的，即在图中发现重要的群落，在已学习的表示中注入这些知识，以及在大规模结构中降低计算成本。池化机制可以分为两大类:自适应的和拓扑的。前者依赖于一种参数化的(因此是可训练的)池化机制。这种方法的一个显著的例子是DiffPool[120]，它使用一个参数化的神经层来学习基于当前节点在前一层的嵌入的聚类。这种聚类是通过一个DNGN层实现的，然后通过一个softmax获得一个软成员矩阵 Sℓ+1\mathrm{S}^{\ell+1}Sℓ+1 ，该软成员矩阵将节点与集群关联起来
Sℓ+1=softmax(GNN(Aℓ,Hℓ))
\mathbf{S}^{\ell+1}=\operatorname{softmax}\left(\operatorname{GNN}\left(\mathbf{A}^{\ell}, \mathbf{H}^{\ell}\right)\right)
Sℓ+1=softmax(GNN(Aℓ,Hℓ))
其中Aℓ\mathbf{A}^{\ell}Aℓ和Hℓ\mathbf{H}^{\ell}Hℓ是层 ℓ\ellℓ 的邻接和编码矩阵。然后，使用Sℓ+1\mathrm{S}^{\ell+1}Sℓ+1 矩阵将当前图形重新组合为（理想情况下）尺寸更小的图：
Hℓ+1=Sℓ+1Hℓ and Aℓ+1=Sℓ+1AℓSℓ+1(5)
\begin{aligned}
&\mathbf{H}^{\ell+1}=\mathbf{S}^{\ell+1} \mathbf{H}^{\ell} \quad \text { and } \quad \mathbf{A}^{\ell+1}=\mathbf{S}^{\ell+1} \mathbf{A}^{\ell} \mathbf{S}^{\ell+1}&&&&&&
&(5)
\end{aligned}
Hℓ+1=Sℓ+1Hℓ and Aℓ+1=Sℓ+1AℓSℓ+1(5)
在实践中，由于群集分配很容易保留可微性，因此其应用会产生密集的邻接矩阵。 TopKPool [37]通过学习投影矢量 pℓp^{\ell}pℓ 克服了这一限制，该投影矢量 p 用于使用点积来计算节点嵌入矩阵的投影得分，即
sℓ+1=Hℓpℓ+1∥pℓ+1∥−−−−−−(6)s^{\ell+1}=\frac{\mathbf{H}^{\ell} p^{\ell+1}}{\left\|p^{\ell+1}\right\|}------(6)sℓ+1=∥pℓ+1∥Hℓpℓ+1−−−−−−(6)
然后，使用这些分数来选择排名最高的节点的索引，并对原始图的矩阵进行切片，以仅保留与顶部节点相对应的条目。通过建立在投影分数上的门控机制，可以使节点选择变得不同。 SAGPool [62]通过使用GCN将得分向量计算为注意力得分来扩展TopKPool [59]。
sℓ+1=σ(GCN(Aℓ,Hℓ))−−−−−−(7)s^{\ell+1}=\sigma\left(\mathrm{GCN}\left(\mathbf{A}^{\ell}, \mathbf{H}^{\ell}\right)\right)------(7)sℓ+1=σ(GCN(Aℓ,Hℓ))−−−−−−(7)
EdgePool[33]从不同的角度进行操作，以边缘代替节点作为目标。边缘的排序基于一个参数评分函数,该函数输入入射节点的级联嵌入,也就是：
sℓ+1((v,u)∈Eg)=σ(wT[hvℓ,huℓ]+b)−−−−−−(8)s^{\ell+1}\left((v, u) \in \mathcal{E}_{g}\right)=\sigma\left(\mathbf{w}^{T}\left[\mathbf{h}_{v}^{\ell}, \mathbf{h}_{u}^{\ell}\right]+\mathbf{b}\right)------(8)sℓ+1((v,u)∈Eg)=σ(wT[hvℓ,huℓ]+b)−−−−−−(8)
然后将排名最高的边缘及其入射节点收缩到具有适当连接性的单个新节点中，并重复该过程。
另一方面，拓扑池是不自适应的，它通常会影响图本身的结构及其群落。注意，由于不是自适应的，这些机制不需要是可微的，它们的结果不依赖于任务。因此，这些方法可能在多任务场景中可重用。GRACLUS[22]是一种广泛使用的图形划分算法，它利用了一种有效的频谱聚类方法。有趣的是，GRACLUS不需要对邻接矩阵进行特征分解。从类似的角度来看，NMFPool[2]使用邻接矩阵的非负因数分解提供了一个软节点聚类。
图6:我们展示了一个用于图分类的池的例子。每个池化层通过将同一社区的节点聚类在一起使图粗化，使每个组成为粗化图的一个节点。如果我们将图简化为单个节点，我们可以将其解释为表示整个图的超源节点。此时，可以使用标准分类器输出一个图预测ygy_{g}yg。
池化方法也可以用来执行图分类，如图6所示。在实践中，通常在几个DNGN层之后应用池化操作，这样上下文信息就可以在图缩小之前扩散。
3.3 、用于图嵌入的节点聚合如果要执行的任务需要它，例如图分类，则可以汇总节点表示以生成全局图嵌入。再次，由于通常没有关于给定图的大小的假设成立，因此聚合需要是置换不变的。更正式地讲，在 ℓ\ellℓ 层的图嵌入表示可以按以下方式计算：
hgℓ=Ψ({f(hvℓ)∣v∈Vg})−−−−−−(9)\mathbf{h}_{g}^{\ell}=\Psi\left(\left\{f\left(\mathbf{h}_{v}^{\ell}\right) | v \in \mathcal{V}_{g}\right\}\right)------(9)hgℓ=Ψ({f(hvℓ)∣v∈Vg})−−−−−−(9)
常见的设置是将 fff 作为恒等函数，在所有元素的均值、总和、最大值。另一种更复杂的聚合方案借鉴了[123]的工作，其中定义了(多)集上的一组自适应置换不变函数。它将f作为应用到图中所有节点表示的神经网络来实现，Ψ\PsiΨ是元素求和，然后是最终的非线性变换。
对于下游任务，有多种方法可以利用不同层上的图嵌入。一种简单的方法是使用最后一层的图嵌入作为整个图的代表。更常见的情况是，将所有中间嵌入连接起来或作为输入提供给置换不变聚合器。[64]的工作提出了一种不同的策略，将所有的中间表示视为一个序列，该模型将最终的图嵌入作为长短时记忆(LSTM)[48]网络对该序列的输出。另一方面，SortPool[125]使用在所有层上获得的节点嵌入连接作为节点着色算法的连续等效，并使用它们来定义整个图上节点的字典顺序。然后选择最上面的有序节点，并将其作为一个序列提供给一维卷积层，该层计算聚合的图形编码。
3.4、总结在本节中，我们讨论了基于局部和迭代处理的DGN如何利用可用信息。特别是，我们展示了如何聚合邻居并考虑边缘信息。更高级的技术包括注意力，汇集（池化？）和采样，所有这些都可以出于不同的目的而引入。通过组合这些构件，我们可以开发可以扩散上下文信息的新图形处理方法。表1总结了一些代表性模型的邻域聚合方法。图7提供了一个可视示例，说明如何配置和组合不同的构建基块以构建可进行端到端训练的前馈或循环模型。
4、任务在介绍了生成节点和图表示的主要构建块和最常见的技术之后，我们现在讨论可以处理的不同学习任务。我们将重点介绍无监督、有监督、生成性和对抗性学习任务，对这一领域的研究进行全面综述。
4.1、无监督学习
图7：用于节点和图分类的两种可能的架构（前馈和递归）。在每一层内部，可以应用本节中介绍的注意力和采样技术。应用池化之后，就无法再执行节点分类，这就是为什么用于节点分类的潜在模型可以简单地组合图卷积层的原因。循环体系结构（底部）迭代地应用相同的邻域聚合，直到满足收敛标准为止。
我们的讨论从无监督的图形表示学习开始，因为其中定义的某些损失经常在有监督的生成任务中得到利用。本节的基本原理是提供一种直观的认识，即每一项损失都会对构建纯粹的无监督节点和图表示造成偏差。
链接预测链接预测链接预测。图神经网络使用的最常见的无监督损失是所谓的链接预测或重建损失。该学习目标旨在构建与弧相连的关联节点相似的节点表示，并且可用于链接预测任务。形式上，重构损失可定义为[59]
| Model | Neighborhood Aggregation hvℓ+1\mathbf{h}_{v}^{\ell+1}hvℓ+1 |
|---|---|
| NN4G [74] | σ(wℓ+1Txv+∑i=0ℓ∑ck∈C∑u∈Nvckwcki∗hui)\sigma\left(\mathbf{w}^{\ell+1^{T}} \mathbf{x}_{v}+\sum_{i=0}^{\ell} \sum_{c_{k} \in \mathcal{C}} \sum_{u \in \mathcal{N}_{v}^{c} k} w_{c_{k}}^{i} * \mathbf{h}_{u}^{i}\right)σ(wℓ+1Txv+∑i=0ℓ∑ck∈C∑u∈Nvckwcki∗hui) |
| GNN [89] | ∑u∈NvMLPℓ+1(xu,xv,auv,huℓ)\sum_{u \in \mathcal{N}_{v}} M L P^{\ell+1}\left(\mathbf{x}_{u}, \mathbf{x}_{v}, \mathbf{a}_{u v}, \mathbf{h}_{u}^{\ell}\right)∑u∈NvMLPℓ+1(xu,xv,auv,huℓ) |
| GraphESN [35] | σ(Wℓ+1xu+W^ℓ+1[hu1ℓ,…,huNvℓ])\sigma\left(\mathbf{W}^{\ell+1} \mathbf{x}_{u}+\hat{\mathbf{W}}^{\ell+1}\left[\mathbf{h}_{u_{1}}^{\ell}, \ldots, \mathbf{h}_{u_{\mathcal{N}_{v}}}^{\ell}\right]\right)σ(Wℓ+1xu+W^ℓ+1[hu1ℓ,…,huNvℓ]) |
| GCN [59] | σ(Wℓ+1∑u∈N(v)Lvuhuℓ)\sigma\left(\mathbf{W}^{\ell+1} \sum_{u \in \mathcal{N}(v)} \mathbf{L}_{v u} \mathbf{h}_{u}^{\ell}\right)σ(Wℓ+1∑u∈N(v)Lvuhuℓ) |
| GAT [102] | σ(∑u∈Nvαuvℓ+1∗Wℓ+1hu)\sigma\left(\sum_{u \in \mathcal{N}_{v}} \alpha_{u v}^{\ell+1} * \mathbf{W}^{\ell+1} \mathbf{h}_{u}\right)σ(∑u∈Nvαuvℓ+1∗Wℓ+1hu) |
| ECC [95] | 1 |
| R-GCN [90] | 2 |
| GraphSAGE [42] | 3 |
| CGMM [3] | 4 |
| GIN [113] | MLPℓ+1((1+ϵℓ+1)hvℓ+∑u∈Nvhuℓ)M L P^{\ell+1}\left(\left(1+\epsilon^{\ell+1}\right) \mathbf{h}_{v}^{\ell}+\sum_{u \in \mathcal{N}_{v}} \mathbf{h}_{u}^{\ell}\right)MLPℓ+1((1+ϵℓ+1)hvℓ+∑u∈Nvhuℓ) |
表1：我们报告了文献中存在的一些邻域聚合。在这里，方括号表示串联，并且 WWW，www 和 ϵ\epsilonϵ 是可学习的参数。请注意，GraphESN假定邻域的最大大小。 GAT的注意力机制由权重αuv\boldsymbol{\alpha}_{\boldsymbol{u} \boldsymbol{v}}αuv来实现，该权重取决于相关节点。至于GraphSAGE，我们描述了它的均值变体，尽管作者也提出了其他变体。最后，回想一下，ℓ\ellℓ 表示GNN[89]中的一个迭代步骤，而不是一个层。
Lrec(g)=∑(u,v)∥hv−hu∥2−−−−−−(10)\mathcal{L}_{r e c}(g)=\sum_{(u, v)}\left\|\mathbf{h}_{v}-\mathbf{h}_{u}\right\|^{2}------(10)Lrec(g)=(u,v)∑∥hv−hu∥2−−−−−−(10)
也存在这种损失的概率公式，它用于图形[58]的变分自动编码器，其中解码器只关注结构重建
P((u,v)∈Eg∣hu,hv)=σ(huThv)−−−−−−(11)
P\left((u, v) \in \mathcal{E}_{g} | \mathbf{h}_{u}, \mathbf{h}_{v}\right)=\sigma\left(\mathbf{h}_{u}^{T} \mathbf{h}_{v}\right)------(11)
P((u,v)∈Eg∣hu,hv)=σ(huThv)−−−−−−(11)
其中σσσ是sigmoid函数（范围在[0,1]）。
重要的是，链路预测损失反映了以下假设：相邻节点应与同一类别/社区相关联，这也被称为同形[69]。从这个意义上讲，这种无监督的损失可以看作是与其他有监督的损失函数组合的正则化器。在所有满足同构假设的任务中，我们希望该损失函数会有所帮助。
最大似然最大似然最大似然。当目标是构建反映相邻状态分布的无监督表示时，将采用不同的方法。在这种情况下，概率模型可能会有所帮助。的确，我们可以计算出节点u具有某个标签的可能性，这个标签是根据邻近的信息确定的。这种可能性可以通过已知的无监督概率学习方法最大化。CGMM[3]给出了这种损失的一个例子，CGMM[3]将深度网络构建为简单贝叶斯网络的堆栈。每一层使下列可能性最大化:
L(θ∣g)=∏u∈Vg∑i=1CP(yu∣Qu=i)P(Qu=i∣qNu)
\mathcal{L}(\theta | g)=\prod_{u \in \mathcal{V}_{g}} \sum_{i=1}^{C} P\left(y_{u} | Q_{u}=i\right) P\left(Q_{u}=i | \mathbf{q}_{\mathcal{N}_{u}}\right)
L(θ∣g)=u∈Vg∏i=1∑CP(yu∣Qu=i)P(Qu=i∣qNu)
其中 QuQ_{u}Qu 是与节点 uuu 关联的 CCC 状态的分类潜在变量，qNu\mathbf{q}_{\mathcal{N}_{u}}qNu是迄今为止计算的相邻状态集合。另一方面，有一些混合方法可以结合变分近似和DNGN来最大化难处理的可能性[83，58]。
互信息。另一种生成节点表示的方法侧重于图对之间的局部互信息最大化。特别是（DGI）[103]使用损坏函数来生成图 ggg 的失真版本，称为 gˉ\bar{g}gˉ。然后，训练一个鉴别器来区分这两个图，通过使用在节点和图表示上的双线性评分。这种无监督方法需要每次手动定义一个破坏函数，例如，在图中注入随机的结构噪声，因此它会对学习过程造成偏差。
池化的熵正则化池化的熵正则化池化的熵正则化。在使用自适应池方法时，鼓励模型将每个节点分配到单个社区是很有用的。实际上，自适应池可以很容易地将节点u的贡献分散到多个社区，这导致了信息量较低的社区。熵损失[120]就是为了解决这个问题而提出的。形式上，如果我们用S∈R∣Vg∣×C\mathbf{S} \in \mathbb{R}^{\left|\mathcal{V}_{g}\right| \times C}S∈R∣Vg∣×C定义软聚类分配矩阵(3.2节，其中C是池化层的聚类数，熵损失计算如下
Lent(g)=1∣Vg∣∑u∈VgH(Su)−−−−−−(13)
\mathcal{L}_{e n t}(g)=\frac{1}{\left|\mathcal{V}_{g}\right|} \sum_{u \in \mathcal{V}_{g}} H\left(\mathbf{S}_{u}\right)------(13)
Lent(g)=∣Vg∣1u∈Vg∑H(Su)−−−−−−(13)
其中 HHH 是熵，Su\mathbf{S}_{u}Su是与节点 uuu 群集分配关联的行。请注意，从实际的角度来看，设计一种不产生密集表示的可微分池方法仍然具有挑战性。但是，鼓励对节点进行一站式社区分配可以增强对所学集群的视觉解释，并且它可以充当强制实施良好分隔的社区的规则化器。
将监督图学习任务分为节点学习任务、图分类学习任务和图回归学习任务。一旦学习了节点或图的表示，预测步骤就与标准的向量机器学习没有区别，常见的损失函数是分类的交叉熵/负对数似然和回归的均方误差。
节点分类节点分类节点分类。正如术语所示，节点分类的目标是为图中的每个节点分配正确的目标标签。可以有两种不同的设置:归纳节点分类(包括对属于未见图的节点进行分类)和转换节点分类(只需要学习一个图，并且只需要对一小部分节点进行分类)。需要注意的是，节点分类的基准测试结果受到了实验设置的严重影响;这个问题后来在严格的设置下通过重新评估最先进的体系结构得到了解决[93]。
图分类/回归图分类/回归图分类/回归 。要解决图分类和回归任务，首先必须应用24节3.3中讨论的节点聚合技术。获得单个图形表示后，可以通过标准的机器学习技术直接进行分类或回归。与节点分类类似，图分类字段遭受模棱两可，不可复制和有缺陷的实验程序的困扰，这在研究界引起了极大的混乱。然而，最近，已经提出了对一致数量的数据集[25]进行最新模型的严格重新评估，旨在抵消这一令人担忧的趋势。
4.3、生成学习与以前的任务相比，学习如何从可用的样本数据集生成图形无疑是一项更复杂的工作。要对图g进行采样，必须能够访问底层的生成分布P(g)P_{(g)}P(g)。然而，由于图形结构是离散的、组合的和可变大小的，基于梯度的方法来学习数据的边际概率就不那么适用了。因此，生成过程取决于一个图形或一组节点的潜在表示，从这个潜在代表中可以解码实际的结构。现在我们介绍两种最流行的DGGNs解码图潜在样本的方法，如图8所示。为了便于理解，我们将重点讨论具有非属性节点和边的图。最重要的是，我们假定我们知道正确的采样技术;稍后，我们将讨论如何学习这些抽样机制。
图级解码图级解码图级解码。这些方法一次性采样图邻接矩阵。更详细地,解码器以图表示作为输入,输出一个密集的概率邻接矩阵A~∈Rk×k\tilde{\mathbf{A}} \in \mathbb{R}^{k \times k}A~∈Rk×k， 其中 kkk 是允许的最大节点数，每个条目 a~ij\tilde{a}_{i j}a~ij 指定观察节点 iii 和 jjj 之间的弧的概率。这对应于最小化以下对数似然：
Ldecoder (g)=−logP(A~∣h~g)−−−−−−(14) \mathcal{L}_{\text {decoder }}(g)=-\log P\left(\tilde{\mathbf{A}} | \tilde{\mathbf{h}}_{g}\right)------(14) Ldecoder (g)=−logP(A~∣h~g)−−−−−−(14)
图8:显示了图级(顶行(上边的))和节点级(底行（下边的额）)生成解码器的简化模式。箭头上的波浪符号表示采样。虚线箭头表示相应的采样过程一般是不可微的。蓝色的阴影表示可能性更高。
其中P(A~∣h~g)=MLP(h~g)P\left(\tilde{\mathbf{A}} | \tilde{\mathbf{h}}_{g}\right)=\operatorname{MLP}\left(\tilde{\mathbf{h}}_{g}\right)P(A~∣h~g)=MLP(h~g) ，这里的 h~g\tilde{\mathbf{h}}_{g}h~g是采样图表示。要获得新的图形，可以执行以下任一操作：
1.用连接概率a~ij\tilde{a}_{i j}a~ij对概率邻接矩阵的每个条目进行抽样； 2.如[96，60]中所示，在概率矩阵和基本事实矩阵之间执行近似图匹配； 3.通过使用Gumbel-Softmax [51]进行分类重新参数化，使采样过程变得可微，例如在[20]中探讨的那样。注意，前两个选项是不可微的;在这种情况下，实际的重建损失不能在训练期间反向传播。因此，重构损失是在概率矩阵上计算的，而不是在实际矩阵上计算[96]。图级解码器不是置换不变的(除非使用近似的图匹配)，因为输出矩阵的顺序假设是固定的
节点级解码节点级解码节点级解码。节点级解码器从一组k个节点表示形式开始生成图。根据它们的概率分布的近似值对它们进行采样。为了在该设置下解码图，需要26生成以采样节点集为条件的邻接矩阵。这是通过将所有可能的k(k + 1)/2无序节点对作为输入引入解码器来实现的，用来优化以下的对数似然。
Ldecoder(g)=−1∣Vg∣∑v∈Vg∑u∈VglogP(a~uv∣h~v,h~u)
\mathcal{L}_{\mathrm{decoder}}(g)=-\frac{1}{\left|\mathcal{V}_{g}\right|} \sum_{v \in V_{g}} \sum_{u \in \mathcal{V}_{g}} \log P\left(\tilde{a}_{u v} | \tilde{\mathbf{h}}_{v}, \tilde{\mathbf{h}}_{u}\right)
Ldecoder(g)=−∣Vg∣1v∈Vg∑u∈Vg∑logP(a~uv∣h~v,h~u)
其中P(a~uv∣h~v,h~u)=σ(h~vTh~u)P\left(\tilde{a}_{u v} | \tilde{\mathbf{h}}_{v}, \tilde{\mathbf{h}}_{u}\right)=\sigma\left(\tilde{\mathbf{h}}_{v}^{T} \tilde{\mathbf{h}}_{u}\right)P(a~uv∣h~v,h~u)=σ(h~vTh~u)和等式11中的一样，并且类似于[58、41]和 h~\tilde{\mathbf{h}}h~ 是采样节点表示。与图级解码相反，此方法是置换不变的，尽管通常计算比单次邻接矩阵生成更昂贵。
为了补充我们的讨论，下面，我们总结那些生成模型，这些模型可以优化解码目标，同时共同学习如何对潜在表示空间进行采样。我们将那些显式学习其（可能是近似的）概率分布的方法与那些隐式学习如何从该分布中进行采样的方法区分开来。前者基于生成自动编码器（AE）[57，100]，而后者则利用生成对抗网络（GAN）[39]。
生成式自动编码器生成式自动编码器生成式自动编码器。图的生成AE通过学习潜在空间中节点（或图）表示的概率分布来工作。然后将这种分布的样本提供给解码器以生成新的图。通过生成式AE对图进行优化的损失函数的一般公式如下：
LAE(g)=Ldecoder(g)+Lencoder(g)−−−−−−(16)
\mathcal{L}_{\mathrm{AE}}(g)=\mathcal{L}_{\mathrm{decoder}}(g)+\mathcal{L}_{\mathrm{encoder}}(g)------(16)
LAE(g)=Ldecoder(g)+Lencoder(g)−−−−−−(16)
其中 Ldecoder \mathcal{L}_{\text {decoder }}Ldecoder 如上所述，是解码器的重构误差，Lencoder\mathcal{L}_{encoder}Lencoder是一种发散度量，它迫使潜伏空间中的点分布类似于“易处理的”先验值（通常是各向同性的高斯N(0,I)\mathcal{N}(\mathbf{0}, \mathbf{I})N(0,I)）。例如，基于变分AE的模型[57]使用以下编码器损耗：
Lencoder (g)=−DKL[N(μ,σ2)∥N(0,I)]−−−−−−(17)
\mathcal{L}_{\text {encoder }}(g)=-D_{K L}\left[\mathcal{N}\left(\boldsymbol{\mu}, \boldsymbol{\sigma}^{2}\right) \| \mathcal{N}(\mathbf{0}, \mathbf{I})\right]------(17)
Lencoder (g)=−DKL[N(μ,σ2)∥N(0,I)]−−−−−−(17)
其中DKLD_{K L}DKL是Kullback-Leibler散度，编码分布的两个参数计算为μ=DGNμ(A,X)\boldsymbol{\mu}=\mathrm{DGN}_{\mu}(\mathbf{A}, \mathbf{X})μ=DGNμ(A,X) 和 σ=DGNσ(A,X)\boldsymbol{\sigma}=\mathrm{D} \mathrm{GN}_{\sigma}(\mathbf{A}, \mathbf{X})σ=DGNσ(A,X)[96，66，87]。诸如[14]等更新的方法建议用相应的Wasserstrain AE [100]项代替AE损失中的编码器误差项。
生成对抗网络。基于GAN的方法特别方便，因为它们不能直接与P（g）一起使用，而只能学习一种自适应机制来从中采样。 GAN使用两种不同的功能：生成器G（生成新的图）和鉴别器D，经过训练以识别其输入是来自生成器还是来自数据集。生成器和鉴别器都经过共同训练，以最大程度地最小化以下目标：
LGAN(g)=minGmaxDEg∼Pdata (g)[logD(g)]+Ez∼P(z)[log(1−D(G(z)))]−−−−−−(18)
\mathcal{L}_{\mathrm{GAN}}(g)=\min _{G} \max _{D} \mathbb{E}_{g \sim P_{\text {data }}(g)}[\log D(g)]+\mathbb{E}_{\mathbf{z} \sim P(\mathbf{z})}[\log (1-D(G(\mathbf{z})))]------(18)
LGAN(g)=GminDmaxEg∼Pdata (g)[logD(g)]+Ez∼P(z)[log(1−D(G(z)))]−−−−−−(18)
其中Pdata P_{\text {data }}Pdata 为数据的真实未知概率分布，P(z)P(z)P(z) 为潜在空间上的先验分布(通常为各向同性(等向性)高斯分布或均匀分布)。注意，这个过程提供了一种隐式的方法来从感兴趣的概率分布中取样，而不直接操作它。在图生成的情况下，GGG 可以是一个图或节点级解码器，它以潜在空间中的一个随机点作为输入，生成一个图，而 DDD 以一个图作为输入并且生成一个伪图的概率取决于生成器。例如，[27]将 GGG 实现为一个图形级解码器，该解码器同时输出一个概率邻接矩阵 A~\tilde{\mathbf{A}}A~ 和一个节点标签矩阵L~\tilde{\mathbf{L}}L~。鉴别器以邻接矩阵 AAA 和节点标号矩阵 LLL 为输入，对其应用Jumping Knowledge Network(跳跃知识网络)[114]，判断图数据是来自生成器还是来自MLP数据集。相反，[107]在节点级工作。具体地说,具体而言，GGG 生成结构感知的节点表示（基于从训练集中采样的随机图的BFS树的连通性），而鉴别器将两个节点表示作为输入，并确定它们是否来自训练集或生成器，优化类似于方程式15的目标函数。
表2:根据我们到目前为止所讨论的内容，我们在这里概述DGNs的主要特性。为了清楚起见，“−”“-”“−”意味着不适用，因为该模型是一个依赖于任何通用学习方法的框架。Layers列描述了一个架构使用了多少个层，这些层可以是一个固定的数字，或者由学习过程自适应地决定。另一方面，“上下文”指的是特定层的上下文扩散方法，如2.5节所述。
在本节的最后，我们将根据到目前为止讨论的构建块和任务提供一些局部迭代模型的特征。具体来说，表2针对四个关键属性对模型进行了区分:上下文扩散方法、如何计算嵌入、如何构造层以及方法的性质。然后，我们添加了模型可能具有或不具有的其他属性，例如处理边缘、执行池化、参与邻居和对邻居进行采样的能力。
5. 总结其他方法和要求有许多方法和主题在前面几节讨论的分类法中没有涉及。我们特别关注图的深度学习方法，这些方法大多基于局部和迭代处理。为了完整的阐述，我们现在简要回顾一些被排除在外的主题。
5.1. Kernels关于应用于图的内核方法有一个长期的和统一的研究路线[94,84,115,31,104]。核被非正式地定义为正定函数的一种广义形式，它计算输入对之间的相似度得分。内核方法的一个重要方面是，它们通常是非局部的、非自适应的，也就是说，它们会影响到图的应用。，它们需要人来设计核函数。当应用于图数据时，当已知感兴趣的属性时，内核方法工作得特别好，但是使用自适应方法仍然很难更好地执行。然而，如上所述，不自适应是内核的主要缺点，因为我们并不总是清楚我们想从图中提取哪些特性。此外，当数据集中的输入数量过大时(尽管有一些例外，参见[94])，内核会遇到可伸缩性问题。将核相似矩阵与支持向量机[19]相结合进行图分类。
5.2. Spectral methods（谱方法）频谱图理论通过相关的邻接关系和拉普拉斯矩阵研究图的性质。这些技术可以解决许多机器学习问题，例如拉普拉斯平滑[86]，图半监督学习[81，17]和频谱聚类[105]。图还可以使用信号处理工具进行分析，例如图傅立叶变换[46]和相关的自适应技术[16]。一般而言，光谱技术旨在基于相同形状的图，因为它们基于邻接和拉普拉斯矩阵的特征分解。但是，存在从节点数抽象的多项式逼近，GCN模型[59]就是这样一个例子。
5.3、随机游走为了捕获图的局部和全局特性，经常使用随机游走创建节点嵌入，并且已经对其进行了长时间的研究[67，104，85，50]。简单地将随机游走定义为连接图中两个节点的随机路径。根据可到达的节点，我们可以设计不同的框架来学习节点表示：例如，Node2Vec [40]通过使
