基于One-Shot聚合自編碼器的圖表示學(xué)習(xí)

袁立寧，劉 釗

（1.中國人民公安大學(xué) 信息網(wǎng)絡(luò)安全學(xué)院，北京 100038；2.中國人民公安大學(xué) 研究生院，北京 100038）

0 引言

圖表示學(xué)習(xí)將原始圖的結(jié)構(gòu)和特征信息嵌入到低維向量空間，從而能夠直接應(yīng)用常見機(jī)器學(xué)習(xí)算法來挖掘網(wǎng)絡(luò)的潛在特征。圖表示學(xué)習(xí)旨在生成保留拓?fù)浜蛯傩孕畔⒌牡途S表示，用于節(jié)點(diǎn)分類［1］、鏈接預(yù)測［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)大的表示能力，受到了越來越多的關(guān)注。在最近的文獻(xiàn)中，已經(jīng)有許多研究嘗試將深度學(xué)習(xí)方法用于圖表示學(xué)習(xí)。其中，基于深度學(xué)習(xí)的無監(jiān)督模型能夠在缺乏先驗(yàn)知識(shí)或標(biāo)記信息有限的情況下，從數(shù)據(jù)中選出具有代表性的特征，因此常用于生成原始數(shù)據(jù)低維節(jié)點(diǎn)向量表示。

基于深度學(xué)習(xí)的無監(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)特征。基于AE 的圖嵌入模型將圖的拓?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］。

針對上述問題，本文使用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ù)測實(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)練過程中參數(shù)過擬合；3）在鏈路預(yù)測實(shí)驗(yàn)中，OSA-GAE 和OSA-VGAE 的性能始終優(yōu)于相同深度的基線方法，而且它們的性能不會(huì)隨著隱藏層數(shù)量的增加而降低，并且在部分?jǐn)?shù)據(jù)集上呈現(xiàn)出上升趨勢。

1 相關(guān)工作

1.1 圖表示學(xué)習(xí)

根據(jù)不同的策略，常見的無監(jiān)督圖表示學(xué)習(xí)模型可以分為兩類：基于隨機(jī)游走和基于AE 的模型。

基于隨機(jī)游走的模型通過隨機(jī)游走獲得訓(xùn)練語料庫，然后將語料庫集成到Skip-Gram 獲得節(jié)點(diǎn)的低維嵌入表示。DeepWalk 使用隨機(jī)游走采樣節(jié)點(diǎn)序列，再通過Skip-Gram 最大化窗口范圍內(nèi)節(jié)點(diǎn)之間的共現(xiàn)概率將節(jié)點(diǎn)映射為嵌入向量，由于優(yōu)化過程中未使用明確的目標(biāo)函數(shù)，使模型保持網(wǎng)絡(luò)結(jié)構(gòu)的能力有限。node2vec 在DeepWalk 的基礎(chǔ)上引入有偏的隨機(jī)游走，增加鄰域搜索的靈活性，但是仍然缺乏一個(gè)明確的目標(biāo)函數(shù)來保持全局網(wǎng)絡(luò)結(jié)構(gòu)。Walklets［15］修改DeepWalk 的采樣過程，捕獲節(jié)點(diǎn)與社區(qū)之間不同尺度信息，顯式建模多尺度關(guān)系，使生成的嵌入能夠保留更豐富的節(jié)點(diǎn)從屬關(guān)系信息。

基于AE 的模型使用AE 對圖的非線性結(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ù)測和節(jié)點(diǎn)分類等任務(wù)所需的底層結(jié)構(gòu)，同時(shí)引入堆疊去噪自編碼器增強(qiáng)模型在含噪聲圖上的魯棒性。VGAE［18］使用變分自編碼器（Variational AutoEncoder，VAE）［19］學(xué)習(xí)可解釋的無向圖嵌入表示，與非概率自編碼器相比，使用VAE 提升了模型性能。Res-VGAE（Variational Graph AutoEncoders with Residual connections）［20］在VGAE 的基礎(chǔ)上引入殘差連接［21］，改善深層VAE 性能，但是模型性能隨著深度的增加仍表現(xiàn)出顯著性降低。ANE［22］使用對抗性自編碼器［23］生成捕獲高度非線性結(jié)構(gòu)信息的低維嵌入，在生成過程中施加對抗性正則化避免流形斷裂問題，同時(shí)利用一階和二階相似度捕捉局部和全局結(jié)構(gòu)。

1.2 深層模型策略

理論上，隨著深度增加，神經(jīng)網(wǎng)絡(luò)模型能夠提取更復(fù)雜的特征，獲得更好的結(jié)果。實(shí)際上，模型性能會(huì)因深度增加而退化，導(dǎo)致準(zhǔn)確度達(dá)到飽和甚至下降，并且在訓(xùn)練中出現(xiàn)梯度消失。

