Graph Neural Networks: A Review of Methods and Applications学习笔记_learning graph distances with message passing neur

 

Abstract

Lots of learning tasks require dealing with graph data which contains rich relation information among elements. Modeling physics system, learning molecular fingerprints, predicting protein interface, and classifying diseases require that a model learns from graph inputs. In other domains such as learning from non-structural data like texts and images, reasoning on extracted structures, like the dependency tree of sentences and the scene graph of images, is an important research topic which also needs graph reasoning models. Graph neural networks (GNNs) are connectionist models that capture the dependence of graphs via message passing between the nodes of graphs. Unlike standard neural networks, graph neural networks retain a state that can represent information from its neighborhood with arbitrary depth. Although the primitive GNNs have been found difficult to train for a fixed point, recent advances in network architectures, optimization techniques, and parallel computation have enabled successful learning with them. In recent years, systems based on graph convolutional network (GCN) and gated graph neural network (GGNN) have demonstrated ground-breaking performance on many tasks mentioned above. In this survey, we provide a detailed review over existing graph neural network models, systematically categorize the applications, and propose four open problems for future research.

许多学习任务都需要处理包含丰富元素间关系信息的图数据。物理系统的建模、分子指纹的学习、蛋白质界面的预测以及疾病的分类都要求模型从图形输入中学习。在从文本、图像等非结构数据学习等领域，对提取出来的结构进行推理，如句子的依赖树、图像的场景图等，是一个重要的研究课题，也需要图形推理模型。图神经网络(GNNs)是一种连接模型，它通过图节点间的消息传递来捕获图之间的依赖关系。与标准神经网络不同，图神经网络保留了一种状态，这种状态可以表示任意深度的邻域信息。虽然原始的gnn很难训练到一个固定的点，但是最近在网络架构、优化技术和并行计算方面的进展使它们能够成功地学习。近年来，基于图卷积网络(GCN)和门控图神经网络(GGNN)的系统在上述许多任务上都取得了突破性的性能。在本研究中，我们对现有的图神经网络模型进行了详细的回顾，系统地对其应用进行了分类，并提出了四个有待进一步研究的问题。

1 INTRODUCTION

Graphs are a kind of data structure which models a set of objects (nodes) and their relationships (edges). Recently, researches of analyzing graphs with machine learning have been receiving more and more attention because of the great expressive power of graphs, i.e. graphs can be used as denotation of a large number of systems across various areas including social science (social networks) [1], [2], natural science (physical systems [3], [4] and protein-protein interaction networks [5]), knowledge graphs [6] and many other research areas [7]. As a unique non-Euclidean data structure for machine learning, graph analysis focuses on node classification, link prediction, and clustering. Graph neural networks (GNNs) are deep learning based methods that operate on graph domain. Due to its convincing performance and high interpretability, GNN has been a widely applied graph analysis method recently. In the following paragraphs, we will illustrate the fundamental motivations of graph neural networks.

图是一种数据结构，它对一组对象(节点)及其关系(边)建模。最近,研究分析图表和机器学习已经收到越来越多的关注,因为图形的表达能力,即图可以用来表示包括社会科学(社交网络)[1],[2]、自然科学（物理系统[3],[4][5]和蛋白质相互作用网络）、知识图[6]和许多其他研究领域[7]在内的各个领域的大量系统。图分析作为一种独特的机器学习非欧几里德数据结构，其研究重点是节点分类、链路预测和聚类。图神经网络（GNNs）是一种基于图域的深度学习方法。由于其令人信服的性能和较高的可解释性，GNN近年来已成为一种广泛应用的图分析方法。在接下来的段落中，我们将阐述图神经网络的基本动机。

The first motivation of GNNs roots in convolutional neural networks (CNNs) [8]. CNNs have the ability to extract multi-scale localized spatial features and compose them to construct highly expressive representations, which led to breakthroughs in almost all machine learning areas and started the new era of deep learning [9]. However, CNNs can only operate on regular Euclidean data like images (2D grid) and text (1D sequence) while these data structures can be regarded as instances of graphs. As we are going deeper into CNNs and graphs, we found the keys of CNNs: local connection, shared weights and the use of multi-layer [9]. These are also of great importance in solving problems of graph domain, because 1) graphs are the most typical locally connected structure. 2) shared weights reduce the computational cost compared with traditional spectral graph theory [10]. 3) multi-layer structure is the key to deal with hierarchical patterns, which captures the features of various sizes. Therefore, it is straightforward to think of finding the generalization of CNNs to graphs. However, as shown in 1, it is hard to define localized convolutional filters and pooling operators, which hinders the transformation of CNN from Euclidean domain to non-Euclidean domain.

GNNs的第一个动机根源于卷积神经网络（CNNs）。CNNs能够提取多尺度的局部空间特征，并将其组合成具有高度表达性的表征，这使得几乎所有的机器学习领域都取得了突破，开启了深度学习[9]的新时代。然而，CNNs只能对图像(二维网格)、文本(一维序列)等常规欧氏数据进行操作，而这些数据结构可以看作是图的实例。随着我们对CNNs和图的深入研究，我们发现了CNNs的关键:局部连接、共享权值和多层[9]的使用。这些对于解决图域问题也具有重要意义，因为：1）图是最典型的局部连通结构。2)与传统谱图理论[10]相比，共享权值降低了计算成本。3)多层结构是处理分层模式的关键，它捕获了不同大小的特征。因此，将CNNs推广到图上是很容易的。但是，如图1所示，局部卷积滤波器和池运算符的定义比较困难，这阻碍了CNN从欧几里德域到非欧几里德域的转换。

