290
Representation Learning on Network 網絡表示學習
Note: 以下是根據綜述 [1][2] 梳理的筆記，由於是初探，語言和理論必然有不嚴謹之處，歡迎指正。
網絡表示學習（Representation Learning on Network），一般說的就是向量化（Embedding）技術，簡單來說，就是將網絡中的結構（節點、邊或者子圖），通過一係列過程，變成一個多維向量，通過這樣一層轉化，能夠將複雜的網絡信息變成結構化的多維特征，從而利用機器學習方法實現更方便的算法應用。
Embedding Nodes
在這些方法中，受研究和應用關注最多的就是節點向量化（Node Embedding），即對於一個圖 G=(V,E)G=(V,E)，學習一種映射：
f:vi→zi∈Rdf:vi→zi∈Rd
其中 zizi 是一個輸出的多維向量，並且滿足d≪|V|d≪|V|。用於評估這個學習效果的標準，就是看向量化後重新複原網絡結構的能力。
在[1]中，作者提到節點向量化有3大挑戰：
- 學習屬性的選擇：不同的向量化表示方法，都是對網絡信息的一種摘要。有時我們會傾向於保存網絡中節點的近鄰關係，有時傾向學習節點在網絡中的角色（比如中心節點）。不同的應用對“學習屬性”的選擇有不同的要求，故而引發了各類算法的爆發。
- 規模化：現實應用中有很多網絡包含了大量的節點和邊，高效的向量化方法，能夠在短時間內處理超大規模的網絡，才比較有實際應用的可能性。
- 向量維度：如何確定合適的向量表示維度，是一個很難的問題，並且也是和具體場景相關的。事實上，越高的維度可能帶來越好的效果，但是會極大降低應用性能。平衡性能和效果，在不同的應用中需要因地製宜。
1. Encoder-decoder View
論文[2] 通過調研今年業界比較流行的向量化方法，提出了一套通用的流程和模型框架。
大部分向量化算法，是屬於非監督學習，沒有針對特定的圖計算任務（比如鏈路預測或者聚類）進行優化，而是針對圖信息的保存情況進行優化學習，其評價標準，就是看其向量化後的數據對原始網絡的恢複能力。整個學習過程被抽象為下圖所示的框架圖，它包括兩個過程：
- Encoder：負責把每個節點映射到一個低維向量中
- Decoder：負責從向量化的信息中重新構建網絡結構和節點屬性
對於上述框架，它包含4個概念：
- 節點關係函數 sG:V×V→R+sG:V×V→R+ 衡量兩個節點之間的距離
- Encode 函數 ENC:V→RdENC:V→Rd 將節點映射到 d 維向量
- Decode 函數 DEC:Rd×Rd→R+DEC:Rd×Rd→R+ 將向量化信息重新恢複成節點關係
- 損失函數 ll 用於度量模型刻畫能力，比如 DEC(zi,zj)DEC(zi,zj) 與 sG(vi,vj)sG(vi,vj)的偏差情況。
對於 Encoder-decoder 框架下現有的 state-of-the-art 模型，[2]的作者提出了幾個弱點：
- 向量化後的節點之間沒有參數共享，完全是一種記憶化的模型存儲和查詢方式（Look-up），這對存儲和計算都構成了不小的挑戰。由於節點之間沒有參數共享，也就大大損失了泛化能力。
- 目前大部分向量化方法，僅利用網絡結構信息，並沒有利用網絡節點本身的屬性（比如文本、圖像和統計特征），使得結果向量對網絡信息的存儲很有限。
- 大部分模型是對靜態網絡結構的直推學習，並沒有考慮網絡時間演化過程中新節點的生成和舊節點的湮滅，而網絡的動態特性對理解其性質也至關重要。這個弱點甚至會影響向量化在動態網絡上的效果。比如在互聯網場景中，每天都有新的結構產生和消除，今天生成的向量化表示，兩天後的可用性是否會大打折扣？這是一個值得深思的問題。
2. Encoding Methods
本模塊主要介紹3種常見的網絡表示學習類別。
2.1 Factorization based
矩陣分解是傳統的節點向量化方法，其思想就是對網絡的鄰接矩陣進行降維，給每個節點生成一個低維表示。
Laplacian Eigenmaps
Laplacian Eigenmaps 的目標是將相似性高的兩個節點，映射到低維空間後依然保持距離相近，其損失函數定義為：
L(Z)=12(zi−zj)2Wij=ZTLZL(Z)=12(zi−zj)2Wij=ZTLZ
其中 LL 是圖 G 的 Laplacian 矩陣，L=D−AL=D−A，其中 DD 是度矩陣，AA 是鄰接矩陣。
GF
根據[1]的調研，GF(Graph Factorization) 是第一個在 O(|E|) 的時間複雜度上完成向量化的算法。其損失函數定義為：
L(Z,λ)=12∑(i,j)∈E(Wij−<Zi,Zj>)2+λ2∑iZi2L(Z,λ)=12∑(i,j)∈E(Wij−<Zi,Zj>)2+λ2∑iZi2
其中 λλ 是正則化參數。跟上麵的 Laplacian Eigenmaps 相比，GF 算法是將兩個向量重構後的邊權作為衡量方法，兩個向量可能有多種重構方式，比如直接點乘，或者求餘弦相似度等等。
HOPE
HOPE(High-Order Proximity preserved Embedding) 模型相比 GF，通過引入 ||S−ZsZTt||2F||S−ZsZtT||F2 考慮了高階相似性，論文作者嚐試了 Kate Index, Root Page Rank, Common Neighbors, Adamic-Adar Score 等相似性指標，然後把相似性矩陣分解為 S=M−1gMlS=Mg−1Ml，因為M−1gMg−1 和 MlMl 都是稀疏的，所以利用 SVD 能有較高的運行效率。
2.2 Random Walk based
隨機遊走利用了網絡結構采樣，在處理大規模網絡問題上，常常有很好的性能表現，同時可以很好地刻畫網絡局部信息。大部分情況下，我們對節點的觀察並不需要考慮離它太遠的節點，利用局部信息已經能夠區別節點間的差異。
DeepWalk&node2vec
DeepWalk 是最早提出的基於 Word2vec 的節點向量化模型。其主要思路，就是利用構造節點在網絡上的隨機遊走路徑，來模仿文本生成的過程，提供一個節點序列，再套用 Word2Vec 對每個節點進行向量化表示。因為知道了節點 V 的前 k 個節點和後 k 個節點，就能很好地將網絡鄰居結構存入向量中。其目標就是最大化 logPr(vi−k,…,vi−1,vi+1,…,vi+k|Zi)logPr(vi−k,…,vi−1,vi+1,…,vi+k|Zi)。
Node2vec 是對 DeepWalk 的一種更廣義的抽象，它引入了 biased-random walks，用來刻畫每次隨機遊走是偏深度探索（DFS）還是廣度探索（BFS），分別側重社區結構和節點重要性的信息。由於 node2vec 有 p 和 q 兩個超參數，所以它是一個比較靈活的模型框架。後麵也會講到，它在節點分類問題中有著不俗的表現。
LINE
LINE(Large-scale Information Network Embeddings) 直觀上看其實並沒有用隨機遊走。但是[2]將其歸類到隨機遊走的範疇，原因是它和 DeepWalk 的框架類似地應用了概率損失函數。即通過最小化節點 i,ji,j 相連的經驗概率 ^p(i,j)p^(i,j) 與向量化後兩個節點相似性 p(vi,vj)p(vi,vj) 的距離，並且同時考慮了一階和二階相似度（優化兩個損失函數），這和隨機遊走的底層動機是相似的。在實際計算過程中，作者引入了一係列預處理和優化方法（比如負采樣），來加快學習性能。
2.3 Deep Learning based
SDNE
SDNE(Structural Deep Network Embeddings) 將節點的相似性向量 sisi 直接作為模型的輸入，通過 Auto-encoder 對這個向量進行降維壓縮，得到其向量化後的結果 zizi。其損失函數定義為：
L=∑vi∈V||DEC(zi)−si||22L=∑vi∈V||DEC(zi)−si||22
其中 sisi 是一個|V||V| 維的輸入向量，而 zizi 的維數必然遠小於前者。其實它的建模思路和前麵提到的矩陣分解是一致的，隻是在降維時用的不是矩陣分解，而是 Auto-encoder。
另一個模型 DNGR(Deep Neural Graph Representations) 與 SDNE 區別主要在於相似性向量的定義不同，DNGR 將兩個節點由隨機遊走得到的「共同路徑」作為衡量其相似性的指標，而 SDNE 直接用一階關係作為相似性的輸入。
這種方法遇到一個較大的問題是，其輸入向量維度被限製為|V||V| ，一方麵對網絡規模有一定限製，另一方麵對新節點的接受程度不好（新節點加入後可能需要重新訓練整個網絡）。
GCN
前麵說的幾種模型，大都是利用網絡結構對節點進行向量編碼。另外有一類方法，強調的更多是將節點本身及其鄰居節點的屬性（比如文本信息）或特征（比如統計信息）編碼進向量中，這類方法可以統稱為 Neighborhood Aggregation Algorithms，它們引入了更多特征信息，並且在鄰居節點間共享了一些特征或參數。
GCN(Graph Convolutional Networks) 就是其中的一類。上圖是 GraphSAGE 算法 [3]的流程步驟。相比 SDNE 類的算法，GCN 的輸入向量不必限製在 |V||V| 維，所以輸入數據可以大大減小維數。因為 GCN 在網絡結構的基礎上，又引入了節點信息，所以在節點分類、鏈路預測等任務上，比隻考慮網絡結構的模型有更好的表現，當然這也取決於數據的豐富程度。
3. Evaluation
文章[2]在人工生成網絡、社交網絡、論文合作網絡和蛋白質網絡上對幾種常見的向量化方法進行了網絡重構、節點可視化、鏈路預測、節點分類的評測，大部分模型實驗的輸出結果是128維的向量。網絡信息如下：
A. Graph Reconstruction
網絡重構，是從向量化的節點出發，重新連邊構建網絡。我們發現 保存了高階節點關係的模型往往能夠更好地重構網絡 ，這也符合直觀認識。SDNE 幾乎在所有數據集上擊敗了其他模型。
B. Visualization
網絡節點可視化，一般是將節點編碼成二維或三維的向量，在坐標軸上標注出來。常常會以事實分類區別顏色標記在圖像上，用來區分不同向量化方法的好壞。
下圖是模型對 SBM 生成網絡處理，輸出編碼至 128 維向量後，再利用 t-SNE 進行壓縮得到的二維圖像。
當 node2vec 模型設置 BFS 傾向大一些時，可以得到界限很清晰的聚類結果。但是 LE(Laplacian Eigenmaps) 和 GF(Graph Factorization) 模型的效果就比較差強人意了，尤其是 GF 基本不能看。
下圖是模型對 Karate 跆拳道俱樂部網絡進行二維向量化編碼的結果。
從網絡結構和節點性質來看，SDNE 和 node2vec 保留了原始網絡較多信息。尤其是 SDNE 把節點0單獨放到了很遠的位置，因為它是社區間的 bridge 節點。而 HOPE 對 0、32、33 的社區中心節點屬性刻畫的比較好，並且明顯地劃分出兩個社區。GF 的表現依然比較差，除了把度大的節點放在了中心，葉子節點放在了周圍，並沒有很好的區別社區距離。
C. Link Prediction
在鏈路預測評估中，各個算法的表現並不是很穩定。這也和模型的設計並不是為特定任務而定製有關。
從 Top k 預測準確性來看，node2vec 模型在 BlogCatelog 數據中表現最好，其他數據集就比較一般（在 PPI 的 Top 表現也不錯）。HOPE 模型在 k 比較大時，效果一般在中上位置，比較穩定。
D. Node Classification
作者在 SBM、PPI 和 BlogCatelog 網絡上做了節點分類的實驗。如下圖：
從數據效果來看，node2vec 模型幾乎在所有數據集中，都遠勝其他模型。原因可能是 node2vec 模型同時刻畫了節點的社區結構和網絡角色，說明在節點分類中 Random Walk 方法有比較不錯的表現。
綜上 node2vec 和 SDNE 在除了鏈路預測問題中，幾乎表現都很亮眼。值得重點挖掘！
Reference
[1] Goyal, Palash, and Emilio Ferrara. "Graph Embedding Techniques, Applications, and Performance: A Survey." arXiv preprint arXiv:1705.02801 (2017).
[2] William L. Hamilton, Rex Ying and Jure Leskovec. "Representation Learning on Graphs: Methods and Applications" arXiv preprint arXiv:1709.05584 (2017).
[3] Hamilton, William L., Rex Ying, and Jure Leskovec. "Inductive Representation Learning on Large Graphs." arXiv preprint arXiv:1706.02216 (2017).
最後更新：2017-10-18 15:03:49