從拓撲的角度緩解圖卷積網絡的過平滑問題

柏 玉,宋 敏，劉士虎，唐 軼，楊昔陽

(1.云南民族大學 數學與計算機科學學院，云南 昆明 650504;2.泉州師范學院 數學與計算機科學學院，福建 泉州 362000)

圖數據作為一種通用語言，用于建模結構化和關系數據，例如社交網絡、點云和交通網絡.近年來，許多研究關注于開發(fā)圖數據的深度學習方法，導致了圖神經網絡(graph neural networks, GNNs)領域的快速發(fā)展.GCNs是一種常用而高效的GNNs方法，其在半監(jiān)督節(jié)點分類[1]、推薦系統(tǒng)[2]和鏈接預測[3]等任務上取得了很大的成功.GCNs主要有2種方法，即基于譜域的方法和基于空間的方法. 然而，由于其簡單性、較低的計算成本和對大型圖更好的可擴展性，基于空間的方法最近變得越來越流行.遵循空間方法的 GCNs模型的操作可以表示為2個階段，即消息傳遞階段和讀出階段.在消息傳遞階段，圖中的一個節(jié)點從它的鄰居接收消息，其中每個消息都是從一個鄰居節(jié)點的特征或連接到該節(jié)點的邊的特征計算出來的.在消息傳遞階段經常執(zhí)行的兩個步驟是聚合和更新步驟.在聚合步驟中，節(jié)點通過執(zhí)行加權求和操作.在更新步驟中，將對聚合的消息應用非線性轉換，以生成更新的節(jié)點表示.在GCNs模型中，消息傳遞階段通常使用圖卷積層來實現.通過疊加多個圖卷積層，可以建立一個深度GCNs模型，并允許在相隔不止一跳的節(jié)點之間傳遞消息，以及通過一系列非線性轉換學習抽象的中間節(jié)點嵌入.在讀出階段，學習到的節(jié)點嵌入被轉換為節(jié)點或整個圖的最終表示.然后將這些表示提供給分類器，根據下游任務產生合適的輸出.

卷積神經網絡(convolutional neural networks,CNNs) 在許多領域中都取得了優(yōu)越的性能， CNNs的成功受益于它們能夠設計和訓練一個深層的網絡模型.受此啟發(fā)，研究者們可能期望通過堆疊更多的圖卷積層，使GCNs具有更好的表現力來表征更豐富的鄰居拓撲.而構建深層并有表達性的GCNs并不容易實現.這是因為深層GCNs實際上受到了主要由過平滑[4]引起的表達能力的損害，該問題指出，重復使用圖卷積使不同類的節(jié)點表示無法區(qū)分.

構建深層GCNs的嘗試可以追溯到GCN模型[1]，其應用了殘差機制.出乎意料的是，當深度為3層及以上時，殘差GCN的表現仍然較差.文獻[4]首先指出了構建深層網絡的主要困難在于過平滑，但遺憾的是，他們未提出解決這個問題的方法.后續(xù)研究[5]通過使用個性化的PageRank解決了過平滑問題，該PageRank還將根節(jié)點加入到消息傳遞循環(huán)中.文獻[6]提出了寬度拓展的方法，即采用多階近鄰連接和序列化連接來緩解深層GCNs的過平滑現象.文獻[7]采用密集連接進行多跳消息傳遞，用于構建深層GCNs.最近,文獻[8]通過首先將表示轉換與傳播解耦，利用自適應調整機制來平衡每個節(jié)點的局部和全局鄰居之間的信息來改進GCNs的體系結構.文獻[9]從理論上證明了深層GCNs的節(jié)點特征會收斂到子空間而導致信息丟失，通過考慮ReLu函數和卷積濾波器，推廣了文獻[4]中的結論.文獻[10]提出了DropEdge的方法，可以將其視為消息傳遞減速器，應用該方法可以去除某些邊使得節(jié)點連接更加稀疏，從而在一定程度上避免了深層GCNs存在的過平滑問題.文獻[11]在文獻[4]結論的基礎上開發(fā)了一種過平滑度量，并提出了一種基于監(jiān)督優(yōu)化的方法來緩解過平滑.最近其他一些防止過度平滑的研究采用激活歸一化[12]和雙殘留連接[13]，它們與文獻[10]中的DropEdge是互補的.最近的一種方法[14]將殘差層、密集連接和膨脹卷積納入GCNs, 以促進深層結構的發(fā)展.然而，該模型的目標是圖分類，其中沒有討論過平滑.

1 預備知識

為了行文簡潔及后文敘述的需要，這里給出文中要用到的一些基本知識的相關數學表示.