The other motivation comes from graph embedding, which learns to represent graph nodes, edges or subgraphs in low-dimensional vectors. In the field of graph analysis, traditional machine learning approaches usually rely on hand engineered features and are limited by its inflexibility and high cost. Following the idea of representation learning and the success of word embedding [11], DeepWalk [12], which is regarded as the first graph embedding method based on representation learning, applies SkipGram model [11] on the generated random walks. Similar approaches such as node2vec [13], LINE [14] and TADW [15] also achieved breakthroughs. However, these methods suffer two severe drawbacks [16]. First, no parameters are shared between nodes in the encoder, which leads to computationally inefficiency, since it means the number of parameters grows linearly with the number of nodes. Second, the direct embedding methods lack the ability of generalization, which means they cannot deal with dynamic graphs or generalize to new graphs.

另一个动机来自图嵌入，它学习在低维向量中表示图节点、边或子图。在图形分析领域，传统的机器学习方法通常依赖于手工设计的特征，并且由于其灵活性和高成本而受到限制。DeepWalk[12]是第一个基于表示学习的图形嵌入方法，它遵循表示学习的思想和单词嵌入[11]的成功，将SkipGram模型[11]应用于生成的随机游动。类似的方法如node2vec[13]、LINE[14]和TADW[15]也取得了突破。然而，这些方法有两个严重的缺点。首先，编码器中的节点之间不共享任何参数，这导致计算效率低下，因为这意味着参数的数量与节点的数量呈线性增长。其次，直接嵌入方法缺乏泛化能力，不能处理动态图或泛化到新的图。

Based on CNNs and graph embedding, graph neural networks (GNNs) are proposed to collectively aggregate information from graph structure. Thus they can model input and/or output consisting of elements and their dependency. Further, graph neural network can simultaneously model the diffusion process on the graph with the RNN kernel.

提出了一种基于神经网络和图嵌入的图神经网络(GNNs)，用于从图结构中对信息进行集合。
因此，它们可以对由元素及其依赖关系组成的输入和/或输出进行建模。
此外，图神经网络可以利用RNN核同时对图上的扩散过程进行建模。

In the following part, we explain the fundamental reasons why graph neural networks are worth investigating. Firstly, the standard neural networks like CNNs and RNNs cannot handle the graph input properly in that they stack the feature of nodes by a specific order. However, there isn t a natural order of nodes in the graph. To present a graph completely, we should traverse all the possible orders as the input of the model like CNNs and RNNs, which is very redundant when computing. To solve this problem, GNNs propagate on each node respectively, ignoring the input order of nodes. In other words, the output of GNNs is invariant for the input order of nodes. Secondly, an edge in a graph represents the information of dependency between two nodes. In the standard neural networks, the dependency information is just regarded as the feature of nodes. However, GNNs can do propagation guided by the graph structure instead of using it as part of features. Generally, GNNs update the hidden state of nodes by a weighted sum of the states of their neighborhood. Thirdly, reasoning is a very important research topic for high-level artificial intelligence and the reasoning process in human brain is almost based on the graph which is extracted from daily experience. The standard neural networks have shown the ability to generate synthetic images and documents by learning the distribution of data while they still cannot learn the reasoning graph from large experimental data. However, GNNs explore to generate the graph from non-structural data like scene pictures and story documents, which can be a powerful neural model for further high-level AI. Recently, it has been proved that an untrained GNN with a simple architecture also perform well [17].

在接下来的部分中，我们将解释为什么图神经网络值得研究的基本原因。首先，像CNNs和RNNs这样的标准神经网络不能很好地处理图形输入，因为它们按照特定的顺序叠加节点的特征。然而，图中没有节点的自然顺序。为了完整的表示一个图形，我们需要遍历所有可能的顺序作为模型的输入，比如CNNs和RNNs，这在计算时是非常冗余的。为了解决这个问题，gnn分别在每个节点上传播，忽略节点的输入顺序。换句话说，GNNs的输出对于节点的输入顺序是不变的。其次，图中的边表示两个节点之间的依赖关系信息。在标准神经网络中，依赖信息只是节点的特征。但是，GNNs可以在图形结构的指导下进行传播，而不是将其用作特性的一部分。一般来说，GNNs通过对节点周围状态的加权和来更新节点的隐藏状态。第三，推理是高水平人工智能的一个非常重要的研究课题，人脑的推理过程几乎是基于从日常经验中提取的图形。标准的神经网络已经显示出通过学习数据分布生成合成图像和文档的能力，而它们仍然不能从大型实验数据中学习推理图。然而，GNNs探索从场景图片和故事文档等非结构化数据中生成图形，这对于进一步的高级人工智能是一个强大的神经模型。最近，已经证明了一个未经训练的简单架构的GNN也可以很好地执行[17]。

