歡迎光臨
每天分享高質量文章

網絡表示學習綜述:一文理解Network Embedding

在碎片化閱讀充斥眼球的時代,越來越少的人會去關註每篇論文背後的探索和思考。

在這個欄目里,你會快速 get 每篇精選論文的亮點和痛點,時刻緊跟 AI 前沿成果。


點擊本文底部的「閱讀原文」即刻加入社區,查看更多最新論文推薦。

這是 PaperDaily 的第 96 篇文章

本期推薦的論文筆記來自 PaperWeekly 社區用戶 @xuehansheng本文是一篇來自 DeepWalk 團隊的綜述文章,對於近幾年網絡表示學習(Network Representation Learning/Network Embedding)進行了一個階段性的總結,並對於未來的發展方向進行了研究。

如果你對本文工作感興趣,點擊底部閱讀原文即可查看原論文。

關於作者:薛寒生,澳大利亞國立大學博士生,研究方向為人工智慧與計算生物學。

■ 論文 | A Tutorial on Network Embeddings

■ 鏈接 | https://www.paperweekly.site/papers/2203

■ 作者 | Haochen Chen / Bryan Perozzi / Rami Al-Rfou / Steven Skiena


論文摘要


網絡嵌入方法(Network Embedding)旨在學習網絡中節點的低維度潛在表示,所學習到的特征表示可以用作基於圖的各種任務的特征,例如分類,聚類,鏈路預測和可視化。


在本文中,通過分類和總結本研究領域的最新進展來概述網絡嵌入學習相關進展。文章首先討論網絡嵌入的屬性特征,並簡要介紹了網絡嵌入學習的歷史。然後文章還討論了在不同場景下的網絡嵌入方法,如監督與無監督學習,同質網絡學習嵌入與異構網絡等。文章進一步論證了網絡嵌入學習方法的具體應用,並總結了該領域未來的工作研究。

Network Embedding 介紹

由於信息網絡可能包含數十億個節點和邊緣,因此在整個網絡上執行複雜的推理過程可能會非常棘手。因此有人提出了用於解決該問題的一種方法是網絡嵌入(Network Embedding)。NE 的中心思想就是找到一種映射函式,該函式將網絡中的每個節點轉換為低維度的潛在表示


總的來說,NE 具有如下幾個特征: 


適應性(Adaptability)– 現實的網絡在不斷發展;新的應用演算法不應該要求不斷地重覆學習過程。 


可擴展性(Scalability)– 真實網絡本質上通常很大,因此網絡嵌入演算法應該能夠在短時間內處理大規模網絡。 


社區感知(Community aware)– 潛在表示之間的距離應表示用於評估網絡的相應成員之間的相似性的度量。這就要求同質網絡能夠泛化。 


低維(Low dimensional)– 當標記資料稀缺時,低維模型更好地推廣並加速收斂和推理。 


持續(Continuous)– 需要潛在的表示來模擬連續空間中的部分社區成員資格。 


一個典型的例子就是 DeepWalk。其學習 Zachary’s Karate network 網絡中的拓撲結構信息並轉換成一個二維的潛在表示(latent representation)。


Network Embedding 簡史 


傳統意義上的 Graph Embedding 被看成是一個降維的過程,而主要的方法包括主成分分析(PCA)和多維縮放(MDS)。所有的方法都可以理解成運用一個 n × k 的矩陣來表示原始的 n × m 矩陣,其中 k << n。


在 2000 年代早期,又提出了其他方法,如 IsoMap 和 LLE,以保持非線性流形的整體結構。總的來說,這些方法都在小型網絡上提供了良好的性能。 然而這些方法的時間複雜性至少是二次的,這使得它們無法在大規模網絡上運行。


另一類流行的降維技術使用可從圖中匯出的矩陣的光譜特性(例如,特征向量)來嵌入圖的節點。拉普拉斯特征映射(Laplacian eigenmaps)通過與其k個最小非平凡特征值相關聯的特征向量表示圖中的每個節點。 


Deep Learning 


