圖神經(jīng)網(wǎng)絡(luò)在處理基于圖數(shù)據(jù)問題方面取得了巨大的成功

1 引言 圖神經(jīng)網(wǎng)絡(luò)在處理基于圖數(shù)據(jù)問題方面取得了巨大的成功，受到了廣泛的關(guān)注和應(yīng)用。GNNs通常是基于消息傳遞的方式設(shè)計(jì)的，本質(zhì)思想即迭代地聚合鄰居信息，而經(jīng)過次的迭代后， 層GNNs能夠捕獲節(jié)點(diǎn)的局部結(jié)構(gòu)，學(xué)習(xí)來自跳鄰居的信息。因此更深層的GNN就能夠訪問更多的鄰居信息，學(xué)習(xí)與建模遠(yuǎn)距離的節(jié)點(diǎn)關(guān)系，從而獲得更好的表達(dá)能力與性能。而在實(shí)際在做深層GNN操作時(shí)，往往會面臨著兩類問題：1. 隨著層數(shù)的增加，GNNs的性能會大幅下降；2. 隨著層數(shù)的增加，利用GNNs進(jìn)行訓(xùn)練與推斷時(shí)需要的計(jì)算量會指數(shù)上升。對于第一個(gè)問題來說，現(xiàn)有的很多工作分析出深層GNNs性能下降的原因是受到了過平滑問題的影響，并提出了緩解過平滑的解決方案；而對于第二個(gè)問題來說，設(shè)計(jì)方案模擬深層GNNs的表現(xiàn)能力并減少GNNs的計(jì)算消耗也成了亟待解決的需求，比如用于實(shí)時(shí)系統(tǒng)的推斷。針對這兩個(gè)問題，本文將分別介紹兩個(gè)在KDD 2020上的關(guān)于深度GNNs的最新工作。 第一個(gè)工作是Research Track的《Towards Deeper Graph Neural Networks》。該工作從另一個(gè)角度去解讀深度圖神經(jīng)網(wǎng)絡(luò)隨著層數(shù)增加性能下降的問題，認(rèn)為影響性能下降的主要原因是Transformation和Propagation兩個(gè)過程的糾纏影響作用，并且基于分析結(jié)果設(shè)計(jì)了深度自適應(yīng)圖神經(jīng)網(wǎng)絡(luò)（Deep Adaptive Graph Neural Networks) 模型，能夠有效地緩解深層模型的性能快速下降問題。 第二個(gè)工作是Research Track的《TinyGNN: Learning E?icient Graph Neural Networks》。該工作嘗試訓(xùn)練small GNN(淺層)去模擬Deep GNN(深層)的表達(dá)能力和表現(xiàn)效果，致力于應(yīng)用在實(shí)時(shí)系統(tǒng)推斷等對推斷速度有較高要求的場景。 2 Towards Deeper Graph Neural Networks 2.1 引言 1層的GCN只考慮了1跳鄰居的信息，而當(dāng)使用多層的圖卷積操作擴(kuò)大GCN的接受域之后，性能也會大幅下降。已有的一些工作[1,2]將這個(gè)性能大幅下降的原因歸根于圖神經(jīng)網(wǎng)絡(luò)的過平滑問題(over-smoothing)。然而這篇文章保持一個(gè)不同的觀點(diǎn)，并且從另一個(gè)角度去解讀深度圖神經(jīng)網(wǎng)絡(luò)性能下降的問題。這篇文章認(rèn)為影響其性能快速下降的主要因素是表示變換(Transformation)和傳播(propagation)的糾纏作用，過平滑問題只有在使用了非常大的接受域，也就是疊加非常多層的時(shí)候才會影響圖神經(jīng)網(wǎng)絡(luò)的表現(xiàn)效果。在進(jìn)行了理論和實(shí)驗(yàn)分析的基礎(chǔ)上，該文章提出了深度自適應(yīng)圖形神經(jīng)網(wǎng)絡(luò)的設(shè)計(jì)方案。代碼鏈接: https://github.com/mengliu1998/DeeperGNN 2.2實(shí)驗(yàn)與理論分析 2.2.1 圖卷積操作 通常圖卷積操作遵循一種鄰居聚合(或消息傳遞)的方式，通過傳播其鄰域的表示并在此之后進(jìn)行變化以學(xué)習(xí)節(jié)點(diǎn)表示。第層的操作一般可以描述為：