There exist several comprehensive reviews on graph neural networks. [18] gives a formal definition of early graph neural network approaches. And [19] demonstrates the approximation properties and computational capabilities of graph neural networks. [20] proposed a unified framework, MoNet, to generalize CNN architectures to non-Euclidean domains (graphs and manifolds) and the framework could generalize several spectral methods on graphs [2], [21] as well as some models on manifolds [22], [23]. [24] provides a thorough review of geometric deep learning, which presents its problems, difficulties, solutions, applications and future directions. [20] and [24] focus on generalizing convolutions to graphs or manifolds, however in this paper we only focus on problems defined on graphs and we also investigate other mechanisms used in graph neural networks such as gate mechanism, attention mechanism and skip connection. [25] proposed the message passing neural network (MPNN) which could generalize several graph neural network and graph convolutional network approaches. It presents the definition of the message passing neural network and demonstrates its application on quantum chemistry. [26] proposed the non-local neural network (NLNN) which unifies several self-attention -style methods. However, the model is not explicitly defined on graphs in the original paper. Focusing on specific application domains, [25] and [26] only give examples of how to generalize other models using their framework and they do not provide a review over other graph neural network models. [27] proposed the graph network (GN) framework. The framework has a strong capability to generalize other models and its relational inductive biases promote combinatorial generalization, which is thought to be a top priority for AI. However, [27] is part position paper, part review and part unification and it only gives a rough classification of the applications. In this paper, we provide a thorough review of different graph neural network models as well as a systematic taxonomy of the applications.

关于图神经网络的研究已有许多综述。[18]给出了早期图神经网络方法的形式化定义。[19]证明了图神经网络的逼近性质和计算能力。[20]提出了一个统一的框架MoNet，将CNN架构推广到非欧几里德域(图和流形)，该框架可以推广图上的几种光谱方法[2]、[21]，以及流形[22]、[23]上的一些模型。[24]全面回顾了几何深度学习，介绍了其存在的问题、难点、解决方案、应用和未来发展方向。[20]和[24]关注于将卷积推广到图或流形，但本文只关注图上定义的问题，也研究图神经网络中使用的其他机制，如门机制、注意机制和跳过连接。[25]提出了消息传递神经网络(MPNN)，它可以推广几种图神经网络和图卷积网络方法。给出了信息传递神经网络的定义，并说明了它在量子化学中的应用。[26]提出了一种非局部神经网络(NLNN)，它统一了几种自我注意方式。然而，该模型并没有在本文的图中明确定义。针对特定的应用领域，[25]和[26]只给出了如何使用它们的框架概括其他模型的例子，并没有对其他图神经网络模型进行综述。[27]提出了图形网络(GN)框架。该框架具有较强的泛化能力，其关联归纳偏差促进了组合泛化，这被认为是人工智能的首要任务。然而，[27]是零件立场文件，零件审查和零件统一，它只给出了一个粗略的分类的应用。本文对不同的图神经网络模型进行了全面的综述，并对其应用进行了系统的分类。

To summarize, this paper presents an extensive survey of graph neural networks with the following contributions.

综上所述，本文对图神经网络进行了广泛的研究，其贡献如下。

We provide a detailed review over existing graph neural network models. We introduce the original model, its variants and several general frameworks. We examine various models in this area and provide a unified representation to present different propagation steps in different models. One can easily make a distinction between different models using our representation by recognizing corresponding aggregators and updaters.

我们对现有的图神经网络模型进行了详细的回顾。我们介绍了原始模型、它的变体和几个通用框架。我们研究了这一领域的各种模型，并提供了一个统一的表示方法来表示不同模型中的不同传播步骤。通过识别相应的聚合器和更新器，可以很容易地使用我们的表示来区分不同的模型。

We systematically categorize the applications and divide the applications into structural scenarios, nonstructural scenarios and other scenarios. We present several major applications and their corresponding methods in different scenarios.

我们系统地对应用程序进行分类，并将应用程序分为结构化场景、非结构化场景和其他场景。我们介绍了几种主要的应用程序及其在不同场景中的相应方法。

We propose four open problems for future research. Graph neural networks suffer from over-smoothing and scaling problems. There are still no effective methods for dealing with dynamic graphs as well as modeling non-structural sensory data.We provide a thorough analysis of each problem and propose future research directions.

我们提出了四个有待进一步研究的问题。图神经网络存在过度平滑和缩放问题。目前还没有有效的方法来处理动态图以及对非结构感测数据进行建模。我们对每个问题进行了深入的分析，并提出了未来的研究方向。

The rest of this survey is organized as follows. In Sec. 2, we introduce various models in the graph neural network family. We first introduce the original framework and its limitations. And then we present its variants that try to release the limitations. And finally, we introduce several general frameworks proposed recently. In Sec. 3, we will introduce several major applications of graph neural networks applied to structural scenarios, non-structural scenarios and other scenarios. In Sec. 4, we propose four open problems of graph neural networks as well as several future research directions. And finally, we conclude the survey in Sec. 5.

调查的其余部分组织如下。在第二节中，我们介绍了图神经网络族中的各种模型。我们首先介绍原始框架及其局限性。然后我们展示了它的变体，试图释放这些限制。最后，介绍了最近提出的几种通用框架。在第3节中，我们将介绍图神经网络在结构场景、非结构场景和其他场景中的几个主要应用。在第4节中，我们提出了图神经网络的四个开放问题以及未来的研究方向。最后，我们在第5节结束了调查。

2 MODELS

Graph neural networks are useful tools on non-Euclidean structures and there are various methods proposed in the literature trying to improve the model's capability.

图神经网络是研究非欧几里德结构的有效工具，文献中提出了多种方法来提高模型的性能。

