嵌入雙曲層的神經排序式圖表示學習方法

唐素勤,劉笑梅,袁 磊

(廣西師范大學 a.教育學部; b.廣西多源信息挖掘與安全重點實驗室,廣西 桂林 541004)

0 概述

網絡圖包含一組相互連接的節點,其中,每對節點之間具有大量的關系信息[1]。幾乎每個領域都需要對圖進行分析,例如,在生物網絡中,人們可能需要分類蛋白質的角色,或者預測現有藥物分子的新應用;在社交網絡中,需要有針對性地向用戶投放廣告或推薦新朋友等。因此,研究人員開發了各種圖數據挖掘算法應用于節點分類、標簽推薦、異常檢測和鏈接預測等任務。但是,這些已有的圖數據挖掘算法通常需要一組圖特征信息作為算法的輸入。例如,為了從圖中提取結構信息,傳統的方法通常依靠圖的相關統計(如度、聚集系數等)、核函數或手工特征來測量局部近鄰結構[2],然而這些手工設計的特征在學習過程中不能自適應,且需要大量的人力成本和專業知識[3]。因此,有學者提出了表示學習方法以避免耗時且成本昂貴的特征設計,該方法同時提高了特征的靈活性。

現有的圖表示學習方法主要聚焦于為圖數據設計新的神經網絡模型或設計更加復雜的隨機游走機制來探索網絡結構,這些方法往往使圖表示學習的復雜性大幅提高。最近,將數據嵌入非歐幾里德空間的方法受到越來越多的關注,原因是歐幾里德模型不能正確地反映復雜數據模式。受此啟發,本文對神經網絡表示設置適當的幾何結構,特別是層次結構和聚集行為,以捕獲圖數據的基本屬性。圖數據的這些基本屬性出現在許多遵循冪律分布的現實復雜網絡場景中,可作為引入雙曲幾何的起點。雙曲空間能夠反映復雜網絡的屬性主要是由于其潛在的關鍵屬性,即空間量隨著距參考點的距離呈指數增長,這與歐幾里德空間中較慢的多項式增長相反。因此,本文探索雙曲空間是否有助于學習圖數據的嵌入,即通過使用神經網絡對相互作用或關系進行建模,并利用數據所存在的流形度量結構來學習得到節點的低維緊湊特征向量表示。

通過對圖表示學習方法和復雜網絡中雙曲幾何理論進行分析,本文提出一種嵌入雙曲層的神經排序式圖表示學習方法Neural-HRNE。該方法利用神經網絡的無監督端到端方式以及雙曲幾何的分層自組織能力來自動抽取節點的相似性和層次結構信息。Neural-HRNE方法沒有使用過度復雜的節點交互機制,而是提出一種更小更快的神經排序架構來實現同樣的性能。其中,利用貝葉斯個性化排序(Bayesian Personalized Ranking,BPR)[4]目標來捕獲節點表示向量之間的局部拓撲結構相似性。文獻[5]研究表明,在Lorentz模型中學習嵌入比在Poincaré球中更加有效,其不僅更適用于上下層級關系的建模,而且能非常有效地執行黎曼優化并避免由Poincaré距離產生的數值不穩定性問題。因此,在Neural-HRNE方法中,本文將距離度量轉換為所嵌入雙曲面模型中的度量,圖中的節點能利用雙曲幾何特性自組織為分層結構,從而使得Neural-HRNE方法可以高效地提取節點的潛在特征表示。在學習得到節點的潛在特征向量表示后,本文在多個不同尺度的數據集上分別進行節點推薦和節點分類任務,通過對比幾種不同空間中的圖表示學習方法來驗證所提方法的有效性,并分析其維度敏感性和模型收斂性。

1 相關工作

早期的圖表示學習可追溯到2000年,當時的算法主要將圖表示學習作為降維技術的一部分,通過特征分解圖的關聯矩陣來得到節點的特征向量。但是,就節點數量而言,多數算法通常至少具有二次時間復雜度,可擴展性較低限制了它們在大規模圖上的應用[6]。與特征工程中需要人工設計特征不同,深度學習會自動從數據中學習特征表示,這使得特征工程向特征學習轉變。近期的圖表示學習方法主要集中于為圖數據設計新的神經網絡模型。DeepWalk[7]首先使用隨機游走從輸入圖中采樣一組路徑,將采樣的路徑類比于來自語料庫的句子,從而利用神經語言模型Skip-Gram學習得到節點的特征向量表示。DeepWalk的成功激發了許多后續的研究,如Node2vec[8]和LINE[9]等。使用遞歸神經網絡模型GRU來嵌入信息的級聯路徑以及將鄰接矩陣輸入到自編碼器中重構鄰域相似的節點也是較典型的方法。作為另一種流行的深度學習模型,卷積神經網絡及其變體也被廣泛應用于圖表示學習。自2008年以來,研究人員聚焦于直接為復雜網絡設計有效且可擴展的表示學習技術,且其表現出了良好的性能并能適用于各種應用[6]。

