網絡表示學習發展綜述

(西華大學計算機與軟件工程學院 四川 成都 610039)

引言

伴隨著互聯網的快速普及、在線社交網絡迅猛發展，每天網絡上都會產生量級極大的數據，在已經成為當前計算機科學重要研究領域的網絡數據挖掘中，這些帶挖掘的數據無疑具有極大的研究價值。

網絡數據最鮮明的特點就體現在數據節點之間存在著鏈接關系，這也反映了網絡中樣本點并非完全獨立。表示學習的目的是為網絡中的每一個節點分配某個線性空間中的向量，使得這些向量能夠保持原來網絡的結構信息，這對于社會網絡分析以及機器學習領域具有重大的意義[1]。

一、網絡表示學習方法介紹

網絡表示學習，又名網絡嵌入、圖嵌入，目的在于用低維緊湊的向量表示網絡中的節點，為下一步的任務提供有效的特征表示。讓映射出來的向量能夠擁有表示和推理的功能，方便下游計算，從而能夠使得到的向量表示使用于社交網絡中廣泛使用的應用場景里去。因此，網絡表示學習具有相當重大的意義。

1.基于因子分解的方法

基于結構的因子分解方法，大都是用傳統的方法進行因子分解[2]。

(1)Locally Linear Embedding (LLE)

局部線性嵌入(Locally Linear Embedding, LLE)是無監督的非線性降維算法，是流形學習經典算法。LLE假設高維空間的數據樣本在局部依舊包含歐式空間的性質，即“鄰域保持”思想：該節點可以通過其鄰居節點點的線性組合重構出來。

假使有樣本節點y1，用K-NN算法找到與它最接近的三個樣本節點y2，y3，y4。使用這三個鄰域節點表示該樣本節點，即：

y1=w12y2+w13y3+w14y4

能夠發現，在降維前后權重系數基本不發生改變的。利用這種局部相關性，LLE在局部建立降為映射關系，之后再將這種局部映射推廣至整個網絡。

(2)Laplacian Eigenmaps

拉普拉斯特征映射的思想比較簡單。觀察問題的角度與LLE類似，用子圖的思想去構建數據之間的關系。

通過拉普拉斯特征映射可以體現出數據內在的流形結構。如果節點之間的邊權重越大，就說明這兩個節點的距離越近，那么在嵌入后節點對應的值就應越接近。 最優化目標如下：

=tr(YTLY)

其中L是對應網絡的拉普拉斯矩陣。即 L=D-A。D 是度矩陣，A 是鄰接矩陣。約束條件為1=YTDY, 移除了嵌入時的隨意縮放因素。問題的標準解就是求標準化拉普拉斯矩陣最小的幾個特征值所對應的特征向量。

2.基于隨機游走的方法

基于隨機游走的方法，主要有DeepWalk和Node2Vec[3]。

(1)DeepWalk

DeepWalk是最早提出的基于Word2Vec的節點向量化模型，是把語言模型的方法用在了社會網絡之中，從而可以用深度學習的方法，除了表示節點以外，還可以反映節點間的拓撲關系，即表現出社會網絡中的社會關系。

其大致思路，就是使用構造節點在網絡上的隨機游走路徑，模擬文本生成的過程，給出節點序列，再將該序列向量化，然后用Skip-gram和Hierarchical Softmax模型對隨機游走序列中每個局部序列內的節點對進行概率建模，將隨機游走序列的似然概率最大化，利用隨機梯度下降方法調整參數。

(2)Node2Vec

Node2Vec通過改進隨機游走序列生成的方法對DeepWalk算法進行了拓展。在DeepWalk中，是完全隨機地去選取隨機游走序列中下一個節點的，而node2vec通過加入兩個超參數p和q，將寬度優先搜索(BFS)和深度優先搜索(DFS)的思路加入到隨機游走序列的生成進程中。BFS重視鄰居節點，并描繪了相對鄰域的表示，BFS中的節點通常會多次出現，使得核心節點鄰域中節點的方差減少；DFS則注重高層次節點間同質性的刻畫。即BFS能夠體現圖的結構性質，而DFS則能夠反映鄰居節點的相似性大小。

3.基于深度學習的方法

在網絡表示學習中，還有基于深度學習的方法，比較具有代表性的方法就是Structural Deep Network Embedding (SDNE)[4]。

SDNE是第一個將深度學習應用于網絡表示學習中的方法。它是一種半監督的學習模型。它屬于在LINE模型的基礎上做出了拓展，在使用深度學習的方法進行網絡表示學習中結合了一階估計和二階估計的優點，以此來表示出網絡中的局部以及全局結構屬性，具有很強的適應性。SDNE利用了深度自動編碼器分別優化1階和2階相似度，通過最小化節點表示之間的歐式距離來保留鄰居節點之間的相似度。學習得到的向量表示能夠包含網絡高度非線性的局部和全局結構，而且對稀疏網絡也有很高的適用性。

4.其他方法

LINE 的大概思路就是把一個大規模網絡中的所有節點根據其關系的緊密程度映射到向量空間中，表征成為低維向量，聯系緊密的節點會被映射到接近的位置，而在網絡中衡量兩個節點聯系緊密程度的重要標準就是這兩個節點之間邊的權值。該模型既想到節點間的一階相似性：兩個節點之間邊的權值較大就認為這兩個節點比較相似，也兼顧到了二階相似性：即兩個節點也許沒有直接相連的邊，但假如它們的一階公共節點相當多，那么也認為這兩個節點是比較相似的。

LINE不僅保留了網絡局部和全局的網絡結構信息，還可以用于含有無權或有權邊的大型網絡，并且相當有效。

二、結論

本文總結了網絡表示學習的節點表示學習的主要方法。上述網絡表示學習方法，基本涵蓋了網絡表示學習的研究。