主要貢獻(xiàn)

文本提出了一個全新的隨機(jī)Dropping方法，該方法在消息傳遞的過程中直接對被傳遞的消息進(jìn)行dropping操作，統(tǒng)一了圖神經(jīng)網(wǎng)絡(luò)的隨機(jī)dropping架構(gòu)。

第一章 摘要

圖神經(jīng)網(wǎng)絡(luò)是圖表示學(xué)習(xí)的重要工具。但盡管圖神經(jīng)網(wǎng)絡(luò)的研究發(fā)展迅速，我們依然面臨著很多挑戰(zhàn)，例如：過擬合、過平滑和低魯棒性這些問題。以前的工作表明這些問題可以通過隨機(jī)droppping方法得到緩解，即通過隨機(jī)遮掩掉部分輸入來將增強(qiáng)數(shù)據(jù)喂給模型。然而，在圖神經(jīng)網(wǎng)絡(luò)上應(yīng)用隨機(jī)dropping方法仍有很多問題待被解決。首先，考慮到不同數(shù)據(jù)集和模型的差異，找到一種適用于所有情況的通用方法是很困難的。其次，在圖神經(jīng)網(wǎng)絡(luò)中引入增強(qiáng)數(shù)據(jù)會導(dǎo)致參數(shù)覆蓋不完全和訓(xùn)練過程不穩(wěn)定的現(xiàn)象。第三，現(xiàn)今沒有在理論層面上分析隨機(jī)dropping方法在圖神經(jīng)網(wǎng)絡(luò)上的有效性。

在本文，我們提出了一個全新的隨機(jī)droppping方法——DropMessage，該方法在消息傳遞過程中直接對被傳遞的消息進(jìn)行dropping操作。更重要的是，我們發(fā)現(xiàn)DropMessage為大多數(shù)現(xiàn)有的隨機(jī)dropping方法提供了一個統(tǒng)一的框架，并在此基礎(chǔ)上我們還對其有效性進(jìn)行了理論分析，以進(jìn)一步闡述了DropMessage的優(yōu)越性:它通過減小樣本方差來穩(wěn)定訓(xùn)練過程;從信息論的角度來看，它保持了信息的多樣性，這使其成為其他方法的理論上限。為了評估所提出的DropMessage方法，我們在五個公共數(shù)據(jù)集和兩個工業(yè)數(shù)據(jù)集上進(jìn)行了多個任務(wù)的實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明：DropMessage有效性且泛化性強(qiáng)，能夠顯著緩解上述提到的問題。

第二章 簡介及背景

圖在現(xiàn)實(shí)世界里面無處不在，被用于在許多領(lǐng)域中呈現(xiàn)各種事物之間的復(fù)雜關(guān)系，圖神經(jīng)網(wǎng)絡(luò)更是研究圖表示學(xué)習(xí)的重要工具。圖神經(jīng)網(wǎng)絡(luò)使用信息傳遞的方法并可以應(yīng)用到大量的下游任務(wù)中。其中消息傳遞就是圖神經(jīng)網(wǎng)絡(luò)在每個卷積層中的各個節(jié)點(diǎn)都會聚合其鄰居信息的行為。

但是圖神經(jīng)網(wǎng)絡(luò)的訓(xùn)練面臨著很多挑戰(zhàn)。因?yàn)榕c其他數(shù)據(jù)形式相比，為圖數(shù)據(jù)收集標(biāo)簽是昂貴的并且會有必然的偏差，這限制了圖神經(jīng)網(wǎng)絡(luò)的泛化能力。此外，由于遞歸地聚合來自其鄰居的信息，圖神經(jīng)網(wǎng)絡(luò)中不同節(jié)點(diǎn)的表示往往變得越來越相似。

使用隨機(jī)dropping方法可以緩解上述問題，但是摘要中所提到的三大問題依然存在著。在本文，我們提出的全新的隨機(jī)Dropping方法DropMessage可以有效解決這些問題。

第三章 數(shù)學(xué)符號和預(yù)備知識

第一節(jié) 符號

1． 表示圖

2. ={}表示圖中的節(jié)點(diǎn)

3． 表示邊

