網路表示學習綜述：一文理解Network Embedding

08-31

來自專欄 PaperWeekly64 人贊了文章

本期推薦的論文筆記來自 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<j，DeepWalk 總是偏向於 A~i~ 而不是 A~j~。為了避免上述缺點，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 http://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.

關於PaperWeekly

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

加入社區：http://paperweek.ly

微信公眾號：PaperWeekly

新浪微博：@PaperWeekly