基于全局對(duì)抗負(fù)樣本的圖對(duì)比學(xué)習(xí)方法

岑科廷,沈華偉,曹 婍,徐冰冰,程學(xué)旗

(1.中國(guó)科學(xué)院 計(jì)算技術(shù)研究所 數(shù)據(jù)智能系統(tǒng)研究中心,北京 100190;2.中國(guó)科學(xué)院大學(xué),北京 101408;3. 中國(guó)科學(xué)院 計(jì)算技術(shù)研究所 網(wǎng)絡(luò)數(shù)據(jù)科學(xué)與技術(shù)重點(diǎn)實(shí)驗(yàn)室,北京 100190)

0 引言

圖表示學(xué)習(xí)期望給每個(gè)節(jié)點(diǎn)學(xué)到保留圖結(jié)構(gòu)和節(jié)點(diǎn)屬性的低維表示[1]。這類方法在很多重要的圖分析任務(wù)上取得了顯著的成果,例如,節(jié)點(diǎn)分類[1]、鏈路預(yù)測(cè)等[2]。最近,基于圖對(duì)比學(xué)習(xí)的節(jié)點(diǎn)表示學(xué)習(xí)方法展現(xiàn)了前所未有的性能[3-5],正在成為該領(lǐng)域的主流方法。

圖對(duì)比學(xué)習(xí)期望通過(guò)拉近正樣本對(duì)之間的距離,推遠(yuǎn)負(fù)樣本之間的距離來(lái)為每個(gè)節(jié)點(diǎn)學(xué)習(xí)表示[6-8]。傳統(tǒng)的圖對(duì)比學(xué)習(xí)方法將同一個(gè)節(jié)點(diǎn)經(jīng)過(guò)兩種不同數(shù)據(jù)增強(qiáng)后得到的節(jié)點(diǎn)視為正樣本對(duì),將其與圖上其它節(jié)點(diǎn)都視為負(fù)樣本對(duì)[3](圖1(a))。由于每個(gè)節(jié)點(diǎn)都將其余節(jié)點(diǎn)視為負(fù)樣本,因此這類方法的時(shí)間復(fù)雜度是關(guān)于節(jié)點(diǎn)數(shù)的平方,導(dǎo)致此類方法難以被應(yīng)用到實(shí)際場(chǎng)景中。

圖1 負(fù)樣本選擇方式對(duì)比

為了降低時(shí)間復(fù)雜度,一種直觀的方式是給每個(gè)節(jié)點(diǎn)選擇一些節(jié)點(diǎn)作為負(fù)樣本。具體來(lái)說(shuō)研究者們?cè)噲D通過(guò)隨機(jī)采樣特定個(gè)負(fù)樣本的方式加速模型[9](圖1(b))。該方法將所有負(fù)樣本視為同等重要,并通過(guò)均勻采樣的方式為每個(gè)節(jié)點(diǎn)生成對(duì)應(yīng)的負(fù)樣本。然而,該方法已經(jīng)被證實(shí)需要大量的負(fù)樣本才能使模型達(dá)到較好的效果[10]。

為了提升圖對(duì)比學(xué)習(xí)方法的性能和效率,一些方法改進(jìn)了負(fù)樣本選擇的策略。最近的一些工作從理論和實(shí)驗(yàn)上發(fā)現(xiàn)難的負(fù)樣本(即難以與正樣本對(duì)區(qū)分的樣本)有助于學(xué)習(xí)更強(qiáng)大的表示。因此,大量現(xiàn)有方法希望啟發(fā)式地為每個(gè)節(jié)點(diǎn)選擇若干難的負(fù)樣本(圖1(c))。常見(jiàn)的選擇標(biāo)準(zhǔn)有節(jié)點(diǎn)間路徑長(zhǎng)度[10-11]和節(jié)點(diǎn)表示間的余弦相似度[10]等?；诠?jié)點(diǎn)間路徑長(zhǎng)度的標(biāo)準(zhǔn)認(rèn)為,距離目標(biāo)節(jié)點(diǎn)越近的節(jié)點(diǎn),作為負(fù)樣本的重要性越高。而基于節(jié)點(diǎn)表示間的余弦相似度的標(biāo)準(zhǔn)認(rèn)為,與目標(biāo)節(jié)點(diǎn)表示的余弦相似度越大的節(jié)點(diǎn),作為負(fù)樣本的重要性越高。然而,這類啟發(fā)式定義的重要性度量標(biāo)準(zhǔn)無(wú)法保證選出來(lái)的負(fù)樣本對(duì)于模型是難的。同時(shí)這些方法在為每個(gè)點(diǎn)篩選負(fù)樣本時(shí),需要計(jì)算其與圖上所有其它節(jié)點(diǎn)之間的相似度,并進(jìn)行排序選擇前K個(gè)節(jié)點(diǎn),引入了額外的時(shí)間復(fù)雜度。

