為什么要進行圖嵌入Graph embedding?|本文較長，預計閱讀時間為14分鐘，本文參考文章[9]的大綱，對其中的部分內(nèi)容進行修改和補充 Graph廣泛存在于真實世界的多種場景中，即節(jié)點和邊的集合。比如社交網(wǎng)絡中人與人之間的聯(lián)系，生物中蛋白質(zhì)相互作用以及通信網(wǎng)絡中的IP地址之間的通信等等。除此之外，我們最常見的一張圖片、一個句子也可以抽象地看做是一個圖模型的結(jié)構，圖結(jié)構可以說是無處不在。 對于Graph的研究可以解決下面的一些問題：比如社交網(wǎng)絡中新的關系的預測，在QQ上看到的推薦的可能認識的人；生物分子中蛋白質(zhì)功能、相互作用的預測；通信網(wǎng)絡中，異常事件的預測和監(jiān)控以及網(wǎng)絡流量的預測。如果要解決以上的問題，我們首先需要做的是對圖進行表示，graph embedding 是中非常有效的技術。 1.什么是圖嵌入（graph embedding）？圖嵌入是一種將圖數(shù)據(jù)（通常為高維稠密的矩陣）映射為低微稠密向量的過程，能夠很好地解決圖數(shù)據(jù)難以高效輸入機器學習算法的問題。圖嵌入需要捕捉到圖的拓撲結(jié)構，頂點與頂點的關系，以及其他的信息，如子圖，連邊等。如果有更多的信息被表示出來，那么下游的任務將會獲得更好的表現(xiàn)。嵌入的過程中有一種共識：向量空間中保持連接的節(jié)點彼此靠近?；诖?，研究者提出了拉普拉斯特征映射（Laplacian Eigenmaps）和局部線性嵌入（Locally Linear Embedding ，LLE）。 圖嵌入： http://www./publications/14_kdd_deepwalk.pdf 總的來說大致可以將圖上的嵌入分為兩種：節(jié)點嵌入和圖嵌入。當需要對節(jié)點進行分類，節(jié)點相似度預測，節(jié)點分布可視化，一般采用節(jié)點的嵌入；當需要在圖級別上進行預測或者預測整個圖結(jié)構，我們需要將整個圖表示為一個向量。
2.為什么要使用圖嵌入？圖是數(shù)據(jù)的有意義且易于理解的表示形式，但是出于下面的原因需要對圖進行嵌入表示。
但是圖嵌入也需要滿足一定的需求
3.圖嵌入方法節(jié)點的嵌入借鑒了word2vec的方法，該方法能夠成立的原因是：圖中的節(jié)點和語料庫中的單詞的分布都遵循冪定律。 http://www./publications/14_kdd_deepwalk.pdf 在介紹圖嵌入的方法之前首先簡單回顧一下在文本領域的Word2Vec【3】和skip-gram模型，如果比較熟悉，可以直接跳過。 Word2vec是一種將單詞轉(zhuǎn)換為嵌入向量的嵌入方法。相似的詞應具有相似的嵌入。Word2vec使用skip-gram網(wǎng)絡，這是具有一層隱藏層的神經(jīng)網(wǎng)絡（總共三層）。skip-gram模型是給出某一詞語來預測上下文相鄰的單詞。下圖顯示了輸入單詞（標有綠色）和預測單詞的示例。通過此任務，作者實現(xiàn)了兩個相似的詞具有相似的嵌入，因為具有相似含義的兩個詞可能具有相似的鄰域詞。 下圖是skip-gram模型。網(wǎng)絡的輸入為one-hot編碼，長度與單詞字典的長度相同，只有一個位置為1，輸出為單詞的嵌入表示： https:///graph-embeddings-the-summary-cc6075aba007 下面介紹三個節(jié)點嵌入（node embedding）的方法，一個圖嵌入(graph embedding)的方法，這些方法都類似Word2vec的嵌入原理。 3.1節(jié)點嵌入方法（Node embeddings）下面介紹三種經(jīng)典的節(jié)點嵌入的方法：DeepWalk【2】, Node2vec【8】, SDNE【7】。 3.1.1 DeepWalk
https:///graph-embeddings-the-summary-cc6075aba007 DeepWalk通過隨機游走去可以獲圖中點的局部上下文信息，因此學到的表示向量反映的是該點在圖中的局部結(jié)構，兩個點在圖中共有的鄰近點（或者高階鄰近點）越多，則對應的兩個向量之間的距離就越短。但是DeepWalk方法隨機執(zhí)行隨機游走，這意味著嵌入不能很好地保留節(jié)點的局部關系，Node2vec方法可以解決此問題。 3.1.2 Node2vec https:///graph-embeddings-the-summary-cc6075aba007 該算法引入了參數(shù)P和Q，參數(shù)Q關注隨機游走中未發(fā)現(xiàn)部分的可能性，即控制著游走是向外還是向內(nèi): 若Q>1，隨機游走傾向于訪問接近的頂點(偏向BFS); 若Q<1，傾向于訪問遠離的頂點(偏向DFS)。 參數(shù)P控制了隨機游走返回到前一個節(jié)點的概率。也就是說，參數(shù)P控制節(jié)點局部關系的表示，參數(shù)Q控制較大鄰域的關系。 3.1.3 SDNE 一階相似度表征了邊連接的成對節(jié)點之間的局部相似性。如果網(wǎng)絡中的兩個節(jié)點相連，則認為它們是相似的。舉個例子：當一篇論文引用另一篇論文時，意味著它們很可能涉及相似的主題，如6和7。但是當兩個節(jié)點不相連時如5和6，他們就不具有相似度了嗎？顯然不是，從圖上可以看出來他們雖然沒有直接連接，但是他們有共同的鄰居1,2,3,4，那么這時候就需要用二階相似度來衡量了。 https:///abs/1503.03578 二階相似度表示節(jié)點鄰域結(jié)構的相似性，它能夠了表征全局的網(wǎng)絡結(jié)構。如果兩個節(jié)點共享許多鄰居，則它們趨于相似。
SDNE的具體做法是使用自動編碼器來保持一階和二階網(wǎng)絡鄰近度。它通過聯(lián)合優(yōu)化這兩個近似值來實現(xiàn)這一點。該方法利用高度非線性函數(shù)來獲得嵌入。模型由兩部分組成：無監(jiān)督和監(jiān)督。前者包括一個自動編碼器，目的是尋找一個可以重構其鄰域的節(jié)點的嵌入。后者基于拉普拉斯特征映射，當相似頂點在嵌入空間中彼此映射得很遠時，該特征映射會受到懲罰。 3.2圖嵌入方法關于整個圖嵌入的方式這里介紹具有代表性的graph2vec。 圖嵌入是將整個圖用一個向量表示的方法，Graph2vec同樣是基于skip-gram思想，把整個圖編碼進向量空間, 類似文檔嵌入doc2vec, doc2vec在輸入中獲取文檔的ID，并通過最大化文檔預測隨機單詞的可能性進行訓練。 https:///graph-embeddings-the-summary-cc6075aba007 Graph2vec同樣由三個步驟構成：
3.3其他的方法以上提到了四個常用的方法，但是除此之外還有非常多的方法和模型值得學習
總結(jié)本文介紹了Graph embedding是什么，為什么要采用Graph embedding，以及進行embedding時需要滿足的性質(zhì)。進一步簡單介紹了node-level的三個經(jīng)典的方法：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