為解決上述問題，ResNet［21］引入殘差單元，將各層的輸入和輸出相加，實(shí)現(xiàn)跨層連接，改善深層模型的梯度更新。DenseNet［24］使用稠密連接，即每一層的輸入來自前面所有層的輸出，改善梯度消失問題。與ResNet 相比，DenseNet 能夠保留多個(gè)感受野的特征圖，更加充分地利用特征信息，但是稠密連接使輸入通道增加，導(dǎo)致模型計(jì)算效率嚴(yán)重降低。VoVnet［13］使用OSA 將全部特征圖聚合到最后一層，使模型在繼承DenseNet 優(yōu)點(diǎn)的情況下，解決了稠密連接效率低的問題。OSA 方式如圖1 所示。以上方法改善了卷積神經(jīng)網(wǎng)絡(luò)（Convolutional Neural Network，CNN）［25］隨深度增加加深出現(xiàn)梯度消失的問題，本文借鑒上述建模思路改進(jìn)深層GNN 編碼器模型架構(gòu)。

圖1 One-Shot聚合Fig.1 One-Shot aggregation

此外，選擇合適的激活函數(shù)，同樣能夠解決深層神經(jīng)網(wǎng)絡(luò)的梯度消失問題。例如，線性整流函數(shù)（Rectified Linear Unit，ReLU）［26］：

ReLU 解決了梯度消失問題，能大幅提升模型的計(jì)算速度，但是在x＜0 時(shí)負(fù)的梯度被置零，導(dǎo)致神經(jīng)元壞死，不再對任何數(shù)據(jù)產(chǎn)生響應(yīng)。ELU 在ReLU 基礎(chǔ)上引入指數(shù)函數(shù)，使其在負(fù)輸入值的情況下也能返回信息：

相較于ReLU，在輸入為負(fù)值的情況下，ELU 有一定的輸出，從而消除ReLU 神經(jīng)元壞死的問題。此外，ELU 的輸出均值接近0，減少了偏移效應(yīng)，使正常梯度接近于自然梯度；在輸入較小時(shí)負(fù)值能夠快速飽和，對噪聲有一定的魯棒性。

2 模型與算法

本章提出基于One-Shot 聚合自編碼器的圖表示學(xué)習(xí)模型OSA-GAE 和OSA-VGAE 并討論算法原理，介紹了模型框架及編碼器和解碼器結(jié)構(gòu)，并討論了模型的損失函數(shù)。

2.1 模型框架

基于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

2.2 編碼器網(wǎng)絡(luò)結(jié)構(gòu)

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ù)。

2.3 解碼器網(wǎng)絡(luò)結(jié)構(gòu)

對于OSA-GAE 模型，解碼器是利用兩個(gè)節(jié)點(diǎn)表示內(nèi)積重構(gòu)鄰接矩陣的非概率模型：

其中：A′表示重構(gòu)矩陣；φ表示sigmoid 函數(shù)。

對于OSA-VGAE 模型，解碼器是利用兩個(gè)節(jié)點(diǎn)表示內(nèi)積重構(gòu)鄰接矩陣的概率模型：

其中：Aij為鄰接矩陣A的元素。

2.4 損失函數(shù)

OSA-GAE 通過最小化A和A′的重構(gòu)損失進(jìn)行訓(xùn)練，表達(dá)式為：

OSA-VGAE 通過最大化變分下界以及最小化重構(gòu)損失進(jìn)行訓(xùn)練，表達(dá)式為：

為了避免參數(shù)過擬合，在OSA-GAE 和OSA-VGAE 損失函數(shù)中引入L2-norm 正則化項(xiàng)Lreg，使用超參數(shù)α控制比重：

在訓(xùn)練過程中，GCN 層的輸入和輸出維度必須相同，才能使用OSA。此外，OSA-GAE 和OSA-VGAE 均執(zhí)行全批次梯度下降，并利用重參數(shù)化技巧［19］進(jìn)行訓(xùn)練。

3 實(shí)驗(yàn)與結(jié)果分析

3.1 數(shù)據(jù)集

本文使用Cora、CiteSeer、PubMed 這3 個(gè)基準(zhǔn)引文網(wǎng)絡(luò)數(shù)據(jù)集［30］評(píng)估OSA-VGAE 和OSA-GAE 生成的低維嵌入表示在鏈接預(yù)測任務(wù)中的性能。在數(shù)據(jù)集中：節(jié)點(diǎn)表示論文，邊表示一篇論文對另一篇論文的引用，節(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

3.2 基線模型

本文使用以下模型作為基線：

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］：該模型使用歸一化鄰接矩陣的簡單線性模型替換VGAE 中的GCN 編碼器，解碼器與VGAE 相同。

Linear-GAE［31］：該模型使用歸一化鄰接矩陣的簡單線性模型替換GAE 中的GCN 編碼器，解碼器與GAE 相同。

Res-VGAE：該模型在VGAE 的基礎(chǔ)上引入殘差連接，改善深層VAE 模型的性能。

Res-GAE［20］：該模型在GAE 的基礎(chǔ)上引入殘差連接，改善深層AE 模型的性能。

3.3 實(shí)驗(yàn)設(shè)置

為了驗(yàn)證模型在鏈接預(yù)測任務(wù)中的性能，需要對基準(zhǔn)引文網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行預(yù)處理［19］：1）保留所有節(jié)點(diǎn)的特征信息，將圖中部分邊移除；2）隨機(jī)采樣無邊的節(jié)點(diǎn)對，其數(shù)量與先前移除的邊數(shù)相同；3）利用移除的邊和無邊節(jié)點(diǎn)對構(gòu)建驗(yàn)證集和測試集，其比例分別為總邊的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)證集和測試集劃分，運(yùn)行10 次獲得平均值。