2 模型構建

本文的圖表示學習方法Neural-HRNE利用BPR來捕獲節點之間的局部拓撲結構相似性,并通過雙曲幾何中的雙曲面模型來有效探索圖的拓撲結構信息,特別是層級結構。模型的整體架構如圖1所示,該模型使用的神經網絡結構主要包括輸入層、嵌入層、隱藏層、雙曲層、輸出層和BPR層。具體而言,模型具有共享參數的2個部分,即一個接受正確的節點鏈接,另一個接受錯誤的節點鏈接,并旨在最大化正確鏈接和錯誤鏈接之間的差距。其中,嵌入層根據節點的局部鄰居結構學習節點的統一矢量表示,隱藏層應用非線性降維嵌入節點的向量,雙曲層使用雙曲面模型來探索圖的層次結構信息,即通過嵌入空間中的雙曲面距離來建模節點對之間的關系,輸出層和BPR層通過反向傳播開啟模型推斷。

圖1 Neural-HRNE模型整體架構

2.1 輸入層和嵌入層

fu=LOOKUP(P,nu)

(1)

在具體實現過程中,本文使用預訓練節點嵌入來初始化嵌入層,嵌入矩陣P在學習過程中迭代更新。

2.2 隱藏層

(2)

2.3 雙曲層

(3)

(4)

因此,雙曲層將節點之間的雙曲距離定義為:

(5)

2.4 輸出層和BPR層

Neural-HRNE方法通過式(6)的線性變換傳遞雙曲距離:

s(hu,hi)=Wsd(hu,hi)+bs

(6)

(7)

(8)

Neural-HRNE方法的嵌入目標是最大化式(8)。為了便于計算,最小化負對數似然損失函數的和,如下:

(9)

2.5 優化和學習

算法1Riemannian Stochastic Gradient Descent

Inputlearning rateη,number of epochsT

for t=1,2,…,T

土地是財富之母，是我國農村人口的重要財富來源與財富象征；同時，土地是重要的生產和生活資料。貴州省山多地少，可以利用的土地資源稀缺，因此，充分利用好土地資源，通過政策、工程手段、科學技術等發揮其潛在價值，對于貴州省實施精準扶貧，幫助農村地區貧困人口擺脫貧困，走可持續發展的致富之路具有重要的理論意義和現實價值。

grad f(θt)←projθt(ht)

θt+1←expθt(-η grad f(θt))

3 實驗結果與分析

將本文方法與現有學習方法進行比較,其中,選取一些常見的具有明確上下級層次結構的概念網絡以及未明確編碼對象層次結構關系的基準圖數據集,以評估各方法的節點推薦和節點分類任務效果,最后分析各方法在不同表示學習空間中的性能,即在歐幾里德、Poincaré和雙曲面模型中分析各方法對維度的敏感性和模型的收斂性。

3.1 實驗設置

本文考慮具有明確上下級層次結構的數據和非樹狀的有向無環圖結構,數據集的相關統計信息如表1所示。其中:

1)WordNet[16]是一個龐大的英文詞匯數據庫,在WordNet中,名詞、動詞、形容詞和副詞各自被組成一個同義詞網絡,每個同義詞集合都代表一種基本的語義概念,本文嵌入WordNet的名詞和動詞層次結構。

2)ACM計算分類系統CCS[17]是由ACM計算機協會設計的用于分類計算機主題的系統,其可看作一種分層本體,各種ACM期刊使用該系統來按領域組織主題。

3)DBLP是來自DBLP數據集[18]的作者網絡,其中包括共同作者、作者引用和文本相似性視圖。本文抽取DBLP中的研究人員的共同作者圖,其標簽表明研究人員發表其研究成果的領域,本文選擇其中的“數據庫”“數據挖掘”“信息檢索”和“機器學習”4個不同的研究領域作為標簽。