2.2.2 平滑度的定量度量 平滑度是反映節(jié)點(diǎn)表示相似程度的度量標(biāo)準(zhǔn)。通常兩個(gè)節(jié)點(diǎn)的歐氏距離值越小，兩個(gè)節(jié)點(diǎn)表示的相似性越高。本文作者提出了一種計(jì)算整張圖平滑度的指標(biāo)：

它與圖中節(jié)點(diǎn)表示的整體平滑度呈負(fù)相關(guān)，即越小，圖的平滑度越大。 2.2.3 深度GNN性能下降的原因 在評價(jià)指標(biāo)的基礎(chǔ)上，作者對GCN在cora數(shù)據(jù)集上進(jìn)行節(jié)點(diǎn)分類實(shí)驗(yàn)的準(zhǔn)確率、可視化以及指標(biāo)數(shù)值的變化情況進(jìn)行了統(tǒng)計(jì)，結(jié)果如下：

并給出質(zhì)疑over-smoothing的兩點(diǎn)原因：(1) 過平滑問題僅會發(fā)生在節(jié)點(diǎn)表示傳播很多層之后，而實(shí)驗(yàn)中cora的分類結(jié)果在10層之內(nèi)就大幅下降。（2）評價(jià)指標(biāo)的值與初始相比只有輕微下降，證明平滑程度只有一定的上升，而不足以導(dǎo)致過平滑。 而作者進(jìn)一步指出，是轉(zhuǎn)換(Transformation)和傳播(propagation)的糾纏作用嚴(yán)重?fù)p害了深度圖神經(jīng)網(wǎng)絡(luò)的性能。并且為了驗(yàn)證該假設(shè)，作者將兩個(gè)過程分解出來，設(shè)計(jì)了如下的一個(gè)簡單模型：

并同樣給出在cora上的實(shí)驗(yàn)結(jié)果：

當(dāng)兩個(gè)過程分解后，50層內(nèi)的GCN準(zhǔn)確率基本能夠在80%左右，當(dāng)層數(shù)達(dá)到100+后才會陸續(xù)下降，對應(yīng)的值也在300層以后變得很低，說明此時(shí)網(wǎng)絡(luò)受到過平滑的影響。以上兩個(gè)實(shí)驗(yàn)說明了在GNN受過平滑影響之前，轉(zhuǎn)換(Transformation)和傳播(propagation)的糾纏作用確實(shí)會損害深度圖神經(jīng)網(wǎng)絡(luò)的性能，導(dǎo)致性能大幅下降。也證實(shí)了解耦轉(zhuǎn)換和傳播可以幫助構(gòu)建更深層次的模型，從而利用更大的可接受域來學(xué)習(xí)更多的信息。 2.2.4 理論證明 經(jīng)過變換與傳播的解耦，作者的理論分析可以更嚴(yán)格且溫和地描述過平滑問題。在本節(jié)中，作者嚴(yán)格描述兩種典型傳播機(jī)制的過度平滑問題，并推導(dǎo)出當(dāng)層數(shù)趨近于無窮時(shí)，兩種(, 的收斂情況。并證明該種傳播模式是線性不可分的，利用它們作為傳播機(jī)制將產(chǎn)生難以區(qū)分表征，從而導(dǎo)致over-smoothing問題。 2.3 模型

主要思想是將節(jié)點(diǎn)表示的變換與傳播過程解耦，并同時(shí)進(jìn)行至層傳播，最后利用學(xué)得的融合權(quán)重向量做一個(gè)自適應(yīng)調(diào)整融合。 2.4 實(shí)驗(yàn)

實(shí)驗(yàn)數(shù)據(jù)集

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

cora數(shù)據(jù)集上不同訓(xùn)練集比例的分類準(zhǔn)確率 值得分析的有以下兩點(diǎn)： （1）為什么低label rate的DAGNN表現(xiàn)要好?這些比較可觀的改進(jìn)主要?dú)w功于DAGNN的優(yōu)勢: 通過消除表示轉(zhuǎn)換和傳播的糾纏，同時(shí)擴(kuò)展接受域的范圍，使得利用信息更豐富。 （2）和APPNP SGC的區(qū)別是什么?APPNP和SGC實(shí)際上都解耦了轉(zhuǎn)換和傳播，并且APPNP也擴(kuò)展了k階接受域。DAGNN比APPNP好，是因?yàn)樵O(shè)計(jì)了自適應(yīng)調(diào)整每個(gè)節(jié)點(diǎn)來自不同接收域的信息權(quán)重。