為了解決上述問(wèn)題,本文提出基于全局對(duì)抗負(fù)樣本的圖對(duì)比學(xué)習(xí)方法。通過(guò)將負(fù)樣本參數(shù)化,直接學(xué)習(xí)模型需要的難負(fù)樣本。通過(guò)最大化模型損失函數(shù),更新該負(fù)樣本參數(shù),不再需要通過(guò)人為先驗(yàn)來(lái)進(jìn)行啟發(fā)式選擇。同時(shí),與之前方法分別為每個(gè)節(jié)點(diǎn)構(gòu)建難負(fù)樣本不同,我們?yōu)樗泄?jié)點(diǎn)學(xué)習(xí)一個(gè)全局的負(fù)樣本(圖1(d)),從而顯著提高了效率。另一種有效的方式是為每個(gè)節(jié)點(diǎn)都學(xué)習(xí)一個(gè)負(fù)樣本,然而這樣會(huì)引入大量的參數(shù),導(dǎo)致過(guò)擬合問(wèn)題,同時(shí)也帶來(lái)了高昂的內(nèi)存代價(jià)。因此我們選擇為所有節(jié)點(diǎn)學(xué)習(xí)一個(gè)共享的全局的負(fù)樣本。具體來(lái)說(shuō),我們將同一個(gè)節(jié)點(diǎn)在兩個(gè)不同增強(qiáng)圖上的表示作為正樣本對(duì),將節(jié)點(diǎn)與待學(xué)習(xí)的全局負(fù)樣本視為負(fù)樣本對(duì)。受Hu等人[12]的啟發(fā),我們通過(guò)將模型形式化成一個(gè)最大最小化問(wèn)題進(jìn)行求解。具體來(lái)說(shuō),我們的模型包含兩個(gè)互相對(duì)抗的參與者: 待學(xué)習(xí)的全局負(fù)樣本和將每個(gè)節(jié)點(diǎn)映射到隱層表示空間的圖編碼器。我們通過(guò)交替優(yōu)化的方式更新圖編碼器的參數(shù)和全局負(fù)樣本的參數(shù)。一方面,我們固定全局負(fù)樣本表示,通過(guò)最小化對(duì)比損失來(lái)訓(xùn)練圖編碼器,即鼓勵(lì)模型能正確區(qū)分正負(fù)樣本對(duì)。另一方面,我們固定圖編碼器參數(shù),通過(guò)最大化對(duì)比損失來(lái)更新全局負(fù)樣本,即產(chǎn)生讓模型無(wú)法分對(duì)的最難的負(fù)樣本。

此外,本文進(jìn)一步對(duì)提出的方法進(jìn)行了深入分析,發(fā)現(xiàn)更新全局負(fù)樣本的梯度為圖中所有節(jié)點(diǎn)表示的加權(quán)線性組合。同時(shí)證明,最小化與該全局負(fù)樣本的對(duì)比損失函數(shù)等價(jià)于最大化圖上節(jié)點(diǎn)之間的加權(quán)平均距離。多個(gè)基準(zhǔn)數(shù)據(jù)集上充分的實(shí)驗(yàn)結(jié)果證明了我們模型的有效性和效率。

1 相關(guān)工作

1.1 傳統(tǒng)圖表示學(xué)習(xí)

圖表示學(xué)習(xí)旨在為每個(gè)節(jié)點(diǎn)學(xué)習(xí)一個(gè)保留網(wǎng)絡(luò)結(jié)構(gòu)性質(zhì)或者節(jié)點(diǎn)屬性的低維節(jié)點(diǎn)表示。 以前的方法通常通過(guò)解決一個(gè)預(yù)定義任務(wù)來(lái)學(xué)習(xí)節(jié)點(diǎn)表示[13]。 大多數(shù)傳統(tǒng)的網(wǎng)絡(luò)嵌入方法采用結(jié)構(gòu)重建[14-15]或?qū)傩灶A(yù)測(cè)[16-17]作為預(yù)定義任務(wù)。

結(jié)構(gòu)重構(gòu)任務(wù)期望利用節(jié)點(diǎn)表表示H恢復(fù)某些結(jié)構(gòu)相關(guān)的矩陣,例如,鄰接矩陣A[14]。GAE[14]利用圖卷積神經(jīng)網(wǎng)絡(luò)將節(jié)點(diǎn)的結(jié)構(gòu)和屬性映射到隱層表示空間,同時(shí)利用節(jié)點(diǎn)vi和vj表示的點(diǎn)積來(lái)重構(gòu)他們之間的連邊概率A′ij。GAE通過(guò)約束重構(gòu)的鄰接矩陣A′盡可能和輸入的鄰接矩陣A保持一致來(lái)訓(xùn)練模型。

