基于全局對抗負樣本的圖對比學習方法

岑科廷,沈華偉,曹 婍,徐冰冰,程學旗

(1.中國科學院 計算技術研究所 數據智能系統研究中心,北京 100190;2.中國科學院大學,北京 101408;3. 中國科學院 計算技術研究所 網絡數據科學與技術重點實驗室,北京 100190)

0 引言

圖表示學習期望給每個節點學到保留圖結構和節點屬性的低維表示[1]。這類方法在很多重要的圖分析任務上取得了顯著的成果,例如,節點分類[1]、鏈路預測等[2]。最近,基于圖對比學習的節點表示學習方法展現了前所未有的性能[3-5],正在成為該領域的主流方法。

圖對比學習期望通過拉近正樣本對之間的距離,推遠負樣本之間的距離來為每個節點學習表示[6-8]。傳統的圖對比學習方法將同一個節點經過兩種不同數據增強后得到的節點視為正樣本對,將其與圖上其它節點都視為負樣本對[3](圖1(a))。由于每個節點都將其余節點視為負樣本,因此這類方法的時間復雜度是關于節點數的平方,導致此類方法難以被應用到實際場景中。

圖1 負樣本選擇方式對比

為了降低時間復雜度,一種直觀的方式是給每個節點選擇一些節點作為負樣本。具體來說研究者們試圖通過隨機采樣特定個負樣本的方式加速模型[9](圖1(b))。該方法將所有負樣本視為同等重要,并通過均勻采樣的方式為每個節點生成對應的負樣本。然而,該方法已經被證實需要大量的負樣本才能使模型達到較好的效果[10]。

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

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

此外,本文進一步對提出的方法進行了深入分析,發現更新全局負樣本的梯度為圖中所有節點表示的加權線性組合。同時證明,最小化與該全局負樣本的對比損失函數等價于最大化圖上節點之間的加權平均距離。多個基準數據集上充分的實驗結果證明了我們模型的有效性和效率。

1 相關工作

1.1 傳統圖表示學習

圖表示學習旨在為每個節點學習一個保留網絡結構性質或者節點屬性的低維節點表示。 以前的方法通常通過解決一個預定義任務來學習節點表示[13]。 大多數傳統的網絡嵌入方法采用結構重建[14-15]或屬性預測[16-17]作為預定義任務。

結構重構任務期望利用節點表表示H恢復某些結構相關的矩陣,例如,鄰接矩陣A[14]。GAE[14]利用圖卷積神經網絡將節點的結構和屬性映射到隱層表示空間,同時利用節點vi和vj表示的點積來重構他們之間的連邊概率A′ij。GAE通過約束重構的鄰接矩陣A′盡可能和輸入的鄰接矩陣A保持一致來訓練模型。

基于屬性重構的網絡表示學習方法,將利用節點表示H重構輸入屬性矩陣X作為目標訓練模型[16-17]。例如,ANRL[17]將節點的鄰接矩陣A作為輸入,經過多層自編碼器后輸出預測的節點屬性矩陣X′,通過約束輸出屬性矩陣X′盡可能接近輸入屬性X來訓練表示學習模型。

1.2 圖對比學習

最近,圖對比學習已成為無監督圖表示學習中最受關注的一種技術。圖對比學習期望學到一個表示學習模型,使得相似的節點(正樣本)得到相似的表示,不相似的節點(負樣本)得到差異較大的表示[3-8,18]。

傳統的圖對比學習將所有負樣本視為同等重要,其不同點在于對正樣本的定義。例如,GRACE[3]將同一節點的不同增強版本定義為正樣本對,而將圖上剩下其它所有節點都當成負樣本。DGI[19]將圖表示和圖上節點表示視為正樣本對,將圖表示和隨機打亂后圖上節點表示視為負樣本對。

最近一些方法通過啟發式的方式來定義重要的負樣本,從而提升圖對比學習的效果。例如,Yang等人[9]認為節點的度反映其作為負樣本的重要性,因此該方法提出負樣本的采樣概率與其度成正比,即度越大的節點越重要。GraphCL[10]定義負樣本節點與目標節點的余弦相似度為其重要性,對于每個節點利用余弦相似度挑選最像的K個節點作為負樣本。Kalantidis等人[20]提出利用得到的負樣本進行線性混合,生成更難的負樣本。

此外,近些年圖對比學習在可解釋性和數據增強方式上也有新的進展。DGCL[21]利用解耦表示提升了圖對比學習的可解釋性。ARIEL[22]利用對抗訓練的方式生成增強樣本。

2 模型

本節首先回顧傳統圖對比學習,分析它的局限性,并介紹我們工作的動機。之后詳細介紹我們模型的框架,以及如何更新模型的參數和我們的全局負樣本。最后,通過分析更新全局負樣本的梯度,更好地揭示了模型背后的含義。

