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