DeepWalk [1] 是第一個被提出來使用表示學習(或深度學習)社區的技術的網絡嵌入方法。DeepWalk 通過將節點視為單詞並生成短隨機游走作為句子來彌補網絡嵌入和單詞嵌入之間的差距。然後,可以將諸如 Skip-gram 之類的神經語言模型應用於這些隨機游走以獲得網絡嵌入。


DeepWalk 的優點可以概括為:首先其可以按需生成隨機游走。由於 Skip-gram 模型也針對每個樣本進行了優化,因此隨機游走和 Skip-gram 的組合使 DeepWalk 成為在線演算法。其次,DeepWalk 是可擴展的,生成隨機游走和優化 Skip-gram 模型的過程都是高效且平凡的並行化。最重要的是,DeepWalk 引入了深度學習圖形的範例


Unsupervised Network Embeddings

LINE [2] 採用廣度優先搜索策略來生成背景關係節點:只有距離給定節點最多兩跳的節點才被視為其相鄰節點。 此外,與 DeepWalk 中使用的分層 softmax 相比,它使用負採樣來優化 Skip-gram 模型。 


Node2vec [3] 是 DeepWalk 的擴展,它引入了一個偏向的隨機步行程式,結合了 BFS 風格和 DFS 風格的鄰域探索。 


Walklets [4] 顯示 DeepWalk 從 A~1~,A~2~,···,A~k~ 的加權組合中學習網絡嵌入。 特別是如果 i為了避免上述缺點,Walklets 建議從 A~1~,A~2~,···,A~k~ 中學習多尺度網絡嵌入。由於計算 A~i~ 的時間複雜度至少是網絡中節點數量的二次方,因此 Walklet 通過在短隨機游走中跳過節點來近似 A~i~。它進一步學習來自 A 的不同權力的網絡嵌入,以不同的粒度捕獲網絡的結構信息。 


GraRep [5] 類似地通過將圖形鄰接矩陣提升到不同的冪來利用不同尺度的節點共現信息。將奇異值分解(SVD)應用於鄰接矩陣的冪以獲得節點的低維表示。


Walklet 和 GraRep之間存在兩個主要差異。首先,GraRep 計算 A~i~ 的確切內容,而 Walklets 接近它。其次,GraRep 採用 SVD 來獲得具有精確分解的節點嵌入,而 Walklet 使用 Skip-gram 模型。


有趣的是,Levy 和 Goldberg 證明帶負抽樣的跳過法(SGNS)隱含地將節點和各個背景關係節點之間的 PMI 矩陣分解。總而言之,GraRep 使用噪聲較小的過程生成網絡嵌入,但 Walklet 證明更具可擴展性。 


GraphAttention [6] 提出了一種 attention 模型,它可以學習多尺度表示,最好地預測原始圖中的鏈接。GraphAttention 不是預先確定超引數來控制背景關係節點分佈,而是自動學習對圖轉換矩陣的冪集的 attention。 


SDNE [7] 學習節點表示,通過深度自動編碼器保持 2 跳鄰居之間的接近度。它通過最小化它們的表示之間的歐幾里德距離來進一步保持相鄰節點之間的接近度。 


DNGR [8] 是另一種基於深度神經網絡的學習網絡嵌入的方法。他們採用隨機衝浪策略來捕獲圖形結構信息。他們進一步將這些結構信息轉換為 PPMI 矩陣,並訓練堆疊去噪自動編碼器(SDAE)以嵌入節點。

Attributed Network Embeddings

上述無監督網絡嵌入方法僅利用網絡結構信息來獲得低維度的網絡特征。但是現實世界網絡中的節點和邊緣通常與附加特征相關聯,這些特征稱為屬性(attribute)。例如在諸如 Twitter 的社交網絡站點中,用戶(節點)發佈的文本內容是可用的。因此期望網絡嵌入方法還從節點屬性和邊緣屬性中的豐富內容中學習。 


