酷应用

GitHub图深度学习引用Top 10文章，你都看过吗？

百家作者：AI100 2019-07-19 09:01:07

作者 | 李靖儒，浙江大学计算机学院博士研究生

来源 | 转载自知乎用户JR Lee

导读：GNN（图神经网络）是一种典型的几何深度学习方法，其主要参考了传统神经网络的结构，并将之应用到图结构的推断中，是图深度学习（Graph Deep Learning）的一种典型模型。在 GitHub 上有一个关注目前图深度学习领域的最新动态的合集，本文将主要简要介绍该 Github 合集中总结的十篇图深度学习文章的基本思想、模型与实验。

Github地址：https://github.com/naganandy/graph-based-deep-learning-literature

Top10 文章按类别总结如下：

GNN概述

我们知道，在传统的深度学习邻域中，其主要目的是通过一系列深度模型（典型的比如深度神经网络、卷积层、池化层、Readout层等）学习出对原有数据的可计算的表示。同样的，图深度学习方法的核心也是学习出对图数据的可计算的表示。然而图数据是一种典型的非欧式数据，其并没有规则的欧式结构，在数学上很难定义四则运算以及一些共享权重以及卷积聚集之类的操作，因此如何定义图深度学习中的层与层之间的推断过程是一个十分重要的方向，这也是GNN所研究的一个主要问题。

在这其中，我们不得不提到2009年发表在IEEE Transactions on Neural Networks(TNN)上的文章The graph neural network model（https://repository.hkbu.edu.hk/cgi/viewcontent.cgi?article=1000&context=vprd_ja）。本文可谓是 GNN 的开山之作，其提出了适用于图结构和节点的新的神经网络模型，并扩展了递归神经网络模型和random walk理论，以及给出了一系列参数训练的方法。

通过定义图，其中为图中节点的集合以及为图中的边的集合，并定义每个点都有一个状态，并且定义点的label 以及边的label 。在本文中，解决的是一个定义在图-节点域中的监督学习框架：

其中为的第个节点。表示第个图的第个节点的target 。

那么，传统的图GNN模型的传播过程如图1所示，公式可以表示为：

其中是叫做局部转移函数的参数方程，定义为局部输出函数，这也是目前大多数基于邻居信息推断的神经网络模型的基本框架。而为了能够使用GNN模型，通常需要解决以下问题：

如何求解推断方程
如何使用训练集训练和
和的具体实现

图2 将原始图使用f_w和g_w函数进行编码后的结果。其中f_w和g_w可以理解成各种非线性函数或者神经网络的映射。

因此，作者在后面定义了损失函数，并证明了函数，以及的连续可微性，反向传播的可行性，并给出了一些GNN网络的例子，另外证明了几个典型的GNN推断模型的时间复杂度。

之后，作者使用GNN模型进行子图匹配，诱变问题，网页排名问题，parity问题等多种问题。但是，其仅仅采用了一些简单的线性和非线性的连接方法，或者一些简单的前馈网络（FNN），相应地其就具有一些诸如梯度消失，高维特征难以提取，鲁棒性差等诸多缺陷。

卷积聚集推断

在Top 10 paper中，我们可以看到关于卷积聚集的方法（GCN-based methods）占据了超过半壁江山，另外卷积网络也在目标识别、实体分割、图像分类等计算机视觉领域，以及文本分类、机器翻译等NLP领域中具有十分杰出的效果。因此，将卷积网络引入到图结构中也是图深度学习领域的一种重要思路。

Spectral Networks and Deep Locally Connected Networks on Graphs

这篇文章是LeCun大佬组在14年ICLR的成果，其将卷积神经网络的操作扩展为定义在通用域中的信号操作。具体的构建方法包括：

空间建构方法。基于域中的层次聚类操作，也就是定义图网络中一些局部连接与池化的层
谱建构方法。基于图Laplacian的谱操作两种方法，将卷积操作拆分为Fourier域的操作。

在这篇文章中，第一次考虑在图域中定义卷积核操作filter，以及层次化聚类操作（也就是图像处理中的下采样操作，神经网络中的带stride的卷积和pooling操作）。无向图的池化过程如图3所示：

图3 空间建构过程，主要进行两次的层次聚类操作（池化操作）。每一层的转换丢失空间信息但是增加了filter的数量。