1.1 符號

設G=(V,E)表示無權無向圖，其中V是節(jié)點的集合，E?V×V是V中節(jié)點之間的邊的集合，|V|=n和|E|=m分別是節(jié)點數和邊數.整個圖的拓撲信息由鄰接矩陣A∈Rn×n描述，其具有如下性質:

用D=diag(d1,d2,…,dn)∈Rn×n表示圖G的節(jié)點對角度矩陣，其中du=∑vA(u,v)，其矩陣形式為

節(jié)點特征矩陣表示為X∈Rn×d, 其中每行xv∈Rd表示節(jié)點v的特征向量，d是節(jié)點特征的維數.X也可使用矩陣的形式表示

1.2 圖卷積運算

大多數GCNs中的圖卷積運算遵循鄰域聚合方式[16]，通過傳播其鄰居的表示并在此之后應用變換來學習節(jié)點表示.一般圖卷積運算的第l層可以描述為

(1)

不失一般性，在下面的分析中重點討論GCN模型，這是最具代表性的圖卷積運算. 每個GCN層(GCN Layer, GCL)定義為:

(2)

一般來說，GCN模型中的2層可以得到很好的效果.兩層時，GCN模型可簡化為

Z=Softmax(σ(XW(0))W(1)).

(3)

采用GCN分類模型，驗證文中的方法在緩解該模型加深時存在的過平滑現象上的有效性，從而提高了其在半監(jiān)督節(jié)點分類任務上的性能.

1.3 半監(jiān)督節(jié)點分類

