袁立寧,劉 釗
(1.中國(guó)人民公安大學(xué) 信息網(wǎng)絡(luò)安全學(xué)院,北京 100038;2.中國(guó)人民公安大學(xué) 研究生院,北京 100038)
圖表示學(xué)習(xí)將原始圖的結(jié)構(gòu)和特征信息嵌入到低維向量空間,從而能夠直接應(yīng)用常見機(jī)器學(xué)習(xí)算法來(lái)挖掘網(wǎng)絡(luò)的潛在特征。圖表示學(xué)習(xí)旨在生成保留拓?fù)浜蛯傩孕畔⒌牡途S表示,用于節(jié)點(diǎn)分類[1]、鏈接預(yù)測(cè)[2]、聚類[3]等機(jī)器學(xué)習(xí)任務(wù)。為了保證圖數(shù)據(jù)挖掘任務(wù)的質(zhì)量,節(jié)點(diǎn)向量在盡可能保留編碼屬性和邊緣信息的同時(shí),還要兼顧較小的嵌入維數(shù)。由于圖數(shù)據(jù)的復(fù)雜性,基于人工設(shè)計(jì)特征[4]的傳統(tǒng)圖嵌入方法成本極高,而直接在圖上學(xué)習(xí)節(jié)點(diǎn)表示深度學(xué)習(xí)的方法[5]因其強(qiáng)大的表示能力,受到了越來(lái)越多的關(guān)注。在最近的文獻(xiàn)中,已經(jīng)有許多研究嘗試將深度學(xué)習(xí)方法用于圖表示學(xué)習(xí)。其中,基于深度學(xué)習(xí)的無(wú)監(jiān)督模型能夠在缺乏先驗(yàn)知識(shí)或標(biāo)記信息有限的情況下,從數(shù)據(jù)中選出具有代表性的特征,因此常用于生成原始數(shù)據(jù)低維節(jié)點(diǎn)向量表示。
基于深度學(xué)習(xí)的無(wú)監(jiān)督圖嵌入模型主要分為基于隨機(jī)游 走[6]和基于自編碼器(AutoEncoder,AE)[7]的算法。DeepWalk[8]和node2vec[9]模型使用隨機(jī)游走獲取節(jié)點(diǎn)序列,然后訓(xùn)練Skip-Gram[10]生成節(jié)點(diǎn)向量表示。這類方法通常以整個(gè)網(wǎng)絡(luò)結(jié)構(gòu)為輸入,能夠有效捕捉鄰域相似性,但是未能充分利用提供重要信息的節(jié)點(diǎn)特征?;贏E 的圖嵌入模型將圖的拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)特征信息作為編碼器輸入生成低維向量表示,再利用解碼器重構(gòu)圖結(jié)構(gòu);但是大部分AE 模型的編碼器部分使用圖神經(jīng)網(wǎng)絡(luò)(Graph Neural Network,GNN)[11]將節(jié)點(diǎn)編碼到低維向量空間中,導(dǎo)致模型性能會(huì)隨著編碼器深度的增加而降低[12]。
針對(duì)上述問(wèn)題,本文使用One-Shot 聚合(One-Shot Aggregation,OSA)和指數(shù)線性單元(Exponential Linear Unit,ELU)函數(shù)改進(jìn)基于圖自編碼器(Graph AutoEncoder,GAE)和圖變分自編碼器(Variational Graph AutoEncoder,VGAE)的深層模型,并在3個(gè)基準(zhǔn)引文數(shù)據(jù)集上的鏈路預(yù)測(cè)實(shí)驗(yàn)中驗(yàn)證模型性能。本文主要工作如下:1)提出新的GAE 模型OSA-GAE和新的VGAE模型OSA-VGAE,使用OSA[13]和ELU函數(shù)[14]編碼圖的拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)特征,改善深層模型的表示能力;2)在損失函數(shù)中引入正則化項(xiàng),防止模型在訓(xùn)練過(guò)程中參數(shù)過(guò)擬合;3)在鏈路預(yù)測(cè)實(shí)驗(yàn)中,OSA-GAE 和OSA-VGAE 的性能始終優(yōu)于相同深度的基線方法,而且它們的性能不會(huì)隨著隱藏層數(shù)量的增加而降低,并且在部分?jǐn)?shù)據(jù)集上呈現(xiàn)出上升趨勢(shì)。
根據(jù)不同的策略,常見的無(wú)監(jiān)督圖表示學(xué)習(xí)模型可以分為兩類:基于隨機(jī)游走和基于AE 的模型。
基于隨機(jī)游走的模型通過(guò)隨機(jī)游走獲得訓(xùn)練語(yǔ)料庫(kù),然后將語(yǔ)料庫(kù)集成到Skip-Gram 獲得節(jié)點(diǎn)的低維嵌入表示。DeepWalk 使用隨機(jī)游走采樣節(jié)點(diǎn)序列,再通過(guò)Skip-Gram 最大化窗口范圍內(nèi)節(jié)點(diǎn)之間的共現(xiàn)概率將節(jié)點(diǎn)映射為嵌入向量,由于優(yōu)化過(guò)程中未使用明確的目標(biāo)函數(shù),使模型保持網(wǎng)絡(luò)結(jié)構(gòu)的能力有限。node2vec 在DeepWalk 的基礎(chǔ)上引入有偏的隨機(jī)游走,增加鄰域搜索的靈活性,但是仍然缺乏一個(gè)明確的目標(biāo)函數(shù)來(lái)保持全局網(wǎng)絡(luò)結(jié)構(gòu)。Walklets[15]修改DeepWalk 的采樣過(guò)程,捕獲節(jié)點(diǎn)與社區(qū)之間不同尺度信息,顯式建模多尺度關(guān)系,使生成的嵌入能夠保留更豐富的節(jié)點(diǎn)從屬關(guān)系信息。
基于AE 的模型使用AE 對(duì)圖的非線性結(jié)構(gòu)建模,生成圖的低維嵌入表示。SDNE(Structural Deep Network Embedding)[16]利用深度自編碼器以及一階和二階相似度,明確優(yōu)化目標(biāo),使生成的嵌入有效保留全局和局部結(jié)構(gòu)信息,增強(qiáng)了模型在稀疏圖上的魯棒性。DNGR(Deep Neural networks for Graph Representations)[17]使用正點(diǎn)互信息矩陣構(gòu)建圖的高階相似度,捕獲鏈路預(yù)測(cè)和節(jié)點(diǎn)分類等任務(wù)所需的底層結(jié)構(gòu),同時(shí)引入堆疊去噪自編碼器增強(qiáng)模型在含噪聲圖上的魯棒性。VGAE[18]使用變分自編碼器(Variational AutoEncoder,VAE)[19]學(xué)習(xí)可解釋的無(wú)向圖嵌入表示,與非概率自編碼器相比,使用VAE 提升了模型性能。Res-VGAE(Variational Graph AutoEncoders with Residual connections)[20]在VGAE 的基礎(chǔ)上引入殘差連接[21],改善深層VAE 性能,但是模型性能隨著深度的增加仍表現(xiàn)出顯著性降低。ANE[22]使用對(duì)抗性自編碼器[23]生成捕獲高度非線性結(jié)構(gòu)信息的低維嵌入,在生成過(guò)程中施加對(duì)抗性正則化避免流形斷裂問(wèn)題,同時(shí)利用一階和二階相似度捕捉局部和全局結(jié)構(gòu)。
理論上,隨著深度增加,神經(jīng)網(wǎng)絡(luò)模型能夠提取更復(fù)雜的特征,獲得更好的結(jié)果。實(shí)際上,模型性能會(huì)因深度增加而退化,導(dǎo)致準(zhǔn)確度達(dá)到飽和甚至下降,并且在訓(xùn)練中出現(xiàn)梯度消失。
為解決上述問(wèn)題,ResNet[21]引入殘差單元,將各層的輸入和輸出相加,實(shí)現(xiàn)跨層連接,改善深層模型的梯度更新。DenseNet[24]使用稠密連接,即每一層的輸入來(lái)自前面所有層的輸出,改善梯度消失問(wèn)題。與ResNet 相比,DenseNet 能夠保留多個(gè)感受野的特征圖,更加充分地利用特征信息,但是稠密連接使輸入通道增加,導(dǎo)致模型計(jì)算效率嚴(yán)重降低。VoVnet[13]使用OSA 將全部特征圖聚合到最后一層,使模型在繼承DenseNet 優(yōu)點(diǎn)的情況下,解決了稠密連接效率低的問(wèn)題。OSA 方式如圖1 所示。以上方法改善了卷積神經(jīng)網(wǎng)絡(luò)(Convolutional Neural Network,CNN)[25]隨深度增加加深出現(xiàn)梯度消失的問(wèn)題,本文借鑒上述建模思路改進(jìn)深層GNN 編碼器模型架構(gòu)。
圖1 One-Shot聚合Fig.1 One-Shot aggregation
此外,選擇合適的激活函數(shù),同樣能夠解決深層神經(jīng)網(wǎng)絡(luò)的梯度消失問(wèn)題。例如,線性整流函數(shù)(Rectified Linear Unit,ReLU)[26]:
ReLU 解決了梯度消失問(wèn)題,能大幅提升模型的計(jì)算速度,但是在x<0 時(shí)負(fù)的梯度被置零,導(dǎo)致神經(jīng)元壞死,不再對(duì)任何數(shù)據(jù)產(chǎn)生響應(yīng)。ELU 在ReLU 基礎(chǔ)上引入指數(shù)函數(shù),使其在負(fù)輸入值的情況下也能返回信息:
相較于ReLU,在輸入為負(fù)值的情況下,ELU 有一定的輸出,從而消除ReLU 神經(jīng)元壞死的問(wèn)題。此外,ELU 的輸出均值接近0,減少了偏移效應(yīng),使正常梯度接近于自然梯度;在輸入較小時(shí)負(fù)值能夠快速飽和,對(duì)噪聲有一定的魯棒性。
本章提出基于One-Shot 聚合自編碼器的圖表示學(xué)習(xí)模型OSA-GAE 和OSA-VGAE 并討論算法原理,介紹了模型框架及編碼器和解碼器結(jié)構(gòu),并討論了模型的損失函數(shù)。
基于One-Shot 聚合自編碼器的圖表示學(xué)習(xí)模型框架如圖2 所示。OSA-GAE 和OSA-VGAE 以節(jié)點(diǎn)特征矩陣和鄰接矩陣為輸入,重構(gòu)鄰接矩陣為輸出,它們的結(jié)構(gòu)分為編碼器(Encoder)和解碼器(Decoder)兩部分。編碼器使用基于OSA的多層圖卷積網(wǎng)絡(luò)(Graph Convolutional Network,GCN)[27]進(jìn)行構(gòu)建,用于特征提取和數(shù)據(jù)降維,生成每個(gè)節(jié)點(diǎn)的低維向量表示。解碼器利用編碼器生成向量的內(nèi)積重構(gòu)鄰接矩陣。
圖2 OSA-GAE和OSA-VGAE模型結(jié)構(gòu)Fig.2 Model structures of OSA-GAE and OSA-VGAE
GCN 利用卷積運(yùn)算從圖中提取特征,生成包含拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)屬性信息的特征向量。具體而言,GCN 使用節(jié)點(diǎn)特征矩陣X與鄰接矩陣A作為原始輸入,其層間傳播公式為:
OSA-GAE 編碼器使用引入One-Shot 聚合的多層GCN 提取特征,其表達(dá)式為:
其中:L為GCN 層數(shù);W(Final)為權(quán)重矩陣。
OSA-VGAE 編碼器使用引入One-Shot 聚合的多層GCN生成均值向量μ和方差向量σ:
采樣層使用μ和σ從高斯先驗(yàn)分布生成樣本,構(gòu)建低維嵌入。最終,將嵌入重新參數(shù)化為潛在空間上概率的分布[18]:
其中:X為節(jié)點(diǎn)特征矩陣;A為引入自環(huán)的鄰接矩陣;yi是節(jié)點(diǎn)i的低維嵌入,N為節(jié)點(diǎn)數(shù)。
對(duì)于OSA-GAE 模型,解碼器是利用兩個(gè)節(jié)點(diǎn)表示內(nèi)積重構(gòu)鄰接矩陣的非概率模型:
其中:A′表示重構(gòu)矩陣;φ表示sigmoid 函數(shù)。
對(duì)于OSA-VGAE 模型,解碼器是利用兩個(gè)節(jié)點(diǎn)表示內(nèi)積重構(gòu)鄰接矩陣的概率模型:
其中:Aij為鄰接矩陣A的元素。
OSA-GAE 通過(guò)最小化A和A′的重構(gòu)損失進(jìn)行訓(xùn)練,表達(dá)式為:
OSA-VGAE 通過(guò)最大化變分下界以及最小化重構(gòu)損失進(jìn)行訓(xùn)練,表達(dá)式為:
為了避免參數(shù)過(guò)擬合,在OSA-GAE 和OSA-VGAE 損失函數(shù)中引入L2-norm 正則化項(xiàng)Lreg,使用超參數(shù)α控制比重:
在訓(xùn)練過(guò)程中,GCN 層的輸入和輸出維度必須相同,才能使用OSA。此外,OSA-GAE 和OSA-VGAE 均執(zhí)行全批次梯度下降,并利用重參數(shù)化技巧[19]進(jìn)行訓(xùn)練。
本文使用Cora、CiteSeer、PubMed 這3 個(gè)基準(zhǔn)引文網(wǎng)絡(luò)數(shù)據(jù)集[30]評(píng)估OSA-VGAE 和OSA-GAE 生成的低維嵌入表示在鏈接預(yù)測(cè)任務(wù)中的性能。在數(shù)據(jù)集中:節(jié)點(diǎn)表示論文,邊表示一篇論文對(duì)另一篇論文的引用,節(jié)點(diǎn)特征是論文的詞袋表示,節(jié)點(diǎn)標(biāo)簽是人工設(shè)定的論文的學(xué)術(shù)主題。表1 為3 個(gè)數(shù)據(jù)集的統(tǒng)計(jì)信息。
表1 數(shù)據(jù)集統(tǒng)計(jì)信息Tab.1 Statistics of datasets
本文使用以下模型作為基線:
VGAE:該模型將VAE 遷移到圖表示學(xué)習(xí),其基本思路是利用GCN 獲得節(jié)點(diǎn)表示的概率分布,然后在分布中采樣生成節(jié)點(diǎn)表示,最后使用內(nèi)積解碼重構(gòu)圖的鄰接矩陣。
GAE[18]:該模型直接使用GCN 編碼器生成節(jié)點(diǎn)表示,然后使用內(nèi)積解碼器重構(gòu)鄰接矩陣。
Linear-VGAE[31]:該模型使用歸一化鄰接矩陣的簡(jiǎn)單線性模型替換VGAE 中的GCN 編碼器,解碼器與VGAE 相同。
Linear-GAE[31]:該模型使用歸一化鄰接矩陣的簡(jiǎn)單線性模型替換GAE 中的GCN 編碼器,解碼器與GAE 相同。
Res-VGAE:該模型在VGAE 的基礎(chǔ)上引入殘差連接,改善深層VAE 模型的性能。
Res-GAE[20]:該模型在GAE 的基礎(chǔ)上引入殘差連接,改善深層AE 模型的性能。
為了驗(yàn)證模型在鏈接預(yù)測(cè)任務(wù)中的性能,需要對(duì)基準(zhǔn)引文網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行預(yù)處理[19]:1)保留所有節(jié)點(diǎn)的特征信息,將圖中部分邊移除;2)隨機(jī)采樣無(wú)邊的節(jié)點(diǎn)對(duì),其數(shù)量與先前移除的邊數(shù)相同;3)利用移除的邊和無(wú)邊節(jié)點(diǎn)對(duì)構(gòu)建驗(yàn)證集和測(cè)試集,其比例分別為總邊的5%和10%。
根據(jù)模型正確分類邊和非邊的能力比較模型性能,使用平均精度(Average Precision,AP)和ROC 曲線下的面積(Area Under ROC Curve,AUC)作為評(píng)價(jià)指標(biāo)。模型的隱藏層維度均設(shè)置為32,生成嵌入的維度設(shè)置為16,學(xué)習(xí)率設(shè)置為0.01,迭代次數(shù)設(shè)置為200。各模型使用相同的驗(yàn)證集和測(cè)試集劃分,運(yùn)行10 次獲得平均值。
鏈接預(yù)測(cè)任務(wù)即預(yù)測(cè)兩個(gè)節(jié)點(diǎn)之間是否存在邊,用于評(píng)估生成嵌入在保持拓?fù)浣Y(jié)構(gòu)方面的性能。表2~4 為各模型不同深度的AP(%)和AUC(%)結(jié)果。
表2 比較了不同模型使用1 層GCN 的實(shí)驗(yàn)結(jié)果。在3 個(gè)數(shù)據(jù)集上,OSA-VGAE 和OSA-GAE 的AUC 和AP 最高,其他基線模型的AUC 和AP 十分接近。對(duì)于淺層模型,增加OSA和ELU 激活函數(shù)能提升模型的準(zhǔn)確度。
表2 1層GCN時(shí)各模型的AUC和AP 單位:%Tab.2 AUC and AP of each model with 1-layer GCN unit:%
表3 比較了不同模型使用3 層GCN 的實(shí)驗(yàn)結(jié)果。在3 個(gè)數(shù)據(jù)集上,引入殘差連接的Res-VGAE 和Res-GAE 表現(xiàn)略優(yōu)于直接疊加GCN 層的模型,而OSA-VGAE 和OSA-GAE 的表現(xiàn)明顯優(yōu)于其他模型,特別是在CiteSeer 數(shù)據(jù)集上,AUC 和AP 相較單層模型有小幅度提升。
表3 3層GCN時(shí)各模型的AUC和AP 單位:%Tab.3 AUC and AP of each model with 3-layer GCN unit:%
表4 比較了不同模型使用6 層GCN 的實(shí)驗(yàn)結(jié)果。在3 個(gè)數(shù)據(jù)集上,不引入殘差連接、OSA 和ELU 函數(shù)的VGAE、GAE、Linear-VGAE 和Linear-GAE 的AUC 和AP 明顯降低,并且采用線性編碼的Linear-VGAE 和Linear-GAE 表現(xiàn)最差。在Cora 數(shù)據(jù)集上,Res-VGAE 和Res-GAE 與VGAE 和GAE 性能相近;在CiteSeer 和PubMed 數(shù)據(jù)集上,Res-VGAE 和Res-GAE 表現(xiàn)優(yōu)于VGAE 和GAE。在3 個(gè)數(shù)據(jù)集上,OSA-VGAE和OSA-GAE 表現(xiàn)最好,深層模型與淺層模型的性能差異不大,尤其是在CiteSeer 上,AUC 和AP 仍有提升。
表4 6層GCN時(shí)各模型的AUC和AP 單位:%Tab.4 AUC and AP of each model with 6-layer GCN unit:%
圖3~5 為不同模型在引文數(shù)據(jù)集上1~6 層的AUC 和AP。與原始的VGAE 和GAE 相比,隨著深度增加,Linear-VGAE 和Linear-GAE 的精度下降最快,表現(xiàn)最差;引入殘差連接的Res-VGAE 和Res-GAE 雖然在一定程度上緩解了深層模型精度下降的問(wèn)題,但是其表現(xiàn)與原始模型相接近。本文提出的OSA-VGAE 和OSA-GAE 明顯好于其他模型,隨著深度的增加,模型的性能基本保持穩(wěn)定,在Cora 和CiteSeer 數(shù)據(jù)集上其性能呈現(xiàn)隨層數(shù)的增加而上升的趨勢(shì)。上述實(shí)驗(yàn)結(jié)果說(shuō)明添加OSA 和ELU 函數(shù)能夠改善深層模型的梯度信息傳遞問(wèn)題,提升模型性能。
圖3 Cora數(shù)據(jù)集上的AUC和APFig.3 AUC and AP on Cora dateset
為了驗(yàn)證OSA-VGAE 和OSA-GAE 模型中使用OSA 和ELU 對(duì)于算法性能的影響,在Cora 數(shù)據(jù)集上進(jìn)行消融實(shí)驗(yàn),對(duì)比單獨(dú)使用OSA 和ELU 函數(shù)的模型性能。為了保證實(shí)驗(yàn)的公平性,保持學(xué)習(xí)率、隱層維度和嵌入維度等參數(shù)一致。實(shí)驗(yàn)結(jié)果如表5 所示。相較于單獨(dú)使用OSA 或ELU 函數(shù),OSA-VGAE 和OSA-GAE 獲得了最佳表現(xiàn),說(shuō)明同時(shí)使用上述兩個(gè)模塊能夠顯著提升性能。
表5 消融實(shí)驗(yàn)結(jié)果 單位:%Tab.5 Results of ablation experiments unit:%
為了評(píng)估不同嵌入維度和迭代次數(shù)對(duì)實(shí)驗(yàn)結(jié)果的影響,在Cora 數(shù)據(jù)集上對(duì)使用1 層GCN 的OSA-VGAE 和OSA-GAE模型進(jìn)行參數(shù)敏感性實(shí)驗(yàn),記錄相關(guān)數(shù)據(jù)。圖6 顯示了不同嵌入維度對(duì)模型性能的影響。最初,AUC 隨維度的增加而提高,這是因?yàn)楦嗟木S度使嵌入中編碼了更多有益信息,提升了實(shí)驗(yàn)表現(xiàn)。但是,隨著維度不斷的增加,AUC 開始下降,這是因?yàn)橛?xùn)練樣本個(gè)數(shù)有限,對(duì)于每一類節(jié)點(diǎn)都存在最大化模型性能的最優(yōu)嵌入維數(shù),當(dāng)嵌入維數(shù)超過(guò)最優(yōu)維數(shù)時(shí),模型性能表現(xiàn)出逐漸下降的趨勢(shì)。此外,從圖6 曲線變化可以看出,OSA-VGAE 相比OSA-GAE 對(duì)維度更敏感。因此,在生成節(jié)點(diǎn)嵌入時(shí)選擇合適的維度十分重要。
圖4 CiteSeer數(shù)據(jù)集上的AUC和APFig.4 AUC and AP on CiteSeer dateset
圖5 PubMed數(shù)據(jù)集上的AUC和APFig.5 AUC and AP on PubMed dateset
圖6 不同嵌入維度的AUCFig.6 AUCs of different embedding dimensions
圖7 記錄了OSA-VGAE 和OSA-GAE 每次迭代的訓(xùn)練損失和AUC。隨著迭代次數(shù)的增加,模型訓(xùn)練損失整體呈下降趨勢(shì),并且在200~1 000 的迭代過(guò)程中,損失值基本處于穩(wěn)定狀態(tài)。在測(cè)試集上,初始階段的AUC 隨著迭代次數(shù)的增加快速上升,到達(dá)一定迭代次數(shù)時(shí),模型開始出現(xiàn)過(guò)擬合,泛化能力下降,導(dǎo)致AUC 小幅下降并上下震蕩。因此,在訓(xùn)練模型時(shí)選取200 左右的迭代次數(shù)即可獲得較為理想的實(shí)驗(yàn)結(jié)果。
圖7 OSA-VGAE和OSA-GAE在不同迭代時(shí)的訓(xùn)練損失和AUCFig.7 Training loss and AUC under different iteration for OSA-VGAE and OSA-GAE
本文提出了基于One-Shot 聚合和ELU 激活函數(shù)的OSAVGAE 和OSA-GAE 模型,改善了模型的梯度信息傳遞,緩解了基于GCN 編碼的自編碼器模型深度問(wèn)題。實(shí)驗(yàn)結(jié)果表明,將計(jì)算機(jī)視覺(jué)中的深層策略引入到圖表示學(xué)習(xí)中是有益的,能夠提升圖機(jī)器學(xué)習(xí)任務(wù)的表現(xiàn)。此外,消融實(shí)驗(yàn)的結(jié)果也說(shuō)明同時(shí)使用One-Shot 聚合和ELU 函數(shù)對(duì)模型性能提升更加顯著。在未來(lái)工作中,除了對(duì)現(xiàn)有編碼器模型的結(jié)構(gòu)進(jìn)行改進(jìn),將采用更為高效的鄰域聚合和鄰域交互編碼器建模,如基于注意力機(jī)制的方法[32];在解碼器部分,將嘗試使用不同的解碼器和概率分布進(jìn)行實(shí)驗(yàn)。此外,后續(xù)工作還將針對(duì)模型復(fù)雜度、模型泛化能力以及模型避免過(guò)擬合能力進(jìn)行量化和分析。