3.4 實(shí)驗(yàn)結(jié)果

鏈接預(yù)測任務(wù)即預(yù)測兩個(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 十分接近。對于淺層模型，增加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 雖然在一定程度上緩解了深層模型精度下降的問題，但是其表現(xiàn)與原始模型相接近。本文提出的OSA-VGAE 和OSA-GAE 明顯好于其他模型，隨著深度的增加，模型的性能基本保持穩(wěn)定，在Cora 和CiteSeer 數(shù)據(jù)集上其性能呈現(xiàn)隨層數(shù)的增加而上升的趨勢。上述實(shí)驗(yàn)結(jié)果說明添加OSA 和ELU 函數(shù)能夠改善深層模型的梯度信息傳遞問題，提升模型性能。

圖3 Cora數(shù)據(jù)集上的AUC和APFig.3 AUC and AP on Cora dateset

3.5 消融實(shí)驗(yàn)

為了驗(yàn)證OSA-VGAE 和OSA-GAE 模型中使用OSA 和ELU 對于算法性能的影響，在Cora 數(shù)據(jù)集上進(jìn)行消融實(shí)驗(yàn)，對比單獨(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)，說明同時(shí)使用上述兩個(gè)模塊能夠顯著提升性能。

表5 消融實(shí)驗(yàn)結(jié)果 單位：%Tab.5 Results of ablation experiments unit：%

3.6 參數(shù)分析

為了評(píng)估不同嵌入維度和迭代次數(shù)對實(shí)驗(yàn)結(jié)果的影響，在Cora 數(shù)據(jù)集上對使用1 層GCN 的OSA-VGAE 和OSA-GAE模型進(jìn)行參數(shù)敏感性實(shí)驗(yàn)，記錄相關(guān)數(shù)據(jù)。圖6 顯示了不同嵌入維度對模型性能的影響。最初，AUC 隨維度的增加而提高，這是因?yàn)楦嗟木S度使嵌入中編碼了更多有益信息，提升了實(shí)驗(yàn)表現(xiàn)。但是，隨著維度不斷的增加，AUC 開始下降，這是因?yàn)橛?xùn)練樣本個(gè)數(shù)有限，對于每一類節(jié)點(diǎn)都存在最大化模型性能的最優(yōu)嵌入維數(shù)，當(dāng)嵌入維數(shù)超過最優(yōu)維數(shù)時(shí)，模型性能表現(xiàn)出逐漸下降的趨勢。此外，從圖6 曲線變化可以看出，OSA-VGAE 相比OSA-GAE 對維度更敏感。因此，在生成節(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)練損失整體呈下降趨勢，并且在200～1 000 的迭代過程中，損失值基本處于穩(wěn)定狀態(tài)。在測試集上，初始階段的AUC 隨著迭代次數(shù)的增加快速上升，到達(dá)一定迭代次數(shù)時(shí)，模型開始出現(xiàn)過擬合，泛化能力下降，導(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

4 結(jié)語

本文提出了基于One-Shot 聚合和ELU 激活函數(shù)的OSAVGAE 和OSA-GAE 模型，改善了模型的梯度信息傳遞，緩解了基于GCN 編碼的自編碼器模型深度問題。實(shí)驗(yàn)結(jié)果表明，將計(jì)算機(jī)視覺中的深層策略引入到圖表示學(xué)習(xí)中是有益的，能夠提升圖機(jī)器學(xué)習(xí)任務(wù)的表現(xiàn)。此外，消融實(shí)驗(yàn)的結(jié)果也說明同時(shí)使用One-Shot 聚合和ELU 函數(shù)對模型性能提升更加顯著。在未來工作中，除了對現(xiàn)有編碼器模型的結(jié)構(gòu)進(jìn)行改進(jìn)，將采用更為高效的鄰域聚合和鄰域交互編碼器建模，如基于注意力機(jī)制的方法［32］；在解碼器部分，將嘗試使用不同的解碼器和概率分布進(jìn)行實(shí)驗(yàn)。此外，后續(xù)工作還將針對模型復(fù)雜度、模型泛化能力以及模型避免過擬合能力進(jìn)行量化和分析。