半監(jiān)督節(jié)點分類在訓練階段同時包含有標簽的節(jié)點和無標簽的節(jié)點，通常無標簽節(jié)點遠遠多于有標簽節(jié)點，與使用所有有標簽節(jié)點的模型相比，其訓練成本更低且效果更好.具體地，對于圖G=(V,E),VL表示z(0

2 深層GCNs模型的實證分析

在本節(jié)中，目的是驗證深層GCNs性能下降的主要原因是過平滑.為此，首先引入一個平滑度的定量度量來度量圖節(jié)點表示的平滑性.然后，利用這一指標以及Zachary空手道俱樂部數據集來驗證過平滑是影響更深層的GCNs模型性能下降的主要因素.

2.1 平滑度的定量度量

眾所周知，平滑度是反映節(jié)點表示的相似性的指標.由于歐氏距離是一種簡單而有效的度量節(jié)點表示的相似性的方法，特別是在高維空間中，首先用歐式距離表示節(jié)點u和節(jié)點v的表示之間的相似性度量

(4)

其中xu為節(jié)點u的特征表示，‖·‖為歐氏范數.歐式距離值越小，表示的相似性越高.為了消除特征表示大小的影響，我們使用歸一化節(jié)點表示來計算它們的歐氏距離，從而將D(xu,xv)限制在[0,1]的范圍內.

基于公式(4)中的相似性度量，提出節(jié)點u的平滑度度量QMSu(quantitative metric for smoothness),用于計算節(jié)點u到其他節(jié)點的平均距離

(5)

其中，n為圖G中的節(jié)點數.因此，QMSu度量節(jié)點u的表示與整個圖的相似性.進一步，可以使用QMSG來表示整個圖G的平滑度度量值.其數學表達式定義為

(6)

這里，QMSG的值越小，則圖G中節(jié)點表示的整體平滑度越高.

2.2 深層的GCNs模型性能下降的原因

基于上述研究，該部分主要探討深層的GCNs性能下降的原因.為此，研究了具有不同層數的GCN模型，并在Cora數據集上對它們進行了評估.在該數據集上對GCN模型進行100次運行，使用與文獻[1]相同的數據分割方案.

圖1 在Cora上對不同GCN層數的節(jié)點表示的測試精度和平滑度度量值

在Cora數據集上的結果如圖1所示.可以觀察到，模型深度為2層時測試精度是最高的，但從3層開始精度隨著層數的增加而減小.同時不難發(fā)現，GCN的平滑度度量值隨著其層數的增加而變小.說明不同GCN層數所導出的不同標簽的節(jié)點表示變得難以分離，整個圖的表示不可避免地出現了過平滑現象.

除了從定量的角度使用上述度量外，還采用Zachary空手道俱樂部數據集的可視化說明這一點，該數據集被分為2個類別，有34個頂點和78條邊.在這里，GCN未經過訓練，其權重參數是隨機初始化的，隱藏層的維數為16，輸出層的維數為2.在這個數據集上應用具有不同層數的GCN模型，不同層的GCN模型的輸出在圖2中被繪制為二維平面上的點.通過圖2,可以觀察到不同層數的GCN模型對這個小數據集的影響.當GCN模型的層數為1層時，這些點沒有很好地分離(圖2a).當應用2層圖卷積時，來自2個類別的點被相對較好地分離(圖2b).而應用多個圖卷積層時，這些點很快發(fā)生了混合，生成的節(jié)點表示很難分離(圖2c、d、e、f).

圖2 不同層數的GCN在Zachary空手道俱樂部網絡上的頂點嵌入

3 從拓撲的角度緩解過平滑問題

在GCNs中，相鄰節(jié)點間的消息傳遞是通過連接2個節(jié)點之間的邊來實現的，用DropEdge技術隨機刪除掉一些邊就可以讓節(jié)點連接更加稀疏.與此同時，GCNs具有局部連接的特點，而混合階傳播能夠包含更多的局部信息.它們能夠在一定程度上避免深層GCNs存在的過平滑問題.因此，我們提出了一種DropEdge技術和混合階傳播結合的方法，從拓撲的角度來緩解過平滑問題(relieving over-smoothing problem from the topological view, ROPTV).在本節(jié)中，首先解釋DropEdge技術和混合階傳播結合的方法如何緩解GCNs的過平滑問題.然后，將緩解了過平滑現象的深層GCNs用于半監(jiān)督節(jié)點分類任務，預測未標記節(jié)點的標簽.

3.1 DropEdge技術和混合階傳播結合的方法

DropEdge是一種簡單而有效的技術，尤其是在緩解深層GCNs存在的過平滑現象方面.每次訓練時，DropEdge技術會隨機刪除原始圖中固定比例的邊.由于文中遵循文獻[1]中對鄰接矩陣進行重歸一化技巧的思想，所以該技術是在對稱歸一化鄰接矩陣上隨機選取Vp個非零元素，然后將它們置為零，其中超參數p∈[0,1]表示刪除邊的概率.刪除后得到鄰接矩陣DE, 用公式表示為

DE=-′,

(7)

(8)

3.2 半監(jiān)督節(jié)點分類任務

(9)

(10)

(11)

對于半監(jiān)督多分類問題，評估所有有標記節(jié)點的交叉熵損失

(12)

其中yL是具有標簽的節(jié)點集合.

針對文中的研究目的，從拓撲的角度應用DropEdge技術和混合階傳播結合的方法來緩解深層GCNs模型存在的過平滑現象，將改進的更深層的GCNs模型應用于半監(jiān)督節(jié)點分類任務.可以將這個過程總結為ROPTV算法.

4 實驗

本節(jié)在3個引文網絡數據集上對半監(jiān)督節(jié)點分類任務進行實驗，以評估本文提出的ROPTV的優(yōu)越性.首先介紹需使用的數據集和實驗設置.然后將ROPTV與代表2種不同類別的8個深度為2層的GCNs基線進行比較，包括6種圖卷積: GCN[1]、 APPNP[5]、 N-GCN[6]、 Dropedge[9]、 GAT[17]、 SGC[18]; 2個基于采用的GCNs: GraphSAGE[19]和 FastGCN[20].此外，還對過平滑問題進行實驗分析.驗證ROPTV在緩解深層GCNs存在的過平滑現象上的有效性，并能提高其在半監(jiān)督節(jié)點分類任務上的性能.ROPTV算法模型為：

輸出 預測Z.

步驟：

3) 執(zhí)行特征轉換：由公式(10)來執(zhí)行特征轉換.

4) 由公式(11)來預測節(jié)點類別分布.

5) 由公式(12)計算半監(jiān)督節(jié)點分類損失.

4.1 數據集

本文對3個公開的引文網絡數據集Cora, Citeseer和Pubmed[21]進行實驗，表2匯總了數據集的統(tǒng)計信息.通過將科學論文視為節(jié)點，論文之間的引用視為邊，為這些數據集構建圖，每個節(jié)點由從相應文檔中提取的詞袋(Bag-of-words)特征向量來表示.針對Cora, Citeseer和Pubmed的預處理腳本是參考文獻[22]的代碼實現的.在每個基準數據集上，使用與半監(jiān)督圖學習[1,17]完全相同的實驗設置，例如特征和數據分割，并使用100個隨機數種子對每個數據集上的所有結果進行了100次實驗.

4.2 實驗設置

