基于融合元路徑權重的異質網絡表征學習①

蔣宗禮,陳浩強,張津麗

(北京工業大學 信息學部,北京 100124)

隨著互聯網技術的不斷發展,現實生活中出現了大量的信息網絡,如社交網絡、論文引用網絡、電商信息網絡.信息網絡中包含豐富的數據信息,對這些數據進行多角度、多層次的分析具有重要意義.例如,分析電商信息網絡中用戶購物數據可獲知用戶的喜好信息,進而可優化電商系統中的商品推薦系統.但是,信息網絡中一般包含數百萬個數據節點和節點之間的連接(稱為“邊”),因此在原始信息網絡中執行復雜的推理、操作將消耗大量計算資源.目前,一種行之有效的解決方法是對信息網絡進行網絡表征學習以降低信息網絡中數據的表示維度.網絡表征學習可將信息網絡中節點或者邊映射到低維向量空間,即通過降維處理,得到節點或者邊的低維、實值、稠密的向量形式,并且在低維空間中具有表示以及推理能力[1].

目前,信息網絡表征學習研究中大部分工作聚焦于同質信息網絡(信息網絡中包含單一類型的節點及單一類型的邊)[2].比如,Perozzi B等[3]首次提出以隨機游走為基礎的網絡表征學習模型DeepWalk.該模型將信息網絡中數據節點視為單詞,節點序列視為句子,然后通過隨機游走構建由節點序列組成的語料庫,進而結合自然語言處理領域中Skip-gram[4]模型學習信息網絡中節點的低維表征.其實驗結果表明隨機游走技術可有效提取信息網絡中結構信息并應用于節點的表征學習.在DeepWalk的基礎上Grover A等[5]提出了應用深度優先隨機游走和廣度優先隨機游走提取信息網絡中結構信息并結合Skip-gram模型的Node2Vec網絡表征學習模型.相比于DeepWalk模型Node2Vec模型在信息網絡的低維表征中保留了更多的結構信息,其在分類實驗中的準確率同樣優于DeepWalk模型.除應用隨機游走技術獲取信息網絡中結構信息進行表征學習外,Tang J[6]提出了應用節點間一介相似性和節點間二階相似性提取網絡結構信息進行表征學習的LINE 模型.此外,Yang C[7]、Cao SS[8]、Tu CC[9]等還提出了基于矩陣分解的網絡表征學習方法.

相比于同質信息網絡,異質信息網絡中包含多種類型的數據節點或者邊[10],導致同質信息網絡的表征學習方法不適用于異質網絡.異質網絡表征學習中元路徑是一個極其重要的概念,Shi C等[11-13]對此進行了整理、研究.這些研究發現元路徑可表示節點類型間的復合關系,不同元路徑表示不同的語義信息,基于不同元路徑的表征學習方法可造成不同的分析結果和特征表示.此外,Zhang JL等[14]利用不同元路徑表示的語義信息對異質信息網絡進行表征學習.在元路徑的基礎上Dong YX等[15]提出了Metapath2Vec異質信息網絡表征學習模型.該模型首次應用基于元路徑的隨機游走獲取異質網絡中的結構信息并結合Skip-gram模型學習異質網絡中節點的低維表征,從而在低維表征中融入元路徑所表示的語義信息.但是,該模型僅基于單條元路徑對異質網絡進行隨機游走以獲取異質信息網絡的結構信息.然而異質信息網絡中存在多條元路徑,導致Metapath2Vec模型學習的低維表征中缺失原始網絡中部分結構信息和其它元路徑表示的語義信息.

針對上述問題,本文提出了基于融合元路徑權重的異質網絡表征.該表征學習方法首先針對異質網絡提取元路徑集合,然后學習元路徑權重并以此為基礎對基于不同元路徑的低維表征進行加權融合,得到一個低維、實值、稠密且融合不同元路徑語義信息的異質網絡表征.該低維表征中包含豐富的結構信息以及不同元路徑表示的語義信息.本文的主要貢獻可概括為以下3點：

(1)在異質網絡表征學習中引入元路徑權重,通過對基于不同元路徑的低維表征進行加權融合,解決了低維表征中缺失原始網絡中結構信息以及缺失其它元路徑表示的語義信息問題.

(2)基于融合元路徑權重的異質網絡表征學習在不同數據規模的異質網絡中具有良好的表征學習能力,并可有效應用于數據挖掘.

(3)在實際數據集上進行的對比試驗驗證了基于融合元路徑權重的異質網絡表征學習方法的正確性、有效性.

1 基本概念

信息網絡[12]用于表示由數據節點以及節點之間聯系組成的數據網絡,可定義為有向圖.

