半監督全局異構信息保存的網絡表示學習

李 征

(常州信息職業技術學院電子工程學院 江蘇 常州 213164) (江蘇科技大學電子信息學院 江蘇 鎮江 212003)

0 引 言

網絡在各種各樣的現實世界場景中無處不在,如社交網絡、評論網絡和新聞媒體等[1-2]。目前,網絡表示學習的基本思想是將網絡中的節點映射到低維空間中,同時保持原始網絡的結構信息和屬性,它可以為許多下游數據挖掘應用提供幫助,如鏈路預測、節點分類、節點聚類和社區檢測[3-4]。

現有的網絡表示學習方法有許多是針對同質網絡設計的,即不管它們的類型是什么,它對所有的節點和邊都一視同仁,例如DeepWalk、LINE、node2vec、GraphSAGE、PRUNE和HARP等,然而,網絡通常包含由不同類型的關系連接起來的多種實體,稱為異構信息網絡(HINs)[5]。由于異構性,傳統的網絡表現學習方法不能滿足異構信息網絡的需要,近年來,一些研究論文在異構信息網絡的學習表示方面取得了豐碩的進展。Chang等[6]首先利用深度學習和卷積神經網絡來獲得異構信息網絡中的節點表示。Xu等[7]提出基于矩陣分解來獲取耦合異構信息網絡的結構信息。然而,深層神經網絡和矩陣分解方法都存在計算量大的問題。周麗等[8]提出了一種基于文本數據的半監督表示學習方法PTE,該方法將異構信息網絡分解為若干個二元網絡,然后學習網絡表示。蔣宗禮等[9]提出了一種異構跳圖模型metapath2vec,將基于元路徑的隨機游動形式化,構造異構鄰域,學習異構信息網絡的表示。雖然上述方法能夠應用于異構信息網絡,但其計算量大,且使用框架有相應的限制,另外無法全方位地保存異構信息。

針對上述分析,提出一種全局異構信息網絡表示學習框架,在保持異構信息網絡全局結構信息的同時,采用基于元路徑的隨機游走策略和自編碼器來提取語義信息。通過幾個異構信息網絡挖掘任務驗證了本文方法的有效性。

1 方 法

1.1 異構信息網絡(HIN)與節點相似度

異構信息網絡是指具有多種對象和/或多種鏈接的網絡。在異構信息網絡中,G=(V,E),V是節點集,E={(vi,vj)}是邊緣集,G是異構信息網絡。異構信息網絡還具有節點型映射函數φ:V→A和邊緣型映射函數ψ:E→R。在此,A和R分別表示預定義節點類型和鏈接類型的集合。當|A|+|E|>2時,該網絡稱為異構信息網絡;否則,為同構網絡。例如,圖1所示的電影網絡具有三個不同類型的節點:用戶(U)、電影(M)和標簽(T)。

圖1 電影網絡結構

異構信息網絡中的節點相似性定義為一對節點間的相似性。對于任意一對節點(vi,vj),如果存在一條邊滿足(vi,vj)∈E,則將vi和vj的一階相似度定義為1。如圖2所示,由實線連接的每個節點對具有一階相似性。異構信息網絡的高階相似性度量了其鄰域結構的成對相似性。給定一個節點對(vi,vj)∈E,如果它們有一個公共的一階相連的頂點vk滿足(vi,vk)∈E以及(vj,vk)∈E,則它們之間存在二階相似性。因此,vj和vj的表示應該相似。圖2中的細虛線圓圈表示節點之間的二階相似性。此外,可以得到高階相似性定義。如果從vj到vj存在路徑(vi,v2,…,vn,vj)則vi、vj具有n階相似度。粗虛線圓圈表示網絡中的四階相似性。

1.2 模型概述