4)PPI是蛋白質分子之間構建的蛋白質-蛋白質相互作用網絡[19]。本文使用PPI網絡的智人誘導子圖,只有人類基因被保留為節點。Hallmark基因集中提供的基因組被視為節點的類別并代表蛋白質生物狀態。

5)Wikipedia[20]是一個維基百科中儲存前100萬字節中單詞的共現網絡。在該數據集中,每個節點都是一個單詞,每條邊是單詞之間的共現關系,每個節點都有一個標簽,表示單詞的POS詞性。

表1 數據集的相關統計信息

在對比實驗中,所有方法均只使用節點的拓撲結構特征,選取一些基于歐幾里德的神經網絡嵌入和基于雙曲空間的圖嵌入方法。本文將Neural-HRNE雙曲層中的雙曲面度量替換為歐幾里德和Poincaré度量并以此來作為其中的對比基線。對比方法具體如下:

1)DNGR[21]采用隨機沖浪策略來捕獲圖結構信息,并進一步將這些結構信息轉換為正點互信息矩陣,然后訓練堆棧降噪自編碼器以學習節點表示。

2)HARP[22]遞歸地合并原始圖中的節點和邊以獲得具有相似性的一系列較小的連續圖結構體,合并的圖均具有不同的粒度,從而提供了原始圖的全局結構視圖。HARP可作為一種通用的元策略來改進圖嵌入算法,本文選取文獻[22]中表現較好的HARP(N2V)方法,其結合了Node2vec算法用于加強節點嵌入。

3)文獻[14]提出了一種雙曲空間中圖的神經嵌入算法,其采用與DeepWalk類似的方法,不同的是該算法不再使用歐幾里德度量,而使用Poincaré度量并在雙曲空間中通過反向傳播來學習節點的向量表示。

4)文獻[13]提出一種基于黎曼流形的“測地線凸錐”模型來學習層次嵌入,其有效解決了Order嵌入[23]和Poincaré嵌入[10]中嵌入空間維度災難、不能編碼不對稱關系和Poincaré球邊界坍塌問題。

本文嵌入模型中有若干用戶定義的超參數。其中,隱藏層中的神經元數量設置為150,嵌入模型中的正則化系數λ設置為0.000 05。在模型學習和優化過程中,設置學習率η為0.5,批量大小定為100。對于其他對比方法,使用網格搜索從集合{0.01,0.001,0.000 1}中選擇正則化系數,并從集合{0.01,0.05,0.1,0.5}中選擇學習率。對于其余的超參數,本文使用各方法在原文中所建議的默認參數值。設置所有節點的表示維度為50維。

3.2 節點推薦

節點推薦可用于相似性搜索等領域,其任務是根據自身的上下文向用戶推薦感興趣的對象。在現實場景中,推薦的節點有各種類型,如用戶興趣、社交朋友和查詢文檔等。使用表示學習的低維矢量通常比原始表示密集得多,這減輕了較多數據的稀疏性問題,使得查詢任務更加簡單和準確。

根據多數圖表示學習中的評估方法,本文對于給定的查詢節點,計算目標節點與查詢節點間的距離并對目標節點進行排序。在實驗中,評估本文所提方法在嵌入明確或隱含層級結構數據上的有效性。在評估過程中,本文分別使用上述5個數據集來評估嵌入質量,并將數據視為無向傳遞閉包,這樣的分層結構不能從觀察到的邊直接得出,而需要被推斷出來。為了測量嵌入質量,本文計算每個觀察到的邊(u,v)在嵌入空間中的相應距離d=(u,v),并按升序排列u的所有未觀察到的邊的距離,即{d=(u,v′):(u,v′)?D},得到原始的正確元組排名(越低越好),然后計算所有正確節點的前50平均精度均值MAP@50,結果如表2所示,其中,最優結果加粗表示。

表2 MAP@50結果對比

從表2可以看出,因為雙曲幾何的分層自組織能力,其所選擇的使用雙曲空間的表示學習方法比歐幾里德空間中的方法更加有效,特別是當學習的特征維度較低時,雙曲幾何能得到更加緊湊的表示,所以能夠更好地在有限空間中表示復雜函數。相比于雙曲幾何強層次嵌入方法,本文方法也表現出了較好的表達力,顯示出其性能優勢。

3.3 節點分類

節點分類通過在標記的節點嵌入集上應用分類器來進行訓練,即給定未標記節點的特征向量表示,訓練的分類器可以預測其類標簽。由于WordNet是一個詞典且CCS通常作為分類法使用,沒有可利用標簽,因此本文僅使用DBLP、PPI和Wikipedia數據集來評估嵌入表示的監督學習任務效果,即節點分類的有效性。