定義1.信息網絡G=(V,E),其中V表示信息網絡中數據節點的集合,E表示節點之間邊的集合.定義映射函數 Φ :V→A表示節點與節點類型之間的映射關系,即對任意節點v∈V都有唯一的節點類型 Φ(v)∈A與之對應.定義映射函數 Ψ :E→R表示邊與邊類型之間的映射關系,即對任意一條邊e∈E都有唯一的邊類型Ψ(e)∈R與之對應.當節點類型數|A|＞1或者邊類型數|R|＞1時,該信息網絡為異質信息網絡.

如圖1(a)所示,作者合著網絡為同質信息網絡,其中只包含作者類型的數據節點以及表示節點之間合著關系的邊.圖1(b)所示的學術文獻網絡為異質信息網絡,其中包含3種節點類型,分別為作者、文章、會議.同時,包含兩種邊類型,分別用于表示作者與文章之間的撰寫與被撰寫關系以及文章與會議之間的發表與被發表關系.

網絡模式[10]是信息網絡G=(V,E)的元級描述.

定義2.網絡模式TG=(A,R).其中A為信息網絡G中節點類型集合,R為信息網絡G中邊類型集合.

例如,在圖1(b)的基礎上可定義學術文獻網絡的網絡模式.如圖1(c)所示,該網絡模式為由3種節點類型和兩種邊類型構成的有向圖.

在網絡模式的基礎上可定義元路徑[16],用于表示節點類型間的復合關系.

定義3.給定異質信息網絡的網絡模式TG=(A,R),其元路徑定義為即在節點類型A1與Al+1之間定義長度為l的復合關系Rc=R1°R2°···°Rl,其中 ° 表示關系間的復合算子.

元路徑不僅刻畫了對象之間的語義關系,而且能夠提取對象之間的特征信息[16].例如,根據定義,可基于圖1(c)中的網絡模式定義學術文獻網絡的元路徑,如APA、APCPA、APAPA等.不同元路徑表示不同的語義信息,比如,APA表示兩個作者合著完成了一篇文章,而APCPA則表示兩個作者在同一個會議中發表了文章,前者語義中側重于文章,后者則側重于會議.

異質信息網絡中存在多條元路徑,基于不同元路徑的表征學習方法可造成不同的分析結果和特征表示.為表示不同元路徑對異質網絡表征學習的重要程度,本文對元路徑賦予相應的權重值.

