为什么要进行图嵌入Graph embedding?|本文较长，预计阅读时间为14分钟，本文参考文章[9]的大纲，对其中的部分内容进行修改和补充 Graph广泛存在于真实世界的多种场景中，即节点和边的集合。比如社交网络中人与人之间的联系，生物中蛋白质相互作用以及通信网络中的IP地址之间的通信等等。除此之外，我们最常见的一张图片、一个句子也可以抽象地看做是一个图模型的结构，图结构可以说是无处不在。 对于Graph的研究可以解决下面的一些问题：比如社交网络中新的关系的预测，在QQ上看到的推荐的可能认识的人；生物分子中蛋白质功能、相互作用的预测；通信网络中，异常事件的预测和监控以及网络流量的预测。如果要解决以上的问题，我们首先需要做的是对图进行表示，graph embedding 是中非常有效的技术。 1.什么是图嵌入（graph embedding）？图嵌入是一种将图数据（通常为高维稠密的矩阵）映射为低微稠密向量的过程，能够很好地解决图数据难以高效输入机器学习算法的问题。图嵌入需要捕捉到图的拓扑结构，顶点与顶点的关系，以及其他的信息，如子图，连边等。如果有更多的信息被表示出来，那么下游的任务将会获得更好的表现。嵌入的过程中有一种共识：向量空间中保持连接的节点彼此靠近。基于此，研究者提出了拉普拉斯特征映射（Laplacian Eigenmaps）和局部线性嵌入（Locally Linear Embedding ，LLE）。 图嵌入： http://www./publications/14_kdd_deepwalk.pdf 总的来说大致可以将图上的嵌入分为两种：节点嵌入和图嵌入。当需要对节点进行分类，节点相似度预测，节点分布可视化，一般采用节点的嵌入；当需要在图级别上进行预测或者预测整个图结构，我们需要将整个图表示为一个向量。
2.为什么要使用图嵌入？图是数据的有意义且易于理解的表示形式，但是出于下面的原因需要对图进行嵌入表示。
但是图嵌入也需要满足一定的需求
3.图嵌入方法节点的嵌入借鉴了word2vec的方法，该方法能够成立的原因是：图中的节点和语料库中的单词的分布都遵循幂定律。 http://www./publications/14_kdd_deepwalk.pdf 在介绍图嵌入的方法之前首先简单回顾一下在文本领域的Word2Vec【3】和skip-gram模型，如果比较熟悉，可以直接跳过。 Word2vec是一种将单词转换为嵌入向量的嵌入方法。相似的词应具有相似的嵌入。Word2vec使用skip-gram网络，这是具有一层隐藏层的神经网络（总共三层）。skip-gram模型是给出某一词语来预测上下文相邻的单词。下图显示了输入单词（标有绿色）和预测单词的示例。通过此任务，作者实现了两个相似的词具有相似的嵌入，因为具有相似含义的两个词可能具有相似的邻域词。 下图是skip-gram模型。网络的输入为one-hot编码，长度与单词字典的长度相同，只有一个位置为1，输出为单词的嵌入表示： https:///graph-embeddings-the-summary-cc6075aba007 下面介绍三个节点嵌入（node embedding）的方法，一个图嵌入(graph embedding)的方法，这些方法都类似Word2vec的嵌入原理。 3.1节点嵌入方法（Node embeddings）下面介绍三种经典的节点嵌入的方法：DeepWalk【2】, Node2vec【8】, SDNE【7】。 3.1.1 DeepWalk
https:///graph-embeddings-the-summary-cc6075aba007 DeepWalk通过随机游走去可以获图中点的局部上下文信息，因此学到的表示向量反映的是该点在图中的局部结构，两个点在图中共有的邻近点（或者高阶邻近点）越多，则对应的两个向量之间的距离就越短。但是DeepWalk方法随机执行随机游走，这意味着嵌入不能很好地保留节点的局部关系，Node2vec方法可以解决此问题。 3.1.2 Node2vec https:///graph-embeddings-the-summary-cc6075aba007 该算法引入了参数P和Q，参数Q关注随机游走中未发现部分的可能性，即控制着游走是向外还是向内: 若Q>1，随机游走倾向于访问接近的顶点(偏向BFS); 若Q<1，倾向于访问远离的顶点(偏向DFS)。 参数P控制了随机游走返回到前一个节点的概率。也就是说，参数P控制节点局部关系的表示，参数Q控制较大邻域的关系。 3.1.3 SDNE 一阶相似度表征了边连接的成对节点之间的局部相似性。如果网络中的两个节点相连，则认为它们是相似的。举个例子：当一篇论文引用另一篇论文时，意味着它们很可能涉及相似的主题，如6和7。但是当两个节点不相连时如5和6，他们就不具有相似度了吗？显然不是，从图上可以看出来他们虽然没有直接连接，但是他们有共同的邻居1,2,3,4，那么这时候就需要用二阶相似度来衡量了。 https:///abs/1503.03578 二阶相似度表示节点邻域结构的相似性，它能够了表征全局的网络结构。如果两个节点共享许多邻居，则它们趋于相似。
SDNE的具体做法是使用自动编码器来保持一阶和二阶网络邻近度。它通过联合优化这两个近似值来实现这一点。该方法利用高度非线性函数来获得嵌入。模型由两部分组成：无监督和监督。前者包括一个自动编码器，目的是寻找一个可以重构其邻域的节点的嵌入。后者基于拉普拉斯特征映射，当相似顶点在嵌入空间中彼此映射得很远时，该特征映射会受到惩罚。 3.2图嵌入方法关于整个图嵌入的方式这里介绍具有代表性的graph2vec。 图嵌入是将整个图用一个向量表示的方法，Graph2vec同样是基于skip-gram思想，把整个图编码进向量空间, 类似文档嵌入doc2vec, doc2vec在输入中获取文档的ID，并通过最大化文档预测随机单词的可能性进行训练。 https:///graph-embeddings-the-summary-cc6075aba007 Graph2vec同样由三个步骤构成：
3.3其他的方法以上提到了四个常用的方法，但是除此之外还有非常多的方法和模型值得学习
总结本文介绍了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://. [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:///graph-embeddings-the-summary-cc6075aba007 [10] https://www./project/graph2vec-learning-distributed-representations-of-graphs/1   |
|
|
https://www./kdd2016/papers/files/rfp0191-wangAemb.pdf