In Sec 2.1, we describe the original graph neural networks proposed in [18]. We also list the limitations of the original GNN in representation capability and training efficiency. In Sec 2.2 we introduce several variants of graph neural networks aiming to release the limitations. These variants operate on graphs with different types, utilize different propagation functions and advanced training methods. In Sec 2.3 we present three general frameworks which could generalize and extend several lines of work. In detail, the message passing neural network (MPNN) [25] unifies various graph neural network and graph convolutional network approaches; the non-local neural network (NLNN) [26] unifies several "self-attention" -style methods. And the graph network(GN) [27] could generalize almost every graph neural network variants mentioned in this paper.

在sec2.1中，我们描述了[18]中提出的原始图神经网络。我们还列出了原始GNN在表示能力和训练效率方面的局限性。在Sec 2.2中，我们介绍了几种图神经网络的变体，旨在消除这些限制。这些变体对不同类型的图进行操作，利用不同的传播函数和先进的训练方法。在Sec 2.3中，我们提出了三个通用框架，它们可以概括和扩展几行工作。其中，消息传递神经网络(MPNN)[25]将各种图神经网络和图卷积网络方法相结合;非局部神经网络(NLNN)[26]统一了几种“自我注意”风格的方法。而图网络(GN)[27]几乎可以推广本文所述的所有图神经网络变体。

Before going further into different sections, we give the notations that will be used throughout the paper. The detailed descriptions of the notations could be found in Table 1.

在深入到不同的部分之前，我们给出了贯穿全文的符号。这些符号的详细描述见表1。

                                          

2.1 Graph Neural Networks

在图中，每个节点的定义是由该节点的特征和相关节点来共同表示的。GNN的目标是训练出一个state embedding函数hv，该函数包含了每个节点的领域信息。

         

hv是节点v的向量化表示，它可以被用来去预测该节点的输出ov（例如节点的标签）。f（*）被称为local transition function，它被所有的节点共享，并根据输入的领域信息来更新节点的状态。xv是节点v的特征表示，xco[v]是v节点上/边的特征表示，hne[v]是该节点的状态，xne[v] 是节点v周围节点的特征表示。

g（*）被称为local output function，它是用来产生节点的输出的。

             

H、O、X、XN为其推广形式，代表图中的所有状态、输出、特征和节点特征的堆叠形式。

F是全局转换函数，G是全局输出函数，是图中所有节点的f和g的堆栈版本。H的值是Eq. 3的不动点，在F为收缩映射的假设下唯一定义。

Banach的fixed point提出以后，GNN中state的迭代计算过程可以表示如下：

              

Ht代表H的第t-th的状态，H（0）代表其动态方程的初始状态。

对于任意初始值H(0)，动力系统Eq. 5以指数方式快速收敛到Eq. 3的解。注意，f和g中描述的计算可以解释为前馈神经网络。

当我们有了GNN的框架后，下一个问题是如何学习f和g的参数。对于有监督的目标信息(特定节点的tv)，损失可以写为：

p是监督节点的数目。学习算法基于一个梯度下降策略并且由以下步骤组成。

    ·状态$h_{v}^{t}$被公式1迭代更新，直到时间T。它们逼近式3:H(T)≈ H的不动点解。

    ·权值W的梯度由损失计算得到。

    ·权值W根据最后一步计算的梯度进行更新

局限性

实验结果表明，GNN是一种功能强大的结构化数据建模体系结构，但与原始GNN相比仍存在一些局限性。

1.针对不动点迭代更新节点的隐藏状态是低效的。如果放松不动点的假设，我们可以设计一个多层GNN来得到节点及其邻域的稳定表示。

2.GNN在迭代中使用相同的参数，而大多数常用的神经网络在不同的层中使用不同的参数，作为分层特征提取方法。此外，节点隐藏状态的更新是一个循序渐进的过程，可以从GRU和LSTM等RNN内核中获益。

3.在原始GNN中也存在一些无法有效建模的边缘信息特征。例如，知识图中的边具有关系的类型，通过不同边的消息传播应该根据它们的类型而有所不同。此外，如何学习边缘的隐藏状态也是一个重要的问题。

4.如果我们把重点放在节点的表示上而不是图上，就不适合使用不动点，因为在不动点上表示的分布将会非常平滑，而且对于区分每个节点的信息也会更少。

2.2 图神经网络的变体

在这一小节中，我们介绍了图神经网络的几种变体。Sec 2.2.1侧重于在不同图形类型上操作的变体。这些变体扩展了原始模型的表示能力。Sec 2.2.2列出了在传播步骤上的几个修改(卷积、门机制、注意机制和跳过连接)，这些模型可以学习到更高质量的表示。Sec 2.2.3描述了使用高级训练方法的变体，能够提高训练效率。图2概述了图神经网络的不同变体。

以下三个图都是图二：图神经网络变异的概述

(a) Graph Types

(b) Training Methods

(c) Propagation Steps

2.2.1 Graph Types

在原始的GNN[18]中，输入图由带有标签信息和无向边的节点组成，这是最简单的图形格式。然而，世界上有许多不同的图形。在这一节中，我们将介绍一些设计用来对不同类型的图建模的方法。

有向图

图的第一个变体是有向图。无向边可以看作是两个有向边，说明两个节点之间存在关系。然而，有向边比无向边能带来更多的信息。例如，在一个边从head实体开始到tail实体结束的知识图中，head实体是tail实体的父类，这意味着我们应该区别对待父类和子类的信息传播过程。