在谱方法中，也定义了基于图Laplacian的特征值分解的方法将图特征进行层层之间的推断：

本文也介绍了在常数复杂度情况下使用平滑的谱乘子的方法，并且将图Laplacian的特征值矩阵定义为Fourier变换的基矩阵。通常graph signal函数越小，图信号就越光滑。

实验上，本文在MINST数据集上测试了池化模型和Laplacian卷积模型，并将结果进行可视化之后呈现出来。

Learning CNN for Graphs

本文发表于2016年ICML上，作者提出了一种对于任意图结构中训练CNN的方法，这些图包括点结构和边结构的属性。具体从传统卷积网络扩展到非欧式空间的卷积过程如下所示：

图4 (a)表示的是一个3x3感受野的CNN网络（也就是使用3x3卷积核的filter）。这个卷积过程从上到下从左到右进行移动，移动的stride为1，并且不采用zero-padding的技术。(b)在图上定义节点序列与感受野的大小，感受野大小由超参决定

本文主要解决以下两个问题：

给定一个图的集合，对一个未知图进行分类和回归。任意两张图的节点不一定相关。
给定有一个大图，学习其中的图表示以推断诸如节点类型和丢失边的未知图特性。

因此，为了解决序列问题，并且为了消除图本身带来的偏移，因此本文的任务是确定创建邻域图的归一化过程。因此，本文提出了以下的架构：

图5 本文的架构。具体的过程是：首先从图中通过节点标注选择节点序列，对于一些序列进行邻居图的建构，之后进行归一化操作。而这个邻居图则可以被视作图的感受野，之后可以构建类似CNN的架构

个人认为本文的主要创新点是提出了在任意图中都可行的CNN结构，这也为GCN奠定了理论基础。另外，本文针对其中graph normalization问题提出了最优graph normalization的问题定义及其近似解（因为这个问题可以规约到图同构问题）

实验上，本文进行了运行时间分析，图特征可视化，以及图分类任务，证明了PATCHY-SAN与非线性特征组合与其在CNN感受野中的工作表现得特别好。

Semi-Supervised Classification with Graph Convolutional Networks

这篇发表在ICLR2017的文章可以看作GCN的经典文章，也是系统化提出图卷积操作的经典之作，目前是GNN领域引用量最大的文章。其提出了一种在图数据结构上的半监督学习方法，并且使用对图谱卷积操作（图Laplacian矩阵的一阶近似），主要为了避免在Loss function中显式的表现出基于图结构的regularization项。

显而易见地，其逐层推断的更新公式为：

其中是对于添加了自连接边的无向图的邻接矩阵，以及是逐层的可训练的邻接矩阵，并外套一层非线性激活函数。是第层的表示结果。这个推断公式，是图的谱filter的一阶近似。因为图Laplacian矩阵的特征值分解通常需要大量的时间开销，目前已经使用Chebyshev多项式对特征值对角矩阵进行近似。

那么，GCN的半监督体现在何处呢？在作者提出的两层GCN网络中，作者对于所有已经标注的样例在多分类问题上定义了一个交叉熵函数：

这里表示拥有Label的节点index。

本文主要进行了对引文网络的半监督文档分类以及对知识图谱网络的半监督实体分类。在其中，GCN的主要问题是其只能使用无向图，并且无法分析边的特征，因为有向图的Laplacian矩阵很难保证半正定。

Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering

这篇发表于NIPS 2016的文章也是基于快速局部的谱过滤方法来进行卷积操作。与之前提到的谱方法类似，这篇文章的CNN架构则是提出了一种谱的方法，并且提出了一种完整的卷积-池化操作过程。具体如图6所示：

在上述过程中，其包含两个关键步骤：

（1）图傅里叶变换（Graph Fourier Transform）。基于传统的离散傅里叶变换过程，我们可以定义图Laplacian使用Fourier基，并进行特征值分解使得，那么我们可以定义图信号的傅里叶变换为，并定义逆傅里叶变换为，那么定义在傅里叶域上的卷积操作为：

定义为Hadamard乘积，定义经过图filter 为：

这里定义为Fourier系数向量的对角阵。另外，本文也提出了使用Chebyshev多项式对Laplacian矩阵进行递归近似。