基于屬性重構(gòu)的網(wǎng)絡(luò)表示學(xué)習(xí)方法,將利用節(jié)點(diǎn)表示H重構(gòu)輸入屬性矩陣X作為目標(biāo)訓(xùn)練模型[16-17]。例如,ANRL[17]將節(jié)點(diǎn)的鄰接矩陣A作為輸入,經(jīng)過(guò)多層自編碼器后輸出預(yù)測(cè)的節(jié)點(diǎn)屬性矩陣X′,通過(guò)約束輸出屬性矩陣X′盡可能接近輸入屬性X來(lái)訓(xùn)練表示學(xué)習(xí)模型。

1.2 圖對(duì)比學(xué)習(xí)

最近,圖對(duì)比學(xué)習(xí)已成為無(wú)監(jiān)督圖表示學(xué)習(xí)中最受關(guān)注的一種技術(shù)。圖對(duì)比學(xué)習(xí)期望學(xué)到一個(gè)表示學(xué)習(xí)模型,使得相似的節(jié)點(diǎn)(正樣本)得到相似的表示,不相似的節(jié)點(diǎn)(負(fù)樣本)得到差異較大的表示[3-8,18]。

傳統(tǒng)的圖對(duì)比學(xué)習(xí)將所有負(fù)樣本視為同等重要,其不同點(diǎn)在于對(duì)正樣本的定義。例如,GRACE[3]將同一節(jié)點(diǎn)的不同增強(qiáng)版本定義為正樣本對(duì),而將圖上剩下其它所有節(jié)點(diǎn)都當(dāng)成負(fù)樣本。DGI[19]將圖表示和圖上節(jié)點(diǎn)表示視為正樣本對(duì),將圖表示和隨機(jī)打亂后圖上節(jié)點(diǎn)表示視為負(fù)樣本對(duì)。

最近一些方法通過(guò)啟發(fā)式的方式來(lái)定義重要的負(fù)樣本,從而提升圖對(duì)比學(xué)習(xí)的效果。例如,Yang等人[9]認(rèn)為節(jié)點(diǎn)的度反映其作為負(fù)樣本的重要性,因此該方法提出負(fù)樣本的采樣概率與其度成正比,即度越大的節(jié)點(diǎn)越重要。GraphCL[10]定義負(fù)樣本節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)的余弦相似度為其重要性,對(duì)于每個(gè)節(jié)點(diǎn)利用余弦相似度挑選最像的K個(gè)節(jié)點(diǎn)作為負(fù)樣本。Kalantidis等人[20]提出利用得到的負(fù)樣本進(jìn)行線性混合,生成更難的負(fù)樣本。

此外,近些年圖對(duì)比學(xué)習(xí)在可解釋性和數(shù)據(jù)增強(qiáng)方式上也有新的進(jìn)展。DGCL[21]利用解耦表示提升了圖對(duì)比學(xué)習(xí)的可解釋性。ARIEL[22]利用對(duì)抗訓(xùn)練的方式生成增強(qiáng)樣本。

2 模型

本節(jié)首先回顧傳統(tǒng)圖對(duì)比學(xué)習(xí),分析它的局限性,并介紹我們工作的動(dòng)機(jī)。之后詳細(xì)介紹我們模型的框架,以及如何更新模型的參數(shù)和我們的全局負(fù)樣本。最后,通過(guò)分析更新全局負(fù)樣本的梯度,更好地揭示了模型背后的含義。

2.1 動(dòng)機(jī)

(1)

現(xiàn)有方法通過(guò)均勻采樣的方式從圖上采樣負(fù)樣本,即每個(gè)點(diǎn)被當(dāng)成負(fù)樣本的概率相同。由于采樣過(guò)程與模型無(wú)關(guān),難以保證采樣到的負(fù)樣本對(duì)于模型是難的。因此現(xiàn)有方法往往需要較大的負(fù)樣本個(gè)數(shù)K,例如,GRACE將圖上所有其它節(jié)點(diǎn)視為負(fù)樣本即K=N,使得模型具有較高的時(shí)間復(fù)雜度。最近,Hafidi等人[11]將余弦相似度定義為負(fù)樣本的重要性,通過(guò)并依此為每個(gè)節(jié)點(diǎn)篩選負(fù)樣本。然而啟發(fā)式定義的余弦相似度并不能真正反映負(fù)樣本的重要性。同時(shí)由于需要在迭代中對(duì)節(jié)點(diǎn)按余弦相似度排序,使得模型又引入了額外高昂的時(shí)間代價(jià)。為了克服上述困難,我們提出直接學(xué)習(xí)全局負(fù)樣本。即通過(guò)對(duì)抗訓(xùn)練學(xué)到使得圖對(duì)比學(xué)習(xí)模型損失函數(shù)最大的全局對(duì)抗負(fù)樣本?？紤]到該負(fù)樣本是基于全局損失函數(shù)學(xué)到的,因此該負(fù)樣本兼顧了所有節(jié)點(diǎn)需要的負(fù)樣本的性質(zhì),我們讓所有節(jié)點(diǎn)共享該負(fù)樣本,因此將負(fù)樣本個(gè)數(shù)降低為1,極大地提升了模型的效率。