本文提出一種半監督的異構信息網絡表示學習方法,主要集中在保存語義信息和高階相似性。SGHIRL的框架如圖3所示。整個體系結構由訓練數據的準備和表示學習兩部分組成。為了保存語義信息和高階相似性,首先對輸入異構信息網絡中的路徑進行采樣,形成路徑集。然后需要一個能夠將它們編碼為低維向量的框架。為此,本文提出使用自動編碼器神經網絡模型和路徑預測任務來分別學習和改進節點的表示。

圖3 SGHIRL的結構框架

1.3 訓練和準備工作

網絡的異構性加快從網絡中提取更多的隱含信息。該算法采用元路徑來獲取異構信息。元路徑模式S=(Asub,Rsub)可以用節點序列和邊緣序列的形式表示。

(1)

式中:Asub和Rsub是A和R的子集;ai表示特定的節點類型;ri表示邊緣類型。給定一個元路徑模式,可以將原始的異構信息網絡G分解為一個能夠保留語義信息的元路徑集合Gs。

Gs的鄰接矩陣可以表示為Mp∈Rn×n,當且僅當節點i通過元路徑樣本P與節點j相連時,Mp(i,j)=1。考慮到Mp的構造比較復雜,在實際應用中不需要構造Mp。事實上,對于任意長度lp的路徑模式,可以通過維護lp-1鄰接查找表來獲得lp-1中任意兩個給定節點的連通性。

為了提取異構信息,本文采用基于元路徑的隨機游走策略從異構信息網絡中采取路徑。對于每個路徑P,設置一個指標變量Ip來標明該路徑是否是原始網絡中的元路徑。例如,在圖3(a)所示的電影網絡中有三種類型的節點:用戶(U)、標簽(T)和電影(M)。假設選擇一個長度為5的元路徑模式可以得到一個正訓練條目(U1,M1,T1,M2,U2,1)或一個負訓練條目(U1,M1,T1,M2,U3,0)。根據元路徑模式生成路徑可能會產生循環路徑,例如,在圖3(a)中,預處理過程可以生成循環路徑。為了盡可能保留網絡中的異構信息,便刪除了對稱路徑。此外,為了緩解過擬合問題,SGHIRL用負采樣方法生成負數據條目。對于每個采樣的正數據條目(P,Ip),通過隨機地將P中的一個或兩個節點替換為從原始網絡中隨機選擇的新節點來生成負數據條目。隨機替換也可以產生一個正數據條目的例子。如上所述,通過維護幾個鄰接查詢表來解決這個問題。算法1給出了詳細的數據準備過程。

算法1基于元路徑的數據采樣

輸入:異構信息網絡G=(V,E),元路徑模式S,每個節點的行走步數u,負樣本數q。

輸出:數據集D。

1.初始化D=[];

2.fori= 1:1:udo

3.根據S從網絡中對路徑P進行采樣;

4.將樣本(P,1)加入D中;

5.forj=k:1:qdo

6.產生一個負樣本P-;

7.將樣本(P-,1)加入D中;

8.end for

9.end for

10.returnD

1.4 表示學習框架

選自給定網絡中的節點序列或路徑,需要一個編碼框架將它們編碼到一個固定的低維空間。在最近提出的許多模型中,自編碼器被證明是最有效的解決方法。一般而言,自編碼器由兩部分組成:將原始輸入編成隱變量表示的編碼器和試圖從隱變量表示中恢復數據的解碼器。給定鄰接矩陣xi的第i行,表示節點i,編碼器將其映射到低維空間:

(2)

(3)

(4)

式中:dist(x,y)表示距離,在實驗中首先考慮歐幾里得距離。對于元路徑中的每個節點,考慮到每個節點的位置和類型不同,使用獨立的自動編碼器將其映射到低維向量。因此,自編碼器部分的代價函數為:

(5)

式中:Pj表示訓練數據中的第j條路徑,總共np條路徑。事實上,大多數網絡是稀疏的,這意味著xi中非零元素的數目遠遠少于零元素的數目。SGHIRL通過獲取網絡中的高階相似性來緩解這個問題。此外,在計算自編碼器的損耗時,只需關注xi中的非零元素。此時自動編碼損失值為:

(6)

式中:?為哈達瑪積。注意,在這里引入哈達瑪積將導致解碼器總是輸出全為1的向量,從而迫使LAE等于零。本文稍后會討論如何解決這個問題。對自動編碼層進行訓練后,可以得到初始節點的表示形式,為[z1,z2,…,zlP]。

實際上,可以通過訓練自編碼器來獲得基礎表示。為了保留高階相似性和語義信息,引入一種中間表示,即路徑表示,用來表示細化過程。所提出的SGHIRL訓練一個神經網絡模型用于二元預測任務,以判別給定節點序列之間是否存在路徑。雖然有很多種深層架構可供選擇,但本文方法模型能高效率計算,且表達式便于應用。具體而言,SGHIRL采用了一個單隱層前向神經網絡,該網絡將序列[z1,z2,…,zlP]作為輸入,用來預測節點間路徑存在的概率。即第一層以多個節點作為輸入,然后通過一個非線性映射函數,由隱藏層獲得集相似性和語義于一體的路徑,表示為:

(7)

(8)

式中:W[2]表示第二個隱藏層的權重;b[2]表示第二個隱藏層偏移向量。

(9)

式中:Ij是訓練集的指標變量。

算法(SGHIRL)步驟如算法2所示。

算法2半監督全局異構信息保存網絡表示學習(SGHIRL)。

輸入:訓練數據D,節點集V,元路徑模式S,每個節點行走步數u,自編碼器lp。

1. 隨機初始化參數θ,θ={WEN,WDE,W[1],W[2],b};

2. while目標函數不收斂do

4. 用小批量梯度下降法更新θ;

5. end while

7. for vi:1:V do

8. 獲取節點表示zi;

10. end for

1.5 優 化

所提出的SGHIRL學習表示法是將前向神經網絡中的自編碼器重構損失LAE和預測損失LNN聯合最小化,即目標是解決以下優化問題:

(10)

為了將參數W和b進行優化,用小批量梯度下降的反向傳播算法對SGHIRL進行訓練。首先從異構信息網絡中抽取路徑并生成(P,Ip)形式的負路徑,用來構造訓練數據集D。

則可采用式(11)對參數θ進行更新。

(11)

式中:η是學習率。可以通過自編碼器獲得任意節點的向量表示形式。

2 實驗與結果分析

2.1 數據集

為了驗證SGHIRL的有效性,本文在四個不同的異構信息網絡上進行了實驗,包括GPS網絡、醫學網絡、電影評論網絡和語言網絡。表1總結了這些異構信息網絡的統計數據。

表1 異構信息網絡參數統計

(1) GPS:這個數據集記錄了164個用戶的軌跡,包括5種不同類型的活動。它最初用于構建推薦活動系統。對于每個包含三個元素的元組:用戶、位置和活動,假設任何兩個對象之間都有一個直接的鏈接。因此,以用戶定位、用戶活動和位置活動的形式構建了一個具有邊緣的異構網絡[9]。

(2) Drug:這是提交給美國食品和藥物管理局(FDA)的關于不良事件和用藥錯誤報告的公共信息的子集。完整的數據集在FDA不良事件報告系統(FAERS)上出版。與GPS一樣,對于數據集中的每個報告,本文假設使用者、藥物和反應是相互關聯的。以用戶藥物、用戶反應和藥物反應的形式構建一個具有邊緣的異構網絡[9]。

(3) MovieLens:這是一個典型的網絡評論數據集,描述人們如何評價電影,并廣泛用于電影推薦服務。根據數據集的組織結構,以電影用戶和電影標簽的形式構建了一個具有邊緣的異構網絡[10]。

(4) WordNet:這是一個大型詞匯數據庫,用于生成詞典,并支持自動文本分析。它由同義詞集和這些同義詞集之間的關系類型組成,是一個具有超邊的異構網絡[11]。