TADW [9] 研究節點與文本特征相關聯的情況。TADW 的作者首先證明瞭 DeepWalk 實質上是將轉移概率矩陣 M 分解為兩個低維矩陣。受此結果的啟發,TADW 包含文本特征矩陣 T 通過將 M 分解為 W,H 和 T 的乘積,進入矩陣分解過程。最後,將 W 和 H×T 連接起來作為節點的潛在表示。 


CENE [10] 是一種網絡嵌入方法,它共同模擬節點中的網絡結構和文本內容。CENE 將文本內容視為特殊型別的節點,並利用節點-節點鏈接和節點內容鏈接進行節點嵌入。 優化標的是共同最小化兩種型別鏈路的損失。 


HSCA [11] 是一種歸因圖的網絡嵌入方法,它同時模擬同音,網絡拓撲結構和節點特征。 


Maxmargin DeepWalk(MMDW)[12] 是一種半監督方法,它學習部分標記網絡中的節點表示。MMDW 由兩部分組成:第一部分是基於矩陣分解的節點嵌入模型,第二部分是將學習的表示作為特征來訓練標記節點上的最大邊緣 SVM 分類器。通過引入偏置梯度,可以聯合更新兩個部分中的引數。


Heterogeneous Network Embeddings

異構網絡具有多類節點或邊緣。為了模擬不同型別的節點和邊緣,大多數異構網絡嵌入方法通過聯合最小化每種模態的損失來學習節點嵌入。這些方法要麼直接在相同的潛在空間中學習所有節點嵌入,要麼事先為每個模態構建嵌入,然後將它們映射到相同的潛在空間。 


Chang [13] 提出了異構網絡的深度嵌入框架。他們的模型首先為每種模態(如圖像,文本)構建一個特征表示,然後將不同模態的嵌入映射到同一個嵌入空間。優化標的是最大化鏈接節點的嵌入之間的相似性,同時最小化未鏈接節點的嵌入。註意,邊可以在相同模態內的兩個節點之間以及來自不同模態的節點之間。 


Zhao [14] 是另一種用於在異構網絡中構造節點表示的框架。具體來說,他們認為維基百科網絡有三種型別的節點:物體,單詞和類別。建立相同和不同型別節點之間的共現矩陣,並且使用坐標矩陣分解從所有矩陣聯合學習物體,詞和類別的表示。 


Li [15] 提出了一種神經網絡模型,用於學習異構社交網絡中的用戶表示。他們的方法聯合模擬用戶生成的文本,用戶網絡和用戶與用戶屬性之間的多方面關係。 


HEBE [16] 是一種嵌入大規模異構事件網絡的演算法,其中事件被定義為網絡中一組節點(可能是不同型別)之間的交互。雖然先前的工作將事件分解為事件中涉及的每對節點之間的成對交互,但 HEBE 將整個事件視為超邊界並同時保留所有參與節點之間的接近度。


具體而言,對於超邊緣中的每個節點,HEBE 將其視為標的節點,並將超邊界中的其餘節點視為背景關係節點。因此,基礎優化標的是在給定所有背景關係節點的情況下預測標的節點。 


EOE [17] 是用於耦合異構網絡的網絡嵌入方法,其中兩個同構網絡與網絡間邊緣連接。EOE 學習兩個網絡的潛在節點表示,並利用和諧嵌入矩陣將不同網絡的表示轉換為相同的空間。 


Metapath2vec [18] 是 DeepWalk 的擴展,適用於異構網絡。為了構建隨機漫游,Metapath2vec 使用基於元路徑的漫游來捕獲不同型別節點之間的關係。對於來自隨機游走序列的學習表示,他們提出異構 Skip-gram,其在模型優化期間考慮節點型別信息。


總結

該 Network Embedding 綜述文章較為系統地闡述了目前 NE 的發展現狀,並從 Unsupervised Network Embeddings, Attributed Network Embeddings 和 Heterogeneous Network Embeddings 等幾個部分進行了介紹。本筆記主要著重於介紹現有的一系列方法,對於其在不同場景的應用不做詳細闡述。


參考文獻


[1] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representations.In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 701–710. ACM, 2014. 

