网络表征学习综述

广而告之

SIGAI飞跃计划第二期下周开班！

SIGAI-AI学习交流群的目标是为学习者提供一个AI技术交流与分享的平台。操作指引：关注本微信公众号，回复“芝麻开门”，即可收到入群二维码，扫码即可。

同时在本微信公众号中，回复“SIGAI”+日期，如“SIGAI0515”，即可获取本期文章的全文下载地址（仅供个人学习使用，未经允许，不得用于商业目的）。

SIGAI 特邀作者：VicFig

研究方向：机器学习，图像处理

背景

当前机器学习在许多应用场景中已经取得了很好的效果，例如人脸识别与检测、异常检测、语音识别等等，而目前应用最多最广泛的机器学习算法就是卷积神经网络模型。但是大多应用场景都是基于很结构化的数据输入，比如图片、视频、语音等，而对于图结构（网络结构）的数据，相对应的机器学习方法却比较少，而且卷积神经网络也很难直接应用到图结构的数据中。在现实世界中，相比图片等简单的网格结构，图结构是更泛化的数据结构，比如一般的社交网络、互联网等，都是由图这种数据结构表示的，图的节点表示单个用户，图的边表示用户之间的互联关系。针对网络结构，用向量的数据形式表示网络结构、节点属性的机器学习方法就是网络表征学习。

图的邻接矩阵是将边的信息表示成了N*N的矩阵（N为节点个数）通过邻接矩阵可以将图重建，那么是否可以直接用邻接矩阵的列向量作为图节点的表示向量呢？其实是可以的，但是这种表示形式有两个问题：第一，图结构中，任意两个节点不一定是相连的，通常一个节点仅有很少的邻居，因此邻接矩阵是稀疏矩阵，倘若节点数目很多（如社交网络，用户可能达百万级甚至更多），以邻接矩阵直接表示图结构将非常不划算。第二，邻接矩阵仅仅表示了边的信息，而无法加入节点的本身属性，在当前的很多应用中，我们不仅仅需要表示图的结构属性，而且还伴随着节点本身的属性（比如社交网络中，每个用户的性别，年龄，爱好等）综合以上两点问题，网络表征学习的目的就有了两个：第一，我们要学习一种低维度的向量表示网络节点，将节点映射到相应的向量空间，这种网络表征学习就是关于图结构的网络表征学习，也称网络嵌入；第二，我们的表示不仅仅可以表征网络结构，同时也可以表征节点本身自带的属性，这种表征学习，就是伴随节点属性的网络表征学习。通常第二种表征学习方法都是从第一种方法中推广而来。

传统网络分析 VS. 网络表征学习【1】

关于图结构的网络表征学习

关于图结构的网络表征学习重点关注的是网络的拓扑结构与性质，是网络表征学习中最基本的一类方法，其目的在于如何得到节点在低维空间中的向量表示，使得向量之间的关系可以保持图结构中节点之间的结构关系。同时，我们需要确定向量之间距离的一种度量方式，用来表征对应节点之间的相似性。

节点之间的结构关系就是边的连接，比如直接邻居节点，就应该比二阶邻居（邻居的邻居）或高阶邻居（邻居的邻居的…）与原本节点的关系更紧密，因为直接邻居与原节点有边的直接连接。这种紧密关系应该可以用向量的距离来表示。节点之间的性质关系，则对应在边的性质。首先是边的权重，如果两个向量距离较小，那么在原图中对应两个节点之间边的权重越小（也可能越大，权重表示距离则权重越小；权重表示相似度则权重越大）。其次是边的方向，在无向图中边仅代表连接，但对于有向图，边的指向将影响节点之间的连接方式。下面我将介绍几种常见且有效的网络表征方法。

DeepWalk

DeepWalk【2】是KDD 2014的一篇文章，这种方法的核心思想是，采用随机游走的方式，将网络结构节点之间的关系转化成句子，那么不同节点就代表不同的词，然后用自然语言处理中Word2Vec的方法得到节点的低维度向量表示。那么这种方法其实就是分两步：随机游走，和词向量表示学习。我们分别来看看这两步操作到底是什么：

随机游走就是在网络结构中，以某个节点做起点，然后以一定的概率随机移动到其邻居位置，再从邻居位置随机移动，直到走t步（t是预先设定好的参数），于是得到一个由t个“词”（节点）组成的“句子”（序列）。图中每个节点都要作为起点做随机游走，设有N个节点；且每个节点都要做r次随机游走，那么最后就可以得到N*r个“句子”，每个“句子”都是由t个“词”组成。

