網路表示學習概述

摘要

2017年最後一天，提前祝大家元旦快樂。

寫在前面

隨著社交媒體的飛速發展，在線社交網路成為了人們賴以生存的第二世界。大規模社交網路用戶的形成使得傳統的網路表示方法遇到了瓶頸，由於隨著深度學習技術的蓬勃發展以及受自然語言處理領域詞嵌入技術的啟發，自動學習網路中節點的向量表示成為近年來的研究熱點。本文將首先對社交網路的現狀進行分析，然後給出網路表示學習技術的基本概念，進而按照歷史發展順序分門別類的介紹具體的網路表示學習方法，最後給出目前的研究熱點與難點。本文旨在為初入社交網路分析的讀者一個清晰的認識，同時能夠為大家建立一個網路表示學習技術的整體框架以及發展趨勢。如果本文能夠幫助到志同道合的朋友，目的也就達到了，同時歡迎大家交流。

社交網路現狀

近年來，在線社交網路可謂發展迅猛。說到社交網路，它的起源可以追溯到1736年Euler提出的圖論理論當中的七橋問題。隨後提出了社會科學理論，在這一階段提出了許多社交網路中著名的結論，比如小世界、弱連接、鄧巴數及結構洞等。緊接著一些搞理論物理的教授們也加入了社交網路分析的大家庭，他們更加側重從物理結構上尋找規律，於是冪率分布、無標度網路、影響力最大化等結論被提出。再往後得益於硬體的飛速發展，進入了計算時代，鏈接預測等應用以及異質網路被提出。這一時代，社交媒體逐漸大量湧現。成立於2004年的Facebook的月活躍用戶數已經達到20億（截止2017年6月），可以說成為了虛擬世界中的第一大國；Twitter的月活躍用戶數保持在3.2億左右（截止2017年8月），有數據顯示，該社交工具雖然較鼎盛時期有所下降，但依然保持活力；國內的社交工具QQ目前的月活躍用戶達到了8.61億（截止2017年8月），崛起於2011年的新興社交工具微信月活躍用戶數超過了9.6億（截止2017年8月），新浪微博最新發布的數據表明，用戶數已超過Twitter，達到3.4億（截止2017年5月）。初步統計，每個網民平均加入了8個在線社交媒體，超過半數的網民通過社交網路來與朋友、同事保持聯繫。具體發展過程詳見圖1（該圖源於微軟研究院的Yuxiao Dong博士）。我們可以得到結論：在線社交網路已經成為了連接網路信息空間和人類物理世界必不可少的橋樑。因此社交網路分析成為了無論工業界還是學術界研究的熱點，特別的最近的網路表示學習技術更可謂是如雨後春筍般的成長。

網路表示學習概念

網路表示學習（Network Representation Learning），又名網路嵌入（Network Embedding）、圖嵌入（Graph Embedding），它旨在將網路中的節點表示成低維、實值、稠密的向量形式，使得得到的向量形式可以在向量空間中具有表示以及推理的能力，同時可輕鬆方便的作為機器學習模型的輸入，進而可將得到的向量表示運用到社交網路中常見的應用中，如可視化任務、節點分類任務、鏈接預測以及社區發現等任務，還可以作為社交邊信息應用到推薦系統等其他常見任務中。網路表示學習是一種分散式的表示學習技術。

網路表示學習是表示學習技術的一個子集。表示學習是一種對於數據廣義的特徵表示，可以是對於網路結構的表示（鄰接矩陣），也可以是對於列表結構的表示（鏈表）；可以是對於文本的特徵描述（TF-IDF），也可以是對於圖像的特徵表示（SIFT）； 可以是人工製造的特徵（特徵工程），也可以是自動學習到的隱含特徵（矩陣分解）； 可以是無監督的特徵表示（AutoEncoder），也可以是監督的降維表示（LDA）；可以是局部的流形學習方法（LLE），也可是全局的特徵表示方法（SVD）； 可以是線性的表示方法（PCA），也可以是高度非線性的自動學習方法（CNN）。 而網路表示學習則更加專註於社交網路的表示，旨在將網路中的節點以更加直觀、更加高效的某種方式儘可能的還原原始空間中節點的關係。

網路表示學習是對於節點的一種分散式表示方案。分散式表示與之相對應的概念為離散的表示方法。離散的表示方法側重於對每個對象進行單獨建模，常見的離散表示方法有one-hot表示，bag of words和TF-IDF等，比如star和sun的離散式表示如圖2，由於只有在該位置出現的地方為1，其他維度都為0，因此star和sun的語義儘管有些相近，但計算相似度時仍然為0。分散式表示是基於通過與他周圍同時出現的詞來表示它，它是基於分散式假設被John Rupert Firth提出的-You shall know a word by the company it keeps.比如拿『』銀行『』舉例，經常與它一同出現的詞為「政府、借貸、存款」等，這樣一來兩個相似的詞就不會出現相似度完全為0的情況，star和sun的分散式表示如圖3。分散式表示相比於離散的表示方法有如下優點：維度大大減小，語義信息相對保留。

網路表示學習分類及代表方法