4． 結(jié)點(diǎn)特征表示為矩陣，其中是結(jié)點(diǎn)的特征向量，是結(jié)點(diǎn)特征的維數(shù)

5． 鄰接矩陣表示為 ，其中表示鄰接矩陣的第行，表示結(jié)點(diǎn)和之間的關(guān)系

6． 結(jié)點(diǎn)的度表示為 ，其中表示為連接到結(jié)點(diǎn)的度權(quán)重之和 7． 信息傳遞矩陣表示為,其中是消息的維數(shù)

第二節(jié) 消息傳遞的圖神經(jīng)網(wǎng)絡(luò)

圖神經(jīng)網(wǎng)絡(luò)大多采用信息傳遞框架，消息在結(jié)點(diǎn)及其鄰居之間傳遞。在傳遞的過程中，結(jié)點(diǎn)的表示不斷更新，下面是它的更新公式： 其中表示結(jié)點(diǎn)在第 1 層的特征表示；表示結(jié)點(diǎn)的鄰居; 和是可微分的函數(shù)；AGG代表聚合操作。從信息傳遞的角度來看，我們可以將所有傳播的消息集合到一個消息矩陣中，其表示為：

第四章 方法

第一節(jié)DropMessage第一小節(jié) 算法描述

不同于現(xiàn)有的隨機(jī)dropping方法，DropMessage在消息矩陣上工作而不是鄰接矩陣，即DropMessage直接在消息矩陣M上以概率執(zhí)行drop操作。具體來說，我們會根據(jù)伯努利分布生成一個和消息矩陣同大小的掩碼矩陣，消息矩陣中的每個元素由對應(yīng)位置的掩碼矩陣中的值來決定以多大的程度被drop，drop之后的消息矩陣表示為：

第二小節(jié) 具體實(shí)現(xiàn)

在具體實(shí)現(xiàn)的過程中，我們不需要額外的時間或空間復(fù)雜度來執(zhí)行DropMessage，因?yàn)橄⒕仃囍械拿恳恍卸急硎緢D中的一條不同的有向邊，并且DropMessage方法可以獨(dú)立地在每個有向邊上執(zhí)行。這個特性使得DropMessage可以有效地并行化。

第三小節(jié) 統(tǒng)一隨機(jī)dropping方法

引理1 Dropout DropEdge DropNode DropMessage都依據(jù)著各自的規(guī)則在消息矩陣上執(zhí)行隨機(jī)掩碼對于Dropout方法，Dropping在特征矩陣中的元素等價于遮掩掉消息矩陣中的元素，其中表示所對應(yīng)的特征矩陣中的那個元素。

對于DropEdge方法，Dropping在鄰接矩陣中的元素等價于遮掩掉消息矩陣中元素，其中表示所對應(yīng)的邊。

對于DropNode方法，Dropping在特征矩陣X中的元素等價于遮掩掉消息矩陣中的元素，其中表示所對應(yīng)的特征矩陣中那一行。

那么根據(jù)以上的描述，我們發(fā)現(xiàn)DropMessage是對消息矩陣進(jìn)行了最細(xì)粒度的屏蔽，這使得它成為最靈活的dropping方法，并且其他方法可以看作是DropMessage的一種特殊形式。

第四小節(jié) DropMessage有效性的理論分析

理論1 圖神經(jīng)網(wǎng)絡(luò)中無偏的隨機(jī)dropping將一個額外的正則化項(xiàng)引入到了目標(biāo)函數(shù)中，這使得模型更加魯棒。

證明：為了簡化分析，我們假設(shè)下游任務(wù)是一個二分類任務(wù)，并且我們應(yīng)用一個簡單的圖卷積神經(jīng)網(wǎng)絡(luò)層，其中是消息矩陣，是轉(zhuǎn)移矩陣，表示那些應(yīng)被每個結(jié)點(diǎn)聚合的消息且是規(guī)模化之后的形式。最后，我們采用一個sigmoid作為激活函數(shù)來生成分類的預(yù)測結(jié)果。并使用交叉熵?fù)p失

作為目標(biāo)函數(shù)，于是目標(biāo)函數(shù)的公式如下：

當(dāng)我們使用隨機(jī)dropping的時候，被擾動的代替了原來的消息矩陣。此時目標(biāo)函數(shù)的期望為：

