机器之心原创
作者：朱梓豪
编辑：QingLin
如果说年机器学习领域什么方向最火，那么必然有图神经网络的一席之地。其实早在很多年前，图神经网络就以图嵌入、图表示学习、网络嵌入等别名呈现出来，其实所有的这些方法本质上都是作用在图上的机器学习。本文将根据近两年的综述对图网络方法做一个总结，为初入图世界的读者提供一个总体的概览。
本文作者朱梓豪为中科院信工所在读硕士，主要研究方向为图神经网络、视觉问答、视觉对话等。
什么是图
图是一种常见的数据结构，用于表示对象及其之间的关系。其中，对象又称节点（node）或顶点（vertex），关系用边（edge）来描述。在数学上一般用G=(V,E,A,X)来表示，其中V={v1,v2……,vn}是节点集合，E=e_ij表示边的集合，A是大小为
V
×
V
的邻接矩阵，用于表示节点之间的连接关系，如果e_ij∈E，则A_ij=1，X是大小为
V
×d的特征矩阵，X的第i行X_i:表示第i个节点的属性特征，其中d是属性的维度。
为何需要在图上应用机器学习方法
图是一种描述和建模复杂系统的通用语言，在真实世界中无处不在。例如，Facebook、Twitter等社交媒体构成了人类之间的社交网络(SocialNetwork)；人体中的蛋白质分子构成了生物网络(BiologicalNetwork)；各种移动终端构成了通信网络(CommunicationNetwork)；智能硬件之间构成了物联网(Internet-of-Things)、城市间的公路、铁路、航线构成了运输网络(TransportationNetwork)等等。因此也催化出一系列在图上进行数据挖掘的任务，如为用户推荐感兴趣的好友、判断蛋白质结构、预测交通流量、检测异常账户等等。但是真实图的数据量庞大，动辄上亿节点、而且内部拓扑结构复杂，很难将传统的图分析方法如最短路径、DFS、BFS、PageRank等算法应用到这些任务上。鉴于机器学习在图像、文本领域的广泛应用，一部分研究者尝试将机器学习方法和图数据结合起来，逐渐成为机器学习领域的一股热潮。
网络表示学习、图嵌入的定义
俗话说「巧妇难为无米之炊」，再强大的机器学习算法也需要数据进行支持。在同样的数据集和任务上，由于特征的不同，同一个算法的结果也可能会有天壤之别。由于特征的选择对结果的决定性作用，很多数据挖掘方面的研究工作把重心放到了针对特定的数据由人工设计出有价值的特征上。
深度学习本质上是一种特征学习方法，其思想在于将原始数据通过非线性模型转变为更高层次的特征表示，从而获得更抽象的表达。与人工设计特征不同，深度学习会自动从数据中学习出特征表示，所以又称为表示学习（RepresentationLearning）。如图像分类，输出的一张高维的图片，经过一系列的卷积池化等操作，低层可以抽取出低级的特征（轮廓、颜色）、较深的层会根据低级特征学习到更高级的特征，然后变换成一个向量通过全连接层进行分类，这个向量就是输入图像的特征表示。
一个很自然的想法就是，既然直接在图上直接应用机器学习方法比较困难，那么能否先将节点或边用低维向量表示出来，然后在这些向量上应用已经很成熟的机器学习算法。这种将图中节点嵌入到低维欧式空间中的方法就叫做图嵌入（GraphEmbedding）。
其实、图嵌入、网络嵌入、图表示学习、网络表示学习这些名词指的的都是同一个概念。给定图$G=(\mathbf{V,E,A,X})$，图嵌入需要学习从节点到向量的映射：$f:v_i\to\mathbf{y}_i\inR^d$，其中$d
V
$，$f$需要尽可能的保留住节点的结构信息和属性信息。
图嵌入方法的分类
图数据最大的特点在于节点之间存在着链接关系，这表明图中节点之间并非完全独立。除了节点间的链接关系，节点自身也可能含有信息，比如互联网中网页节点对应的文本信息，这些特性使得图嵌入需要考虑很多的因素。从训练所需的信息来看，一般有三种主要的信息源：图结构、节点属性和节点标签，可基于此分成无监督图嵌入和半监督图嵌入；还有一种是根据输入数据的不同进行划分，比如按照边的方向性、是否是异构网络等性质。然而这两种划分依据并不合适，因为当前图嵌入算法的主要区别在于算法类型，同一算法类型下的框架都是相似的，因此本文基于Hamilton等[1]和Goyal等[2]两篇关于图嵌入的综述，将图嵌入方法概括为基于矩阵分解的图嵌入、基于随机游走的图嵌入、基于神经网络的图嵌入（即图神经网络）。
基于矩阵分解的图嵌入
基于矩阵分解的方法是将节点间的关系用矩阵的形式加以表示，然后分解该矩阵以得到嵌入向量。通常用于表示节点关系的矩阵包括邻接矩阵、拉普拉斯矩阵、节点转移概率矩阵、节点属性矩阵等。根据矩阵的性质不同适用于不同的分解策略。主要包括LocalLinearEmbedding（LLE）[3]、LaplacianEigenmaps[4]、SPE[5]、GraRep[6]等。
LLE算法其实是流形学习的一种，LLE算法认为每一个数据点都可以由其邻域节点的线性加权组合构造得到。降维到低维空间后，这种线性关系仍然得到保留。LaplacianEigenmaps和LLE有些相似，直观思想是希望相互间有关系的点（在图中相连的点）在降维后的空间中尽可能的靠近。为了使得输入图的嵌入是低维表示并且保留图全局拓扑结构，Shaw等[5]提出在欧式空间中嵌入图的结构保留嵌入方法（SPE，StructurePreservingEmbedding），学习由一组线性不等式约束的低秩核矩阵，用于捕获输入图结构。SPE在图的可视化和无损压缩方面获得明显改善，优于LaplacianEigenmaps等方法。Cao等[6]认为考虑节点之间的k阶关系对把握网络的全局特征非常重要，考虑越高阶的关系，得到的网络表示效果会越好。GraRep通过SVD分解分别学习节点的k阶表示，然后将其结合起来作为最终的表示，这样可以很好地捕捉到远距离节点之间的关系。
基于随机游走的方法
随机游走方法已经被用来近似图的许多属性，包括节点中心性和相似性等。当图的规模特别大或者只能观察到部分图的时候，随机游走就变得非常有用。有研究者提出了利用图上随机游走来获取节点表示的嵌入技术，其中最著名的就是DeepWalk[7]和node2vec[8]。
DeepWalk是基于word2vec词向量提出来的。word2vec在训练词向量时，将语料作为输入数据，而图嵌入输入的是整张图，两者看似没有任何关联。但是DeepWalk的作者发现，预料中词语出现的次数与在图上随机游走节点被访问到底的次数都服从幂律分布。因此DeepWalk把节点当做单词，把随机游走得到的节点序列当做句子，然后将其直接作为word2vec的输入来得到节点的嵌入表示。其框架如图1所示，首先采用随机游走的方法产生标准的输入序列，用SkipGram模型对序列建模得到节点的向量表示，然后使用分层softmax解决节点高维度输出问题。DeepWalk模型的提出为图嵌入提出了一种新的研究思路，也算是引发了对图嵌入研究的热潮。
图一
node2vec通过改变生成随机游走序列的方式改进了DeepWalk算法。DeepWalk是按照均匀分布随机选取随机游走序列的下一个节点。node2vec同时考虑了广度优先搜索(BFS)和深度优先搜索(DFS)。Grover等发现，广度优先搜索注重刻画网络中的局部特征，而深度优先搜索能更好地遍历整个网络，反映了节点间的同质性。特别地，node2vec引入searchbias函数来平衡这两种采样方式，通过参数p和q来调整下一步的跳转概率。
其他基于随机游走的方法还包括Walklets、LsNet2vec、TriDNR、HARP、DDRW等等。
基于神经网络的图嵌入（图神经网络）
还有一类方法是将神经网络和图结合起来的图表示学习方法，也是最近一年来最火的方向之一，我们统称为图神经网络。机器之心已经为其做过了全面的介绍，具体请参见：深度学习时代的图模型，
清华发文综述图网络、清华大学图神经网络综述：模型与应用、图神经网络概述第三弹：来自IEEEFellow的GNN综述。主要将其分为图卷积网络、图注意力网络、图生产网络、图时空网络、图自编码器。又可以分为基于谱的方法和基于空间的方法。由于基于谱的方法需要分解矩阵特征向量，因此绝大多数新提出的方法都是基于空间，也就是如何传播并聚合节点和边的信息。图像和文本本质上是有规则的格栅结构的图，因此，很自然想到可以将已经在CV、NLP领域成功应用的模型拓展到图上，如词向量和图卷积。最近，也出现了基于胶囊的图神经网络和基于图像语义分割U-Net模型的GraphU-Net。
注意力机制的在图嵌入的应用
有一部分研究者将注意力(attention)机制引入到了图神经网络中。注意力机制的本质是从人类视觉注意力机制中获得灵感。大致是我们视觉在感知东西的时候，一般不会是一个场景从到头看到尾全部都看，而是根据需求观察特定的一部分。这意味着，当人们注意到某个目标或某个场景时，该目标内部以及该场景内每一处空间位置上的注意力分布是不一样的。而且当我们发现一个场景经常在某部分出现自己想观察的东西时，我们就会进行学习在将来再出现类似场景时把注意力放到该部分上。更通用的解释就是，注意力机制是根据当前的某个状态，从已有的大量信息中选择性的