入门提问 || 为什么要进行图嵌入Graph embedding?
为什么要进行图嵌入Graph embedding?
|本文较长，预计阅读时间为14分钟，本文参考文章[9]的大纲，对其中的部分内容进行修改和补充
Graph广泛存在于真实世界的多种场景中，即节点和边的集合。比如社交网络中人与人之间的联系，生物中蛋白质相互作用以及通信网络中的IP地址之间的通信等等。除此之外，我们最常见的一张图片、一个句子也可以抽象地看做是一个图模型的结构，图结构可以说是无处不在。
对于Graph的研究可以解决下面的一些问题：比如社交网络中新的关系的预测，在QQ上看到的推荐的可能认识的人；生物分子中蛋白质功能、相互作用的预测；通信网络中，异常事件的预测和监控以及网络流量的预测。如果要解决以上的问题，我们首先需要做的是对图进行表示，graph embedding 是中非常有效的技术。
1.什么是图嵌入（graph embedding）？
图嵌入是一种将图数据（通常为高维稠密的矩阵）映射为低微稠密向量的过程，能够很好地解决图数据难以高效输入机器学习算法的问题。图嵌入需要捕捉到图的拓扑结构，顶点与顶点的关系，以及其他的信息，如子图，连边等。如果有更多的信息被表示出来，那么下游的任务将会获得更好的表现。嵌入的过程中有一种共识：向量空间中保持连接的节点彼此靠近。基于此，研究者提出了拉普拉斯特征映射（Laplacian Eigenmaps）和局部线性嵌入（Locally Linear Embedding ，LLE）。
图嵌入：
http://www.perozzi.net/publications/14_kdd_deepwalk.pdf
总的来说大致可以将图上的嵌入分为两种：节点嵌入和图嵌入。当需要对节点进行分类，节点相似度预测，节点分布可视化，一般采用节点的嵌入；当需要在图级别上进行预测或者预测整个图结构，我们需要将整个图表示为一个向量。
后面将会介绍一下经典的方法如DeepWalk, node2vec, SDNE和graph2vec.
2.为什么要使用图嵌入？
图是数据的有意义且易于理解的表示形式，但是出于下面的原因需要对图进行嵌入表示。
在graph直接进行机器学习具有一定的局限性，我们都知道图是由节点和边构成的，这些向量关系一般只能使用数学，统计或者特定的子集进行表示，但是嵌入之后的向量空间具有更加灵活和丰富的计算方式；
图嵌入能够压缩数据， 我们一般用邻接矩阵描述图中节点之间的连接。连接矩阵的维度是|V| x |V|，其中|V| 是图中节点的个数。矩阵中的每一列和每一行都代表一个节点。矩阵中的非零值表示两个节点已连接。将邻接矩阵用用大型图的特征空间几乎是不可能的。一个具有1M个节点和1Mx1M的邻接矩阵的图该怎么计算和表示呢？但是嵌入可以看做是一种压缩技术，能够起到降维的作用；
向量计算比直接在图上操作更加的简单、快捷。
但是图嵌入也需要满足一定的需求
属性选择：确保嵌入能够很好地描述图的属性。它们需要表示图拓扑，节点连接和节点邻域。预测或可视化的性能取决于嵌入的质量；
可扩展性：大多数真实网络都很大，包含大量节点和边。嵌入方法应具有可扩展性，能够处理大型图。定义一个可扩展的模型具有挑战性，尤其是当该模型旨在保持网络的全局属性时。网络的大小不应降低嵌入过程的速度。一个好的嵌入方法不仅在小图上高效嵌入，同时也需要在大图上能够高效地嵌入；
嵌入的维度：实际嵌入时很难找到表示的最佳维数，维度越大能够保留的信息越多，但是通常有更高的时间和空间复杂度。较低的维度虽然时间、空间复杂度低，但无疑会损失很多图中原有的信息。
3.图嵌入方法
节点的嵌入借鉴了word2vec的方法，该方法能够成立的原因是：图中的节点和语料库中的单词的分布都遵循幂定律。
http://www.perozzi.net/publications/14_kdd_deepwalk.pdf
在介绍图嵌入的方法之前首先简单回顾一下在文本领域的Word2Vec【3】和skip-gram模型，如果比较熟悉，可以直接跳过。
Word2vec是一种将单词转换为嵌入向量的嵌入方法。相似的词应具有相似的嵌入。Word2vec使用skip-gram网络，这是具有一层隐藏层的神经网络（总共三层）。skip-gram模型是给出某一词语来预测上下文相邻的单词。下图显示了输入单词（标有绿色）和预测单词的示例。通过此任务，作者实现了两个相似的词具有相似的嵌入，因为具有相似含义的两个词可能具有相似的邻域词。
下图是skip-gram模型。网络的输入为one-hot编码，长度与单词字典的长度相同，只有一个位置为1，输出为单词的嵌入表示：
https://towardsdatascience.com/graph-embeddings-the-summary-cc6075aba007
下面介绍三个节点嵌入（node embedding）的方法，一个图嵌入(graph embedding)的方法，这些方法都类似Word2vec的嵌入原理。
3.1节点嵌入方法（Node embeddings）
下面介绍三种经典的节点嵌入的方法：DeepWalk【2】, Node2vec【8】, SDNE【7】。
3.1.1 DeepWalk
DeepWalk通过随机游走(truncated random walk)学习出一个网络的表示，在网络标注顶点很少的情况也能得到比较好的效果。随机游走起始于选定的节点，然后从当前节点移至随机邻居，并执行一定的步数，该方法大致可分为三个步骤：
采样：通过随机游走对图上的节点进行采样,在给定的时间内得到一个节点构成的序列，论文研究表明从每个节点执行32到64次随机遍历就足够表示节点的结构关系； 训练skip-gram：随机游走与word2vec方法中的句子相当。文本中skip-gram的输入是一个句子，在这里输入为自随机游走采样得到了一个序列，进一步通过最大化预测相邻节点的概率进行预测。通常预测大约20个邻居节点-左侧10个节点，右侧10个节点； 计算嵌入。
https://towardsdatascience.com/graph-embeddings-the-summary-cc6075aba007
DeepWalk通过随机游走去可以获图中点的局部上下文信息，因此学到的表示向量反映的是该点在图中的局部结构，两个点在图中共有的邻近点（或者高阶邻近点）越多，则对应的两个向量之间的距离就越短。但是DeepWalk方法随机执行随机游走，这意味着嵌入不能很好地保留节点的局部关系，Node2vec方法可以解决此问题。
3.1.2 Node2vec
Node2vec是DeepWalk的改进版，定义了一个bias random walk的策略生成序列，仍然用skip gram去训练。
https://towardsdatascience.com/graph-embeddings-the-summary-cc6075aba007
该算法引入了参数P和Q，参数Q关注随机游走中未发现部分的可能性，即控制着游走是向外还是向内: 若Q>1，随机游走倾向于访问接近的顶点(偏向BFS); 若Q<1，倾向于访问远离的顶点(偏向DFS)。
参数P控制了随机游走返回到前一个节点的概率。也就是说，参数P控制节点局部关系的表示，参数Q控制较大邻域的关系。
3.1.3 SDNE
SDNE没有采用随机游走的方法而是使用自动编码器来同时优化一阶和二阶相似度，学习得到的向量表示保留局部和全局结构，并且对稀疏网络具有鲁棒性, 那么什么是一阶和二阶相似度？
一阶相似度表征了边连接的成对节点之间的局部相似性。如果网络中的两个节点相连，则认为它们是相似的。举个例子：当一篇论文引用另一篇论文时，意味着它们很可能涉及相似的主题，如6和7。但是当两个节点不相连时如5和6，他们就不具有相似度了吗？显然不是，从图上可以看出来他们虽然没有直接连接，但是他们有共同的邻居1,2,3,4，那么这时候就需要用二阶相似度来衡量了。
https://arxiv.org/abs/1503.03578
二阶相似度表示节点邻域结构的相似性，它能够了表征全局的网络结构。如果两个节点共享许多邻居，则它们趋于相似。
https://www.kdd.org/kdd2016/papers/files/rfp0191-wangAemb.pdf
SDNE的具体做法是使用自动编码器来保持一阶和二阶网络邻近度。它通过联合优化这两个近似值来实现这一点。该方法利用高度非线性函数来获得嵌入。模型由两部分组成：无监督和监督。前者包括一个自动编码器，目的是寻找一个可以重构其邻域的节点的嵌入。后者基于拉普拉斯特征映射，当相似顶点在嵌入空间中彼此映射得很远时，该特征映射会受到惩罚。
3.2图嵌入方法
关于整个图嵌入的方式这里介绍具有代表性的graph2vec。
图嵌入是将整个图用一个向量表示的方法，Graph2vec同样是基于skip-gram思想，把整个图编码进向量空间, 类似文档嵌入doc2vec, doc2vec在输入中获取文档的ID，并通过最大化文档预测随机单词的可能性进行训练。
https://towardsdatascience.com/graph-embeddings-the-summary-cc6075aba007
Graph2vec同样由三个步骤构成：
采样并重新标记图中的所有子图。子图是出现在所选节点周围的一组节点。
训练skip-gram模型。类似于文档doc2vec, 由于文档是单词集，而图是子图集，在此阶段，对skip-gram模型进行训练。经过训练，可以最大程度地预测输入中存在于图中的子图的概率。
计算。通过在输入处提供子图的id索引向量来计算嵌入。
https://www.groundai.com/project/graph2vec-learning-distributed-representations-of-graphs/1
3.3其他的方法
以上提到了四个常用的方法，但是除此之外还有非常多的方法和模型值得学习
Node embedding: LLE, Laplacian Eigenmaps, Graph Factorization, GraRep, HOPE, DNGR, GCN, LINE
Graph embedding approaches: Patchy-san, sub2vec (embed subgraphs), WL kernel andDeep WL kernels
总结
本文介绍了Graph embedding是什么，为什么要采用Graph embedding，以及进行embedding时需要满足的性质。进一步简单介绍了node-level的三个经典的方法：DeepWalk, node2vec, SDNE以及graph-levle的graph2vec，下期将梳理GCN, GAT, GraphSage, GIN等工作，欢迎关注。
参考：
[1] C. Manning, R. Socher, Lecture 2 | Word Vector Representations: word2vec (2017), YouTube.
[2] B. Perozzi, R. Al-Rfou, S. Skiena, DeepWalk: Online Learning of Social Representations (2014), arXiv:1403.6652.
[3] C. McCormick. Word2Vec Tutorial — The Skip-Gram Model (2016), http://mccormickml.com.
[4] T. Mikolov, K. Chen, G. Corrado, J. Dean, Efficient Estimation of Word Representations in Vector Space (2013), arXiv:1301.3781.
[5] A. Narayanan, M. Chandramohan, R. Venkatesan, L. Chen, Y. Liu, S. Jaiswal, graph2vec: Learning Distributed Representations of Graphs (2017),
arXiv:1707.05005.
[6] P. Goyal, E. Ferrara, Graph Embedding Techniques, Applications, and Performance: A Survey (2018), Knowledge-Based Systems.
[7] D. Wang, P. Cui, W. Zhu, Structural Deep Network Embedding (2016), Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining.
[8] A. Grover, J. Leskovec, node2vec: Scalable Feature Learning for Networks (2016), Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining.
[9] https://towardsdatascience.com/graph-embeddings-the-summary-cc6075aba007
[10] https://www.groundai.com/project/graph2vec-learning-distributed-representations-of-graphs/1