信息網絡表示學習方法綜述

魯軍豪 許云峰

摘要：網絡表示學習方法將信息網絡表示為低維稠密攜帶網絡節點特征信息的實數向量，應用于下游機器學習任務的輸入，隨著機器學習與深度學習的發展，網絡表示學習擁有強大的建模能力且應用廣泛。對網絡表示學習方法、應用進行了歸納總結。首先，對當前國內外網絡表示學習方法進行梳理歸類，分為傳統方法、基于網絡結構的嵌入、融入屬性信息的嵌入，以及基于譜域的圖卷積、基于空間的圖卷積和圖attention網絡，按類別對各類模型詳細闡述，對比模型之間的適用性和方法特點;其次，介紹了網絡表示學習的相關應用，包括推薦系統領域、生物醫藥領域等，整理常用的數據集、開源實現的表示學習模型和強大的圖深度學習庫供研究者參考調用;最后，對網絡表示學習的發展趨勢進行了總結與展望。未來可在深層的圖神經網絡學習、動態和異構網絡的表示、網絡模型的泛化能力等方面繼續開展研究。

關鍵詞：計算機神經網絡;網絡;表示學習;圖神經網絡;圖卷積;圖深度學習庫

中圖分類號：TP311.13 文獻標識碼：A doj：10.7535/hbkd.2020yxO2004

網絡是表達實體與實體之間聯系的一種數據形式，廣泛存在于人們的生活中，例如：人們與周邊人形成的社交網絡;論文作者之間形成的引文網絡;生物醫藥中的蛋白質網絡和藥物網絡;甚至人臉掃描的點云網絡等。網絡表示學習是銜接網絡與原始數據與網絡應用任務的橋梁，如圖1所示，網絡表示學習方法從復雜的信息網絡中學習每個實體的特征信息，將其表示為低維稠密的實數向量，以應用于下游的機器學習任務。

網絡中蘊含豐富信息，對社會生產中的信息網絡進行分析與研究具有非常高的學術與應用價值。例如，在電子商務中，一個基于信息網絡的學習系統能夠利用用戶和產品之間的交互做出準確推薦;在化學研究中，分子被建模為圖網絡，它們的生物活性需要被識別，以發現藥物;在社交網絡中，對網絡進行社區劃分與鏈路預測，可對客戶人群進行分組與推薦。神經網絡與深度學習在歐幾里德數據上取得了很大成功，但信息網絡屬于不規則的非歐幾里德數據，如何進行有效地信息提取成為一個值得研究的課題。最初的網絡表示學習方法受到經典降維技術的影響，主要集中在矩陣分解方法上，隨后受到Word2vec技術和DeepWalk的啟發，涌現出許多利用隨機游走產生節點序列并輸人給skip-gram模型生成節點嵌人的表示方法。隨著深度學習的興起，許多研究者將卷積與self-attention機制引入網絡表示中，在網絡的譜域與空間域進行端到端的網絡計算，取得了優異的任務效果。

目前對包括圖神經網絡的網絡表示學習綜述數量有限，BRONSTEIN等給出了非歐幾里德領域的深度學習方法的概述，包括圖和流形，但忽略了幾個重要的基于空間的方法。WU等給出圖神經網絡領域的模型介紹，但缺少了對傳統方法以及基于隨機游走方法的介紹。涂存超等的綜述中僅簡單提到譜域的圖卷積模型，缺少對基于空間的圖卷積以及圖atten-tion網絡的介紹。本文系統并詳細地介紹了網絡表示學習相關方法模型，將其分為2大類，分別為網絡節點嵌入方法和圖神經網絡方法，細分為6個類別，分別是傳統方法、基于網絡結構的嵌人、融人屬性信息的嵌入，以及基于譜域的圖卷積、基于空間的圖卷積和圖attention網絡，并對比各模型的適用性和優缺點，為網絡表示學習領域的學者提供全面的綜述參考。同時，本文整理了開源實現的表示學習模型和圖深度學習庫，以及常用的數據集供研究者參考使用。網絡表示學習方法類別如圖2所示。

