蔣宗禮 謝欣彤
(北京工業(yè)大學信息學部 北京 100124)
各種類型的網(wǎng)絡可以看做是這個世界在某些方面的抽象,關于它的研究也一直是學術界的一個熱點。如社交網(wǎng)絡,它是人們社會關系網(wǎng)絡的抽象,這種網(wǎng)絡僅由一種類型的節(jié)點和邊構成,也被稱為同質(zhì)信息網(wǎng)絡。與之相對應的,包含一種或多種類型的節(jié)點和邊的網(wǎng)絡被稱為異質(zhì)信息網(wǎng)絡(Heterogeneous Information Network,HIN)[1]。相較于同質(zhì)信息網(wǎng)絡,HIN 將網(wǎng)絡中的對象和關系進行了區(qū)分,能夠表達更豐富的信息,如圖1所示。
圖1 HIN舉例
HIN 中通常包含大量的節(jié)點,這些節(jié)點分布在高維稀疏空間中。復雜而龐大的網(wǎng)絡數(shù)據(jù)往往難以處理[2],網(wǎng)絡表征學習(Network Representation Learning,NRL)[3]則是應對以上問題的一種典型方法。NRL 將網(wǎng)絡中的節(jié)點在高維空間的稀疏向量表示映射成低維空間稠密的向量表示,能夠在一定程度上保留原始網(wǎng)絡中的信息。由于低維的向量很容易被機器學習算法處理,故可有效地應用于節(jié)點分類、聚類、鏈接預測、社區(qū)發(fā)現(xiàn)和推薦等任務中[4]。
本文的研究任務就是HIN 的表征學習。目前已經(jīng)有一些關于NRL 的工作。Perozzi 等提出的DeepWalk[5]就是一種經(jīng)典的NRL 方法。但該方法僅適用于同質(zhì)信息網(wǎng)絡的表征學習,在HIN上的表征學習效果并不好。Goodfellow等提出的生成對抗網(wǎng)絡(Generative Adversarial Network,GAN)[6]由一個生成網(wǎng)絡和一個判別網(wǎng)絡組成,通過兩個神經(jīng)網(wǎng)絡相互博弈的方式進行學習。Hu 等將其應用于HIN 的表征學習,提出了HeGAN[7]。該方法利用一個節(jié)點的鄰居節(jié)點作為該節(jié)點的上下文語義信息,融合到模型中,取得了不錯的效果。
但是,僅僅考慮鄰居節(jié)點并不能完全反應該節(jié)點的上下文信息。因此我們提出利用DeepWalk的隨機游走的方法,盡可能多地獲取一個節(jié)點的上下文信息,再結合GAN 的生成對抗思想,提出RHGAN模型,并取得了較好的效果。
隨著機器學習技術的發(fā)展,學習網(wǎng)絡中的節(jié)點特征成為了一項新興研究任務[8~9]。2014 年,Perozzi 等提出的DeepWalk 通過隨機游走遍歷網(wǎng)絡中的節(jié)點,得到有序的節(jié)點序列。利用Word2Vec[10]思想和skip-gram[11]模型,由單個節(jié)點預測前后序列,從而學習得到該節(jié)點的向量表示。該方法可以處理無權重的無向圖。LINE[12]由Tang 等于2015年提出,該算法保留了節(jié)點的一階相似度和二階相似度,可以處理任意類型的大規(guī)模網(wǎng)絡,包括有權重或無權重的有向或無向圖。2016年,Grover等在DeepWalk 的基礎上,通過引入兩個超參數(shù)p 和q 來控制游走策略,即采用寬度優(yōu)先搜索或廣度優(yōu)先搜索進行游走,從而提出了node2vec[13]。該方法可處理有權重或無權重的有向或無向圖。由同質(zhì)信息網(wǎng)絡表征學習方法得到啟發(fā),一些學者嘗試將同質(zhì)信息網(wǎng)絡中的NRL 思想應用到HIN 中。Dong 等采用了node2vec 中的隨機游走的思想,結合Skip-gram 模型,提出了metapath2vec[14]。該方法對隨機游走和Skip-gram 模型分別進行改進,采用基于元路徑的方式來控制隨機游走,同時使改進后的Skip-gram模型能夠在輸出層上區(qū)分節(jié)點的類型。
Wang等由GAN得到啟發(fā),提出了GraphGAN[15]。該方法根據(jù)生成器在線生成策略,使生成器為每個節(jié)點生成假樣本。將真實數(shù)據(jù)與生成器生成數(shù)據(jù)同時輸入到判別器中,由判別器進行區(qū)分,并將區(qū)分結果反饋給生成器。但該方法僅適用于同質(zhì)信息網(wǎng)絡。Hu等提出的HeGAN方法,結合GAN的思想,設計了關系感知的判別器和生成器。廣義生成器雖然能夠直接從連續(xù)分布中采樣“潛在節(jié)點”,并且不局限于原始網(wǎng)絡中的節(jié)點,但沒有充分考慮節(jié)點的上下文信息。
本文提出的RHGAN 模型利用隨機游走,將節(jié)點的上下文信息融入到GAN 中,以充分挖掘網(wǎng)絡的結構和語義信息。模型中用到的參數(shù)如表1 所示。
表1 RHGAN模型用到的參數(shù)
隨機游走就是在網(wǎng)絡上不斷重復地隨機選擇游走路徑,最終形成一條貫穿網(wǎng)絡的路徑。從某個特定的端點開始,游走的每一步都從與當前節(jié)點相連的邊中隨機選擇一條,沿著選定的邊移動到下一個頂點,不斷重復這個過程。而截斷隨機游走(Truncated Random Walk)實際上就是長度固定的隨機游走。它在DeepWalk中被用于同質(zhì)網(wǎng)的表征學習,算法1對該算法進行了描述。
算法1 截斷隨機游走(Truncated Random Walk)
輸入:源節(jié)點u,隨機游走步長sl
輸出:以節(jié)點u為起點的路徑uPath
1)將u加入uPath;
2)while uPath的長度!=2*sl+1 do
3)令currU為uPath中的最后一個節(jié)點;
4) 從currU 所具有的關系中隨機選取一種關系作為selR
5)從currU 通過關系selR 鏈接到其他鄰居節(jié)點的序列中隨機選擇一個節(jié)點作為selU
6) 分別將selR、selU加入uPath
7)end while
直觀上,節(jié)點u 的上下文和u 之間的關系更加緊密,可以用u 的上下文來表示u 所蘊含的語義信息。我們使用截斷隨機游走算法,來獲取節(jié)點u 的語義信息。我們?yōu)槊恳粋€節(jié)點采樣一批路徑,路經(jīng)p 表示為p:〈u,r1,v,r2,u3,r3,…rsl,usl+1〉,其中,u表示源節(jié)點,v 表示節(jié)點u 的鄰居,sl 表示隨機游走的步長。我們令Rp=(r1,r2,r3,…rsl),表示路徑p中所有關系的序列。同時,我們將采樣得到的路徑作為新的訓練集,用ucontext表示節(jié)點u的上下文。
以圖1 中的HIN 為例,從節(jié)點business1 出發(fā),隨機游走步長分別為1、2、3 時,我們可以得到三條游 走 的 路 徑p1:〈business1,re3,star level 1〉,p2:〈business1,re2,user1,re1,business2〉,以 及p3:〈business1,re2,user1,re1,business2,re3,star level 2〉。這些路徑本身包含了可解釋的語義,如p1表示商家business1 的星級star level 1,p2表示用 戶 user1 同 時 關 注 了 商 家 business1 和business2 ,p3表示用戶user1 同時關注了商家business1 和星級為star level 2 的商家business2 。正是因為這些隨機游走出來的路徑包含了豐富的語義,因此我們希望通過隨機游走的方式盡可能多的游走一個節(jié)點的上下文,以充分挖掘這些語義信息。
按算法1 對節(jié)點u 進行隨機游走,可以得到路徑p:〈u,r1,v,r2,u3,r3,…rsl,usl+1〉,路徑p 中的關系序列Rp為(r1,r2,r3,…rsl),v為u的鄰居節(jié)點。
u 的上下文信息ucontext由u 和Rp得到。令ucontext為正樣本。負樣本產(chǎn)生方式如下:隨機選擇Rp中 的 一 種 關 系 進 行 替 換,得 到Rp'=(r1,r2',r3,…rsl),此時路徑中的兩個節(jié)點存在一種錯誤的關系。負樣本即為u 的錯誤的上下文信息u'context,由u和Rp'得到。將路徑p放入生成模型中,得到假樣本,即u的生成的上下文信息
判別模型的目的是對采樣得到的正樣本、負樣本和假樣本進行判別,根據(jù)節(jié)點u 的上下文信息和節(jié)點u 的鄰居的關系,從而判斷該樣本是否來自原始網(wǎng)絡。判別模型的目標函數(shù)如式(1)所示。表示路徑
表示p 中節(jié)的點關u系在序判列別模Rp型 在中判的別表模示型向中量的,矩陣乘積,。若為正確的上下文信息,則節(jié)點u 的鄰居節(jié)點v 與u 的上下文信息相近,判別器的值接近1,說明該樣本屬于原始網(wǎng)絡的可能性較大;反之,判別器的值接近0,說明該樣本屬于原始網(wǎng)絡的可能性較小。
正樣本的損失函數(shù)如式(2)所示。〈u,Rp,v〉~P表示從集合P 中取路徑p,u 為p 中的源節(jié)點,Rp為p 中的關系序列,v 為p 中節(jié)點u 的鄰居。示隨
負機替樣換本的Rp損 中失的函任數(shù)意如一式種(關3)系所得示到。RRp'p。'~PRp表
判別模型的損失函數(shù)由正樣本、負樣本和假樣本的損失函數(shù)構成,如式(5)所示。λD是判別模型中用于控制正則化的參數(shù)。θD是判別模型中所有節(jié)點u 的向量表示和對應關系序列Rp的矩陣的集合,由最小化判別模型的損失函數(shù)進行更新。
將路徑p 和隨機噪聲放入生成模型中,用以生成節(jié)點u 的上下文信息的表示向量。生成模型的目標函數(shù)如式(6)所示:
f 表示激活函數(shù),模型所采用的激活函數(shù)為帶泄露線性整流函數(shù)(Leaky ReLU)。同時,為增強偽裝性,還增加了多層感知器,WL、bL分別表示第L層的權重矩陣和偏置矩陣。e的求法如式(7)所示。表示路徑
表示p中節(jié)關點系u序在列生成Rp模 在型生中成的模表型示中向的量矩,陣乘積,,z表示隨機噪聲。
生成模型的目標是盡可能地生成節(jié)點u 的真實的上下文信息,以混淆判別模型的判斷。其損失函數(shù)定義如式(8)所示。
λG是生成模型中用于控制正則化的參數(shù)。θG是系生序成列模R型p的中矩所陣有節(jié)點以u的及向多量層表感示知器中和的對參應關數(shù)WL和bL的集合,由最小化生成模型的損失函數(shù)進行更新。
RHGAN模型的整體訓練過程如算法2所示。
算法2 RHGAN模型訓練
輸入:HIN N;模型的訓練次數(shù)epoch;生成模型、判別模型的訓練次數(shù)Gepoc?、Depoc?;每個節(jié)點的采樣次數(shù)nsample;隨機游走步長sl
輸出:eG、eD
1)初始化θD、θG
2)for e=0;e 3)for n=0;n 4)for num=0;num 5)N中每個節(jié)點進行步長為sl的隨機游走,得路徑p 6)由p可得路徑p中的源節(jié)點u的關系序列Rp 7)由u和Rp得到正樣本,即u的上下文信息 8)隨機替換路徑p 中的任一關系得到Rp'(Rp'~PRp),由u和Rp'得到負樣本 9)將路徑p放入生成模型中,得到u的生成的上下文信息G(u,Rp;θG) 10)通過式(5),更新θD 11)end for 12)end for 13)for n=0;n 14)for num=0;num 15)N中每個節(jié)點進行步長為sl的隨機游走,得路徑p 16)由p可得路徑p中的源節(jié)點u的關系序列Rp 17)通過u和Rp生成u的上下文信息G(u,Rp;θG) 18)通過式(8),更新θG 19)end for 20)end for 21)end for 本文在YELP 數(shù)據(jù)集上驗證了RHGAN 模型的有效性。YELP 數(shù)據(jù)集中的實體類型及數(shù)量如表2(a)所示,關系類型及數(shù)量如表2(b)所示。 表2 (a) YELP數(shù)據(jù)集中的實體類型及數(shù)量 由表2(a)和2(b)可以看出,YELP 數(shù)據(jù)集中包含用戶(User,U)、商家(Business,B)、服務(Service,S)、星級(Star level,St)、預定(Reservation,R)六種節(jié)點類型和B-U、U-B、B-S、S-B、B-St、St-B、B-R、R-B八種關系類型,共計3913個節(jié)點,38680條邊。 本文通過RHGAN 在聚類任務上的表現(xiàn),來驗證其有效性。歸一化互信息(NMI)常被選作為評價聚類效果的標準。NMI值越大,表明聚類效果越好。其范圍為[0,1]。計算方法見式(9)。 I 表示互信息,即兩個隨機變量X 和Y 之間的關聯(lián)程度。X 與Y 關系越密切,則I(X;Y)的值越大。計算方法見式(10)。 H 表示熵,由概率的極大似然估計推導而來,計算方法見式(11)。 4.3.1 對比實驗 本文選用NRL 經(jīng)典算法DeepWalk、LINE(采用一階相似度LINE-1st 和二階相似度LINE-2nd)與基于GAN 思想的GraphGAN、HeGAN 作為基準實驗,與本文所提出的RHGAN 進行對比實驗。其中,DeepWalk、LINE-1st、LINE-2nd、GraphGAN 均為基于同質(zhì)信息網(wǎng)絡的模型,而HeGAN 和RHGAN均為基于HIN的模型。 基準實驗的參數(shù)設置:Deepwalk設置從每個節(jié)點的出發(fā)次數(shù)number-walks為10,隨機游走的步長walk-length 為100,window-size 為5。LINE-1st 和LINE-2nd 設置總的樣本數(shù)均為10000。GraphGAN設置生成模型和判別模型的訓練次數(shù)均為30 次、學習率均為0.001,每個節(jié)點的采樣次數(shù)為20,總體的訓練次數(shù)為20次。HeGAN設置生成模型和判別模型的訓練次數(shù)分別為5 和15 次、學習率均為0.0001,總體的訓練次數(shù)為20 次。實驗結果如表3所示。 表3 對比實驗結果 由表3 可以看出,基于HIN 的模型整體上要優(yōu)于基于同質(zhì)信息網(wǎng)絡的模型,在基于GAN 思想的三種方法中,RHGAN 要明顯優(yōu)于另外兩種方法。在基準實驗中,效果最好的是HeGAN,其NMI值達到 了0.4037。 RHGAN 相 較 于HeGAN 提 升 了1.41%,其NMI值達到了0.4178。 以上結果表明HIN 較同質(zhì)信息網(wǎng)絡具有更好的表征效果,同時,在GAN 中融入節(jié)點的上下文信息對HIN表征學習方面具有一定的提升效果,驗證了本文所提出的RHGAN的正確性和有效性。 4.3.2 參數(shù)敏感度 用epoch 表示總體訓練次數(shù),nsample表示每個節(jié)點的采樣次數(shù),Gepoc?、Depoc?分別表示生成模型和判別模型的訓練次數(shù)分別表示生成模型和判別模型的學習率,sl表示隨機游走步長。 1)sl對模型效果的影響 固定epoch 為20,nsample為16,Gepoc?為5、為0.0003,Depoc?為15、為0.0001。將sl 分別設置為[1,2,3,4,5,6,7,8,9,10,11,12]。探究隨機游走步長的變化對聚類結果的影響。 實驗結果如圖2 所示。其中,左側縱坐標軸表示在該隨機游走步長下聚類的效果,以NMI值來評估;右側縱坐標軸表示epoch 為20 時,在不同隨機游走步長下,平均每個epoch所花費的訓練時間,單位為s。 圖2 隨機游走步長對模型效果的影響 圖2中的NMI 曲線表明,隨著隨機游走步長的增加,NMI 值先增后減。當步長由1 增加至2 時,NMI值有所上升;當步長由2 增加至3 時,NMI值變化不大;當步長由3 增加至4 時,NMI 值下降較多;繼續(xù)增加步長,發(fā)現(xiàn)NMI值變化較為平緩。 以上結果表明了在模型中對節(jié)點進行隨機游走并融入節(jié)點上下文信息,可以提升聚類效果,但隨機游走的步長并不是越長越好。隨著步長的增加,節(jié)點的有效的上下文信息可能會被弱化,從而影響模型的表征學習效果。 圖2 中的時間變化曲線表明,隨著步長的增加,每個節(jié)點進行隨機游走所得到的路徑就越長,平均每個epoch所花費的訓練時間會逐步增加。但是所花費的訓練時間基本符合線性增長,說明模型的訓練是可控的且能被較好預測的。 綜合以上分析,當sl 為2、3 時,該模型在聚類效果和訓練時間上都能取得較好的效果。 2)Gepoc?、Depoc?的不同組合對模型的影響 固定epoch 為20,nsample為16,為0.0003,為0.0001,sl 為3。將Gepoc?、Depoc?分別設置為[2,4,6,8,10,12,14,16],探究其不同的組合對聚類結果的影響。實驗結果如圖3所示。 圖3 Gepoch、Depoch 的不同組合對模型的影響 由圖3 可以看出,當Depoc?=2,Gepoc?為2、4,或Depoc?=4,Gepoc?為2、8、14、16 時,模型能有較好的聚類效果;當Depoc?=6 和Depoc?=8,除了Gepoc?=14,模型均能有較好的聚類效果;當Depoc?=10,除了Gepoc?=8,模型均能有較好的聚類效果;當Depoc?=12、Depoc?=14 或Depoc?=16,無論Gepoc?取值如何,模型均能有較好的聚類效果,且NMI 值要優(yōu)于Depoc?取其他值的情況。當Gepoc?位于[4,8]區(qū)間時,大多數(shù)Depoc?的曲線波動變化較為平穩(wěn);當Gepoc?大于8 時,不同取值的Depoc?曲線波動不同,存在上升和下降兩種趨勢。 綜合以上分析,當Depoc?位于[12,16],Gepoc?位于[4,8]時,模型能有較好的效果。 3)epoch對模型的影響 固 定nsample為16,Gepoc?為5、為0.0003,Depoc?為15、為0.0001,sl 為3,設置epoch 為50。探究在一次訓練過程中對抗學習的過程,以及生成模型和判別模型損失函數(shù)和聚類結果的變化。實驗結果如圖4(a)、4(b)所示。 圖4(a) 總的訓練次數(shù)對損失函數(shù)的影響 圖4(b) 總的訓練次數(shù)對模型效果的影響 其中,圖4(a)、4(b)的橫坐標軸表示一次訓練中epoch 的變化,縱坐標軸分別表示損失函數(shù)以及該epoch下聚類的效果,以NMI值來評估。 由圖4(a)可以看出,初始時判別模型的損失函數(shù)值較高,但隨著epoch的增加,判別模型和生成模型的損失函數(shù)均逐漸下降。當epoch 大于21 時,判別模型和生成模型的損失函數(shù)曲線較為平緩,表明此時判別模型和生成模型均已趨于收斂。 由圖4(b)可以看出,隨著epoch 的增加,判別模型和生成模型的NMI 值變化曲線呈現(xiàn)出上升后又下降的趨勢。當epoch 大于19 時,判別模型的NMI 值變化曲線總體呈下降趨勢,而生成模型的NMI 值變化曲線與之前趨勢相同,總體較為平緩。這表明增加epoch 并不一定會提升模型的效果,反而可能會導致模型出現(xiàn)過擬合的問題。 綜合以上分析,當epoch 位于[19,21]區(qū)間時,模型能取得較好的效果。 本文通過在聚類任務上的實驗驗證了所提RHGAN 方法的正確性和有效性,表明該方法在HIN 表征學習方面有較好的表現(xiàn)。今后將在如何更好地融合網(wǎng)絡中的結構信息和語義信息以及提升模型效率方面繼續(xù)研究。4 實驗與結果
4.1 數(shù)據(jù)集
4.2 評價指標
4.3 實驗結果與分析
5 結語