[2] Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Largescale information network embedding. In Proceedings of the 24th International Conference on World Wide Web, pages 1067–1077. ACM, 2015. 

[3] Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 855–864. ACM, 2016. 

[4] Bryan Perozzi, Vivek Kulkarni, Haochen Chen, and Steven Skiena. Don’t walk, skip! online learning of multi-scale network embeddings. In 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM). IEEE/ACM, 2017. 

[5] Shaosheng Cao, Wei Lu, and Qiongkai Xu. Grarep: Learning graph representations with global structural information. In Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, pages 891–900. ACM, 2015. 

[6] Sami Abu-El-Haija, Bryan Perozzi, Rami Al-Rfou, and Alex Alemi. Watch your step: Learning graph embeddings through attention. arXiv preprint arXiv:1710.09599, 2017. 

[7] Daixin Wang, Peng Cui, and Wenwu Zhu. Structural deep network embedding. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1225–1234. ACM, 2016. 

[8] Shaosheng Cao, Wei Lu, and Qiongkai Xu. Deep neural networks for learning graph representations. In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, pages 1145–1152. AAAI Press, 2016. 

[9] Cheng Yang, Zhiyuan Liu, Deli Zhao, Maosong Sun, and Edward Y Chang. Network representation learning with rich text information. In IJCAI, pages 2111–2117, 2015. 

[10] Xiaofei Sun, Jiang Guo, Xiao Ding, and Ting Liu. A general framework for content-enhanced network representation learning. arXiv preprint arXiv:1610.02906, 2016. 

[11] Daokun Zhang, Jie Yin, Xingquan Zhu, and Chengqi Zhang. Homophily, structure, and content augmented network representation learning. In Data Mining (ICDM), 2016 IEEE 16th International Conference on, pages 609–618. IEEE, 2016. 

[12] Cunchao Tu, Weicheng Zhang, Zhiyuan Liu, and Maosong Sun. Max-margin deepwalk: discriminative learning of network representation. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (IJCAI 2016), pages 3889–3895, 2016. 

[13] Shiyu Chang, Wei Han, Jiliang Tang, Guo-Jun Qi, Charu C Aggarwal, and Thomas S Huang. Heterogeneous network embedding via deep architectures. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 119–128. ACM, 2015. 

[14] Yu Zhao, Zhiyuan Liu, and Maosong Sun. Representation learning for measuring entity relatedness with rich information. In IJCAI, pages 1412–1418, 2015. 

[15] Jiwei Li, Alan Ritter, and Dan Jurafsky. Learning multi-faceted representations of individuals from heterogeneous evidence using neural networks. arXiv preprint arXiv:1510.05198, 2015. 

[16] Huan Gui, Jialu Liu, Fangbo Tao, Meng Jiang, Brandon Norick, and Jiawei Han. Large-scale embedding learning in heterogeneous event data. 2016. 

[17] Linchuan Xu, Xiaokai Wei, Jiannong Cao, and Philip S Yu. Embedding of embedding (eoe): Joint embedding for coupled heterogeneous networks. In Proceedings of the Tenth ACM International Conference on Web Search and Data Mining, pages 741–749. ACM, 2017. 

[18] Yuxiao Dong, Nitesh V Chawla, and Ananthram Swami. metapath2vec: Scalable representation learning for heterogeneous networks. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 135–144. ACM, 2017.

本文由 AI 學術社區 PaperWeekly 精選推薦,社區目前已改寫自然語言處理、計算機視覺、人工智慧、機器學習、資料挖掘和信息檢索等研究方向,點擊「閱讀原文」即刻加入社區!


點擊標題查看更多論文解讀: 

關於PaperWeekly


PaperWeekly 是一個推薦、解讀、討論、報道人工智慧前沿論文成果的學術平臺。如果你研究或從事 AI 領域,歡迎在公眾號後臺點擊「交流群」,小助手將把你帶入 PaperWeekly 的交流群里。


▽ 點擊 | 閱讀原文 | 下載論文

赞(0)

分享創造快樂