本文給定了表示學習方法公式中常見的符號定義，對網絡表示學習方法進行詳細的闡述，整理對比了各模型的適用性與優缺點，給出了基礎數據集和開源實現的表示學習模型和圖深度學習庫，對網絡表示學習的應用進行了介紹，并對網絡表示學習的未來進行了展望。

1網絡表示學習的基本定義

網絡表示學習公式中常見的符號及其含義如表1所示。

2網絡表示學習方法

網絡表示學習方法將非歐幾里德結構的網絡節點表示為低維稠密的特征向量，供下游機器學習任務使用，是一項特征工程任務。隨著近年來深度學習的興起，圖神經網絡成為網絡表示學習領域研究的熱點。與網絡節點的嵌入表示不同，圖神經網絡多為端到端的訓練框架。

2.1網絡節點嵌入方法

2.1.1傳統方法

早期的網絡表示學習方法被作為降維技術的一部分，將網絡節點嵌入到低維空間的思想是讓互相連接的節點在嵌入后的低維向量空間中彼此保持更近的距離。LLE（locally linear embedding）算法認為每一個數據點都可以由其近鄰點的線性加權組合得到。該方法先尋找每個樣本點的是個近鄰點，由每個樣本點的近鄰點計算出該樣本點的局部重構權重矩陣，然后用局部權重矩陣和其近鄰點計算出該樣本點的輸出值，LLE算法的目標函數表示為

2.1.2基于網絡結構的嵌入方法

Google在2013年推出一個用于獲取詞向量的工具包Word2vec，它的簡單高效引起了很多人的關注，同時也給網絡表示學習提供了很好的思路。Word2vec是根據大量語料庫中詞語的共現關系來得出每個單詞的向量嵌入，有CBOW和skip-gram兩種模型。前者根據上下文預測中心詞，后者是根據中心詞預測上下文，這里只介紹skip-gram模型，如圖3所示。

用核心詞w與其上下文context（w）組成訓練樣本，skip-gram模型用核心詞w預測上下文context（W），通過大量語料庫的詞語共現關系來不斷更新詞語的向量表示，用負采樣來加快訓練速度，最終得到每個詞語的向量表示。在Word2vec被提出之后，研究者在其基礎上提出了大量基于隨機游走的網絡表示學習方法，如DeepWalk，Node2vec等，這些方法利用隨機游走產生的節點序列作為skip-gram的輸入，從而生成節點的低維向量表示。

PEROZZI等觀測到節點在短隨機游走中的分布和詞語在自然語言中的分布都滿足冪律分布，并在游走的過程中獲取了節點的局部結構信息，從而將Word2vec模型引入網絡表示學習，提出DeepWalk算法，利用節點截斷隨機游走產生的類似語料中句子的序列，借助詞向量模型生成節點的嵌入向量，使得效果有了較大的提升。Deep-Walk對Karate數據集的嵌入效果如圖4所示。

GROVER等將BFS與DFS融人節點的隨機游走，提出了Node2vec算法。相比于DeepWalk算法中節點的隨機游走，加入BFS和DFS策略的Node2vec可以更好地挖掘網絡中的拓撲信息，如圖5所示。

需要注意的是在嵌入向量的更新計算中，DeepWalk采用分層Softmax來計算歸一化因子，使用二叉樹結構加速計算，而Node2vec算法則采用負采樣方法，每個訓練樣本只更新部分模型權重，從而提高嵌入的訓練速度。

DeepWalkEls3和Node2vecEzz]利用隨機或有偏隨機游走來獲得節點的鄰域信息，從而生成嵌入向量，使在網絡結構中相連和距離較近的節點在對應的低維空間中也具有相近的距離。但是在網絡中存在結構一致性（structural identify）節點，如圖6所示，頂點u與頂點v的度數分別是5和4，分別連接3個和2個三角形網絡結構，并通過2個頂點（d，e;x，w）與外界相連，這樣的節點雖然沒有直接相連也沒有共同鄰域，但具有空間結構一致性。RIBERIO等觀察到DeepWalk和Node2vec等算法構造的節點序列不能識別相隔較遠的具有結構一致性的節點，為了解決此問題，提出Struc2vec算法。

