魯軍豪 許云峰

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

關(guān)鍵詞：計算機神經(jīng)網(wǎng)絡(luò);網(wǎng)絡(luò);表示學習;圖神經(jīng)網(wǎng)絡(luò);圖卷積;圖深度學習庫

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

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

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

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

本文給定了表示學習方法公式中常見的符號定義，對網(wǎng)絡(luò)表示學習方法進行詳細的闡述，整理對比了各模型的適用性與優(yōu)缺點，給出了基礎(chǔ)數(shù)據(jù)集和開源實現(xiàn)的表示學習模型和圖深度學習庫，對網(wǎng)絡(luò)表示學習的應(yīng)用進行了介紹，并對網(wǎng)絡(luò)表示學習的未來進行了展望。

1網(wǎng)絡(luò)表示學習的基本定義

網(wǎng)絡(luò)表示學習公式中常見的符號及其含義如表1所示。

2網(wǎng)絡(luò)表示學習方法

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

2.1網(wǎng)絡(luò)節(jié)點嵌入方法

2.1.1傳統(tǒng)方法

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

2.1.2基于網(wǎng)絡(luò)結(jié)構(gòu)的嵌入方法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2圖神經(jīng)網(wǎng)絡(luò)方法

2.2.1基于譜域的圖卷積

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

3應(yīng)用

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

3.1模型對比與數(shù)據(jù)集及開源實現(xiàn)

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

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

3.2實際應(yīng)用

網(wǎng)絡(luò)表示學習可以應(yīng)用到許多實際任務(wù)中?？梢詫挿旱貙?yīng)用分為4類，即節(jié)點分類、社區(qū)發(fā)現(xiàn)、鏈接預(yù)測和網(wǎng)絡(luò)可視化。

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

2）社區(qū)發(fā)現(xiàn)社區(qū)發(fā)現(xiàn)是在給定網(wǎng)絡(luò)中，將物理對象或抽象對象的集合分組為類似對象組成的多個社區(qū)。社區(qū)發(fā)現(xiàn)是無監(jiān)督的聚類，即對大量未知標注的數(shù)據(jù)集按數(shù)據(jù)的內(nèi)在相似性將數(shù)據(jù)劃分成多個類別，使得類別內(nèi)數(shù)據(jù)相似度較大而類別間的數(shù)據(jù)相似度較小。與節(jié)點分類不同的是社區(qū)發(fā)現(xiàn)不需要任何標記信息，可應(yīng)用范圍更廣，節(jié)省數(shù)據(jù)標記成本。在實際應(yīng)用中，社區(qū)發(fā)現(xiàn)可以為藥物網(wǎng)絡(luò)劃分社區(qū)，幫助推測相似藥物，依據(jù)蛋白質(zhì)網(wǎng)絡(luò)中節(jié)點的聯(lián)系將蛋白質(zhì)自動分類。

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

4）網(wǎng)絡(luò)可視化網(wǎng)絡(luò)表示學習為節(jié)點生成嵌入向量和網(wǎng)絡(luò)降維可視化提供了新方法。每一個節(jié)點都被表示為一個低維稠密的向量，可以方便地利用已有的降維可視化算法如t-SNE，LargeVis等生成網(wǎng)絡(luò)的二維或三維圖形，這對于發(fā)現(xiàn)網(wǎng)絡(luò)社區(qū)和其他隱藏結(jié)構(gòu)有很大幫助。例如，Deepwalk的作者利用降維可視化嵌入的空手道俱樂部網(wǎng)絡(luò)來展現(xiàn)DeepWalk方法的優(yōu)越之處。Line的作者利用LargeVis可視化DBLP作者網(wǎng)絡(luò)，表明LINE能夠?qū)⒑献髯髡呔奂谕粋€領(lǐng)域。

4總結(jié)與展望

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

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

2）動態(tài)和異構(gòu)網(wǎng)絡(luò)的表示真實世界中存在大量的異構(gòu)網(wǎng)絡(luò)并且隨時間動態(tài)變化，大多方法模型將網(wǎng)絡(luò)簡化為同構(gòu)的靜止不變的網(wǎng)絡(luò)去處理?，F(xiàn)有的解決動態(tài)異構(gòu)網(wǎng)絡(luò)表示的模型仍有很大的提升空間。

3）網(wǎng)絡(luò)模型的泛化能力實際場景中的網(wǎng)絡(luò)往往復(fù)雜且差異較大，現(xiàn)有的網(wǎng)絡(luò)模型設(shè)計都是針對某一種簡化的網(wǎng)絡(luò)，設(shè)計一個能泛化到大量網(wǎng)絡(luò)的模型是一個值得深入研究的問題。