正如上述公式所示，在圖上的隨機(jī)dropping方法引入了一個額外的正則化項(xiàng)，這使得模型預(yù)測的結(jié)果趨近于0或1，因此會有更加清晰的分類判斷。通過減小的方差，隨機(jī)dropping方法激勵模型提取更重要的高級表示以提升模型的魯棒性。

第二節(jié) DropMessage的優(yōu)勢第一小節(jié) 減小樣本方差

所有的隨機(jī)dropping方法都面臨著訓(xùn)練不穩(wěn)定的問題?，F(xiàn)有的工作表明，不穩(wěn)定是由每個訓(xùn)練輪次的時候引入的隨機(jī)噪聲導(dǎo)致的，這些噪聲增加了參數(shù)覆蓋的難度和訓(xùn)練的不穩(wěn)定性。一般來說，樣本方差被用來衡量穩(wěn)定程度。而相比于其他方法，DropMessage可以有效減少樣本方差。

理論2 在現(xiàn)有的隨機(jī)dropping方法中以相同概率進(jìn)行drop的情況下，DropMessage表現(xiàn)出最小的樣本方差

證明：隨機(jī)dropping方法的樣本方差可以通過計(jì)算消息矩陣的范數(shù)來衡量。在不失一般性的前提下，我們假設(shè)原始的消息矩陣是，即每個元素都是1。因此，我們可以通過消息矩陣的1-范數(shù)來計(jì)算其樣本方差。

我們認(rèn)為消息傳遞的GNN沒有結(jié)點(diǎn)sampler和邊sampler，這意味著每個有向邊都等價于消息矩陣M中的一個行向量。為了簡化分析，我們假設(shè)圖是無向圖，每個結(jié)點(diǎn)的度都是。在本例中，消息矩陣的總行數(shù)為。所有的隨機(jī)dropping方法都可以看作多個獨(dú)立的伯努利采樣。整個過程是符合二項(xiàng)分布的，因此我們可以計(jì)算出的方差。

對于Dropout來說，執(zhí)行次的伯努利采樣，在特征矩陣中遮掩一個元素會遮掩消息矩陣中的個元素，方差為

對于DropEdge來說，執(zhí)行nc次的伯努利采樣，在鄰接矩陣中遮掩一個元素會遮掩消息矩陣中的個元素，方差為

對于DropNode來說，執(zhí)行n次的伯努利采樣，在邊集合中遮掩一個元素會遮掩消息矩陣中的個元素，方差為

對于DropMessage來說，執(zhí)行次的伯努利采樣，在消息矩陣中遮掩一個元素會遮掩消息矩陣中的1個元素，方差為

綜上，DropMessage的方差最小。

直覺上，DropMessage獨(dú)立地決定了在消息矩陣中的元素掩碼與否，這恰好是隨機(jī)dropping消息矩陣的最小伯努利跡。通過減小樣本方差，DropMessage減小了不同訓(xùn)練輪次的消息矩陣差異，這穩(wěn)定了訓(xùn)練并加快了收斂速度。DropMessage具有最小樣本方差的原因是它是GNN模型中最細(xì)粒度的隨機(jī)dropping方法。在應(yīng)用DropMessage時會獨(dú)立判斷每個元素是否需要屏蔽。

第二小節(jié) 保持信息多樣性

我們將從信息論的角度比較不同隨機(jī)dropping方法損失信息多樣性的程度。

定義1 信息多樣性包含特征多樣性和拓?fù)涠鄻有浴Ｎ覀兌x特征多樣性為，這里，指的是對應(yīng)于來自的邊的行號的切片。信息多樣性定義為，這里，表示信息矩陣，表示集合中元素的個數(shù)。

換而言之，特征多樣性被定義為來自不同源結(jié)點(diǎn)的保留特征維度的總數(shù);拓?fù)涠鄻有员欢x為傳播至少一個維度消息的有向邊的總數(shù)。根據(jù)上述的定義，我們認(rèn)為只有在隨機(jī)dropping后特征多樣性和拓?fù)涠鄻有远疾粶p少的方法才具有保持信息多樣性的能力。