DAGNN在不同數(shù)據(jù)集上隨層數(shù)變化的表現(xiàn) 3 TinyGNN: Learning E?icient Graph Neural Networks 3.1 引言 經(jīng)過k次迭代后，k層GNN可以捕獲來自k-hop節(jié)點(diǎn)結(jié)構(gòu)信息。通過這種方式，一個(gè)更深層的GNN就有獲取更多鄰居信息的能力，從而取得更好的性能。舉例來說，下圖隨著GAT層數(shù)的增加，兩個(gè)數(shù)據(jù)集的分類準(zhǔn)確率都有大幅提升。

而相對應(yīng)的，當(dāng)GNN進(jìn)一步擴(kuò)展層數(shù)時(shí)，鄰域的指數(shù)擴(kuò)增會導(dǎo)致GNNs模型需要大量的訓(xùn)練和推理計(jì)算消耗。這使得許多應(yīng)用程序(如實(shí)時(shí)系統(tǒng))無法使用更深層的GNN作為解決方案。舉例來說，同樣的兩個(gè)數(shù)據(jù)，4層GAT的計(jì)算時(shí)間以指數(shù)級增長，導(dǎo)致計(jì)算消耗十分巨大。

因此這里就存在著一個(gè)困境，即采用深層的GNN就越容易取得高性能，但是從效率的角度又往往傾向于開發(fā)一個(gè)小而推斷迅速的GNN。但是較小的GNN與較深的GNN之間存在較大的鄰域信息差距，這也是需要考慮的。因此這篇文章旨在訓(xùn)練一個(gè)較小的GNN，既能很好地刻畫了局部結(jié)構(gòu)信息，與較深的GNN相比可以獲得相似性能，同時(shí)也能夠進(jìn)行快速的推斷?？偨Y(jié)來說，貢獻(xiàn)如下： （1）提出了一種小型、高效的TinyGNN，能夠在短時(shí)間內(nèi)實(shí)現(xiàn)推斷出高性能的節(jié)點(diǎn)表示。 （2）利用對等感知模塊(PAM)和鄰居蒸餾策略(NDS)，以顯式和隱式兩種方式對局部結(jié)構(gòu)建模，并解決小GNN和較深GNN之間的鄰居信息差距。 （3）大量的實(shí)驗(yàn)結(jié)果表明，TinyGNN可以實(shí)現(xiàn)與更深層次的GNN相似甚至更好的性能，并且在實(shí)驗(yàn)數(shù)據(jù)集上，推理過程能夠有7.73到126.59倍的提速。 3.2 模型 3.2.1 對等感知模塊 對等節(jié)點(diǎn)(peer nodes)指的是同一層GNN從同一個(gè)點(diǎn)源點(diǎn)采樣出的所有鄰居集合，在下圖(b)用相同的顏色表示。對等節(jié)點(diǎn)之間沒有通信，所有對等節(jié)點(diǎn)都能夠通過上層節(jié)點(diǎn)在兩跳內(nèi)相連。大量的對等節(jié)點(diǎn)是鄰居，來自底層的鄰居信息可以被對等節(jié)點(diǎn)直接配置。

PAM建模對等節(jié)點(diǎn)的方式如下，以兩個(gè)節(jié)點(diǎn)隱層表示的相似度作為融合權(quán)重。PAM能夠幫助探索同一層中的節(jié)點(diǎn)之間的新關(guān)系，并幫助建模較小的GNN從而避免由較低層的鄰居迭代聚集而導(dǎo)致的大量計(jì)算。

PAM可以被用于任何圖網(wǎng)絡(luò)結(jié)構(gòu)中，作為一個(gè)基礎(chǔ)的模塊，1層GNN+1層PAM的計(jì)算量要小于兩層GNN。 3.2.2 鄰居蒸餾策略 作者利用知識蒸餾設(shè)計(jì)了鄰居信息蒸餾方案，teacher GNN是深層模型，能夠建模更廣泛的鄰域。而student GNN采用淺層模型，能夠有更快的推斷速度。并且利用teacher GNN 教student GNN隱式地捕捉全局深層結(jié)構(gòu)信息，使得student GNN有深層GNN的表現(xiàn)效果。

teacher GNN的損失函數(shù)：

student GNN的損失函數(shù)，同時(shí)利用來自teacher網(wǎng)絡(luò)的軟標(biāo)簽和真實(shí)標(biāo)簽進(jìn)行學(xué)習(xí)，T表示蒸餾溫度。

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

實(shí)驗(yàn)數(shù)據(jù)集

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

速度提升情況