在圖嵌入專題的前三篇文章中，我們分別從圖嵌入算法的整體概況、基於深度學習的圖嵌入算法以及基於skip-gram的圖嵌入算法三個方面進行了介紹。本文從圖嵌入算法與矩陣分解算法的關係出發，對圖嵌入算法進行進一步的介紹。
圖嵌入與矩陣的關係
圖嵌入算法的基本思想，是通過一種學習方式，將複雜網絡中的節點表達成一個低維的向量，使其能夠反映出該節點在網絡中複雜的交互信息。早期的圖嵌入算法通過構造一個設計好的節點連接矩陣，通過矩陣分解的方式學習到節點的嵌入向量；近年來，許多的圖嵌入算法雖然沒有顯式地構建連接矩陣（例如deep-walk算法），但本質上依然可以近似為對一種隱性的連接矩陣進行分解。這一節我們先介紹圖嵌入算法與矩陣分解的聯繫，在第二節我們將以deepwalk為例詳述這一過程。
圖嵌入算法的基本思想是，對於一個節點，首先尋找它的鄰近節點（這裡簡稱鄰域），通過該節點鄰域的嵌入信息，學習到該節點的嵌入表示。一般來講，與目標節點直接相連的節點，可以被看作它的一階鄰域，例如對於下述網絡：
如果圖嵌入算法只考慮了與目標節點直接連接的節點（即一階鄰域），例如我們在圖嵌入算法（三）中介紹的，deepwalk算法通過截斷式隨機遊走尋找鄰域，如果設置隨機遊走的長度為1，則得到的實際是鄰接矩陣：
如果圖嵌入算法考慮二階鄰域（即鄰域的鄰域），也就是deepwalk算法的遊走長度為2，則得到的節點的連接矩陣為：
當然，如果根據節點的鄰近關係設置不同節點之間的權重，則上述矩陣將不再是0,1矩陣，而是一個帶權矩陣。可以看出，在我們的例子中僅6個節點，二階鄰域構成的節點連接矩陣已經非常稠密了。那麼在大型的網絡中，如果設置鄰域的窗口長度L趨近於無窮，則連接矩陣將被節點之間的近似關係填滿。
圖嵌入算法，編碼的雖然是節點，編碼需要保留的信息卻是圖中的拓撲結構，即節點之間的連接關係。因此，有了節點之間的連接矩陣後，圖嵌入算法的假設是，這個連接矩陣是低秩的。因此可以通過某種低秩矩陣近似方法來學習節點的嵌入表達，並且這些圖中重要的連接信息，能夠通過這個低維的嵌入向量得到很好的編碼。
小結一下，雖然圖嵌入算法有很多，但他們通用框架本質上都是相似的。即先通過一種方式得到節點的連接矩陣，再通過一種方式對該連接矩陣進行分解。根據對節點鄰域的定義不同，不同的圖嵌入算法將得到不同的連接矩陣。例如有的算法直接用鄰接矩陣進行嵌入，skip-gram算法通過設置隨機遊走的窗口長度尋找鄰域。得到連接矩陣也就是得到了節點的鄰域信息，不同的嵌入算法按照不同的方式利用鄰域信息進行嵌入。
論文[2]從數學上對基於skip-gram的網絡嵌入方法進行了理論證明：
DeepWalk,Line,PTE從理論上講都是一種隱式的矩陣分解。（這篇文章從數學書推導出了三種模型近似的矩陣分解形式）；
當節點的上下文規模被設為1時，Line實際上是DeepWalk的一個特殊形式；作為Line的一種擴展，PTE可以被看作多個網絡的拉普拉斯矩陣的聯合分解；
這篇文章發現了DeepWalk的隱式矩陣和圖拉普拉斯算子之間的理論聯繫。
文中推導出的關於DeepWalk,Line,PTE和node2vec的近似隱性矩陣分解形式為：
矩陣分解的一般形式為 W=UV,而基於skip-gram的嵌入算法在學習過程中卻從而產生過類似的矩陣分解形式。本節將以DeepWalk為例，分析其學習方式的內在原理，探究其與矩陣分解形式的共性。我們知道，DeepWalk在訓練過程中需要維護一個target矩陣和一個context矩陣。target矩陣中存儲的是最終要得到的嵌入向量，context矩陣中存儲的是作為上下文節點時節點的嵌入向量。每次訓練時從target矩陣中抽出相應的列，與context矩陣的每一行作內積，就可以得到當前節點與所有節點的近似關係，即：
其中正樣本是通過隨機遊走得到的，除此之外的節點都是負樣本，這一步其實就是在構建節點連接矩陣。所以，通過將當前節點的target向量與所有節點的Context向量一一相乘，就可以得到這些節點兩兩之間的相似度，再通過一層softmax函數，就可以對哪些節點該讓其更接近，哪些節點該讓其遠離進行優化。
從而我們發現，若對所有節點進行一次訓練，則實際上就是Targer矩陣中的每一列與Context矩陣的每一行相乘，從而有W = UV，這裡U是Target矩陣，V是Context矩陣，W是相乘後的矩陣。
通過分析發現，得到的W矩陣表徵的正是節點之間的兩兩近似關係。反過來思考，現在我們通過隨機遊走知道了正負樣本，即連接矩陣W，我們的目標是得到節點的嵌入矩陣U，這其實正是對W矩陣的分解過程。具體地，我們將W分解為矩陣U和矩陣V的乘積，U是我們想要的Target矩陣，那麼V就是附加產生的Target矩陣。
事實上，為了簡化訓練的過程，DeepWalk並沒有將非正樣本之外的節點全部作為負樣本，而是進行了一種負採樣的方式對負樣本進行抽取。如果從矩陣分解的視角來看，就是構建的連接矩陣W並沒有徹底反映出節點之間的連接關係，而只反應部分行之間的連接關係（即正樣本和負樣本所在行）。在矩陣分解的過程中，也只有這部分行成為了優化的目標，而大部分行（既不是正樣本也不是負樣本所在行）則在訓練過程中被忽視了。
[4]從一個更一般的視角推導出最大化嵌入算法的目標函數相當於對一個偏移相似度矩陣進行矩陣分解。其中S是節點的相似度矩陣，是平衡兩個子目標矩陣的參數。下面我們將展示[4]中的推導過程。
對於一個嵌入算法，我們有如下目標函數：
其中衡量的是節點對的相似度，它越大，表示節點對越相似。衡量的是嵌入向量的相似度，它越大，表示這兩個節點的嵌入向量越相似。是兩個增函數。優化目標為最大化O1,意味著節點之間的相似度和他們嵌入向量的相似度都要達到最大。同樣的有第二個目標函數：
其中表示減函數，最大化O2就相當於要最小化節點之間的相似度和他們嵌入向量之間的相似度。結合O1和O2有：
上述定義的可以被任意選擇，通過選擇合適的函數，可以得到DeepWalk，Node2Vec,Cauchy Graph Embedding的目標函數。
論文[4]接下來從上述通用的目標函數推導出了Cauchy Graph Embedding的目標函數。將嵌入向量之間的相似度換成距離，可以得到替代的目標函數為：
另外將上述抽象函數具體化：
從而可以得到目標函數：
這個目標函數正是Cauchy Graph Embedding優化的目標函數。
現在我們將通過將上述抽象函數具體化的過程，推導出圖嵌入的矩陣分解形式。將上述抽象函數具體化為：
從而可以得到：
為了最大化上述目標函數，我們將和有關的偏導數設為0，並簡化公式，得到:
現在將單個節點i,j擴展到全部節點，上述公式可以被表示為：
至此，這篇論文證明了嵌入向量可以被看成是矩陣S的分解形式。下面我們來探究矩陣S的具體形式。
可以看到，只是對嵌入結果貢獻了一個乘法因子，因此可以將其忽視，從而得到：
其中。這就是被分解的矩陣，它相當於一個進行了偏移的節點相似度矩陣。
在前面幾個章節中，我們分別從不同的方面介紹了嵌入算法和矩陣分解的聯繫。在本章中，我們將介紹一種基於矩陣分解視角提出的嵌入算法：BoostNE[3]。
[3]認為，現在的嵌入算法都嘗試使用一個嵌入向量來表示節點在圖中複雜的交互信息，這種假設太強，當涉及到複雜網絡和複雜交互時，這種one size fits all的嵌入並不能充分編碼這些信息。它指出，傳統嵌入的嵌入算法本質上都是首先構建連接矩陣，然後通過對連接矩陣進行分解得到嵌入向量。例如對於DeepWalk來說，得到的節點連接矩陣是一個非負矩陣，為了得到節點的嵌入表達，可以採用非負矩陣分解的方法對這個連接矩陣X進行分解：
分解後的矩陣，，d是嵌入表達的維度，它遠遠小於節點的個數n。這種非負矩陣分解的方法背後隱含的意義是這個連接矩陣X是全局低秩的。這篇文章認為，這種全局低秩的假設在現實場景中是很難成立的，尤其涉及到複雜的節點交互時。因此單個的矩陣分解得到的嵌入結果不足以近似出節點之間全部的連接關係。
為了得到更好的嵌入表達，這篇文章採用了一種迭代近似的矩陣分解算法。在每輪迭代的矩陣分解中，他們鬆弛了全局低秩的假設。相反地他們認為原始的連接矩陣X是通過多階的NMF才得到很好的近似。基於這種思想，有下列優化函數：
也就是說，這個算法會執行一系列矩陣分解的操作，每次的矩陣分解擬合的目標都是上一次矩陣分解擬合的殘差。可以理解為初始嵌入表示提供節點連接模式的粗略視圖，而後者嵌入提供細粒度嵌入表示。換句話說，就是不同階段的矩陣分解呈現不同粒度的嵌入視圖。更具體地，在第i次迭代的矩陣分解定義如下:
下圖對該BoostNE算法進行了進一步的展示：
它首先構建了一個連接矩陣，然後通過嵌入算法進行對該矩陣進行第一次擬合，將擬合殘差作為下一輪迭代的目標矩陣。最終的嵌入表達是所有迭代輪次嵌入向量的集成。
該算法的偽代碼如下：
實驗設置
這篇文章的對比算法主要來自於兩類：
（1）基於矩陣分解的嵌入算法
Spectral Clustering[5]：這個算法將網絡拉普拉斯矩陣的前K個特徵向量作為節點的嵌入向量
Modularity[6]：他假設良好的嵌入能夠最大化節點劃分的模塊性，從網絡的模塊矩陣中提取了前K個特徵向量
GraRep：該方法通過捕獲節點之間的不同k步關係信息來學習節點嵌入表示。
（2）基於skip-gram的嵌入算法
這篇文章在四個數據集中，通過節點分類問題證明了該算法的優越性。評價指標只要為微F1和宏F1，定義如下：
實驗結果
該文章首先利用多標籤節點分類問題對比了BoostNE算法和其他算法的嵌入質量，如下表3-6所示：
接下來，這篇文章也比較了該多階網絡嵌入算法在不同的階數K時的近似誤差，可以看出在四個數據集上，隨著矩陣分解階數提高，近似誤差逐漸變小。
在知道了更大的近似階數導致更小的近似誤差後，論文又進一步分析不同的近似階數對嵌入質量的影響：
從上圖中看出，隨著矩陣分解階數的增多，嵌入向量分類表現首先達到了頂峰，接著逐漸下降。最好的分類結果在K為4或8時獲得。通過實驗，這篇文章證明了其觀點的正確性，即全局的節點連接矩陣不一定符合低秩假設，文章鬆弛了這一全局假設，提出了一種從不同粒度由粗到細學習多個網絡表達的方法。實驗證明了該方法要優於現階段的圖嵌入算法，即多個弱嵌入表達的集合能產生更有辨別性的節點表達。
本文分別從理解和理論兩個角度介紹了嵌入算法和矩陣分解之間的聯繫，並介紹了一種基於矩陣分解視角的嵌入算法。希望讀者能夠從本文中加深對圖嵌入算法的理解。後續我們會繼續對圖嵌入算法進行介紹，並總結出它未來的研究方向。
參考文獻
[1]https://zhuanlan.zhihu.com/p/29305464
[2]Network Embedding as Matrix Factorization= Unifying DeepWalk, LINE, PTE, and node2vec (arXiv, 2018)
[3]Multi-Level Network Embedding with Boosted Low-Rank Matrix Approximiation (arXiv, 2018)
[4]A General View for Network Embedding as Matrix Factorization(WSDM,2019)
[5]Lei Tang and Huan Liu. Leveraging social media networks for classification(Data Mining and Knowledge Discovery,2011)
[6]Lei Tang and Huan Liu. Relational learning via latent social dimensions.(KDD,2009)
[7]Shaosheng Cao, Wei Lu, and Qiongkai Xu. Grarep: Learning graph representations with global structural information.(CIKM,2015)
[8]Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representations.(KDD,2014)
[9]Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Large-scale information network embedding.(WWW,2015)