網路表示學習方法的分類仁者見仁、智者見智，因此不同的人會有不同的分類標準，在這我給出兩套不同的分類體系，圖4注重是否考慮了網路本身的屬性以及是否結合了其他領域知識，圖5則主要基於網路結構與是否結合了外部信息進行分類。雖然分類方法有所不同，但都是對於網路表示學習方法的總結，一套方法體系，不同視角分析。

圖4的分類方法中，第一部分為基於結構的分類方法，但都是用傳統的方法進行因子分解。隨著自然語言處理中詞嵌入技術在2013年被提出後，14年的deepwalk隨後也被提出，進而更多考慮社交結構的方法也相繼被提出，有的是改進deepwalk的隨機遊走策略的，比如node2vec，提出應該有一個偏置參數來控制模型更傾向於深度優先搜索還是廣度優先搜索；有的是改進deepwalk的一階近鄰稀疏問題，比如LINE，提出應該利用豐富的二階近鄰關係來彌補一階近鄰的稀疏問題；隨後又有人提出應該採用深度學習技術來捕捉網路中高度非線性的關係，同時還能保護好一階與二階近鄰關係。後來人們考慮到既然是社交網路，那就不能脫離社交網路的一些經典性質，比如無標度網路、三角閉包關係以及社交網路中社區的概念，因此這一類方法是在學習節點的表示時仍要保護好網路結構的固有性質。後來有學者將自然語言處理領域的相關知識運用到了網路表示學習領域，進而提高網路中節點的表示。

圖5的分類方法中，主要側重在於基於網路結構的方法，又可進一步分為基於分解的方法、淺層網路的方法和深度學習的方法。另外結合外部信息的方法在這主要是介紹結合豐富的文本信息以及借鑒自然語言處理領域的經典模型等。接下來主要以此為框架來分別對代表性方法進行介紹。

1. Locally Linear Embedding

2. Laplace Eigenmaps

3. Graph Factorization

4. Deepwalk

5. LINE

Deepwalk是根據節點之間的連邊進行隨機遊走，繼而產生節點序列，因此只考慮了節點的一階近鄰。實際上網路中的一階近鄰是非常稀疏的，因此LINE認為應該考慮更多的近鄰來豐富節點的表示。其中，二階近鄰就是看兩個節點的共同鄰居，共同鄰居數越多，兩個節點的二階鄰近度越高。

6. Node2vec

Deepwalk中的隨機遊走策略是完全隨機的，node2vec認為我們應該保證網路結構中的結構等價性與同質性，因此分別對應於寬度優先搜索與廣度優先搜索。所以定義了一個偏置參數來控制模型更傾向於BFS還是DFS。

同時將鄰居節點分成了三類，假設節點已經從t節點到達了v節點，那麼對於v節點的下一跳有4種選擇，分別是再次回到t節點、訪問x1、x2、x3中任意一個節點，由於x2，x3都距離t節點的跳數為2，因此屬於一種情況，因此即使4種選擇，但是3類情況。所以如果序列為（t-v-t），則表示節點返回到t的概率；如果序列為（t-v-x1），則表示節點進行寬度優先搜索的概率；如果序列為（t-v-x2或者t-v-x3），則表示節點進行廣度優先搜索的概率。因此p參數用來控制模型是否更傾向於返回重新訪問已經訪問的節點概率，q參數用來控制模型更傾向於進行廣度還是深度優先搜索的概率。

7. SDNE

上述介紹的模型雖然可以學到網路中的節點表示，但大部分都是基於線性的表示，或者淺層神經網路的表示。往往現實世界中的節點之間存在著千絲萬縷的非線性的關係，因此SDNE認為我們應該利用深度學習模型來捕捉節點間高度的非線性關係。因此SDNE通過無監督學習方法autoencoder來自動捕捉節點的局部關係，通過將節點的二階近鄰來作為輸入，進而學習二階近鄰的低維表示。同時將Laplacian Eigenmaps作為autoencoder之後的輸入，來保證兩個節點之間的一階鄰近關係，以此來保護網路的全局的結構信息。

8. TADW

Deepwalk只是考慮了網路中的結構屬性，往往在現實世界中節點存在豐富的文本信息，因此TADW認為我們在對於節點進行表示的過程中，不僅要考慮網路的結構信息，還應利用節點產生的文本信息。因此它在矩陣分解的基礎上，通過將鄰接矩陣進行分解，同時用節點的文本表示矩陣來進行約束，以此來緩解網路結構的稀疏問題。

研究熱點與趨勢

隨著社交媒體的飛速發展以及深度學習技術的逐漸成熟，網路表示學習成為了工業界和學術界的新寵。從13年自然語言處理領域Wordvec的提出，到14年deepwalk的提出，網路表示學習開始大火，最近幾年的研究成果可謂是如雨後春筍般出現，大量的工作都是基於網路表示學習的擴展，從近兩年的發展趨勢來看，網路表示學習開始向著更複雜的網路進發，比如超圖、異質網路、動態網路。同時也開始逐漸往更深的模型靠攏，比如生成對抗網路，更深的深度模型等。同時結合外部信息的網路表示學習更具有實用性與挑戰性，因此期待大家在此基礎上更好的開展工作。

推薦閱讀：