2.2 對比方法

本文比較了SGHIRL與以下網絡表示學習方法的性能:

(1) DeepWalk[12]:從網絡生成截短隨機游動,并應用skip-Gram模型來學習網絡表示。在這里,對整個異構信息網絡進行DeepWalk,而忽略了節點的類型。

(2) LINE[13]:LINE分別保留網絡中節點的一階和二階相似性,并通過skip-gram模型學習網絡表示。將一階和二階相似性的表示串聯起來,同樣忽略了節點類型。

(3) node2vec[14]:作為DeepWalk的一種廣義方法,node2vec通過參數化隨機游動捕捉w-hop鄰域內的節點對,從而學習低維度節點向量。此方法無法處理節點類型。

(4) HEBE[15]:HEBE是基于超邊的網絡表示學習框架,它可以捕獲不同類型節點之間的交互情況。

(5) DHNE[16]:DHNE的目標是學習超級網絡的低維度表示,并使用深度模型來保持向量空間中的局部和全局相似性。

注意,DeepWalk、LINE和node2vec是為同構網絡設計的。為了公平比較,SGHIRL還采用普通隨機游走策略從異構信息網絡中抽取路徑,盡管HEBE和DHNE是為異構網絡設計的。

2.3 參數設定

本文為每個數據集在SGHIRL中設計前向自編碼器神經網絡。針對GPS這個規模較小的數據集,節點表示的維度均設置為64,因此自編碼器的輸出層尺寸為64×5。權衡參數α通過線性搜索進行調整,取值范圍為[0,1],每隔0.1取一個值。對于所有適用的模型,負采樣率始終設置為5;學習率η的起始值設置為0.1,并采用Adam自動調整學習率;批的最小值設置為16。在SGHIRL中為每個節點抽取了1 000條路徑。為了公平比較,DeepWalk和node2vec中每個節點的行走次數設為125,行走長度為40。為了考察SGHIRL的一般適用性,其隨機行走路徑模式下的行走長度設為5。以上未提及的其他參數均設為默認值。而針對MovieLens以及WordNet兩個規模較大的數據集來說,單一隱層的自編碼器計算能力稍顯不夠,因此根據數據集的規模,可以設置不同層數的隱藏層自動編碼器來匹配相應的計算需求,從而進行驗證,其各隱藏層節點數與單一隱藏層的節點數相同,相關參數設置與單一隱藏層無異。為了觀察自編碼器在節點表示學習中的作用,建立一個只包含一個自編碼器的SGHIRL模型進行比較。注意,模型的復雜性與自編碼器的數量呈線性關系。例如,當采用長度為l的路徑模式時,正常SGHIRL參數值如表2所示,忽略偏差參數b。

表2 每個數據集上的參數值

通過網絡重構、鏈路預測和節點分類等多個下游任務來評估不同模型的性能。為了確保實驗的可靠性,將所有評估重復進行5次,并計算出平均結果。

2.4 網絡重構

為了直接評估表示學習算法能在多大程度上保留原始網絡的結構信息,本文對所有數據集進行網絡重構。使用整個網絡以及生成的負樣本來訓練模型并獲得每個節點的表示。特別是對于SGHIRL,將節點反饋給相應類型的自編碼器,從而獲得表示。如果有多個對應類型的自編碼器,取平均值即可。其任務是通過比較兩個節點表示之間的相似性來重構原始網絡中的邊緣。利用余弦相似性來預測原始網絡中的邊緣。采用AUC[16]進行評價,結果見表3。

表3 AUC在網絡重建方面得分

