转载 LemonQC
翻译 见 1
论文 A Gentle Introduction to Deep Learning for Graphs
作者：Davide Bacciua, Federico Erricaa, Alessio Michelia, Marco Poddaa意大利比萨大学计算机科学系
文章主要讲解的是深度学习在图领域的应用，倾向于对主要概念和架构的一致性和渐进性介绍。
结构化信息，采用基于局部和迭代的泛化的图表示学习方法。主要介绍了大图、局部关系和信息的迭代处理、语境扩散的三种机制
基本的图神经块构建。该章主要关注的点是局部图学习模型，作者指出并非是给出规划最全面和通用的模型公式，而是对各个组件进行详细讲解，以及这些组件如何高效组成图学习模型。故本章主要包含三个方面的主要内容：邻居节点聚集=卷积（aggregation）、池化（Pooling）及图嵌入的节点聚集，
方法分类，有监督、无监督、生成+ 其他方法：核方法、谱方法、随机游走、对坑、顺序生成
介绍了目前领域中的仍然存在的一些研究挑战（边信息引入、超图、动态图、偏差和方差权衡）和普遍性应用（1.化学和生物制药设计2.社交网络分析。3.自然语言处理。4.安防问题。5.时空预测。6.推荐系统）。
目录
引言：
摘要：
1、Introduction：
2、High-level Overview
2.1 符号描述
2.2 动机
2.3 大图
2.4 局部关系和信息的迭代处理
2.5 语境扩散的三种机制
3、Building Blocks
3.1 邻居聚合（卷积+注意力+采样）
3.2 池化
3.3 用于图嵌入的节点聚合
4、任务
4.1 无监督（连接预测-概率->贝叶斯-最大似然）
4.2 监督
4.3 生成
4.4 总结
5、其他方法及任务的总结
5.1. Kernels（核方法）
5.2. Spectral methods（谱方法）
5.3、随机游走
5.4、图的对抗训练和攻击
5.5、图的顺序生成模型
6、挑战和研究途径
6.1. Time-evolving graphs（随着时间变化的图）
6.2. Bias-variance trade-offs（偏差方差的权衡）
6.3. A sensible use of edge information（合理使用边缘信息）
6.4、超图学习
7、应用
7.1、化学与药物设计
7.2、社交网络
7.3. Natural Language Processing
7.4. Security
7.5. Spatio-temporal forecasting（时空预测）
7.6. Recommender Systems
8、总结
引言：
最近阅读了一篇2020新的综述，作者对其相对较新的图神经网络相关文献进行总结。该文章作为一个入门级教程还是比较好的，其模型的定义，经典算法的讲解和之前没什么实质性差别，但是其自上往下的讲解还是很明确。
摘要：作者首先提出自适应的图数据的处理是一个仍需要研究的过程。其次，指出该文章主要讲解的是深度学习在图领域的应用，倾向于对主要概念和架构的一致性和渐进性介绍。然后，引出该文章的自上往下的架构。介绍了一个针对于结构化信息，采用基于局部和迭代的泛化的图表示学习方法。接着引入了基本的图神经块构建。最后，介绍了目前领域中的仍然存在的一些研究挑战和普遍性应用。
1、Introduction：图作为一种可以有效的表示外部世界的工具，可以表示有不同的人工或者自然过程产生的数据。此外也可以表示多维的数据关系，如离散关系类型，化学属性和分子键等。丰富的数据及其内容的不断增加，带来了以下三个方面的挑战：①图模型应该可以处理异构图（不同尺寸和不同拓扑）；②图都是离散数据，在诸如差分性、组合性质上存在很多限制（这对可微性有一定的限制，而图的组合性质又阻碍了穷举搜索方法的应用）；③最通用的图允许表示回环，存在无法并行性，增肌计算复杂难度。这是消息传递和节点访问的复杂性来源。
换句话说，处理图形数据在表现形式和计算复杂度方面，以及在矢量数据学习方面，都带来了前所未有的挑战。因此，这是一个很好的开发和测试新的神经网络方法的领域。
接着作者对循环神经网络的一些框架进行介绍，如RecNN用以处理树结构化数据（即起源于90年代初，涉及树状结构数据的递归神经网络（RecNN）的开创性工作（请参阅[ [98、32、9]及其中的参考文献）），随着新方法的提出，这些结构的递归处理也被用以概率的方法。递归模型的主要思想是：一个可以穿过结构来计算他的嵌入的状态过渡系统。将这种方法扩展到一般图(循环/非循环、有向/无向)的主要问题是循环的处理，因为在神经递归单元中定义的状态变量之间存在相互依赖关系。最早解决这个问题的模型是前馈方法Graph Neural Network (GNN)[89]和Neural Network for Graphs (NN4G)[74]
作者在文中最后指出，这篇文章是作为一个入门的tutorial文章，旨在循序渐进、了解主要的概念。此外，作者介绍了其三方面的motivation：①图表示深度学习虽然paper活相关文献激增，然而存在重新发现已知结果和模型的风险；②研究者开始在模型评估问题上采用更有原则的方式；③survey paper缺乏细致的讲解。
文章的组织结构：第二章引入贯穿全文的基础内容，包含数学表达、泛化的表示、基本结构等等（首先提供了图形表示学习问题的一个通用公式，介绍并激发了我们将在本文其余部分中遵循的体系结构路线图。我们将特别关注处理信息的局部和迭代处理的方法，因为这些方法更符合神经网络的操作机制。在这方面，我们将较少关注基于谱图方法的全局方法(即假设单个固定邻接矩阵）；第三章介绍了最基本的构建块，引入图卷积的概念。在第四章，作者介绍了图表示学习的主要学习任务。第五章介绍了相关survey（即related work）。第六、七章分别介绍了研究挑战和应用。最后提出了一些未来的研究点。
2、High-level Overview在这一章，作者主要对图深度学习进行概览，首先，对必要的数学符号进行总计；其次讨论了研究动机，并提出一些paper中主要的思想。为方便整体了解文章脉络，依然采用思维导图，如图1。
图1 high-level overview
本章从最基本的数学表示开始，对整个深度图表示学习网络框架做了一个总体性概述，总体评价还是很好理解和记忆的。
2.1 符号描述
2.2 动机
由于模型能够自动地从原始数据中提取相关特征来解决问题，因此表示学习在研究领域引起了广泛的兴趣。在这方面，卷积神经网络[61]可能是这种平面数据方法的最佳代表。由于结构化域允许表示比平面数据更清晰的信息，因此考虑实体之间的现有关系至关重要。换句话说，需要对结构进行自适应处理才能最大限度地利用这些附加信息。注意，在图的特定情况下，不能对图的大小或拓扑结构做出任何假设;因此，为了确保它们的普遍适用性，图数据处理方法必须在没有已知的和固定的因果关系的情况下设计，该机制允许施加适当的顺序来处理图形组件)。
自适应就是在处理和分析过程中，根据处理数据的数据特征自动调整处理方法、处理顺序、处理参数、边界条件或约束条件，使其与所处理数据的统计分布特征、结构特征相适应，以取得最佳的处理效果的过程。自适应过程是一个不断逼近目标的过程，它所遵循的途径以数学模型表示，称为自适应算法。通常采用基于梯度的算法，其中最小均方误差算法(即LMS算法)尤为常用。
2.3 大图不管我们关心的训练目标是什么，几乎所有用于图的深度学习方法最终都会产生节点表示（状态）
。在[32]中，这个过程被称为执行图的同构转换。这些表示是并行访问图节点的结果;也就是说，在没有任何特定节点或划分的情况下遍历图。图2所示的整体机制非常有用，因为它允许处理节点、边和图相关的任务;例如，图7表示可以很容易地通过将其节点表示聚合在一起来计算。因此，研究人员和实践者的工作围绕着从图中自动提取相关特征的深度学习模型的定义展开。在本教程中，我们将这些模型称为深图网络(DGNs)。一方面，这个通用术语的目的是消除术语图神经网络(Graph Neural Net- work, GNN)和图卷积网络(Graph Convolutional Network, GCN)之间的歧义，图神经网络(Graph Neural Net- work, GNN)指的是[89]，而图卷积网络(Graph Convolutional Network, GCN)指的是[59]。
为了进一步阐明我们对术语的使用，这里DGN指的是产生最终内部节点表示
的体系结构的子集。可以通过将每一层计算得到的所有内部表示连接起来（进行级联），也可以通过获取最后一层生成的内部表示来获得。因此，术语DGN不包括全局节点聚合机制，也不包括最终分类器或回归器。通过这种方式，我们在体系结构上保持了一个模块化的视图，并且我们可以将任何DGN与一个通过使用最终的内部节点表示作为输入来解决任务的预测器相结合。
我们将DGNs分为三类:深度神经图网络(DNGNs)，其中包括受神经结构启发的模型;以图的概率模型为代表的深度贝叶斯图网络;还有深度生成图网络(DGGNs)，它包括利用神经模型和概率模型的图的生成方法。这种分类法绝不是方法的严格划分;实际上，我们在本教程中所关注的所有方法都是基于局部关系和迭代处理来将节点上下文分散到整个图中，而不考虑它们的神经或概率性质。
从任意图的总体中学习提出了两个基本问题:第一，对一般图的拓扑结构不作任何假设;第二，结构可能包含循环。现在我们讨论这两点，重点介绍文献中采用的最常见的解决方案。
具有可变拓扑的图。首先，我们需要一种无缝处理大小和形状均变化的图形信息的方法。在文献中，这已经通过构建在节点级别而不是图级别本地工作的模型来解决[98]。换句话说，模型只关心节点及其附近的关系。这回想起卷积模型中图像的局部处理，在该模型中，焦点集中在单个像素及其有限邻居（无论如何定义）上。这种平稳性假设可以极大地减少模型所需的参数数量，因为它们可在所有节点上重复使用（类似于卷积滤波器在像素上的重复使用方式）。此外，它有效且高效地结合了数据集中所有节点和图形的“经验”，以学习单个功能。同时，平稳性假设要求引入一些机制，这些机制也可以从图的全局结构中学习，我们将在下一节中讨论这些机制。
尽管有这些优点，但仅进行局部处理并不能解决可变邻域形状的图的问题。在非位置图的情况下会出现此问题，在这种情况下，没有一致的方式来排序邻域中的节点。在这种情况下，一种常见的解决方案是使用对每个节点的邻居集起作用的置换不变函数。
图包含循环。图的自适应局部处理意味着任何节点的中间状态都是其邻居状态的函数。因此，如果一个图包含一个循环，则需要处理节点状态之间的相互因果关系。解决这个问题的方法是假设一个迭代方案，即
是通过在上一次迭代中计算出的邻居状态定义的。这样，我们就可以近似出属于一个循环的节点之间的相互依赖关系。正如我们将看到的，这样的迭代定义可以很好地并入深层架构。
本节介绍了上下文扩散，它可以说是局部图学习方法中最重要的概念。顾名思义，上下文扩散的目标是在整个图上传播信息。在更广泛环境中为节点提供与其有关的知识，而不是仅限于其直接邻域。这对于节点的更好的表达是很有必要的。
根据不同的上下文扩散机制，我们可以将大多数深度图学习模型划分为递归、前馈和构造方法。我们现在讨论它们是如何工作的以及它们之间的区别。
循环架构。该系列模型将节点信息的迭代处理实现为动态系统。这个家族中最受欢迎的两个代表是图神经网络[89]和图回波状态网络[35]。两种方法都依赖于施加收缩动力学来确保迭代过程的收敛。前者在（监督的）损失函数中施加了这样的约束，而后者则从（未经训练的）储层动力学的收缩性继承了收敛性。门控图神经网络[63]是循环体系结构的另一个示例，与[89]不同，迭代次数是先验固定的，无论是否达到收敛。在[69]中引入了一种基于集体推理的迭代方法，该方法不依赖任何特定的收敛标准。这一系列模型通过建模节点状态相互依存关系，以迭代的方式来处理图循环。在这些情况下，我们可以将图4的符号 ℓ 解释为递归状态转换函数的“迭代步骤”，用来计算每一个节点的状态。
前馈架构。与递归模型不同的是，前馈模型没有利用递归单元在同一层上的迭代扩散机制，而是将多层叠加起来，以构成每一步学习的局部上下文。结果，由循环引起的相互依赖通过不同的参数化层进行管理，不需要约束来确保编码过程的收敛。为了与图4进行对比(这里对应的是一个层的索引)，这种组合性会影响每个节点的上下文，上下文随着网络深度的增加而增加，直到包含整个图[74]。
毫不奇怪，这种上下文扩散与CNNs的局部接受域有密切的相似性，这种相似性随着架构中添加更多层而增加。CNNs的不同之处在于，图没有固定的结构，因为邻居的大小可能不同，而且很少给出节点排序。特别是CNNs的局部接受域可以看作是图数据中一个节点的上下文，而平面数据上的卷积算子则回忆起图数据中节点的无序并行访问(即使参数化技术不同)。这就是图卷积层这一术语在文献中经常使用的原因。前馈模型系列因其简单、高效、适用于多种不同的任务而广受欢迎。但是，图的深层网络与其他深层神经网络同样面临与梯度相关的问题，尤其是与整个架构中的“端到端”学习过程相关时。
建设性架构。我们确定的最后一个族可以看作是前馈模型的特例，其中的训练是逐层进行的。建设性架构的主要好处是，深层网络不会因设计而导致消失/爆炸梯度问题，因此上下文可以更有效的在节点之间传播。在有监督的情况下，这种构造技术甚至可以自动确定完成一项任务所需的层数[26,72]。就像在图4中解释的那样，在图形模型中，该特性也与当前问题所需的上下文相关，因此，无需先验确定它，如[74]所示，其中层的深度和上下文形状已得到正式证明。此外，建设性模型的一个重要特征是它们以“分而治之”的方式解决问题，将任务逐步拆分为更简单的子任务（从而放宽了“端到端”方法）。每一层都有助于解决子问题，随后的层使用此结果逐步解决全局任务。在这些建设性的方法中，我们提到了图数据的神经网络(NN4G)74，而最近的一种概率变体是上下文图数据马尔科夫模型(CGMM)[3]。
3、Building Blocks该章主要关注的点是局部图学习模型，作者指出并非是给出规划最全面和通用的模型公式，而是对各个组件进行详细讲解，以及这些组件如何高效组成图学习模型。故本章主要包含三个方面的主要内容：邻居节点聚集（aggregation）、池化（Pooling）及图嵌入的节点聚集，思维导图如下图2：
图2 building blocks
在这一章中，作者主要讨论了DGN如何通过基于局部和迭代处理数据的获取图中有用的信息。此外也介绍了注意力机制、池化和采样机制以及他们所实现的效果。通过将这些机制块组合起来我们可以设计很多新的图处理模型。
3.1 邻居聚合（卷积+注意力+采样）
3.2 池化
3.3 用于图嵌入的节点聚合
4、任务
在这一章，作者主要对监督的、非监督、生成式和对抗学习任务进行综合的概述。思维导图如下图3。
图3 tasks
4.1 无监督（连接预测-概率->贝叶斯-最大似然）
图7：用于节点和图分类的两种可能的架构（前馈和递归）。在每一层内部，可以应用本节中介绍的注意力和采样技术。应用池化之后，就无法再执行节点分类，这就是为什么用于节点分类的潜在模型可以简单地组合图卷积层的原因。循环体系结构（底部）迭代地应用相同的邻域聚合，直到满足收敛标准为止。
4.2 监督
4.4 总结
在本节的最后，我们将根据到目前为止讨论的构建块和任务提供一些局部迭代模型的特征。具体来说，表2针对四个关键属性对模型进行了区分:上下文扩散方法、如何计算嵌入、如何构造层以及方法的性质。然后，我们添加了模型可能具有或不具有的其他属性，例如处理边缘、执行池化、参与邻居和对邻居进行采样的能力。
5、其他方法及任务的总结
该章主要引入了一些传统的经典算法，如核方法、谱方法、随机游走，对抗训练和攻击及序列化生成模型等。
图4 methods
在我所阅读过文献中，关于图分类相关的问题，大部分还是以谱方法和池化方法为主，从而和kernel方法及相关算法进行对比。
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]通过使用随机游走来探索图，从而根据给定的环境最大化了节点的可能性。此外，在深度优先搜索比广度优先搜索更可取的情况下，可学习的参数指导行走的偏向。类似地，DeepWalk [82]通过将随机游走建模为句子并最大化似然目标来学习连续的节点表示。最近，随机游走也已用于生成图[12]，并且已经探索了GCN的上下文信息传播与随机游走之间的形式联系[114]。
5.4、图的对抗训练和攻击考虑到使用图数据结构的实际应用的重要性，最近人们对研究DGNs对恶意攻击的鲁棒性越来越感兴趣。对抗性训练这个术语是在深层神经网络的背景下使用的，它用于识别基于输入扰动的模型的正则化策略。关键是要让网络对[10]的攻击具有弹性。最近，神经DGNs也被证明有对抗攻击的倾向[131]，而使用对抗训练进行正规化是相对较新的[28]。对抗性训练的目标函数被表述为一个最小化对抗性例子的有害影响的最大博弈。简单地说，模型是用来自训练集的原始图和对抗性图进行训练的。使一个图具有对抗性的扰动的例子包括弧的插入和删除[117]或向节点表示[54]添加对抗性噪声。对抗性图是根据其在数据集中最接近的匹配程度进行标记的，以保持损失函数空间的平滑性，并在存在扰动图的情况下保持模型的预测能力。
5.5、图的顺序生成模型生成图的另一个可行选择是将生成过程建模为一系列动作。事实证明，这种方法能够概括来自非常不同的训练分布的图形。但是，它依赖于图节点的固定顺序。文献[65]中的方法是一种开创性的方法，其中图的生成被建模为决策过程。具体来说，共同训练一堆神经网络，以了解是否要添加新节点，是否要添加新边缘以及要关注下一个迭代的节点。另一个有趣的工作是[121]，其中将生成公式化为自回归过程，其中将节点顺序添加到现有图。每次添加新节点时，节点级别的门控循环单元（GRU）网络都会预测其相对于现有节点的邻接矢量。同时，图级GRU网络跟踪整个图的状态，以调节邻接矢量的生成。最后，[5，4]通过学习使用两个GRU网络预测图的有序边集来对生成任务进行建模。第一个生成边缘的第一个端点，而第二个则根据这些信息预测缺失的端点。
6、挑战和研究途径在该章作者介绍了一些没有被广泛研究的问题。主要包含：时卷积图、偏置方差的权衡问题、边信息的挖掘应用及超图学习（hypergraph）。
6.1. Time-evolving graphs（随着时间变化的图）在时卷积中，缺乏大量的数据集，尤其是非合成的数据。
6.2. Bias-variance trade-offs（偏差方差的权衡）在偏置方差权衡中，需要根据结构区分能力来辨别结点的聚合技术，一个DGN需要有能力针对特定的应用去选择合适的模型
第3.1节中描述的不同节点聚合机制在确定模型可以区分的结构类型方面起着至关重要的作用。例如，已经证明[113]，GIN在理论上与图同构的1维Weisfeiler Lehman测试一样强大。结果，GIN模型能够适合它所应用的大多数数据集。尽管该模型非常灵活，但要学习一个泛化效果好的函数可能会很困难：这是通常的偏差-方差折衷的结果[34]。因此，需要根据结构区分能力来表征所有节点聚合技术。 DGN的更原则性定义对于能够为特定应用选择正确的模型至关重要。
6.3. A sensible use of edge information（合理使用边缘信息）在边信息的挖掘中，是否可以采用上下文扩散技术，设计的网络模型是否可以挖掘边信息。
在信息源方面，边缘通常被视为二等公民。实际上，大多数处理附加边缘特征的模型[74、95、3、90]都会计算加权聚合，其中权重是通过对边缘信息进行适当的转换来给出的。但是，还有一些有趣的问题尚未得到回答。例如，将上下文扩展技术应用于边缘是否合理？这种方法的优点仍然不清楚。此外，表征利用边缘信息的方法的辨别力将是有趣的。
6.4、超图学习超图，作为图的一种推广，其中边包含两个及两个节点。这个缺口比较大。甚至方法比较难以评估。
超图是图的一般化（泛化），其中边连接到的是节点的子集，而不仅仅是连接两个节点。最近已经出版了一些有关从超图学习的著作[129，128，29，53]，而最新的著作则从图的局部和迭代处理中获得启发。像时间演变图一样，基准数据集的稀缺可用性使得难以凭经验评估这些方法。
7、应用该章主要讲述了图相关方面的应用，和前面几篇综述讲解的相差无几，这里仅仅对其进行简单概括。包含四个方面的内容：1.化学和生物制药设计2.社交网络分析。3.自然语言处理。4.安防问题。5.时空预测。6.推荐系统。同学们感兴趣的可以针对其中的某项进行研究。
7.1、化学与药物设计
7.2、社交网络
7.3. Natural Language Processing
7.4. Security
7.5. Spatio-temporal forecasting（时空预测）
7.6. Recommender Systems
作者在文章最后，也介绍几个研究所应用的框架，如pytorch geometrics，dgl等，也是希望为大家作为一个了解图深度学习的入门。
参考
https://zhuanlan.zhihu.com/p/90963988