引理2 Dropout DropEdge DropNode 都不具有保持信息多樣性的能力

根據(jù)定義1，當(dāng)我們drop掉特征矩陣X中的一個元素時，所有在消息矩陣中對應(yīng)的元素都會被遮掩掉并且特征多樣性降低1. 當(dāng)我們drop掉鄰接矩陣中的一條邊時，對應(yīng)的在消息矩陣無向圖的兩行也會被遮掩掉并且拓?fù)涠鄻有越档?.同理，當(dāng)drop掉一個結(jié)點(diǎn)時特征多樣性和拓?fù)涠鄻有远紩档汀?/p>

理論3 當(dāng)drop率小于等于時，DropMessage可以保持信息多樣性。其中是結(jié)點(diǎn)的出度，是特征維度。

證明：DropMessage直接對消息矩陣進(jìn)行隨機(jī)丟棄。為了保持拓?fù)涠鄻有?，我們期望消息矩陣中每一行至少保留一個元素:

為了保持特征多樣性，我們期望對于特征矩陣中的每個元素，消息矩陣中至少保留一個其對應(yīng)的元素:

因此，為了滿足上述兩式以保持信息多樣性的drop比例應(yīng)滿足： 從信息論的角度來看，具有保持信息多樣性能力的隨機(jī)dropping方法比沒有這種能力的能保存更多的信息，并在理論分析上其性能也更好。因此，這也解釋了為什么DropMessage比現(xiàn)有的其他方法都要好。實(shí)際上，我們只為整個圖設(shè)置了一個drop率參數(shù)，沒有為每個結(jié)點(diǎn)都設(shè)置。雖然這樣會使DropMessage損失更多信息，但DropMessage仍然比具有相同drop率的其他方法能保留更多信息。

第五章 實(shí)驗(yàn)

我們在不同的圖神經(jīng)網(wǎng)絡(luò)和不同數(shù)據(jù)集中比較DropMessage和其他方法，我們主要想驗(yàn)證：

DropMessage是否在圖神經(jīng)網(wǎng)絡(luò)中優(yōu)于其他drop方法？

DropMessage是否提升了魯棒性，并讓圖神經(jīng)網(wǎng)絡(luò)的訓(xùn)練更高效？

定義1中所描述的信息多樣性在圖神經(jīng)網(wǎng)絡(luò)中重要嗎?

如圖所示，我們使用了三種圖神經(jīng)網(wǎng)絡(luò)（GCN、GAT、APPNP），每種神經(jīng)網(wǎng)絡(luò)都被應(yīng)用了Dropout、DropEdge、DropNode、DropMessage這四種隨機(jī)dropping方法。

通過上述實(shí)驗(yàn)，我們得出以下結(jié)論：

DropMessage優(yōu)于其他隨機(jī)dropping方法。在結(jié)點(diǎn)分類任務(wù)下的21個實(shí)驗(yàn)設(shè)置中DropMessage在15個設(shè)置中取得最好的實(shí)驗(yàn)結(jié)果，在剩下6個設(shè)置中取得次好的實(shí)驗(yàn)結(jié)果；在鏈路預(yù)測任務(wù)下的9個實(shí)驗(yàn)設(shè)置中DropMessage在5個設(shè)置中取得最好的實(shí)驗(yàn)結(jié)果，在剩下4個設(shè)置中取得次好的實(shí)驗(yàn)結(jié)果。

DropMessage 在不同的數(shù)據(jù)集中的表現(xiàn)十分穩(wěn)定。而以DropEdge為反例，我們可以看出其在工業(yè)數(shù)據(jù)集（FinV和Telecom）上表現(xiàn)出色，但在其余的公開數(shù)據(jù)集上表現(xiàn)差勁。我們認(rèn)為是得益于DropMessage細(xì)粒度的drop策略使其有更小的歸納偏置，也因此更適用于大多數(shù)的場景。

除了上述實(shí)驗(yàn)，我們還做了更多的實(shí)驗(yàn)分析：

一、 魯棒性分析