2.2 基于全局對(duì)抗負(fù)樣本圖對(duì)比學(xué)習(xí)

本節(jié)形式化地介紹基于全局對(duì)抗負(fù)樣本圖對(duì)比學(xué)習(xí)的節(jié)點(diǎn)表示學(xué)習(xí)方法ANGCL。

2.2.1 模型框架

如圖2所示,我們的ANGCL模型包含兩個(gè)對(duì)抗性參與者: 圖編碼器θ和可學(xué)習(xí)的全局負(fù)樣本n。圖編碼器旨在通過(guò)最小化對(duì)比損失來(lái)學(xué)習(xí)將正樣本與負(fù)樣本區(qū)分開(kāi)來(lái)的節(jié)點(diǎn)表示。而全局負(fù)樣本n則是指最容易讓模型做錯(cuò)的負(fù)樣本,即最大化對(duì)比損失的負(fù)樣本。我們將求解圖編碼器θ和對(duì)抗負(fù)樣本n的過(guò)程抽象成最大最小化問(wèn)題,其形式化如式(2)所示。

圖2 ANGCL模型框架圖

(2)

其中,θ*表示最優(yōu)的圖編碼器的參數(shù),n*表示最優(yōu)的全局負(fù)樣本,L(θ,n)是對(duì)比損失函數(shù)。正如許多現(xiàn)有的對(duì)抗性訓(xùn)練算法所示,找到此類問(wèn)題的鞍點(diǎn)既困難又耗時(shí)[12,23]。 因此,我們采用了被廣泛使用的快速梯度法[23],通過(guò)交替更新它們,直到收斂。即在更新圖編碼器參數(shù)時(shí),保持全局負(fù)樣本不變。在更新全局負(fù)樣本時(shí),保持圖編碼器參數(shù)不變。該過(guò)程形式化為以下等式:

其中,ηθ和ηn分別是更新圖編碼器θ和全局負(fù)樣本n的學(xué)習(xí)率。下文將詳細(xì)介紹圖編碼器的實(shí)現(xiàn),以及全局負(fù)樣本更新的具體形式及其意義。

2.2.2 圖編碼器實(shí)現(xiàn)

如圖2所示,對(duì)于一張圖我們首先通過(guò)數(shù)據(jù)增強(qiáng)函數(shù)t1和t2,分別生成對(duì)應(yīng)的增強(qiáng)圖(A(1),X(1))和(A(2),X(2)),之后通過(guò)圖編碼器θ得到對(duì)應(yīng)的節(jié)點(diǎn)表示。

為了公平對(duì)比,我們使用與之前的方法相同的數(shù)據(jù)增強(qiáng)函數(shù)。增強(qiáng)函數(shù)包含兩個(gè)算子,連邊去除和特征掩蔽。連邊去除通過(guò)隨機(jī)丟棄一些邊來(lái)生成增強(qiáng)圖。具體來(lái)說(shuō),對(duì)于每條邊,我們隨機(jī)生成一個(gè)遵循伯努利分布B(1-pe)的指示Re。其中,pe是邊移除的概率。如果Re=1,則刪除邊e以生成增廣圖。類似地,我們生成一個(gè)遵循伯努利分布B(1-pf)的指標(biāo)Rf,pf表示特征掩蔽的概率。如果Rf=1,我們將圖中所有節(jié)點(diǎn)的特征f設(shè)置為零。t1和t2的區(qū)別在于概率pe和pf不同。圖編碼器θ用于將每個(gè)節(jié)點(diǎn)嵌入到隱藏空間中,可以使用任何圖神經(jīng)網(wǎng)絡(luò)[24-26]來(lái)構(gòu)建。為了同之前的方法進(jìn)行公平的對(duì)比,我們采用與其相同的架構(gòu),即堆疊兩層 GCN[24]以形成圖形編碼器。具體來(lái)說(shuō),它形式化為:

(5)

2.2.3 負(fù)樣本更新

首先,我們給出模型對(duì)比損失函數(shù)的定義。與之前的方法不同,ANGCL通過(guò)約束同一節(jié)點(diǎn)在不同增強(qiáng)圖(A(1),X(1))和(A(2),X(2))中的表示相近,與全局負(fù)樣本表示n相遠(yuǎn)來(lái)實(shí)現(xiàn),其形式化如式(6)所示。

(6)

(7)

如果我們將左側(cè)的分式子視為權(quán)重,即

(8)

那么,全局負(fù)樣本更新的梯度可以視為對(duì)圖上所有節(jié)點(diǎn)表示的線性組合,其形式化如式(9)所示。

