知識星球
在碎片化閱讀充斥眼球的時代，越來越少的人會去關註每篇論文背後的探索和思考。
在這個欄目裡，你會快速 get 每篇精選論文的亮點和痛點，時刻緊跟 AI 前沿成果。
點選本文底部的「閱讀原文」即刻加入社群，檢視更多最新論文推薦。
本期推薦的論文筆記來自 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
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 的交流群裡。
▽ 點選 | 閱讀原文 | 下載論文