2.1 動機

(1)

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

2.2 基于全局對抗負樣本圖對比學習

本節形式化地介紹基于全局對抗負樣本圖對比學習的節點表示學習方法ANGCL。

2.2.1 模型框架

如圖2所示,我們的ANGCL模型包含兩個對抗性參與者: 圖編碼器θ和可學習的全局負樣本n。圖編碼器旨在通過最小化對比損失來學習將正樣本與負樣本區分開來的節點表示。而全局負樣本n則是指最容易讓模型做錯的負樣本,即最大化對比損失的負樣本。我們將求解圖編碼器θ和對抗負樣本n的過程抽象成最大最小化問題,其形式化如式(2)所示。

圖2 ANGCL模型框架圖

(2)

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

其中,ηθ和ηn分別是更新圖編碼器θ和全局負樣本n的學習率。下文將詳細介紹圖編碼器的實現,以及全局負樣本更新的具體形式及其意義。

2.2.2 圖編碼器實現

如圖2所示,對于一張圖我們首先通過數據增強函數t1和t2,分別生成對應的增強圖(A(1),X(1))和(A(2),X(2)),之后通過圖編碼器θ得到對應的節點表示。

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

(5)

2.2.3 負樣本更新

首先,我們給出模型對比損失函數的定義。與之前的方法不同,ANGCL通過約束同一節點在不同增強圖(A(1),X(1))和(A(2),X(2))中的表示相近,與全局負樣本表示n相遠來實現,其形式化如式(6)所示。

(6)

(7)

如果我們將左側的分式子視為權重,即

(8)

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

(9)

由上述公式可知,我們的全局負樣本是沿圖上所有節點表示加權平均的方向更新。其中每個節點的權重wi由其與當前全局負樣本的相似度和其與正樣本的相似度一同決定的。換句話說,一個節點表示與當前全局負樣本的相似度相比于該節點與對應正樣本的相似度越大,則它對更新全局負樣本的貢獻就越大。即那些難以將全局負樣本與其正樣本區分開的節點,對與全局負樣本的更新貢獻更大。按此方式更新后的全局對抗樣本對于模型更具有挑戰性,因為對于每個節點都難將其與正樣本區分開。將該全局負樣本用于圖編碼器的參數更新,可以進一步提升圖編碼器的質量,得到在下游任務表現更好的節點表示。

2.3 時間復雜度對比

本節分析了我們的模型和基于圖對比學習的基準方法GRACE和GraphCL的時間復雜度。

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

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

表1 方法時間復雜度對比

2.4 模型分析

根據2.2.3節我們可以得到全局負樣本的更新方式,本節將分析該負樣本對模型的意義。

(10)

其中,C是常數項。我們發現最小化該損失函數等價于最大化圖上所有節點對之間的加權距離。

定理1:L′(θ)是所有節點對之間的加權距離和的上界。

證明:

根據定理1,可以得出最小化與我們的全局負樣本的對比損失函數等價于最大化所有節點對之間的加權距離,其權重為節點參與更新全局負樣本梯度的權重。即如果兩個點都很靠近當前的全局負樣本,則會給這兩個點較大的權重,從而讓模型更關注于將這兩個節點推開。

同時,我們發現該損失函數與節點分布的均勻性之間存在關聯。均勻性是指學到的節點表示均勻分布在球面上,從而保留最大的信息量。均勻性的形式化度量如式(11)所示。

(11)

該式子要求任意兩個節點表示之間盡可能分開,且任意節點之間的重要性相同。一些研究者指出,傳統圖對比學習方法[27-28],通過推遠與所有負樣本之間的距離實現了均勻性[29]。這類傳統的圖對比學習方法將所有節點視為同等重要,而我們的模型相當于實現了加權的均勻性。同時當所有的權重wi=1時,我們的模型退化成了傳統的圖對比學習方法。

3 實驗

本節我們對提出的ANGCL模型進行實驗,并將其與現有的無監督表示學習方法在節點分類任務上進行比較。最后,我們進一步深入探討、分析了模型的有效性。

3.1 實驗細節設置

本節首先介紹數據集、基準方法以及實驗的基本設置。

3.1.1 數據集

本文使用7個廣泛使用的具有節點分類任務的基準數據集的基線[3,30]。Cora、Citeseer、Pubmed是三個引用網絡,其中每個節點表示一篇論文,每條邊表示一個引用關系。Amazon Computers(Am.C)、Amazon Photos(Am.P)是從亞馬遜共同購買圖中提取的,其中節點代表產品,邊代表經常一起購買的成對商品。Coauthor CS(Co.CS)、Coauthor Physics(Co.Phy)是共同創作的圖表,其中節點代表作者,而作者之間的邊則代表共同撰寫的論文。上述數據集的統計信息如表2所示,其中類別數表示圖上所有不同標簽的數量,且每個節點只有一個標簽。該標簽用于構建下游節點分類任務。