(9)

由上述公式可知,我們的全局負(fù)樣本是沿圖上所有節(jié)點(diǎn)表示加權(quán)平均的方向更新。其中每個(gè)節(jié)點(diǎn)的權(quán)重wi由其與當(dāng)前全局負(fù)樣本的相似度和其與正樣本的相似度一同決定的。換句話說(shuō),一個(gè)節(jié)點(diǎn)表示與當(dāng)前全局負(fù)樣本的相似度相比于該節(jié)點(diǎn)與對(duì)應(yīng)正樣本的相似度越大,則它對(duì)更新全局負(fù)樣本的貢獻(xiàn)就越大。即那些難以將全局負(fù)樣本與其正樣本區(qū)分開(kāi)的節(jié)點(diǎn),對(duì)與全局負(fù)樣本的更新貢獻(xiàn)更大。按此方式更新后的全局對(duì)抗樣本對(duì)于模型更具有挑戰(zhàn)性,因?yàn)閷?duì)于每個(gè)節(jié)點(diǎn)都難將其與正樣本區(qū)分開(kāi)。將該全局負(fù)樣本用于圖編碼器的參數(shù)更新,可以進(jìn)一步提升圖編碼器的質(zhì)量,得到在下游任務(wù)表現(xiàn)更好的節(jié)點(diǎn)表示。

2.3 時(shí)間復(fù)雜度對(duì)比

本節(jié)分析了我們的模型和基于圖對(duì)比學(xué)習(xí)的基準(zhǔn)方法GRACE和GraphCL的時(shí)間復(fù)雜度。

首先所有模型都采用了相同的數(shù)據(jù)增強(qiáng)方式,連邊去除和特征掩藏,其時(shí)間復(fù)雜度為O(E+F)。此外所有模型的編碼器采用了相同的結(jié)構(gòu),即圖卷積神經(jīng)網(wǎng)絡(luò)[14],其時(shí)間復(fù)雜度為O(lEF+lNF2)。其中,l表示圖卷積神經(jīng)網(wǎng)絡(luò)的層數(shù),E表示圖上的連邊數(shù),N表示節(jié)點(diǎn)數(shù),F表示特征維度,我們假設(shè)每層輸出的表示維度不變。

下面介紹各方法損失函數(shù)的時(shí)間復(fù)雜度。GRACE[3]對(duì)于每個(gè)節(jié)點(diǎn)將圖上剩下所有節(jié)點(diǎn)視為負(fù)樣本,因此在計(jì)算損失函數(shù)時(shí)依賴于所有節(jié)點(diǎn)對(duì),其時(shí)間復(fù)雜度為O(N2)。若GRACE采樣K個(gè)負(fù)樣本,則其時(shí)間復(fù)雜度降低為O(KN),我們將該模型記做GRACE(K)。然而在實(shí)驗(yàn)中發(fā)現(xiàn),隨著負(fù)樣本數(shù)K減少,GRACE(K)效果顯著下降。GraphCL[11]對(duì)于每個(gè)點(diǎn)選擇最相似的K個(gè)負(fù)樣本,因此其損失函數(shù)時(shí)間復(fù)雜度為O(KN)。然而對(duì)于每個(gè)點(diǎn)挑選其對(duì)應(yīng)K個(gè)負(fù)樣本的過(guò)程中,依賴于對(duì)剩下所有點(diǎn)計(jì)算相似度,同時(shí)對(duì)結(jié)果進(jìn)行排序,因此其時(shí)間復(fù)雜度為O(N+NlogN)。圖上共有N個(gè)節(jié)點(diǎn),因此GraphCL損失函數(shù)總時(shí)間復(fù)雜度為O(KN+N2+NlogN2)。我們的ANGCL只有一個(gè)負(fù)樣本,因此其損失函數(shù)時(shí)間復(fù)雜度為O(2N)。雖然我們引入了額外的更新對(duì)抗負(fù)樣本的時(shí)間復(fù)雜度,但是由于每輪迭代更新的梯度為所有節(jié)點(diǎn)表示的線性組合,即這部分的時(shí)間復(fù)雜度為O(N)。所有方法的時(shí)間復(fù)雜度總結(jié)如表1所示。我們發(fā)現(xiàn)我們方法的時(shí)間復(fù)雜度與采樣版的圖對(duì)比學(xué)習(xí)方法GRACE(K)相當(dāng),且低于其它方法。

表1 方法時(shí)間復(fù)雜度對(duì)比

2.4 模型分析

根據(jù)2.2.3節(jié)我們可以得到全局負(fù)樣本的更新方式,本節(jié)將分析該負(fù)樣本對(duì)模型的意義。

(10)

其中,C是常數(shù)項(xiàng)。我們發(fā)現(xiàn)最小化該損失函數(shù)等價(jià)于最大化圖上所有節(jié)點(diǎn)對(duì)之間的加權(quán)距離。