（2）图粗糙化（Graph Coarsening）。这个问题可以理解成将一系列图的节点和边进行聚类之后用一个点或者一条边来代替，是一个节点和边的分割问题，这个问题已经在1992年被Bui等人证明是NP-hard的。在池化操作中，通常是需要一个Table以储存所有匹配的节点。这样会导致计算无法并行，因此作者首先建立了一个二叉平衡树，然后重排节点。

这个模型在文本分类任务上具有较好的效果，可以看到使用图CNN进行图数据的处理具有较好的效果。

Convolutional Networks on Graphs for Learning Molecular Fingerprints

这篇文章是发表于2015年的NIPS，其提供了一种对于任意大小的图的端对端的预测模型。关于端对端我们可以理解为输入和输出是同一批类型的数据，即输入是一张图，那么输出的表示也是一张图。本文主要介绍了一种基于循环指纹提取分子特征的模型，并提出了data-driven的特征。

这篇文章主要是解决了计算分子指纹时需要处理任意大小的分子的需求。本文中主要将计算分子指纹向量的神经网络层替换为可微神经网络，其中输入是代表整个分子的图模型。这种模型具有以下几种优势：

较好的预测效果
结构简单（可以避免对无关特征的编码）
可表达性。神经网络模型比传统模型更具有表达性。

本文主要使用Hash和Index两种方法建立可微指纹。这里由于有些偏化学的东西（好歹我还是材料出身的emmm）没仔细看，然而值得注意的是本文的实验除了测试了各种合成的有机物的化学性质之外，还定义了相似性度量的方法。在本文中，作者总结了该项工作相似于神经图灵机问题，为基于数据的机器学习问题提供了一种解决思路。

其它聚集方式

在Top10 paper中，我们也可以看到一些其他类型的聚集方式，包括基于序列模型的Gate GNN(LSTM-based GNN)，基于Attention机制的GAT，以及基于推理模型的GraphSAGE，另外还有包含边聚集信息的MPNN。下面将逐一介绍。

Gated Graph Sequence Neural Networks

这篇文章发表于2016年的ICLR。本文的主要贡献是为GNN提供了一种输出序列，而传统GCN则一般解决的是图级别的分类任务，而不是输出序列结果。

在推断过程中，作者引入了与节点label相关的node annotation，提出的推断过程如下：

并定义图级别的表示为：

可以看到，作者将神经网络之间的推断则是基于LSTM中的输入门、输出门、隐藏门等门模型来实现更新。作者另外描述了一种基于门的图序列神经网络模型（GGS-NN模型），这每个GG-NN模型都会产生一个输出序列，整个GGS-NN模型的结构如下：

这种序列输出的结果可以很好地解决输出序列生成的问题。由于这种方法可以高效生成序列，因此这种输出序列的模型可以被应用于自然语言生成等多种实际任务。本文的实验也是测试文本因果关系的数据。

Graph Attention Netowrks

本文是基于attention机制的新型的神经网络结构，通过引入self-attention机制，其克服了GCN中的邻居聚集过程未加权的结果。

同样地，在传统的图推断过程中，其引入了一个简单的图Attention层。通过定义一系列输入的节点特征，输出特征，另外定义权重矩阵，并且定义一个共享的attention过程，定义的attention 系数为：

那么，为了定义边的权重，也就是attention系数可以用Softmax+LeakyRelu函数：

其中 || 定义为连接操作。整体结构的模型如图8所示：

图8 左侧为attention机制的原理，主要是连接+LeakyRelu+Softmax得到attention系数

单head的更新如下：

当使用个独立的attention机制进行操作时，即为 -head attention机制。多head的更新推断如下：

相比较而言，GAT更具有高效的计算性，并且为每个节点提供了加权的重要性。在实验中，作者测试了几个比较有名的引文数据集，并且建立了一系列基于图的任务进行测试，在分类任务上体现出了比GCN更好的效果。

Inductive Representation Learning on Large Graphs

本文主要介绍了一种在图上的推理学习方法。在介绍本文之前需先了解Transductive Learning 以及Inductive Learning。

在图数据中，transductive的方法指的是需要在训练之前必须了解图的所有节点和边的特征的方法，而作者提出的GraphSAGE模型则是一种推理框架，在训练过程中利用了已有的节点和边的信息来推断位置数据的Embedding结果。在本文中作者是通过采样和聚集邻居节点的特征来生成embedding的结果，并不需要知道全局的节点信息。因此，GraphSAGE可以应用在大规模的图数据上。