1 目錄
- 摘要
- 社交網絡分析現狀
- 網絡表示學習概念
- 網絡表示學習分類及代表方法
- 其與圖神經網絡的關系
- 常用包庫
- 研究熱點及趨勢
2 摘要
随着社交媒體的飛速發展，線上社交網絡成為了人們賴以生存的第二世界。大規模社交網絡使用者的形成使得傳統的網絡表示方法遇到了瓶頸，由于随着深度學習技術的蓬勃發展以及受自然語言處理領域詞嵌入技術的啟發，自動學習網絡中節點的向量表示成為近年來的研究熱點。
本文旨在為初入社交網絡分析的讀者一個清晰的認識，同時能夠為大家建立一個網絡表示學習技術的整體架構以及發展趨勢。如果本文能夠幫助到志同道合的朋友，目的也就達到了，同時歡迎大家交流。
3 社交網絡分析現狀
近年來，線上社交網絡可謂發展迅猛。說到社交網絡，它的起源可以追溯到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博士）。我們可以得到結論：線上社交網絡已經成為了連接配接網絡資訊空間和人類實體世界必不可少的橋梁。是以社交網絡分析成為了無論工業界還是學術界研究的熱點，特别的最近的網絡表示學習技術更可謂是如雨後春筍般的成長。
圖1 社交網絡科學發展簡史
4 網絡表示學習概念
網絡表示學習（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。分布式表示相比于離散的表示方法有如下優點：次元大大減小，語義資訊相對保留。
圖2 離散的表示方法
圖3 分布式表示方法
5 網絡表示學習分類及代表方法
網絡表示學習方法的分類仁者見仁、智者見智，是以不同的人會有不同的分類标準，在這我給出兩套不同的分類體系，圖4注重是否考慮了網絡本身的屬性以及是否結合了其他領域知識，圖5則主要基于網絡結構與是否結合了外部資訊進行分類。雖然分類方法有所不同，但都是對于網絡表示學習方法的總結，一套方法體系，不同視角分析。
圖4的分類方法中，第一部分為基于結構的分類方法，但都是用傳統的方法進行因子分解。随着自然語言進行中詞嵌入技術在2013年被提出後，14年的deepwalk随後也被提出，進而更多考慮社交結構的方法也相繼被提出，有的是改進deepwalk的随機遊走政策的，比如node2vec，提出應該有一個偏置參數來控制模型更傾向于深度優先搜尋還是廣度優先搜尋；有的是改進deepwalk的一階近鄰稀疏問題，比如LINE，提出應該利用豐富的二階近鄰關系來彌補一階近鄰的稀疏問題；随後又有人提出應該采用深度學習技術來捕捉網絡中高度非線性的關系，同時還能保護好一階與二階近鄰關系。後來人們考慮到既然是社交網絡，那就不能脫離社交網絡的一些經典性質，比如無标度網絡、三角閉包關系以及社交網絡中社群的概念，是以這一類方法是在學習節點的表示時仍要保護好網絡結構的固有性質。後來有學者将自然語言處理領域的相關知識運用到了網絡表示學習領域，進而提高網絡中節點的表示。
圖4 基于是否考慮社交屬性的分類
圖5的分類方法中，主要側重在于基于網絡結構的方法，又可進一步分為基于分解的方法、淺層網絡的方法和深度學習的方法。另外結合外部資訊的方法在這主要是介紹結合豐富的文本資訊以及借鑒自然語言處理領域的經典模型等。接下來主要以此為架構來分别對代表性方法進行介紹。
圖4 基于網絡結構的NRL方法分類
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認為我們在對于節點進行表示的過程中，不僅要考慮網絡的結構資訊，還應利用節點産生的文本資訊。是以它在矩陣分解的基礎上，通過将鄰接矩陣進行分解，同時用節點的文本表示矩陣來進行限制，以此來緩解網絡結構的稀疏問題。
6 與圖神經網絡的關系
圖神經網絡，顧名思義，就是利用神經網絡概念來解決圖中相關問題的技術，其中尤以目前大火的圖卷積網絡（GCN）最為出名。
圖卷積網絡（GCN），其是受直接作用于歐式空間中的卷積神經網絡（CNN）的啟發，探索在非歐式空間中的圖結構如何應用卷積的技術。
① 不同于隻利用網絡拓撲結構的圖嵌入技術，其不僅利用圖的結構資訊，同時也将圖中節點的特征資訊考慮其中；
②圖嵌入技術往往是無監督的，需要下遊任務進行有監督的訓練，而圖卷積網絡往往是端到端的有監督任務，比如節點分類任務；
③ 圖嵌入技術往往研究的對象為網絡（Network），而圖卷積網絡往往研究的對象為數學上的圖（Graph）。一個網絡可以表示為圖，一個不是網絡的資料往往也可以表示為圖，比如譜聚類就是這樣的思想。
來源于崔鵬老師的tutorial
7 常用包庫
1、DeepWalk
論文提出作者實作的python版deepwalk方法，支援兩種圖存儲結構輸入。
2、OpenNE
清華劉知遠團隊總結實作的GE方法集合，包括deepwalk，node2vec等常見GE方法。
3、GEM
實作了一些經典的GE方法集合，包括LE，LLE，GF，HOPE，SDNE等GE方法，同時附有配套綜述論文。
4、PyTorch Geometric
該庫為基于Pytorch架構實作的幾何深度學習擴充庫，已實作近五十種的模型。另外還提供了60多個與圖相關的基準資料集。
5、Deep Graph Library
該庫支援Pytorch以及Tensorflow作為其後端，值得注意的是除了複現經典的圖神經網絡模型，其還開源了關于異質圖神經網絡的模型，比如Metapath2vec等。
6、tf_geometric
該庫為基于Tensorflow架構實作的幾何深度學習擴充庫，目前已開源幾種經典的圖模型。由于開源時間不久，功能還需完善，也歡迎大家貢獻。
8 研究熱點與趨勢
随着社交媒體的飛速發展以及深度學習技術的逐漸成熟，網絡表示學習成為了工業界和學術界的新寵。從13年自然語言處理領域Wordvec的提出，到14年deepwalk的提出，網絡表示學習開始大火，最近幾年的研究成果可謂是如雨後春筍般出現，大量的工作都是基于網絡表示學習的擴充，從近兩年的發展趨勢來看，網絡表示學習開始向着更複雜的網絡進發，比如超圖、異質網絡、動态網絡。同時也開始逐漸往更深的模型靠攏，比如生成對抗網絡，更深的深度模型等。同時結合外部資訊的網絡表示學習更具有實用性與挑戰性，是以期待大家在此基礎上更好的開展工作。