接下来是词向量表示学习的方法，原工作中使用Skip-gram的方法学习词向量表示，具体思想类似于极大似然概率：比如现在有一个随机游走得到的句子（序列） A B C D E，每个字母代表一个词（节点），这个句子共5个词。这个句子之所以出现，是因为这种词的顺序是常见的形式（比如我们只能从一群学生中抽1个学生，问他考试前是否复习，如果这个同学说复习，那么我们就会更倾向于相信在这个群体中，考试动作之前会发生复习动作的概率更大），所以我们可以认为C词很大概率就是与B词和D词相邻的，我们以C词的词向量作为输入，那么其邻居词中，B词和D词出现的概率就应该更高，也就是P(邻居是B词和D词 | 输入为C词的词向量)的值应该更高，那么我们就应该更新C词的词向量，使得上述的条件概率最大。其更新公式如下所示：

Node2Vec

Node2Vec【3】是KDD 2016的一篇文章，Node2Vec的方法同样也是采用了随机游走和Skip-gram的学习方法，主要的创新点在于随机游走的策略。在 Node2Vec方法中对随机游走向邻节点转移的概率做了调整。

Node2Vec偏置示意图【3】

图中t是上一次走的节点，v是当前节点，α是一个偏置，影响最终的转移概率，转移概率的公式如下：

式中为边的权重，πvx表示转移概率。由图可知，v点回到t点转移概率的偏置设为1/p，v点向x1点（既与v相连，又与t相连）转移概率的偏置设为1，v点向其他点转移概率的偏执设为1/q

这种方法的好处是结合了BFS（p控制）与DFS（q控制）来做随机游走（DeepWalk方法是基于DFS的）以两个参数p，q来控制，得到的序列可以更全面地表示网络结构中节点的邻居关系。

LINE

LINE方法由2015年发表在WWW会议上的论文【4】提出来。首先我们需要使用卷积神经网络模型对节点提特征，得到节点的低维向量表示，那么究竟怎样的低维向量表示是更好的呢？作者提出了两种相似度的衡量方式：一阶相似度和二阶相似度，其中一阶相似度表示节点与直接邻居之间的相似性，二阶相似度表示节点与高阶邻居之间的相似性。原本网络结构中边的连接和权重表示了节点之间的相似性，在这里不妨设权重越大，表示两个节点越相近。那么我们得到的低维向量表示，也一定需要符合原结构中各个节点的相似性关系。

一阶邻节点与二阶邻节点【4】

首先我们来看看一阶相似度。式中，是根据网络边的权重计算出的节点之间相似度，是连接节点i，j边的权重。其本质是选中i，j两个节点的经验概率。

而节点的低维向量的内积，可以用来衡量两个向量的相似度（距离），式中使用了sigmoid函数，将向量的内积映射到[0，1]之间。也可以表示i，j两个节点同时出现的联合概率

接下来作者以KL散度，来衡量两个概率分布的距离作为损失函数，并通过BP算法更新卷积神经网络的参数。优化函数如下所示

对于二阶相似度，首先求得在节点i出现的条件下，节点j出现的条件概率，即从i出发，能到达j的条件概率；然后求得网络结构中两个节点的经验条件概率，始终的分母表示i点的度；最后同样利用KL散度表示两个分布的差异，求得优化函数如下。

最后我们可以将一阶相似度和二阶相似度结合在一起，共同训练卷积神经网络的参数。

SDNE

论文【8】提出了一种半监督模型来做图嵌入，引入了自动编码机的模型架构，以邻接矩阵中第i个列向量表示节点i，设为，输入编码器，得到低维的

SDNE模型结构

编码向量设为yi，那么对于原图结构中相连的节点i，j，对应的编码向量的距离应该很小，因此这里引入一个监督学习的目标函数

式中表示邻接矩阵中i，j两个节点的连接情况。同时我们还需要训练解码器，使得解码得到的输出设为，与输入xi相同，于是引入了无监督学习的损失函数

但是由于输入xi为邻接矩阵的列向量，其中会有很多0元素，我们更希望要求输出与输入在非0元素处的值相近，即最好保证原始边的权重不变，因此在上式中加入了一个惩罚因子∈ R，使损失函数在非0处不同的值有更大的惩罚项。

于是总损失函数包含三个部分：监督学习的损失函数L1、无监督学习的损失函数L1，以及参数正则化项

最终我们编码器的输出即为对节点i的向量表示。

伴随节点属性的网络表征学习

伴随节点属性的网络表征学习，则是在关于图结构的网络表征学习基础上，加入了节点本身的属性，例如社交用户组成的网络，每个节点表示一个用户，同时每个用户有其自己的属性，比如年龄、性别、星座、爱好等，我们其实最需要的是节点本身的属性，但经常我们得到的标签可能并不完全精准或全面，而网络中边的存在，使用户之间的信息可以得到交流，我们可以通过邻居的节点属性，更新原节点的属性，可以得到相对更精准或全面的节点属性，在推荐系统等方面有着很好的应用前景。

伴随节点属性的网络表征学习方法，通常都是由关于图结构的网络表征学习方法变体而来，这里我将主要介绍图卷积的方法，将神经网络应用在网络结构中。