TANG等提出了LINE算法，使得在小時范圍內單機學習百萬級頂點網絡表示成為了可能。LINE算法提出了一階相似度與二階相似度，一階相似度描述了直接相連的節點之間的相似度，如圖8中節點6和節點7直接相連，兩節點相似度為邊的權重;二階相似度描述為一對節點之間的接近程度和鄰居網絡結構之間的相似性，如圖8中節點5與節點6之間沒有直接的邊關系，但有共同的網絡鄰居。

一個網絡中的邊關系往往是非常稀疏的，所以有必要進一步刻畫二階相似度關系來考慮雖然并不直接相連但是共同鄰居較多的節點對，從而對第一階相似度的信息予以補充。LINE算法適用于大規模網絡，并且網絡的邊不限制是否有向和是否帶權，在節點分類等任務中表現出不錯的效果。

GraRep算法在LINE定義的一階和二階相似性的啟發下，將這種相似性推廣到更高階，定義了k階相似性。GraRep中也使用了像LINE中一樣將高階的圖中的相似關系在低維向量空間中用條件概率表示，并且使用了負采樣優化的策略。

2.1.3融入屬性信息的嵌入方法

上述方法模型只利用了網絡中拓撲結構的相似性來生成節點嵌入向量，真實世界的網絡通常在節點和邊上附屬有標簽文本等豐富的屬性信息，若能充分利用網絡中的屬性信息，會得到更好的嵌入效果。

TU等提出的CANE算法在兼顧網絡結構相似性的同時，利用attention機制自適應計算節點文本內容的相似性。圖10為CANE方法的框架示意圖，該方法利用卷積神經網絡對一條邊上2個節點的文本信息進行編碼。在文本表示生成的過程中，利用相互注意力機制，選取2個節點彼此最相關的卷積結果構成最后的文本表示向量。

文獻[29]中將文本也轉化為特殊的節點，形成兩種連接的邊，即節點一節點和節點一文檔，對兩種邊一起建模嵌入得到節點表示。針對屬性網絡的表示學習方法有ANRL，SIGNet，TransNet和SANE，它們結合網絡結構和節點的屬性信息使學習到的嵌入表示具有更多的信息性。BiasedWalk則考慮兼顧有偏隨機游走的優勢以及網絡節點的屬性信息，以學習到信息更加豐富的網絡嵌入表示。

當信息網絡中的節點或邊類型數量n≥2時，這種網絡被稱為異構網絡。針對異構網絡的表示學習方法也有大量研究者做出很多探索，典型的方法有metapat2vec，HIN2Vec，Tri-DNR，HNEE，HEBE，EOE，以及基于Attention機制的HAN等。

2.2圖神經網絡方法

2.2.1基于譜域的圖卷積

BRUNA等首先提出了在圖網絡中基于譜域的卷積方法，函數卷積的傅里葉變換等于函數傅里葉變換的乘積，表達式如下：

3應用

網絡表示學習在社會生產中有非常廣泛的應用。本文給出了網絡表示學習模型適用性與特點的比較，以及研究中可能會用到的數據集及其分類統計信息，整理了部分模型的實現鏈接和已開源的圖深度學習庫，方便研究者快速復現驗證并掌握模型，討論了網絡表示學習的應用方向和實例。

3.1模型對比與數據集及開源實現

表2對比了網絡表示學習模型的適用性和方法特點，包括模型是否支持帶權圖、有向圖以及屬性圖，并給出了模型的時間復雜度和模型特點，可供研究者參考使用。表3給出了眾多測試算法性能的數據集，數據集包括3類，分別是引文網絡、社交網絡和化學生物網絡。對應于每個數據集，表中給出了數據集來源，分別統計了該數據集的子圖數、節點數、邊數、特征數和標簽類別數量，方便研究者選擇適合模型的數據集。

開源實現的模型總結如表4所示，圖深度學習開源庫總結如表5所示。在表4與表5中整理出了一些具有代表性模型的開源實現，以及強大的圖深度學習庫，可供研究者快速學習或復現驗證模型效果。其中在表5中列出的Euler，PGL，Plato圖深度學習庫支持分布式計算，使得更大規模的網絡計算成為可能。