定理1:L′(θ)是所有節(jié)點(diǎn)對(duì)之間的加權(quán)距離和的上界。

證明:

根據(jù)定理1,可以得出最小化與我們的全局負(fù)樣本的對(duì)比損失函數(shù)等價(jià)于最大化所有節(jié)點(diǎn)對(duì)之間的加權(quán)距離,其權(quán)重為節(jié)點(diǎn)參與更新全局負(fù)樣本梯度的權(quán)重。即如果兩個(gè)點(diǎn)都很靠近當(dāng)前的全局負(fù)樣本,則會(huì)給這兩個(gè)點(diǎn)較大的權(quán)重,從而讓模型更關(guān)注于將這兩個(gè)節(jié)點(diǎn)推開(kāi)。

同時(shí),我們發(fā)現(xiàn)該損失函數(shù)與節(jié)點(diǎn)分布的均勻性之間存在關(guān)聯(lián)。均勻性是指學(xué)到的節(jié)點(diǎn)表示均勻分布在球面上,從而保留最大的信息量。均勻性的形式化度量如式(11)所示。

(11)

該式子要求任意兩個(gè)節(jié)點(diǎn)表示之間盡可能分開(kāi),且任意節(jié)點(diǎn)之間的重要性相同。一些研究者指出,傳統(tǒng)圖對(duì)比學(xué)習(xí)方法[27-28],通過(guò)推遠(yuǎn)與所有負(fù)樣本之間的距離實(shí)現(xiàn)了均勻性[29]。這類傳統(tǒng)的圖對(duì)比學(xué)習(xí)方法將所有節(jié)點(diǎn)視為同等重要,而我們的模型相當(dāng)于實(shí)現(xiàn)了加權(quán)的均勻性。同時(shí)當(dāng)所有的權(quán)重wi=1時(shí),我們的模型退化成了傳統(tǒng)的圖對(duì)比學(xué)習(xí)方法。

3 實(shí)驗(yàn)

本節(jié)我們對(duì)提出的ANGCL模型進(jìn)行實(shí)驗(yàn),并將其與現(xiàn)有的無(wú)監(jiān)督表示學(xué)習(xí)方法在節(jié)點(diǎn)分類任務(wù)上進(jìn)行比較。最后,我們進(jìn)一步深入探討、分析了模型的有效性。

3.1 實(shí)驗(yàn)細(xì)節(jié)設(shè)置

本節(jié)首先介紹數(shù)據(jù)集、基準(zhǔn)方法以及實(shí)驗(yàn)的基本設(shè)置。

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

本文使用7個(gè)廣泛使用的具有節(jié)點(diǎn)分類任務(wù)的基準(zhǔn)數(shù)據(jù)集的基線[3,30]。Cora、Citeseer、Pubmed是三個(gè)引用網(wǎng)絡(luò),其中每個(gè)節(jié)點(diǎn)表示一篇論文,每條邊表示一個(gè)引用關(guān)系。Amazon Computers(Am.C)、Amazon Photos(Am.P)是從亞馬遜共同購(gòu)買圖中提取的,其中節(jié)點(diǎn)代表產(chǎn)品,邊代表經(jīng)常一起購(gòu)買的成對(duì)商品。Coauthor CS(Co.CS)、Coauthor Physics(Co.Phy)是共同創(chuàng)作的圖表,其中節(jié)點(diǎn)代表作者,而作者之間的邊則代表共同撰寫的論文。上述數(shù)據(jù)集的統(tǒng)計(jì)信息如表2所示,其中類別數(shù)表示圖上所有不同標(biāo)簽的數(shù)量,且每個(gè)節(jié)點(diǎn)只有一個(gè)標(biāo)簽。該標(biāo)簽用于構(gòu)建下游節(jié)點(diǎn)分類任務(wù)。

表2 數(shù)據(jù)集統(tǒng)計(jì)信息

3.1.2 基準(zhǔn)方法介紹

文本的基準(zhǔn)方法包含傳統(tǒng)的網(wǎng)絡(luò)表示學(xué)習(xí)方法和基于圖對(duì)比學(xué)習(xí)的方法兩類。對(duì)于傳統(tǒng)的網(wǎng)絡(luò)表示學(xué)習(xí)方法,我們選擇了最受關(guān)注的Deepwalk(DW)[31]方法。同時(shí)將節(jié)點(diǎn)屬性和Deepwalk得到的表示拼接作為同時(shí)刻畫(huà)結(jié)構(gòu)和屬性的基準(zhǔn)方法,記作DW+F。對(duì)于圖對(duì)比學(xué)習(xí)方法,我們選擇了利用隨機(jī)采樣負(fù)樣本的方法DGI和GRACE[3]。以及利用相似度選取難負(fù)樣本的方法GraphCL[11]。對(duì)于每個(gè)節(jié)點(diǎn),GraphCL只使用與其相似度最高的20個(gè)節(jié)點(diǎn)作為負(fù)樣本。對(duì)于基于圖對(duì)比學(xué)習(xí)的方法GRACE,GraphCL,DGI[19],我們?cè)O(shè)定其迭代輪數(shù)為500。