一般的网格结构，如图片，可以看作网络结构的一种特殊形式：一个像素点表示一个节点，而相邻的像素点表示互联的邻居。这种结构的特殊性在于每个节点的邻居个数是固定的（每个节点有6个邻居，H,W,C维度各2个），所以神经网络的卷积可以很轻松地做到参数共享。而对于一般网络结构的节点，其邻居个数是不固定的，因此普通的神经卷积网络很难直接应用其中。最近几年研究者提出图卷积的操作，并逐渐进行改进，最终取得了很好的效果。

图谱域的图卷积

起初图卷积是在图谱域计算的。两个时域信号的卷积，在频域上是相乘的关系；两个图片的卷积，也可以通过二维傅立叶变换转化成频域的乘法。因此研究者定义了图结构数据的傅立叶变换，将图从节点域转换到图谱域，那么图卷积就可以通过图谱域上的乘法来实现。如果大家想详细了解图卷积的理论知识的话，可以参考论文【5】，或者网址【6】中的回答。

首先类比连续信号的傅立叶变换()= F[()]=∫()−，其中−是拉普拉斯算子的特征函数，那么对于图结构，拉普拉斯矩阵数学意义上等同于离散的拉普拉斯算子，我们找到拉普拉斯矩阵的特征向量和特征值=−1=（的列向量是单位特征向量，为特征值的对角矩阵），那么图的傅立叶变换即为=⋅。最终图卷积可以表示为图谱域的乘法，再做逆傅立叶变换得到节点域的结果

我们设= (⋅ h)为卷积核，将向量点乘转化为与对角矩阵的乘法，卷积层的输出可以表示为

式中{}表示激活函数。这就是最初的图卷积操作流程，这个初版本的图卷积有两个很大问题：第一，每次前向传播都需要计算⋅ () ⋅；第二，参数个数与节点个数相同，倘若网络复杂，节点个数达百万级，则卷积参数将非常大。因此论文【7】提出了图卷积的改进版

节点域的图卷积

设

经过简化，则有

通过对参数的近似，将卷积从图谱域的计算简化到节点域，省去了计算⋅() ⋅的操作，同时将参数个数从节点个数减少到K个，K是预先设定的参数。在节点域上这种简化的卷积操作本质上表示K阶邻居的属性向量，按权重影响当前节点的属性向量。下图中表示K=1时（仅有一阶邻居影响当前节点属性向量）的更新操作。

红色节点的一阶邻居用来更新该节点

以上的方法，都是从图谱理论出发，通过推导得到的计算过程，改进版的GCN方法实现了节点域的卷积操作，上述方法中的K类似于传统CNN中的kernel_size，决定了卷积核的感受野（每个节点的感受野中节点数目很可能是不相同的，因为每个节点的邻居个数不是固定的）。

除此之外，还有一种更加直观，直接从节点域出发的计算卷积方法：我们固定每个节点的感受野中只有M个节点，然后对每个节点计算其他节点与它的距离（一阶邻居可以直接使用边的权重；高阶邻居则需要额外的距离函数），并按照距离进行排序，选取前M个最近的节点作为感受野中的节点。这种方法中参数个数为M个，同样也是在节点域执行了卷积操作，但这种方法的最大难点在于如何选取鲁棒性强的距离函数。

小结

当前网络表征学习仍是正在研究中的热门课题之一，网络作为更加泛化的数据形式，其结构的复杂度也远高于普通的网格结构（图片）。为了挖掘网络结构本身的性质，出现了关于图结构的网络表征学习，研究着重于节点之间的拓扑结构关系。但是网络中蕴藏的信息不仅仅是拓扑关系，更重要的是每个节点自己的属性，因此从关于图结构的网络表征学习中，衍生出伴随节点属性的网络表征学习，起目的是利用网络中节点的拓扑关系，确定或完善每个节点本身的属性信息。

参考文献

【1】 王啸 崔鹏 朱文武. 网络表征学习中的基本问题初探[J] 中国计算机学会通讯. 2018.

【2】 Perozzi, Bryan, Rami Al-Rfou, and Steven Skiena. "Deepwalk: Online learning of social representations." Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2014.

【3】 Grover, Aditya, and Jure Leskovec. "node2vec: Scalable feature learning for networks." Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2016.

【4】 Tang, Jian, et al. "Line: Large-scale information network embedding." Proceedings of the 24th International Conference on World Wide Web. International World Wide Web Conferences Steering Committee, 2015.

【5】 Bruna, Joan, et al. "Spectral networks and locally connected networks on graphs." arXiv preprint arXiv:1312.6203 (2013).

【6】 https://www.zhihu.com/question/54504471

【7】 Defferrard, Michaël, Xavier Bresson, and Pierre Vandergheynst. "Convolutional neural networks on graphs with fast localized spectral filtering." Advances in Neural Information Processing Systems. 2016.

【8】 Wang, Daixin, Peng Cui, and Wenwu Zhu. "Structural deep network embedding." Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2016.