表2 數據集統計信息

3.1.2 基準方法介紹

文本的基準方法包含傳統的網絡表示學習方法和基于圖對比學習的方法兩類。對于傳統的網絡表示學習方法,我們選擇了最受關注的Deepwalk(DW)[31]方法。同時將節點屬性和Deepwalk得到的表示拼接作為同時刻畫結構和屬性的基準方法,記作DW+F。對于圖對比學習方法,我們選擇了利用隨機采樣負樣本的方法DGI和GRACE[3]。以及利用相似度選取難負樣本的方法GraphCL[11]。對于每個節點,GraphCL只使用與其相似度最高的20個節點作為負樣本。對于基于圖對比學習的方法GRACE,GraphCL,DGI[19],我們設定其迭代輪數為500。

3.1.3 模型設置

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

3.1.4 下游任務設置

我們在無監督范式下訓練我們的模型和基準方法,并利用節點表示在下游任務上的表現來評價[2-5,32]。本文將節點分類任務作為下游任務,其具體流程如下。我們將學到的節點表示作為輸入,根據數據劃分,利用訓練集中的節點表示訓練線性分類器。同時利用驗證集調整超參數,利用測試集評價模型。

我們使用常用的線性支撐向量機(SVM)來作為下游節點分類任務的分類器[3,11]。對于 Cora、Citeseer和 Pubmed,我們遵循之前論文中的固定劃分,構建下游任務缺乏標簽數據的情況,即每類只有30個訓練標簽。對于其余四個數據集,我們將節點隨機拆分為訓練/驗證/測試集,其比例為(80%/10%/10%)。對于所有實驗,我們重復10次,并展示了平均結果和方差。

3.2 節點分類實驗

節點分類任務的結果如表3所示,其中最優值加粗展示,次優解用下劃線展示,OOM表示超過GPU內存限制,本文使用的是32G內存的V100顯卡,是當前最被廣泛使用的先進顯卡。從表3中,可以發現基于圖對比學習的方法優于傳統的圖表示學習方法。由于較高的空間復雜度,GraphCL在較大的數據集上會超過內存限制,導致無法成功運行,說明基于余弦相似度篩選負樣本的的方法難以適用于大規模的網絡。

表3 節點分類準確率 (單位: %)

我們發現ANGCL方法優于除了GraphCL的所有基準方法。該結果說明相比于基于全局、隨機負樣本的GRACE方法,我們的ANGCL模型通過對抗訓練的方式找到了對于模型難的負樣本,從而提升了節點表示的質量,使其在下游任務中表現更好。同時我們也觀察到針對每個節點選擇合適負樣本的方法GraphCL在結果上優于我們的ANGCL。這是由于ANGCL是全局共享了負樣本,沒有為每個節點自適應的選擇合適的負樣本。但通過全局共享負樣本,使我們的模型在計算代價上明顯低于GraphCL。

3.3 效率對比實驗

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

表4 模型運行時間對比

同時我們觀察到雖然GraphCL取得了最優的效果,但時間消耗明顯高于其他的方法。因為該方法在為每個節點篩選其對應K個最難的負樣本時,需要與圖上剩余所有節點計算相似度,并排序,從而引入了高昂的時間代價。當數據規模較大時,這種高昂的時間代價是不可忍受的。而我們的ANGCL在并沒有降低很多效果的情況下,明顯提升了模型的速度。

3.4 節點表示分布度量

本節我們對比了ANGCL和傳統圖對比學習方法GRACE學到的節點表示分布之間的差異。我們比較了不同方法學到的節點表示,在下游任務標簽下,類內節點間的平均距離和類間節點間的平均距離。其結果如表5所示。

表5 節點表示在下游任務中的類內與類間距離度量

我們發現相比于原始的節點屬性,圖對比學習方法都增加了類內距離和類間距離之間的差距。該結果反映了這類方法能取得較好節點分類結果的原因。同時我們發現,ANGCL模型相對于GRACE,又進一步提升了兩者距離之間的差異。該結果表明全局負樣本的有效性。但同時我們基于全局共享負樣本的方法ANGCL在效果上弱于針對每個樣本選擇合適負樣本的方法GraphCL。

3.5 模型超參數分析

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

圖3 Cora數據集上模型超參數對分類準確率的影響

4 總結

本文提出了基于對抗負樣本的圖對比學習模型,該模型利用對抗學習的框架,讓模型自動學習需要的難負樣本。ANGCL通過全局共享該負樣本,減少了每個節點需要比較的負樣本個數,大幅降低了模型的時間復雜度。同時通過對抗學習框架,使得每輪得到的負樣本從梯度角度都是對于模型較難的,從而保證模型的效果。本文通過大量的實驗,驗證了模型的有效性。