ADGPM用两种权重系数矩阵，Wp和Wc，来包含更精确的结构信息。传播规则如下：

其中是父类和子类的标准化邻接矩阵。

异构图

图的第二种变体是异构图，其中有几种节点。处理异构图最简单的方法是将每个节点的类型转换为一个与原始特征相连接的独热特征向量。此外，GraphInception[30]将元路径的概念引入到异构图的传播中。使用元路径，我们可以根据邻居的节点类型和距离对它们进行分组。对于每个邻居组，GraphInception将其作为一个同构图中的子图进行传播，并将来自不同同构图的传播结果连接起来，以进行一个集合节点表示。

---

元路径

元路径是定义在网络模式上的链接两类对象的一条路径，形式化定义为，

表示对象类型之间的一种复合关系，其中○代表关系之间的复合算子，Ai表示对象类型，Ri表示关系类型。

图3：元路径示例

[1]

---

边信息图

在图的最后一个变体中，每条边也有它的信息，比如边的权重或类型。有两种方法来处理这类图:首先,我们可以将图转换成双向加权联合图，原边也成为节点和一个原边分成两个新的边，意味着有两个新的边在边节点和开始/结束节点之间。

G2S的编码器为邻居使用以下聚合函数：

Wr和br是不同类型变（关系）的传播参数。

第二，我们可以根据不同的权值矩阵在不同的边上进行传播。当关系数量非常大时，r-GCN[32]引入两种正则化来减少关系数量建模的参数数量:基分解和块对角分解。

在基分解的情况下，每个Wr被定义为：

即，作为基变换的线性组合，Vb∈用系数arb表示，以致只有系数依赖于r。

在块对角分解中，r-GCN通过对一组低维矩阵的直和来定义每个Wr，该矩阵比第一个矩阵需要更多的参数。

2.2.2 Propagation Types

传播步长和输出步长对于获取节点(或边)的隐藏状态至关重要。如下所示，在原图神经网络模型的传播步骤中有几个主要的修改，而研究人员通常在输出步骤中遵循一个简单的前馈神经网络设置。不同变异GNN的比较如表2所示。这些变体使用不同的聚合器从每个节点的邻居和特定的更新器收集信息，以更新节点的隐藏状态。

卷积

将卷积推广到图域的兴趣越来越大。这方面的进展通常分为光谱方法和非光谱方法。

谱方法使用图的光谱表示。[35]提出了频谱网络。通过计算图拉普拉斯变换的特征分解，在傅里叶域中定义了卷积运算。

该操作可以定义为一个信号(每个节点的标量)与一个滤波器的乘积，该滤波器由参数化：

U是归一化后的拉普拉斯图（D 是次数矩阵，A是图的邻接矩阵）的特征向量矩阵及其特征值$\Lambda$的对角矩阵

这种操作会导致潜在的密集计算和非空间局部化过滤器。[36]试图通过引入一个光滑系数的参数化使光谱滤波器在空间上局部化。[37]说明可以根据切比雪夫多项式Tk（x）截断扩张近似到k阶。因此这个操作是：

λmax表示L的最大特征值。现在是切比雪夫系数的向量。切比雪夫多项式被定义为Tk（x）= 2xTk-1(x)-Tk-2(x)，其中T0(x)=1,T1(x)=x。

可以看出，由于拉普拉斯多项式是k阶多项式，所以操作是k局域的。[38]使用k局部卷积来定义卷积神经网络，该网络可以不再需要计算拉普拉斯特征向量。

[2]将分层卷积运算限制为K = 1，以缓解节点度分布非常广的图对局部邻域结构的过拟合问题。

进一步逼近λmax= 2，方程简化为:

有两个自由参数,在用约束参数个数之后，我们可以得到如下表达式：

注意，叠加这个操作符可能导致数值不稳定和爆炸/消失梯度，[2]引入了重整化技巧：

其中，，

最后，[2]将该定义推广到一个带有C输入通道和用于特征映射的F过滤器的信号，如下所示：

其中为滤波器参数矩阵，为卷积信号矩阵。

[39]提出了一种基于高斯过程的贝叶斯方法来解决图上的半监督学习问题。它显示了模型和光谱滤波方法之间的相似性，这可以从另一个角度给我们一些启示。

然而，在上述所有的谱方法中，学习滤波器都依赖于拉普拉斯特征基，而拉普拉斯特征基又依赖于图的结构，即针对特定结构训练的模型不能直接应用于不同结构的图。

非光谱方法直接在图上定义卷积，并在空间上邻近操作。非光谱方法的主要挑战是定义具有不同大小邻域的卷积运算，并保持神经网络的局部不变性。

[33]对不同程度的节点使用不同的权重矩阵，

其中为第L层深度为Nv的节点的权值矩阵，该方法的主要缺点是不能应用于节点度较大的大规模图。

[21]提出了扩散卷积神经网络(DCNNs)。转换矩阵用于定义DCNN中节点的邻域。对于节点分类，它有

X是输入特征的一个NxF张量（N是节点数，F是特征数）。P*是一个包含矩阵P的幂级数{P,P^2,...,P^K}的NxKxN张量。P是图的邻接矩阵A的深度归一化转换矩阵。每一个实体都被转换成一个扩散卷积表示，它是一个K x F矩阵，由图在F特征上扩散的K跳定义。然后由KxF权矩阵和非线性激活函数f定义，最后H(即NxKxF)表示图中每个节点的扩散表示。