3.1.3 模型設(shè)置

我們利用Tensorflow2.3實(shí)現(xiàn)模型。模型參數(shù)通過(guò)Glorot算法進(jìn)行初始化,并且利用Adam優(yōu)化器最小化對(duì)比損失函數(shù)L(θ,n)進(jìn)行優(yōu)化,學(xué)習(xí)率為0.001,并且設(shè)定迭代輪數(shù)為300。對(duì)于控制超參數(shù)τ的選擇范圍是{0.05, 0.1, 0.5, 1.0}。對(duì)于Dropout概率,隨機(jī)丟邊的概率,隨機(jī)刪除節(jié)點(diǎn)屬性的概率的選擇范圍都為{0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9},最優(yōu)的τ=0.1,Dropout=0.6。

3.1.4 下游任務(wù)設(shè)置

我們?cè)跓o(wú)監(jiān)督范式下訓(xùn)練我們的模型和基準(zhǔn)方法,并利用節(jié)點(diǎn)表示在下游任務(wù)上的表現(xiàn)來(lái)評(píng)價(jià)[2-5,32]。本文將節(jié)點(diǎn)分類任務(wù)作為下游任務(wù),其具體流程如下。我們將學(xué)到的節(jié)點(diǎn)表示作為輸入,根據(jù)數(shù)據(jù)劃分,利用訓(xùn)練集中的節(jié)點(diǎn)表示訓(xùn)練線性分類器。同時(shí)利用驗(yàn)證集調(diào)整超參數(shù),利用測(cè)試集評(píng)價(jià)模型。

我們使用常用的線性支撐向量機(jī)(SVM)來(lái)作為下游節(jié)點(diǎn)分類任務(wù)的分類器[3,11]。對(duì)于 Cora、Citeseer和 Pubmed,我們遵循之前論文中的固定劃分,構(gòu)建下游任務(wù)缺乏標(biāo)簽數(shù)據(jù)的情況,即每類只有30個(gè)訓(xùn)練標(biāo)簽。對(duì)于其余四個(gè)數(shù)據(jù)集,我們將節(jié)點(diǎn)隨機(jī)拆分為訓(xùn)練/驗(yàn)證/測(cè)試集,其比例為(80%/10%/10%)。對(duì)于所有實(shí)驗(yàn),我們重復(fù)10次,并展示了平均結(jié)果和方差。

3.2 節(jié)點(diǎn)分類實(shí)驗(yàn)

節(jié)點(diǎn)分類任務(wù)的結(jié)果如表3所示,其中最優(yōu)值加粗展示,次優(yōu)解用下劃線展示,OOM表示超過(guò)GPU內(nèi)存限制,本文使用的是32G內(nèi)存的V100顯卡,是當(dāng)前最被廣泛使用的先進(jìn)顯卡。從表3中,可以發(fā)現(xiàn)基于圖對(duì)比學(xué)習(xí)的方法優(yōu)于傳統(tǒng)的圖表示學(xué)習(xí)方法。由于較高的空間復(fù)雜度,GraphCL在較大的數(shù)據(jù)集上會(huì)超過(guò)內(nèi)存限制,導(dǎo)致無(wú)法成功運(yùn)行,說(shuō)明基于余弦相似度篩選負(fù)樣本的的方法難以適用于大規(guī)模的網(wǎng)絡(luò)。

表3 節(jié)點(diǎn)分類準(zhǔn)確率 (單位: %)

我們發(fā)現(xiàn)ANGCL方法優(yōu)于除了GraphCL的所有基準(zhǔn)方法。該結(jié)果說(shuō)明相比于基于全局、隨機(jī)負(fù)樣本的GRACE方法,我們的ANGCL模型通過(guò)對(duì)抗訓(xùn)練的方式找到了對(duì)于模型難的負(fù)樣本,從而提升了節(jié)點(diǎn)表示的質(zhì)量,使其在下游任務(wù)中表現(xiàn)更好。同時(shí)我們也觀察到針對(duì)每個(gè)節(jié)點(diǎn)選擇合適負(fù)樣本的方法GraphCL在結(jié)果上優(yōu)于我們的ANGCL。這是由于ANGCL是全局共享了負(fù)樣本,沒(méi)有為每個(gè)節(jié)點(diǎn)自適應(yīng)的選擇合適的負(fù)樣本。但通過(guò)全局共享負(fù)樣本,使我們的模型在計(jì)算代價(jià)上明顯低于GraphCL。

3.3 效率對(duì)比實(shí)驗(yàn)