定義4.元路徑集合P={p1,p2,···,pn},對于任意一條元路徑pi∈P都有權重wpi與之對{應,各條元路徑的權重值構成元路徑的權重集合其中wp1+wp1+···+wpn=1.

網絡表征學習[17]用于降低信息網絡中數據節點的表示維度.

定義5.對于給定的信息網絡G=(V,E),網絡表征學習的目標是通過對目標函數fG=V→Ld的學習將信息網絡中的節點在低維空間Ld中進行向量表示,從而得到信息網絡的低維表征M∈ R|V|×d,其中d?|V|.低維空間Ld中的低維表征需盡可能保留原始信息網絡中的結構信息,以便低維表征在低維空間中具有良好的表示、推理能力.

圖1 信息網絡及網絡模式

2 基于融合元路徑權重的異質網絡表征學習

異質網絡表征學習中元路徑具有刻畫對象之間語義關系以及能夠抽取對象之間特征信息的特點,經常用于指導獲取異質信息網絡的結構信息.異質信息網絡中不同元路徑表示不同的語義信息,因此基于不同元路徑的表征學習方法可造成不同的分析結果和特征表示.但是,現有的異質網絡表征學習方法往往采用單條元路徑提取節點間結構信息,進而學習節點的低維表征.導致學習到的低維表征中缺失原始信息網絡中部分結構信息及其它元路徑表示的語義信息,影響低維表征在低維空間中的表示、推理能力,進而影響其在數據挖掘任務中的有效性.基于融合元路徑權重的異質網絡表征學習方法學習到的低維表征融合了不同元路徑表示的語義信息,在低維空間中具有良好的表示、推理能力,提高了低維表征在數據挖掘任務中的有效性.如圖2所示,基于融合元路徑權重的異質網絡表征學習方法包含4個處理階段：階段1用于構建元路徑集合.階段2對元路徑集合進行權重學習.階段3根據元路徑集合學習各個元路徑所對應的異質信息網絡的低維表征.階段4將基于元路徑權重對各個低維表征進行融合.

2.1 階段 1：構建元路徑集合

此階段首先根據實際生活中的異質信息網絡定義其網絡模式.對異質信息網絡G=(V,E),其節點類型數|A|＞1或者邊類型數|R|＞1,定義其網絡模式為TG=(A,R).然后,基于網絡模式定義不同的元路徑pi,從而構建異質信息網絡的元路徑集合P={p1,p2,···,pn}.

2.2 階段 2：元路徑權重學習

目前,多個研究發現不同元路徑對異質網絡表征學習的重要程度不同[14,16,18].因此,階段2中應用HeteClass[18]框架中的元路徑權重學習思想對階段1中

應用上述元路徑權重學習思想實現了元路徑權重學習程序并對元路徑集合P={p1,p2,···,pn}進行權重學習,以此計算元路徑的權重并構建元路徑的權重集合

圖2 基于融合元路徑權重的異質網絡表征學習

2.3 階段3：異質信息網絡的表征學習

階段3將根據元路徑集合對異質信息網絡進行表征學習.本文采用基于元路徑的隨機游走技術[15]獲取異質信息網絡中節點序列集,結合Skip-gram[4]模型學習異質信息網絡的低維表征.

基于元路徑的隨機游走技術是Dong YX[15]等人提構建的元路徑集合進行權重學習,為元路徑賦予權重值,以此表明不同元路徑對異質信息網絡表征學習的重要程度.

HeteClass框架是Gupta M等[18]提出的一種基于元路徑的直推式分類框架.該框架提出了一種基于目標類型對象之間關聯程度的元路徑權重學習方法.該方法以最大化相同標簽對象之間的相關性,同時最小化不同標簽對象之間的相關性為思想提出了式(1)所示的損失函數.其中 θk表示第k個元路徑的重要程度,vi,vj表示帶標簽的目標類型對象.Sign為符號函數,用于表示目標類型對象是否具有相同標簽信息,若相同值為1,否則值為-1.Simpk為目標對象的相關性矩陣[19].λ為正則化系數,‖·‖為 ?2范數.該學習方法通過最小化目標函數計算元路徑權重.出的一種基于元路徑的圖隨機遍歷技術.對于給定的異質信息網絡G=(V,E)和元路徑隨機游走的起始節點為A1類型節點,第i+ 1個游走節點的選擇概率如式(2)所示.其中表示At類型的節點,表示節點的鄰域中At+1類型的節點數量.第i+ 1個游走節點應從節點的所有At+1類型的鄰居節點中隨機選擇.基于節點選擇概率,隨機游走將在元路徑的指導下游走出包含元路徑語義信息以及異質信息網絡中結構信息的節點序列.

Skip-gram模型是Mikolov T等[4]提出的用于自然語言處理中學習大型數據集中單詞的連續向量表征的神經網絡模型.Skip-gram模型具有三層網絡結構,分別為輸入層、隱藏層和輸出層,并提出了式(3)所示的損失函數[20].其中,C為上下文中單詞數量,V為語料庫中單詞數量,wI表示輸入的單詞,wO,i表示第i個輸出的上下文單詞,j*c為輸出層輸出的第c個上下文單詞在語料庫中的真實索引,u表示單詞從隱藏層到輸出層過程中的計算分數.該模型輸入為由文本中句子構成的語料庫,通過最小化損失函數,學習語料庫中單詞的低維表征.

目前,DeepWalk[3]、Node2Vec[5]、Metapath2Vec[15]等研究發現將信息網絡中節點信息映射為自然語言可應用Skip-gram模型學習信息網絡中節點的低維表征.基于元路徑的隨機游走技術可提取包含元路徑語義信息、網絡結構信息的節點序列,從而將異質信息網絡中的節點信息映射為自然語言,進而可結合Skip-gram模型學習異質信息網絡中節點的低維表征.

如圖2中階段3所示,首先應用基于元路徑的隨機游走技術獲取異質信息網絡中的節點序列.對任意元路徑pi∈P獲取其相應的節點序列集cpi并構建語料庫集合C={cp1,cp2,···,cpn}.

對語料庫集合中任意一個節點序列集cpi應用Skip-gram模型學習異質信息網絡的低維表征Mpi.此時,任意元路徑pi都有唯一的低維表征Mpi與之對應.各個低維表征構成了基于不同元路徑的低維表征集合M={Mp1,Mp2,···,Mpn}.

2.4 階段4：基于元路徑權重對低維表征進行融合

此階段基于元路徑權重集合W={wp1,wp2,···,wpn}對低維表征集合M={Mp1,Mp2,···,Mpn}進行加權融合.對于任意的低維表征Mpi均基于相應的元路徑pi,所以低維表征Mpi中僅包含元路徑pi所表示的語義信息,導致基于單一元路徑的低維表征中缺失其它元路徑表示的語義信息.而元路徑因語義信息的不同對表征學習的重要程度不同,從而具有不同的權重.所以對基于不同元路徑的低維表征進行加權融合可得到融合不同元路徑語義信息的低維表征,從而提高低維表征質量.因此,本文提出了式(4)所示的低維表征融合公式,并基于該公式實現了基于元路徑權重的低維表征融合算法.

如算法1所示,該算法的輸入為元路徑權重集合、低維表征集合以及低維表征維度,然后依次對低維表征中d個特征分量進行加權融合,得到融合不同元路徑語義信息的低維表征MW.低維表征MW不僅包含不同元路徑的語義信息,而且還包含豐富的網絡結構信息.以上特點使得基于融合元路徑權重的低維表征在低維空間中具有良好的表示、推理能力,并且可有效應用于數據挖掘任務.

算法1.基于元路徑權重的低維表征融合算法images/BZ_36_1632_2616_1903_2653.pngimages/BZ_36_2137_2616_2262_2653.pngimages/BZ_36_1290_2667_1457_2705.png輸入：元路徑權重集合,低維表征集合,維度d images/BZ_36_1775_2723_1825_2752.png輸出：融合元路徑權重的低維表征images/BZ_36_1375_2769_1554_2798.png1.for doimages/BZ_36_1324_2824_1953_2857.png2.3.end for

3 實驗結果與分析

為證明本文提出的基于融合元路徑權重的異質網絡表征學習方法的正確性以及在數據挖掘任務中的有效性,本文對實際數據集進行了節點分類對比試驗.

3.1 實驗數據集

實驗所用數據集為AMIner[15,21]數據集,該數據集為典型的異質學術文獻信息網絡.如表1所示,該數據集中包含作者、文章、會議3種節點類型,共計4891 819個數據節點,其中246 678個帶標簽的作者節點被分為8個類別,分別為Computing Systems,Theoretical Computer Science,Computer Networks & Wireless Communication,Computer Graphics,Human Computer Interaction,Computational Linguistics,Computer Vision &Pattern Recognition,Databases & Information Systems.

表1 AMIner數據集中的節點

如表2所示,AMiner數據集中共包含12 518 144個邊,其中表示文章與作者之間撰寫與被撰寫關系的邊共9323 739個,表示文章與會議之間發表與被發表關系的邊共3194 405個.

表2 AMIner數據集中的邊

此外,本文在AMIner數據集的基礎上構建數據規模較小的子數據集AMIner-Small,用于驗證本文提出的基于融合元路徑權重的異質網絡表征學習方法對不同數據規模的異質信息網絡的表征學習能力.如表3所示,AMIner-Small數據集中數據規模遠遠小于AMiner數據集.

表3 AMIner-Small數據集中的節點

3.2 評價指標

在分類實驗中,數據的低維表征質量對實驗結果具有重要影響,因此本文通過實驗結果評價低維表征質量,進而分析異質網絡表征學習方法的正確性、有效性.

本文采用分類精確率(Precision)、召回率(Recall)、Micro-F1分數、Macro-F1分數評價分類實驗結果,從而評價不同異質網絡表征學習方法的正確性、在數據挖掘任務中的有效性.

分類精確率為預測為正類的樣本中實際為正類的樣本比例.召回率表示預測為正類的樣本數占全部正類樣本數的比例.F1分數(Micro-F1分數、Macro-F1分數)表示精確度和召回率的加權平均值.以上4個評價指標值越高表示分類實驗越精確,相應的低維表征質量越高、異質網絡表征學習方法越正確、有效.

3.3 節點分類實驗

3.3.1 AMIner-Small數據集的節點分類實驗

采用HIN2Vec[17]異質網絡表征框架作為對比實驗方法.不同于之前基于Skip-gram模型的表征方法,HIN2Vec核心是一個神經網路模型,并且將元路徑視為節點間的不同類型關系,然后通過捕獲節點間不同類型關系學習節點的低維表征.

首先在AMIner-Small數據集的基礎上構建元路徑集合并學習各個元路徑的權重.權重學習實驗重復十次,結果如表4所示,其中APA的權重均值為0.01,APAPA的權重均值為0.02,APCPA的權重均值為0.97.根據元路徑權重學習結果發現在AMIner-Small數據集中元路徑APCPA表示的語義信息對異質網絡表征學習的重要程度遠高于APA、APAPA表示的語義信息,而APA、APAPA表示的語義信息對異質網絡表征學習的重要程度則十分接近.

表4 元路徑及其權重

在元路徑集合及權重的基礎上分別應用本文提出的基于融合元路徑權重的異質網絡表征學習方法以及HIN2Vec框架學習AMIner-Small數據集中節點的低維表征.然后將帶標簽的675個作者節點的低維表征作為特征向量訓練和測試SVM分類器.分類實驗中將675個低維表征按70%/30%比例隨機分為訓練數據集與測試數據集,分類結果是取10次實驗結果的均值.具體實驗結果如表5所示,其中FMPW表示本文提出的基于融合元路徑權重的異質網絡表征學習方法.

表5 AMIner-Small數據集中作者節點分類結果

根據實驗結果發現本文提出的基于融合元路徑權重的異質網絡表征學習方法在分類精確率、召回率、Micro-F1分數、Macro-F1分數上均明顯高于HIN2Vec方法.該結果表明基于融合元路徑權重的異質網絡表征學習方法對小規模異質網絡具有良好的表征學習能力,證明了該方法的正確性、有效性.

3.3.2 AMIner數據集的節點分類實驗

由于AMIner數據集中數據規模遠大于AMiner-Small數據集,導致HIN2Vec不能處理AMiner數據集,所以本文采用Metapath2Vec[15]異質網絡表征方法作為對比實驗方法.Metapath2Vec應用基于單條元路徑的隨機游走獲取異質網絡中的結構信息并結合Skip-gram模型需學習異質網絡的低維表征.

此部分實驗中,實驗步驟與AMIner-Small數據集中分類的實驗步驟一致,首先提取元路徑APA、APAPA、APCPA構成元路徑集合并學習其權重,然后分別采用本文提出的基于融合元路徑權重的異質網絡表征學習方法和Metapath2Vec方法學習AMIner數據集中節點的低維表征.

元路徑權重學習的實驗結果與AMIner-Small數據集中的元路徑權重學習結果一致,即APA的權重均值為0.01,APAPA的權重均值為0.02,APCPA的權重均值為0.97.該結果表示在AMIner數據集中APCPA表示的語義信息對異質網絡表征學習的影響程度最大.

本文在全部節點的低維表征中隨機挑選47 108個帶標簽的作者的低維表征作為SVM分類器的特征向量,其中訓練集比例為10%～90%,其余節點為測試集.實驗重復十次并取平均值,結果如圖3所示,其中FMPW表示本文提出的基于融合元路徑權重的異質網絡表征學習方法.

根據實驗結果可知,隨著訓練集比例的提高,分類結果越加精確.而且本文提出的基于融合元路徑權重的異質網絡表征學習方法的分類精確率、召回率、Micro-F1分數、Macro-F1分數中均明顯高于基于元路徑APA和基于元路徑APAPA的Metapath2Vec方法,但是僅率高于基于APCPA的Metapath2Vec方法.造成以上結果的原因在于,元路徑APCPA的 權重為0.97,導致融合不同元路徑的低維表征中APCPA對應的低維表征占主要比例.該結果從側面驗證了元路徑權重學習結果的正確性.此外,基于圖3所示的實驗結果發現基于不同元路徑的Metapath2Vec方法學習的低維表征質量差別大,導致應用Metapath2Vec方法學習異質網絡的低維表征時結果具有不確定性.而本文提出的基于融合元路徑權重的異質網絡表征學習方法可得出最優結果,從而有效解決上述問題.

3.4 實驗分析

綜合以上實驗結果可知,基于融合元路徑權重的異質網絡表征學習方法可應用于不同數據規模的異質網絡,并且在不同數據規模的異質網絡中分類實驗結果優于基準方法HIN2Vec和Metapath2Vec.因此本文提出的基于融合元路徑權重的異質網絡表征學習方法對不同數據規模的異質網絡具有良好的表征學習能力,可學習得到高質量的低維表征,可有效應用于數據挖掘任務,并且優于基于單條元路徑的異質網絡表征學習方法.

4 結論

本文提出基于融合元路徑權重的異質網絡表征學習方法,通過元路徑權重學習表明元路對異質網絡表征學習的重要程度,并以此為基礎對基于不同元路徑的低維表征進行加權融合,得到融合不同元路徑語義信息的異質網絡表征.該方法解決了基于單條元路徑的異質網絡表征學習方法不能包含其它元路徑語義信息而導致的低維表征中缺失結構信息、語義信息的問題.同時通過對比試驗證明本文提出的基于融合元路徑權重的異質網絡表征學習方法在不同數據規模的異質網絡中具有良好的表征學習能力,并且可有效應用于數據挖掘任務.在未來的工作中,將對如何提高大規模異質網絡的表征學習效率進行深入研究.