我們通過測量隨機(jī)dropping方法處理每個擾動圖的能力來研究它的魯棒性。為了保證初始數(shù)據(jù)相對干凈，我們在Cora、CiteSeer和PubMed這三個數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)。我們在這些數(shù)據(jù)集中隨機(jī)添加一定比例的邊，并進(jìn)行節(jié)點(diǎn)分類任務(wù)。我們發(fā)現(xiàn)，當(dāng)擾動率從0%增加到30%時，所有的隨機(jī)掉落方法都有正向的效果。與沒有攝動的情況相比，在30%擾動的情況下，平均提高了37%，這表明隨機(jī)掉落方法增強(qiáng)了圖神經(jīng)網(wǎng)絡(luò)模型的魯棒性。此外，我們所提出的DropMessage顯示了它的通用性，并優(yōu)于其他方法。

二、 過平滑分析

過平滑指的是隨著網(wǎng)絡(luò)深度的增加，結(jié)點(diǎn)的表示越來越難以區(qū)分。在這一部分中，我們評估了各種隨機(jī)dropping方法對這個問題的影響，并通過MADGap測量了過度平滑的程度(Chenet al. 2020)，其值越小結(jié)點(diǎn)的表示越難以區(qū)分。

A圖表明隨著模型深度的增加，隨機(jī)dropping方法都可以增加MADGap值；B圖表明隨著模型深度的增加，隨機(jī)dropping方法都可以提高測試準(zhǔn)確率。但是在這些隨機(jī)dropping方法DropMessage的表現(xiàn)是最佳的。當(dāng)層數(shù)l≥3時，與其他隨機(jī)掉落方法相比，其MADGap值平均提高3.3%，測試準(zhǔn)確率平均提高4.9%。這個結(jié)果可以說明DropMessage比其他方法生成了更多不同的消息，這在一定程度上阻止了節(jié)點(diǎn)收斂到相同的表示上。

三、 訓(xùn)練過程分析

我們分析了不同隨機(jī)dropping方法在訓(xùn)練過程中的損失變化。C圖是Cora數(shù)據(jù)集上不同隨機(jī)dropping方法應(yīng)用于GCN網(wǎng)絡(luò)的損失曲線。這個實(shí)驗(yàn)結(jié)果說明DropMessage有最小的樣本方差，因此收斂得更快且具有更穩(wěn)定的性能表現(xiàn)。

四、 信息多樣性分析

我們用Cora數(shù)據(jù)集來驗(yàn)證信息多樣性是否重要，Cora數(shù)據(jù)集有2708個結(jié)點(diǎn)，5429條邊，結(jié)點(diǎn)的平均度接近于4。根據(jù)之前在信息多樣性小節(jié)的分析，dropping率的上屆由結(jié)點(diǎn)的度和特征維度計(jì)算得來。在Cora數(shù)據(jù)集中特征維度為1433，它比結(jié)點(diǎn)的度大得多，因此上屆僅由度來決定。我們用兩個實(shí)驗(yàn)設(shè)置來驗(yàn)證信息多樣性。第一個是結(jié)點(diǎn)粒度實(shí)驗(yàn)，它對每個結(jié)點(diǎn)應(yīng)用其dropping率上屆大小的dropping率 。第二個是平均粒度實(shí)驗(yàn)，所有結(jié)點(diǎn)的dropping率都是。根據(jù)實(shí)驗(yàn)，我們發(fā)現(xiàn)結(jié)點(diǎn)粒度的效果好于平均粒度，這也就驗(yàn)證了信息多樣性的重要性。

第六章 結(jié)論

本文，我們提出DropMessage，一種更泛化的應(yīng)用于圖神經(jīng)網(wǎng)絡(luò)的隨機(jī)dropping方法。首先，我們統(tǒng)一了隨機(jī)dropping方法并分析了它們的性能。其次，我們從理論上說明了DropMessage在穩(wěn)定訓(xùn)練過程和保持信息多樣性方面的優(yōu)勢。由于其對消息矩陣做細(xì)粒度的drop操作，DropMessage在大多數(shù)情況下顯示出更大的可應(yīng)用性。最后，通過在五個公共數(shù)據(jù)集和兩個工業(yè)數(shù)據(jù)集上進(jìn)行的多任務(wù)實(shí)驗(yàn)，我們證明了所提方法的有效性和泛化性。

審核編輯 ：李倩