本文從數據集中隨機抽取不同比例的標記節點,并將它們用作訓練數據,其余的作為測試數據。對于歐幾里德模型,本文使用LibLinear庫中的one-vs-rest SVM分類器預測每個節點最可能的標簽,而對于雙曲模型,本文使用基于雙曲距離的內核訓練SVM分類模型。重復上述過程10次,表3和表4所示為DBLP、PPI和Wikipedia數據集中的各方法平均性能表現,最優結果加粗表示。

表3 DBLP數據集上的準確率對比

表4 PPI和Wikipedia數據集上的節點多標簽分類Macro-F1結果

從表3、表4可以看出,相比于經典的基于歐幾里德空間的方法,雙曲幾何對于數據的層次結構特征抽取更加有效,這有助于輕松高效地處理各種下游圖數據分析任務。隨著分類訓練數據的增加,各分類器的性能均在不斷提高,而對比于同等情況下使用歐幾里德嵌入的EuclideanEmb,本文提出的圖表示學習方法在Poincaré和雙曲面模型中性能均有所提高。在同是使用了雙曲幾何自組織能力的方法中,Neural-HRNE的結果基本持平或略微降低,這可能是由于Neural-HRNE中的節點采樣策略過于簡單,未探索到節點之間諸如同質性或結構等價性的關系,或者所設計的神經網絡較為淺層并直接使用了One-hot來初始化該神經網絡,導致方法學習性能有所降低。因此,下一步考慮探索結合復雜網絡和機器學習的更加高效的采樣策略和更加強健的神經網絡,以提高Neural-HRNE方法的性能。

3.4 模型性能分析

為了進一步說明雙曲面模型對圖表示學習性能的影響,本文選取僅改變雙曲層設置的表示學習方法進行比較。具體地,分別在EuclideanEmb、PoincaréEmb和Neural-HRNE方法中測試模型對表示學習維度的敏感性和模型的收斂性。圖2所示為不同空間學習方法在WordNet名詞層的維度敏感性和收斂性。圖2(a)為僅改變表示學習的維度后對WordNet名詞層的節點推薦結果MAP@50的影響,從中可以看出,相比于歐幾里德幾何,雙曲幾何對空間的使用效率更高,歐幾里德嵌入在維度較低時對特征的表達能力較弱,而雙曲幾何能在較低的維度時依然具有較好的表現性能,雙曲幾何大約在50維時就趨于穩定,其比歐幾里德更能提供緊湊的特征向量表示。圖2(b)為EuclideanEmb、PoincaréEmb和Neural-HRNE模型在50維時對WordNet名詞層中節點特征表示學習的收斂情況。從中可以看出,本文提出的神經排序網絡大約在10個時期內收斂,與歐幾里德嵌入相比,雙曲幾何的嵌入方法收斂更快,損失誤差更低。

圖2 3種方法在WordNet名詞中的維度敏感性和 模型收斂性結果對比

對不同空間中圖表示學習方法的維度敏感性和模型收斂性進行分析,結果表明,相比于歐幾里德嵌入,雙曲幾何能提供更高質量的嵌入,特別是在學習維度較低的情況下。本文提出的雙曲面模型表現出與Poincaré模型相當的性能,且其神經網絡模型具有高效的學習能力。

4 結束語

如何對圖中的節點進行有效的特征表示一直是圖挖掘領域的研究熱點。本文提出一種嵌入雙曲層的神經排序式圖表示學習方法,以提取節點的相似性和層次結構特性。該方法利用貝葉斯個性化排序作為其目標函數,并在其中加入一層雙曲層來度量節點對之間的局部拓撲結構相似性,利用黎曼梯度下降來學習更高效的節點特征向量表示。對比使用歐幾里德、Poincaré和雙曲面模型的不同表示學習方法的性能,結果表明,本文所提方法能夠更高效地學習節點特征,而且可以獲得更加緊湊、更具表達力的特征向量表示。嵌入雙曲空間中的層次結構能很好地獲取數據的基礎語義,下一步將探索雙曲空間的優化方法以提高嵌入質量并獲得更快的收斂速度。此外,將雙曲嵌入有效地整合到下游的任務和應用中,以及在多關系數據或圖像等更復雜的數據嵌入中應用雙曲幾何理論,也是今后的研究重點。