对于图的分类，DCNN只取节点表示的平均值

这里$1_{N}$是一个由1组成的Nx1的向量。DCNN也可以应用于边缘分类任务，这需要将边缘转换为节点，并增加邻接矩阵。

[40]为每个节点提取并规范化一个恰好包含k个节点的邻域。然后归一化邻域作为卷积运算的接受域。

欧几里得域，它可以推广前面的几种技术。流形上的测地线CNN (GCNN)[22]和各向异性CNN (ACNN)[23]或图上的GCN[2]和DCNN[21]可以表示为MoNet的具体实例。

[1]提出了GraphSAGE，一个通用的归纳框架。该框架通过从节点的本地邻居中采样和聚合特性来生成嵌入。

然而，[1]并没有利用Eq.18中的完整邻域集，而是通过均匀采样来利用固定大小的邻域集。[1]建议使用三个聚合器函数。

       · 平均聚合器。它可以被看作是从转导GCN框架[2]中卷积运算的近似值，因此GCN变量的归纳版本可以被得到：

       

        平均聚合器与其他聚合器不同，因为它不执行连接Eq.18中的和的连接操作。它可以看作是跳过连接[41]的一种形式，可以获得更好的性能。

        ·LSTM聚合器。[1]还使用了一个基于lstm的聚合器，它具有更大的表达能力。然而，LSTMs以顺序的方式处理输入，因此它们不是置换不变的。[1]通过改变节点的邻居使LSTMs对无序集进行操作。

        ·池聚合器。在池聚合器中，每个邻居的隐藏状态通过一个完全连接的层提供，然后对节点的邻居集应用最大池操作。

       

        注意，任何对称函数都可以用来替代这里的最大池操作。

近年来，结构感知卷积和结构感知卷积神经网络(SACNNs)被提出。单变量函数被用作过滤器，它们可以处理欧几里德和非欧几里德结构化数据。

门。有几项工作尝试在传播步骤中使用诸如GRU[43]或LSTM[44]这样的gate机制，以减少以前GNN模型中的限制，提高信息在图结构中的长期传播。

[45]提出了一种门控图神经网络(GGNN)，它在传播步长中使用门控递归单元(GRU)，将递归展开到固定步长T，并通过时间反向传播来计算梯度。

具体而言，传播模型的基本递归式为

                                   

节点V首先聚集来自其邻居的消息，其中Av是图邻接矩阵A的子矩阵，表示节点V与其邻居的连接。类似GRU的更新函数包含来自其他节点和上一个时间步骤的信息，以更新每个节点的隐藏状态。a收集节点v、z和r的邻域信息，即更新和重置门。

在基于树或图的传播过程中，LSTM也以类似于GRU的方式使用。

[46]提出了对基本LSTM体系结构的两个扩展：子和树LSTM和n元树LSTM。和标准LSTM单元一样，每个树LSTM单元（用v索引）包含输入和输出门iv和ov、存储单元cv和隐藏状态hv。树lstm单元不是一个单独的遗忘门，而是为每个子k包含一个遗忘门fvk，允许该单元有选择地合并来自每个子级的信息。子和树lstm转换方程如下：

                                                 

                                                    

是标准LSTM设置中t时刻的输入向量。

如果一棵树的分支因子最多为k，并且一个节点的所有子节点都是有序的，也就是说，它们可以从1索引到k，那么就可以使用n元树lstm。对于节点V，和分别表示其第k个子在t时刻的隐藏状态和存储单元。过渡方程如下：

                                                         

为每个子k引入单独的参数矩阵，使得模型能够比子和树lstm学习更多关于单元子级状态的细粒度表示。

这两种类型的树LSTM可以很容易地适应图表。[47]中的图结构lstm是应用于图的n元树lstm的示例。但是，这是一个简化的版本，因为图中的每个节点最多有2个传入边缘（来自其父节点和同级节点的前置节点）。[34]基于关系提取任务提出了图lstm的另一个变体。图和树的主要区别在于图的边缘有它们的标签。并且[34]使用不同的权重矩阵来表示不同的标签。

                                                         

其中m (v;k)表示节点v与k之间的边标号。

[48]提出了改进文本编码的句子lstm（s-lstm）。它将文本转换为图形，并利用图形LSTM学习表示。在许多非线性规划问题中，S-LSTM具有很强的表示能力。[49]提出了一个图形LSTM网络来解决语义对象解析任务。它采用了信任驱动方案，自适应地选择起始节点，确定节点更新顺序。它遵循将现有LSTM归纳为图形结构数据的相同思想，但具有特定的更新序列，而我们上面提到的方法对节点顺序不可知。

注意力。注意力机制已成功地应用于机器翻译[50][52]、机器阅读[53]等许多基于序列的任务中。[54]提出了一种图形注意力网络（GAT），它将注意力机制纳入传播步骤。它按照一种自我关注策略，通过关注相邻节点来计算每个节点的隐藏状态。

[54]提出了一个单图注意层，通过叠加该层构造任意图注意网络。层通过计算节点对（i，j）注意机制中的系数:

aij是节点j对i的注意系数，Ni表示图中节点i的邻域，该层的节点特征的输入集为，hi∈，N是节点数量，F是每个节点的特征数，该层生成一组新的节点特性(可能具有不同的基数F')，，作为输出。

是应用于每个节点的共享线性变换的权矩阵，是单层前馈神经网络的权向量。它由一个SoftMax函数进行归一化，并应用了非线性LeakyReLU（负输入斜率=0:2）。

然后（在应用非线性特征$\sigma$之后）可以获得每个节点的最终输出特征：

                                                       

此外，该层利用与[52]类似的多头关注来稳定学习过程。它应用k独立注意机制来计算隐藏状态，然后连接它们的特征（或计算平均值），从而得到以下两种输出表示：

                                                   

是由第k个注意机制计算的归一化注意系数。

[54]中的注意力结构具有以下几个特点：（1）节点-邻居对的计算是可并行并行的，因此操作是有效的；（2）通过对邻居指定任意权重，可以应用于不同程度的图节点；（3）很容易应用于归纳学习问题。

残差连接Skip connection

许多应用程序展开或堆叠图形神经网络层，以获得更好的结果，因为更多的层（即k层）使每个节点从邻居k跳离聚集更多的信息。然而，在许多实验中已经观察到，更深的模型不能提高性能，更深的模型甚至可能表现更差[2]。这主要是因为更多的层也可以传播来自指数级增加的扩展邻居成员的噪声信息。

解决这个问题的一个简单方法，即残余网络[55]，可以从计算机视觉社区中找到。但是，即使有剩余连接，具有更多层的GCN在许多数据集上的性能也不如2层的GCN[2]。

[56]提出了一条公路GCN，使用类似于公路网络的分层门[57]。一个层的输出与它的输入和选通权重相加：

在[56]中讨论的一个具体问题中，通过添加高速公路闸门，性能在4层达到峰值。

[58]研究邻域聚合方案的性质及其局限性。提出了一种学习自适应结构感知表示的跳跃知识网络。跳变知识网络从最后一层节点的所有中间表示(跳变到最后一层)中进行选择，使模型根据需要对每个节点的有效邻域大小进行调整。在实验中，[58]使用了连接、最大池和LSTM-attention三种方法来聚合信息。跳跃知识网络在社会、生物信息学和引文网络等领域的实验中表现良好。它还可以与Graph Convolutional Networks、GraphSAGE和Graph Attention Networks等模型相结合，提高性能。

 

2.2.3 Training Methods

原始的图卷积神经网络在训练和优化方法上存在一些不足。具体地说，GCN需要完整的图拉普拉斯矩阵，这对于大型图来说是需要计算的。此外，一个节点在第L层的嵌入是由它的所有邻居在第L层的嵌入递归计算。因此，单个节点的接受域相对于层数呈指数增长，因此计算单个节点的梯度代价较大。最后，针对固定图对GCN进行独立训练，缺乏归纳学习的能力。

GraphSAGE[1]是对原GCN的全面改进。为了解决上述问题，GraphSAGE用可学习的聚集函数代替了完整的图拉普拉斯函数，这是执行消息传递和推广到不可见节点的关键。如Eq.18所示，它们首先聚合邻域嵌入，与目标节点的嵌入连接，然后传播到下一层。使用学习的聚合和传播函数，GraphSAGE可以为不可见节点生成嵌入。此外，GraphSAGE使用邻域抽样来减缓接受域的扩展。

FastGCN[59]进一步改进了采样算法。FastGCN没有对每个节点的邻居进行采样，而是直接对每个层的接受域进行采样。FastGCN采用重要性抽样，其重要性因子计算如下：

与上述固定采样方法相比，[60]引入了一个参数化、可训练的采样器，在前一层的基础上进行分层采样。此外，该自适应采样器可以找到最优的采样重要性，同时降低方差。

[61]提出了一种基于控制变量的GCN随机逼近算法，利用节点的历史激活作为控制变量。该方法限制了1跳邻域的接受域，但使用历史隐藏状态作为可负担的近似。

[62]重点研究了GCN的局限性，其中包括GCN需要很多额外的带标签的数据进行验证，而且卷积滤波器的本地化特性也使GCN受到影响。为了解决这些局限性，提出了联合训练GCN和自训练GCN来扩充训练数据集。前一种方法寻找训练数据的最近邻，后一种方法采用类似于启动的方法。

 

2.3 General Frameworks

除了图神经网络的不同变体外，还提出了几种通用框架，旨在将不同的模型集成到一个框架中。[25]提出了消息传递神经网络(MPNN)，它统一了各种图神经网络和图卷积网络方法。[26]提出了非局部神经网络(NLNN)。它统一了几种自我注意风格的方法[52]，[54]，[63]。[27]提出了图网络(GN)，它统一了MPNN和NLNN方法，以及交互网络[4]、[64]、神经物理引擎[65]、CommNet[66]、structure2vec[7]、[67]、GGNN[45]、关系网络[68]、[69]、深度集[70]、点网[71]等多种变体。

2.3.1 Message Passing Neural Networks

[25]提出了一种用于图形监督学习的通用框架——消息传递神经网络(MPNNs)。MPNN框架抽象了图结构数据中常用的几种模型之间的共性，如图卷积中的谱方法[35][2]、[38]和非谱方法[33]，门控图神经网络[45]、交互网络[4]、分子图卷积[72]、深度张量神经网络[73]等。

该模型包括两个阶段，一个消息传递阶段和一个读出阶段。消息传递阶段(即传播步骤)运行T个时间步长，定义为消息函数Mt和顶点更新函数Ut。

利用消息，隐藏状态的更新函数如下：

其中evw表示节点v到w的边缘特征，读出阶段使用读出函数R计算出整个图的特征向量，根据：

其中T为总时间步长。消息函数Mt、顶点更新函数Ut和读出函数R可以有不同的设置。因此，MPNN框架可以通过不同的函数设置泛化多个不同的模型。在这里我们给出了一个广义GGNN的例子，其他模型的函数设置可以在[25]中找到。GGNNs的函数设置为：

其中Aevw为邻接矩阵，每个边标e对应一个邻接矩阵。GRU为[43]中引入的门控递归单元。i和j是函数R中的神经网络。

 

2.3.2 Non-local Neural Networks

[26]提出了非局部神经网络(NLNN)来捕获与深度神经网络的长期依赖关系。非局部操作是计算机视觉中经典的非局部均值操作[74]的推广。非本地操作计算一个位置的响应，作为所有位置特征的加权和。这组位置可以是在空间、时间或时空中。因此，NLNN可以看作是[52]，[54]，[63]中不同的自我注意方式的统一。我们将首先介绍非本地操作的一般定义，然后介绍一些特定的实例。

在非局部均值操作[74]之后，一般的非局部操作定义为:

其中i是输出位置的索引，j是枚举所有可能位置的索引。计算i和j之间的标量，表示它们之间的关系。g(hj)表示输入hj的一个变换，利用因子对结果进行归一化。

有几个实例设置不同的f和g。为简单起见，[26]使用线性变换作为函数g，这意味着，其中Wg是一个学习权矩阵。下面我们列出函数f的选项。

高斯函数。根据非局部均值[74]和双侧滤波器[75]，高斯函数是一种自然选择。
因此:

在这里，是点积相似，

嵌入式高斯。通过计算嵌入空间中的相似度来扩展高斯函数是很简单的：

可以发现，[52]中提出的自我注意是嵌入式高斯版本的一个特例。对于给定的i, 成为沿j维的softmax计算。

所以h' = ，这与[52]中的自我注意形式相匹配。

点积。函数f也可以实现为点积相似性：

这里因子C(h) = N，其中N是h中的位置数。

连接。这里我们有：

其中wf是一个权向量，将向量投影到标量上，C(h) = N。

[26]将上述非本地操作封装到一个非本地块中：

其中$h_{i}^{'}$在Eq.34中给出，"$+h_{i}$"表示剩余连接[55]。因此，非局部块可以插入到任何预先训练的模型中，这使得块更适用。

2.3.3 Graph Networks

[27]提出了图形网络(GN)框架，对各种图形神经网络进行了概括和扩展，MPNN和NLNN分别逼近[18]、[25]、[26]。首先介绍了[27]中图形的定义，然后介绍了核心GN计算单元GN块及其计算步骤，最后介绍了它的基本设计原则。

图的定义。在[27]中，图被定义为一个三元组G = （u，H，E）（这里我们用H代替V来表示符号的一致性）。u是一个全局属性，是一组节点(基数为)，其中每个$h_{i}$都是一个节点的属性。是边的集合(基数$N_{e}$)，其中每个ek是边的s属性，rk是接收节点的索引，sk是发送节点的索引。

GN块。GN块包含三个更新函数φ和三个聚合函数ρ：

在这里，，

ρ函数必须不变排列的输入和应变量数量的参数。

计算步骤。GN块的计算步骤如下：

（略）

设计原则。基于灵活表示、可配置的块内结构和可组合的多块体系结构的图形网络设计。

        灵活的表示。GN框架支持属性的灵活表示以及不同的图形结构。全局、节点和边缘属性可以使用任意的表示格式，但实值向量和张量是最常见的。我们可以简单地根据任务的特定需求定制GN块的输出。例如，[27]列出了几个边缘聚焦[76]、[77]、节点聚焦的[3]、[4]、[65]、[78]和图形聚焦的[4]、[25]、[69]GNs。在图结构方面，框架既可以应用于图结构是显式的结构场景，也可以应用于应该推断或假设关系结构的非结构场景。

       可在块结构中配置。gn块中的函数及其输入可以有不同的设置，这样gn框架在块结构配置中提供了灵活性。例如，[77]和[3]使用完整的gn块。他们的φ实现使用神经网络，他们的ρ函数使用元素求和。根据不同的结构和功能设置，gn框架可以表达各种模型（如mpnn、nlnn和其他变体）。更多细节见[27]。

        可组合的多块体系结构。可以组成gn块来构建复杂的体系结构。任意数量的gn块可以按共享或非共享参数的顺序组成。[27]利用gn块构造一个编码过程解码体系结构和一个重复的基于gn的体系结构。这些架构如图3所示。构建基于gn的架构的其他技术也可能有用，例如跳过连接、LSTM或GRU风格的选通方案等。

 

 

 

 

 

---

卷积神经网络一：https://cloud.tencent.com/developer/news/131400

卷积神经网络二：https://cloud.tencent.com/developer/news/134921

三维卷积：https://www.cnblogs.com/xiaojianliu/articles/9905278.html

 

,

 

 

---

参考文献：

[1] https://blog.csdn.net/swy520/article/details/78962895