3.2實際應用

網絡表示學習可以應用到許多實際任務中。可以寬泛地將應用分為4類，即節點分類、社區發現、鏈接預測和網絡可視化。

1）節點分類節點分類是網絡節點表示為向量后最常見的任務，一般屬于半監督的學習任務，即初始數據中數據標簽只占一部分，學習已有標簽的數據信息來標記其余數據的標簽。常見的半監督學習任務有視頻文檔網頁的類別標記、蛋白質生物功能的學習標記或者社交網絡中預測部分用戶的標簽信息。通常先抽取節點的屬性或結構特征來為節點生成嵌入信息，然后應用邏輯回歸等分類器為對應節點預測標簽。最近的研究評估表明這些模型對節點標簽的預測或分類有很高的精度。其中GcN為代表的圖卷積神經網絡對節點的分類精度要高于傳統方法，但它們都是對靜態圖進行嵌入分類。HAMILTON等提出歸納式學習模型Graphsage，利用鄰域信息學習聚合函數，以便對動態網絡中的新增節點進行嵌入和分類。

2）社區發現社區發現是在給定網絡中，將物理對象或抽象對象的集合分組為類似對象組成的多個社區。社區發現是無監督的聚類，即對大量未知標注的數據集按數據的內在相似性將數據劃分成多個類別，使得類別內數據相似度較大而類別間的數據相似度較小。與節點分類不同的是社區發現不需要任何標記信息，可應用范圍更廣，節省數據標記成本。在實際應用中，社區發現可以為藥物網絡劃分社區，幫助推測相似藥物，依據蛋白質網絡中節點的聯系將蛋白質自動分類。

3）鏈接預測網絡由實體間的交互信息構成，但在實體之間這種交互信息往往會缺失或者會在未來出現，在生物網絡分析中驗證節點之間是否存在鏈接需要復雜的實驗測試和高昂的代價，因此網絡的鏈接預測顯得尤為重要。鏈接預測在推薦系統中應用廣泛，例如WANG等和OU等預測了來自公共協作和社交網絡上的節點鏈接。另外，鏈接預測在生物網絡分析中也非常普遍，利用鏈接預測方法給出一個可能存在鏈接的序列是非常經濟有效的。

4）網絡可視化網絡表示學習為節點生成嵌入向量和網絡降維可視化提供了新方法。每一個節點都被表示為一個低維稠密的向量，可以方便地利用已有的降維可視化算法如t-SNE，LargeVis等生成網絡的二維或三維圖形，這對于發現網絡社區和其他隱藏結構有很大幫助。例如，Deepwalk的作者利用降維可視化嵌入的空手道俱樂部網絡來展現DeepWalk方法的優越之處。Line的作者利用LargeVis可視化DBLP作者網絡，表明LINE能夠將合作作者聚集在同一個領域。

4總結與展望

本文介紹了現有的網絡表示學習方法，將其分為兩類并細分為6個類別，分別是傳統方法、基于網絡結構的嵌入、融人屬性信息的嵌入，以及最近非常流行的基于譜域的圖卷積、基于空間的圖卷積和圖attention網絡。本文還對比了模型的適用性與算法特點，給出網絡表示學習中的經典數據集，整理了常用模型的開源實現項目以及8個開源的圖深度學習庫。最后還介紹了網絡表示學習的應用。網絡表示學習發展迅速，不斷取得成果，但在以下方面仍面臨挑戰。

1）深層的圖神經網絡學習不同于圖像分類任務，實驗表明，隨著網絡層數增加，相鄰節點的嵌人表示將會逐漸靠近直至收斂到一個點，圖神經網絡模型性能會急劇下降。

2）動態和異構網絡的表示真實世界中存在大量的異構網絡并且隨時間動態變化，大多方法模型將網絡簡化為同構的靜止不變的網絡去處理?，F有的解決動態異構網絡表示的模型仍有很大的提升空間。

3）網絡模型的泛化能力實際場景中的網絡往往復雜且差異較大，現有的網絡模型設計都是針對某一種簡化的網絡，設計一個能泛化到大量網絡的模型是一個值得深入研究的問題。