如表3所示,除了隨機模式和單個SGHIRL外,在AUC方面,所提出的SGHIRL在四個數據集上的運行結果優于其他所有比較方法。很明顯,僅使用單個自編碼器來學習節點表示的SGHIRL性能最差。與SGHIRL隨機游走模型相比,該結果表明單個SGHIRL的自適應能力受到自編碼器的限制。與DHNE和HEBE等異構信息網絡表示學習模型相比,SGHIRL+metapath模型在所有數據集上的運行結果相對改進率分別至少為3.43%、2.78%、3.26%和4.32%。結果表明,表示形式的改進對于保存異構信息網絡的結構信息具有積極效果。注意,DHNE和本文模型均優于HEBE,這說明高階相似性在網絡表示學習中的重要性。此外,通過比較全部采用隨機游走取樣策略的DeepWalk、LINE和node2vec,SGHIRL在四個數據集上的精確率分別提高了19.09%、36.11%、2.22%和4.05%,說明了本文模型在異構信息網絡中保存異構信息的有效性。此外,觀察到具有元路徑抽樣策略的SGHIRL始終優于隨機行走抽樣策略,這說明表示學習可以從語義信息中受益。此外,SGHIRL在不同路徑模式下的性能表明使用較長的元路徑將獲得更好的節點表示。

2.5 鏈接預測

網絡表示學習的最原始對象是預測將來哪對節點將形成一條邊緣。對于鏈接預測任務,首先隨機均勻地隱藏10%的邊緣,剩余網絡和生成的無邊緣用于訓練SGHIRL并獲得表示,其任務是使用獲得的表示來預測那些隱藏的邊緣。與網絡重建任務相似,使用余弦相似性來預測邊緣,并使用AUC來評估預測性能,結果見表4。

表4 AUC在鏈接預測方面得分

由于HEBE、DHNE和SGHIRL都利用語義信息進行預測,因此它們的性能相對較好。實驗過程中注意到,在這些異構網絡表示學習方法中,本文模型的性能最佳,這主要是因為SGHIRL將高階相似性和語義信息集成在一起。與以前的研究結果一致,證明了保留高階相似性可以提高鏈路預測性能,這反映了網絡結構信息的重要性。較長的路徑架構仍然有助于SGHIRL獲得更高的分數。此外,在僅考慮節點相似性的模型,即DeepWalk、LINE、node2vec和SGHIRL+隨機行走模型中,本文模型仍然表現最佳。一致認為性能改進的主要原因是SGHIRL中改進的優越性。此外,與SGHIRL+隨機游走模型相比SGHIRL+metapath,在四個數據集上的增益達到了6.12%～11.18%,這表明保留語義信息可以提高模型的泛化能力。

2.6 節點分類

在節點分類任務中,為每個節點歸為一類或多個類。在MovieLens數據集中,每部電影都有一個或多個流派的標簽。而在Wordnet數據集中,每個同義詞都有一個正屬性。由于只有兩個數據集具有類信息,因此在這兩個異構信息網絡上進行了節點分類實驗。最近鄰分類器被用來預測將表示學習作為輸入的節點的標簽。首先,在整個網絡上訓練模型,得到所有節點的表示。然后將學習到的節點表示按9∶1的比例隨機分為訓練集和測試集。節點的類屬性作為標簽。在訓練集上擬合一個最近鄰分類器,即K=1,然后使用測試集來驗證SGHIRL節點表示學習的有效性。表5和表6分別記錄了宏觀F1和微觀F1的平均值。

表5 用于節點分類的MovieLens和WordNet上的宏觀F1

表6 用于節點分類的MovieLens和WordNet上的微觀F1

從結果來看,SGHIRL在節點分類任務上各方面優于所有對比方法,進一步驗證了語義信息和細化過程的有效性。在所有基于隨機游走的模型中,DeepWalk和LINE的性能最差,因為它們采用嚴格的策略來探索網絡中的鄰域。在探索網絡鄰域方面具有更靈活策略的Node2vec表現得更好。另外,與SGHIRL和DHNE相比,HEBE表現最差。在WordNet數據集上所有方法中,HEBE的F1得分最低,這意味著數據稀疏性嚴重損害了HEBE的性能,并且在LINE和DeepWalk中觀察到類似的情況。在所有四個數據集上,SGHIRL+隨機游走模型始終比HEBE表現得更好,這說明表示精簡程序的有效性。

