|本文較長，預(yù)計閱讀時間為14分鐘，本文參考文章[9]的大綱，對其中的部分內(nèi)容進(jìn)行修改和補(bǔ)充
Graph廣泛存在于真實(shí)世界的多種場景中，即節(jié)點(diǎn)和邊的集合。比如社交網(wǎng)絡(luò)中人與人之間的聯(lián)系，生物中蛋白質(zhì)相互作用以及通信網(wǎng)絡(luò)中的IP地址之間的通信等等。除此之外，我們最常見的一張圖片、一個句子也可以抽象地看做是一個圖模型的結(jié)構(gòu)，圖結(jié)構(gòu)可以說是無處不在。
對于Graph的研究可以解決下面的一些問題：比如社交網(wǎng)絡(luò)中新的關(guān)系的預(yù)測，在QQ上看到的推薦的可能認(rèn)識的人；生物分子中蛋白質(zhì)功能、相互作用的預(yù)測；通信網(wǎng)絡(luò)中，異常事件的預(yù)測和監(jiān)控以及網(wǎng)絡(luò)流量的預(yù)測。如果要解決以上的問題，我們首先需要做的是對圖進(jìn)行表示，graph embedding 是中非常有效的技術(shù)。
圖嵌入是一種將圖數(shù)據(jù)（通常為高維稠密的矩陣）映射為低微稠密向量的過程，能夠很好地解決圖數(shù)據(jù)難以高效輸入機(jī)器學(xué)習(xí)算法的問題。圖嵌入需要捕捉到圖的拓?fù)浣Y(jié)構(gòu)，頂點(diǎn)與頂點(diǎn)的關(guān)系，以及其他的信息，如子圖，連邊等。如果有更多的信息被表示出來，那么下游的任務(wù)將會獲得更好的表現(xiàn)。嵌入的過程中有一種共識：向量空間中保持連接的節(jié)點(diǎn)彼此靠近?；诖耍芯空咛岢隽死绽固卣饔成洌↙aplacian Eigenmaps）和局部線性嵌入（Locally Linear Embedding ，LLE）。
圖嵌入：
http://www.perozzi.net/publications/14_kdd_deepwalk.pdf
總的來說大致可以將圖上的嵌入分為兩種：節(jié)點(diǎn)嵌入和圖嵌入。當(dāng)需要對節(jié)點(diǎn)進(jìn)行分類，節(jié)點(diǎn)相似度預(yù)測，節(jié)點(diǎn)分布可視化，一般采用節(jié)點(diǎn)的嵌入；當(dāng)需要在圖級別上進(jìn)行預(yù)測或者預(yù)測整個圖結(jié)構(gòu)，我們需要將整個圖表示為一個向量。
后面將會介紹一下經(jīng)典的方法如DeepWalk, node2vec, SDNE和graph2vec.
圖是數(shù)據(jù)的有意義且易于理解的表示形式，但是出于下面的原因需要對圖進(jìn)行嵌入表示。
在graph直接進(jìn)行機(jī)器學(xué)習(xí)具有一定的局限性，我們都知道圖是由節(jié)點(diǎn)和邊構(gòu)成的，這些向量關(guān)系一般只能使用數(shù)學(xué)，統(tǒng)計或者特定的子集進(jìn)行表示，但是嵌入之后的向量空間具有更加靈活和豐富的計算方式；
圖嵌入能夠壓縮數(shù)據(jù)， 我們一般用鄰接矩陣描述圖中節(jié)點(diǎn)之間的連接。連接矩陣的維度是|V| x |V|，其中|V| 是圖中節(jié)點(diǎn)的個數(shù)。矩陣中的每一列和每一行都代表一個節(jié)點(diǎn)。矩陣中的非零值表示兩個節(jié)點(diǎn)已連接。將鄰接矩陣用用大型圖的特征空間幾乎是不可能的。一個具有1M個節(jié)點(diǎn)和1Mx1M的鄰接矩陣的圖該怎么計算和表示呢？但是嵌入可以看做是一種壓縮技術(shù)，能夠起到降維的作用；
向量計算比直接在圖上操作更加的簡單、快捷。
但是圖嵌入也需要滿足一定的需求
屬性選擇：確保嵌入能夠很好地描述圖的屬性。它們需要表示圖拓?fù)洌?jié)點(diǎn)連接和節(jié)點(diǎn)鄰域。預(yù)測或可視化的性能取決于嵌入的質(zhì)量；
可擴(kuò)展性：大多數(shù)真實(shí)網(wǎng)絡(luò)都很大，包含大量節(jié)點(diǎn)和邊。嵌入方法應(yīng)具有可擴(kuò)展性，能夠處理大型圖。定義一個可擴(kuò)展的模型具有挑戰(zhàn)性，尤其是當(dāng)該模型旨在保持網(wǎng)絡(luò)的全局屬性時。網(wǎng)絡(luò)的大小不應(yīng)降低嵌入過程的速度。一個好的嵌入方法不僅在小圖上高效嵌入，同時也需要在大圖上能夠高效地嵌入；
嵌入的維度：實(shí)際嵌入時很難找到表示的最佳維數(shù)，維度越大能夠保留的信息越多，但是通常有更高的時間和空間復(fù)雜度。較低的維度雖然時間、空間復(fù)雜度低，但無疑會損失很多圖中原有的信息。
節(jié)點(diǎn)的嵌入借鑒了word2vec的方法，該方法能夠成立的原因是：圖中的節(jié)點(diǎn)和語料庫中的單詞的分布都遵循冪定律。
http://www.perozzi.net/publications/14_kdd_deepwalk.pdf
在介紹圖嵌入的方法之前首先簡單回顧一下在文本領(lǐng)域的Word2Vec【3】和skip-gram模型，如果比較熟悉，可以直接跳過。
Word2vec是一種將單詞轉(zhuǎn)換為嵌入向量的嵌入方法。相似的詞應(yīng)具有相似的嵌入。Word2vec使用skip-gram網(wǎng)絡(luò)，這是具有一層隱藏層的神經(jīng)網(wǎng)絡(luò)（總共三層）。skip-gram模型是給出某一詞語來預(yù)測上下文相鄰的單詞。下圖顯示了輸入單詞（標(biāo)有綠色）和預(yù)測單詞的示例。通過此任務(wù)，作者實(shí)現(xiàn)了兩個相似的詞具有相似的嵌入，因?yàn)榫哂邢嗨坪x的兩個詞可能具有相似的鄰域詞。
下圖是skip-gram模型。網(wǎng)絡(luò)的輸入為one-hot編碼，長度與單詞字典的長度相同，只有一個位置為1，輸出為單詞的嵌入表示：
https://towardsdatascience.com/graph-embeddings-the-summary-cc6075aba007
下面介紹三個節(jié)點(diǎn)嵌入（node embedding）的方法，一個圖嵌入(graph embedding)的方法，這些方法都類似Word2vec的嵌入原理。
下面介紹三種經(jīng)典的節(jié)點(diǎn)嵌入的方法：DeepWalk【2】, Node2vec【8】, SDNE【7】。
3.1.1 DeepWalk
DeepWalk通過隨機(jī)游走(truncated random walk)學(xué)習(xí)出一個網(wǎng)絡(luò)的表示，在網(wǎng)絡(luò)標(biāo)注頂點(diǎn)很少的情況也能得到比較好的效果。隨機(jī)游走起始于選定的節(jié)點(diǎn)，然后從當(dāng)前節(jié)點(diǎn)移至隨機(jī)鄰居，并執(zhí)行一定的步數(shù)，該方法大致可分為三個步驟：
https://towardsdatascience.com/graph-embeddings-the-summary-cc6075aba007
DeepWalk通過隨機(jī)游走去可以獲圖中點(diǎn)的局部上下文信息，因此學(xué)到的表示向量反映的是該點(diǎn)在圖中的局部結(jié)構(gòu)，兩個點(diǎn)在圖中共有的鄰近點(diǎn)（或者高階鄰近點(diǎn)）越多，則對應(yīng)的兩個向量之間的距離就越短。但是DeepWalk方法隨機(jī)執(zhí)行隨機(jī)游走，這意味著嵌入不能很好地保留節(jié)點(diǎn)的局部關(guān)系，Node2vec方法可以解決此問題。
3.1.2 Node2vec
Node2vec是DeepWalk的改進(jìn)版，定義了一個bias random walk的策略生成序列，仍然用skip gram去訓(xùn)練。
https://towardsdatascience.com/graph-embeddings-the-summary-cc6075aba007
該算法引入了參數(shù)P和Q，參數(shù)Q關(guān)注隨機(jī)游走中未發(fā)現(xiàn)部分的可能性，即控制著游走是向外還是向內(nèi): 若Q>1，隨機(jī)游走傾向于訪問接近的頂點(diǎn)(偏向BFS); 若Q<1，傾向于訪問遠(yuǎn)離的頂點(diǎn)(偏向DFS)。
參數(shù)P控制了隨機(jī)游走返回到前一個節(jié)點(diǎn)的概率。也就是說，參數(shù)P控制節(jié)點(diǎn)局部關(guān)系的表示，參數(shù)Q控制較大鄰域的關(guān)系。
3.1.3 SDNE
SDNE沒有采用隨機(jī)游走的方法而是使用自動編碼器來同時優(yōu)化一階和二階相似度，學(xué)習(xí)得到的向量表示保留局部和全局結(jié)構(gòu)，并且對稀疏網(wǎng)絡(luò)具有魯棒性, 那么什么是一階和二階相似度？
一階相似度表征了邊連接的成對節(jié)點(diǎn)之間的局部相似性。如果網(wǎng)絡(luò)中的兩個節(jié)點(diǎn)相連，則認(rèn)為它們是相似的。舉個例子：當(dāng)一篇論文引用另一篇論文時，意味著它們很可能涉及相似的主題，如6和7。但是當(dāng)兩個節(jié)點(diǎn)不相連時如5和6，他們就不具有相似度了嗎？顯然不是，從圖上可以看出來他們雖然沒有直接連接，但是他們有共同的鄰居1,2,3,4，那么這時候就需要用二階相似度來衡量了。
https://arxiv.org/abs/1503.03578
二階相似度表示節(jié)點(diǎn)鄰域結(jié)構(gòu)的相似性，它能夠了表征全局的網(wǎng)絡(luò)結(jié)構(gòu)。如果兩個節(jié)點(diǎn)共享許多鄰居，則它們趨于相似。
SDNE的具體做法是使用自動編碼器來保持一階和二階網(wǎng)絡(luò)鄰近度。它通過聯(lián)合優(yōu)化這兩個近似值來實(shí)現(xiàn)這一點(diǎn)。該方法利用高度非線性函數(shù)來獲得嵌入。模型由兩部分組成：無監(jiān)督和監(jiān)督。前者包括一個自動編碼器，目的是尋找一個可以重構(gòu)其鄰域的節(jié)點(diǎn)的嵌入。后者基于拉普拉斯特征映射，當(dāng)相似頂點(diǎn)在嵌入空間中彼此映射得很遠(yuǎn)時，該特征映射會受到懲罰。
關(guān)于整個圖嵌入的方式這里介紹具有代表性的graph2vec。
圖嵌入是將整個圖用一個向量表示的方法，Graph2vec同樣是基于skip-gram思想，把整個圖編碼進(jìn)向量空間, 類似文檔嵌入doc2vec, doc2vec在輸入中獲取文檔的ID，并通過最大化文檔預(yù)測隨機(jī)單詞的可能性進(jìn)行訓(xùn)練。
https://towardsdatascience.com/graph-embeddings-the-summary-cc6075aba007
Graph2vec同樣由三個步驟構(gòu)成：
采樣并重新標(biāo)記圖中的所有子圖。子圖是出現(xiàn)在所選節(jié)點(diǎn)周圍的一組節(jié)點(diǎn)。
訓(xùn)練skip-gram模型。類似于文檔doc2vec, 由于文檔是單詞集，而圖是子圖集，在此階段，對skip-gram模型進(jìn)行訓(xùn)練。經(jīng)過訓(xùn)練，可以最大程度地預(yù)測輸入中存在于圖中的子圖的概率。
計算。通過在輸入處提供子圖的id索引向量來計算嵌入。
https://www.groundai.com/project/graph2vec-learning-distributed-representations-of-graphs/1
以上提到了四個常用的方法，但是除此之外還有非常多的方法和模型值得學(xué)習(xí)
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，以及進(jìn)行embedding時需要滿足的性質(zhì)。進(jìn)一步簡單介紹了node-level的三個經(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://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