使用 Pytorch 框架和Pytorch Geometric來實現所提出的方法和一些必要的基線，Pytorch Geometric是一個基于Pytorch構建的用于對不規(guī)則結構化數據進行深度學習的庫. GCN的代碼參考GCN模型的PyTorch版本實現.使用Glorot正態(tài)初始化器來初始化分類器的權重矩陣，采用Adam優(yōu)化器來優(yōu)化模型的參數，并采用基于驗證損失的早期停止控制訓練周期.另外，只在訓練集上使用DropEdge技術，在驗證集和測試集上不再使用. 對于GCNs的過平滑問題的實驗，用GCN模型[1]做對比實驗，將GCN模型和ROPTV模型的層數l設置為2到32層不等，而ROPTV模型的傳播步長k被設置為2.

表1 基準數據集統(tǒng)計

所有實驗都是在16GB內存大小的11th Gen Intel(R) Core(TM) i5-11300H @ 3.10GHz 3.11 GHz上進行的.服務器操作系統(tǒng)為Windows 10.對于軟件版本，使用Python3.7.3, PyTorch 1.2.0, NumPy 1.16.4, SciPy 1.3.0.

4.3 實驗結果總體分析

半監(jiān)督節(jié)點分類結果匯總在表2，其中每一列的最高精度用粗體加下劃線突出顯示.方法顯示在表格的最后一行.

表2 總體分類準確率 %

從表2的頂部可以觀察到，在Cora和Citeseer數據集上，ROPTV在所有基線上實現了較大幅度的超越，在Pubmed數據集上表現的不是很好，但是和其他基線差距不大，說明文中提出的方法是有效的.具體來說，ROPTV在Cora和Citeseer數據集上的精度比GCN分別提高了3.3%和3.6%, 而GCN相比較，GAT的精度分別只提高了1.5%和2.2%.與最近的基于正則化的模型DropEdge相比，所提出的方法實現了2.0%和1.6%的改進，而DropEdge對GCN的改進分別僅為1.3%, 2.0%和0.6%.

此外，與基于節(jié)點采樣的方法——GraphSAGE和FastGCN相比，可以看到ROPTV在Cora, Citeseer和Pubmed數據集上的精度都得到了大幅度的提升.具體來說，ROPTV在3個數據集上的精度比GraphSAGE分別提高了5.9%, 6.5%和0.6%, 比FastGCN分別提高了3.4%, 5.1%和0.8%.該方法也被稱為DropNode，其對刪除邊的影響是面向節(jié)點的和間接的.這說明本文從拓撲角度出發(fā)，采用面向邊的DropEdge方法，其可以為訓練保留所有節(jié)點特征，比DropNode方法表現出了更大的靈活性.

4.4 過平滑問題分析

當增加模型層數時，許多GCNs面臨過平滑的問題——不同標簽的節(jié)點變得難以區(qū)分.通過使用MADGap[13]來研究ROPTV是如何緩解這個現象的.MADGap是衡量節(jié)點表示的過平滑度的指標，MADGap值越小，說明節(jié)點表示越難以區(qū)分，因此過平滑問題越嚴重.具體實驗結果如圖3所示.

PORTV和GCN模型在Cora數據集上的過平滑現象，分別表示模型的MADGap值和不同層數的分類結果.可以觀察到，隨著模型層數加深到32層，GCN的2個指標都顯著下降——MADGap值從70.10%下降到20.3%, 精度從81.5%下降到60.30%.這表明，隨著模型層數的加深，由于發(fā)生了過平滑現象，模型性能急劇下降，即半監(jiān)督節(jié)點分類的結果較差.然而，ROPTV方法隨著模型層數的增加，雖然2個指標都在下降，但在模型加深到10層之前，下降的比較緩慢.并且直到層數加深到32層時，ROPTV的MADGap值和分類精度遠高于GCN.這表明，隨著模型層數的加深，當現有的代表性GCN模型非常容易受到過平滑的影響時，ROPTV在一定程度上緩解了過平滑現象，從而提高了深層GCNs在半監(jiān)督節(jié)點分類任務上的性能.

(a)MADGap (b)分類結果圖3 在Cora上的過平滑現象分析

5 結語

針對深層GCNs存在過平滑現象，從而影響其在半監(jiān)督節(jié)點分類任務上的性能的問題，對GCNs的過平滑問題進行了定量的研究.引入了一個平滑度的定量度量，驗證深層GCNs性能下降的主要原因是過平滑.然后從拓撲的角度出發(fā)，應用DropEdge技術和混合階傳播結合的方法來緩解深層GCNs存在的過平滑現象.實驗結果表明，文中提出的方法緩解了深層GCNs模型存在的過平滑現象，在一定程度上提高了半監(jiān)督節(jié)點分類的精度.