在本節(jié)中,我們比較了不同方法在Cora數(shù)據(jù)集上迭代一輪需要消耗的時(shí)間,以及模型訓(xùn)練總耗時(shí)。同時(shí)展示了各個(gè)方法在節(jié)點(diǎn)分類任務(wù)上準(zhǔn)確率。所有結(jié)果如表4所示,其中2 708為Cora數(shù)據(jù)集的節(jié)點(diǎn)數(shù),即GRACE方法將圖上所有節(jié)點(diǎn)都視為負(fù)樣本。我們發(fā)現(xiàn)ANGCL運(yùn)行的時(shí)間少于GRACE同時(shí)也取得了更好的節(jié)點(diǎn)分類效果。雖然ANGCL在得到全局負(fù)樣本時(shí),引入了額外的計(jì)算,但是其整體的時(shí)間消耗仍然低于利用所有負(fù)樣本的圖對(duì)比學(xué)習(xí)方法。

表4 模型運(yùn)行時(shí)間對(duì)比

同時(shí)我們觀察到雖然GraphCL取得了最優(yōu)的效果,但時(shí)間消耗明顯高于其他的方法。因?yàn)樵摲椒ㄔ跒槊總€(gè)節(jié)點(diǎn)篩選其對(duì)應(yīng)K個(gè)最難的負(fù)樣本時(shí),需要與圖上剩余所有節(jié)點(diǎn)計(jì)算相似度,并排序,從而引入了高昂的時(shí)間代價(jià)。當(dāng)數(shù)據(jù)規(guī)模較大時(shí),這種高昂的時(shí)間代價(jià)是不可忍受的。而我們的ANGCL在并沒(méi)有降低很多效果的情況下,明顯提升了模型的速度。

3.4 節(jié)點(diǎn)表示分布度量

本節(jié)我們對(duì)比了ANGCL和傳統(tǒng)圖對(duì)比學(xué)習(xí)方法GRACE學(xué)到的節(jié)點(diǎn)表示分布之間的差異。我們比較了不同方法學(xué)到的節(jié)點(diǎn)表示,在下游任務(wù)標(biāo)簽下,類內(nèi)節(jié)點(diǎn)間的平均距離和類間節(jié)點(diǎn)間的平均距離。其結(jié)果如表5所示。

表5 節(jié)點(diǎn)表示在下游任務(wù)中的類內(nèi)與類間距離度量

我們發(fā)現(xiàn)相比于原始的節(jié)點(diǎn)屬性,圖對(duì)比學(xué)習(xí)方法都增加了類內(nèi)距離和類間距離之間的差距。該結(jié)果反映了這類方法能取得較好節(jié)點(diǎn)分類結(jié)果的原因。同時(shí)我們發(fā)現(xiàn),ANGCL模型相對(duì)于GRACE,又進(jìn)一步提升了兩者距離之間的差異。該結(jié)果表明全局負(fù)樣本的有效性。但同時(shí)我們基于全局共享負(fù)樣本的方法ANGCL在效果上弱于針對(duì)每個(gè)樣本選擇合適負(fù)樣本的方法GraphCL。

3.5 模型超參數(shù)分析

本節(jié)我們分別分析超參數(shù)邊移除概率pe、特征移除概率pf以及τ對(duì)模型的影響,其結(jié)果分別如圖3(a)、圖3(b)、圖3(c)所示。我們發(fā)現(xiàn)pe、pf值對(duì)模型效果影響不大,但是隨著概率增大,結(jié)果的方差增大。這可能是由于超參數(shù)邊移除概率pe、特征移除概率pf過(guò)大每次迭代中得到的增強(qiáng)圖差異比較大導(dǎo)致。此外我們發(fā)現(xiàn)隨著τ增大模型效果有下降,這是由于τ變大,縮小了表示相似度之間的差異,使得正樣本和負(fù)樣本間的差異變小,導(dǎo)致效果下降。

圖3 Cora數(shù)據(jù)集上模型超參數(shù)對(duì)分類準(zhǔn)確率的影響

4 總結(jié)

本文提出了基于對(duì)抗負(fù)樣本的圖對(duì)比學(xué)習(xí)模型,該模型利用對(duì)抗學(xué)習(xí)的框架,讓模型自動(dòng)學(xué)習(xí)需要的難負(fù)樣本。ANGCL通過(guò)全局共享該負(fù)樣本,減少了每個(gè)節(jié)點(diǎn)需要比較的負(fù)樣本個(gè)數(shù),大幅降低了模型的時(shí)間復(fù)雜度。同時(shí)通過(guò)對(duì)抗學(xué)習(xí)框架,使得每輪得到的負(fù)樣本從梯度角度都是對(duì)于模型較難的,從而保證模型的效果。本文通過(guò)大量的實(shí)驗(yàn),驗(yàn)證了模型的有效性。