2.7 魯棒性

進一步進行魯棒性測試,為了模擬具有不同稀疏度的網絡,在四個數據集上將訓練率從10%調整到90%,網絡的剩余部分用于測試鏈路預測模型的魯棒性。本節中使用的路徑模式如表7所示,結果如圖4所示。

表7 用于穩健性檢驗的路徑架構

圖4 四種數據集鏈路預測的魯棒性檢驗

圖4描繪了在所有方法上隨著訓練數據大小的增加而不斷改進的AUC模型。注意到SGHIRL+元路徑始終優于DHNE和HEBE,這表明當網絡稀疏時,高階相似性非常重要。通過SGHIRL+metapath和SGHIRL+隨機游走模型的比較,說明了表示細化的有效性。

2.8 參數靈敏度

本節研究了模型中不同參數對鏈路預測的敏感性,包括表示尺寸、損失權衡參數α和每個節點的遍歷次數。結果如圖5所示。

圖5 靈敏度測試

從圖5(a)可以看出,性能首先隨著表示維度的增長而提高,然后達到飽和,原因是SGHIRL需要合適的維度對異構信息進行編碼。當表示尺寸大于128時,除WordNet外,AUC開始下降。這是因為較大的尺寸可能會引入一些冗余,但是對于WordNet,較適合采用高維向量表示節點,因為它包含許多節點,而且是一個稀疏網絡。

圖5(b)描繪了損耗權衡參數α對性能產生的影響。參數α衡量無監督誤差LAE和有監督誤差LNN。當α為0時,忽略了自編碼器的損耗,因此SGHIRL只考慮了路徑預測的誤差,可以認為該模型主要保留網絡中的語義信息。即使在這種情況下,神經網絡模型也能取得良好的效果,這也表明了語義信息在網絡中的重要性。隨著α的增加,性能得到了改善,因為引入的LAE主要影響高階相似性。該研究結果表明了高階相似性和語義信息的集成的重要性。但是,當α大于0.5時,這意味著SGHIRL的路徑預測誤差LNN對模型沒有太大影響,而四個數據集的性能都急劇下降。當α為1時,SGHIRL只考慮重構LAE的損失,從而得到的AUC值很低。結果表明自學習是一種合理的無監督編碼方法,能同時保留高階相似性和語義信息的必要性。

圖5(c)表示在每個節點上存在的數據和信息產生更多的行走,但增加步行次數所產生的收益也將會達到飽和。為了驗證不同長度的路徑模式的復雜性,在藥物數據集上測量了每批數據的訓練時間,如圖5(d)所示。可以觀察到訓練時間與路徑模式的長度呈線性關系,證實了之前對模型的參數估計。

3 結 語

傳統的網絡表示學習模型存在網絡信息保存不全面的缺點,為此提出一種半監督全局異構信息保存網絡表示學習框架。通過多個異構數據集的驗證結果可得出如下結論:

(1) 相較于其他方法,本文模型在異構信息網絡中保存異構信息更加有效。

(2) 具有元路徑抽樣策略的SGHIRL始終優于隨機行走抽樣策略,這說明表示學習可以從語義信息中受益。此外,SGHIRL在不同路徑模式下的性能表明使用較長的元路徑將獲得更好的節點表示,驗證了語義信息和細化過程對改善方法的重要性。

(3) 保留高階相似性可以提高鏈路預測性能,這反映了網絡結構信息的重要性,另外,保留語義信息可以提高模型的泛化能力。

(4) 自編碼器是一種合理的無監督編碼方法,能夠有效提升方法的應用范圍,且同時保留高階相似性和語義信息,對于性能的提升有著十分重要的作用。