最新研究提出，圖神經(jīng)網(wǎng)絡(luò)僅對特征向量進行低通濾波，不具有非線性流形學(xué)習(xí)特性。論文提出了一種基于圖形信號處理的理論框架，用于分析圖神經(jīng)網(wǎng)絡(luò)。
圖神經(jīng)網(wǎng)絡(luò)已成為解決圖結(jié)構(gòu)數(shù)據(jù)機器學(xué)習(xí)問題的最重要技術(shù)之一。
最近關(guān)于頂點分類(vertex classification)的工作提出了深度和分布式的學(xué)習(xí)模型，以實現(xiàn)高性能和可擴展性。
但最近，一篇題為“Revisiting Graph Neural Networks: All We Have is Low-Pass Filters”的論文引起關(guān)注，文中提出，圖神經(jīng)網(wǎng)絡(luò)僅僅是對特征向量進行低通濾波而已。

來自東京工業(yè)大學(xué)、RIKEN的兩位研究人員發(fā)現(xiàn)，基準(zhǔn)數(shù)據(jù)集的特征向量對于分類任務(wù)來說已經(jīng)能提供很多有用信息，而圖結(jié)構(gòu)僅僅提供了一種對數(shù)據(jù)進行去燥的方法。
論文提出了一種基于圖形信號處理的理論框架，用于分析圖神經(jīng)網(wǎng)絡(luò)。
作者稱，他們的結(jié)果表明，圖神經(jīng)網(wǎng)絡(luò)僅對特征向量進行低通濾波(low-pass filtering)，不具有非線性流形學(xué)習(xí)特性。論文進一步研究了它們對特征噪聲的適應(yīng)力，并對基于GCN的圖神經(jīng)網(wǎng)絡(luò)設(shè)計提出了一些見解。
什么時候應(yīng)該使用圖神經(jīng)網(wǎng)絡(luò)？
圖神經(jīng)網(wǎng)絡(luò)(Graph neural networks, GNN)是一類能夠從圖結(jié)構(gòu)數(shù)據(jù)中學(xué)習(xí)的神經(jīng)網(wǎng)絡(luò)。近年來，用于頂點分類和圖形同構(gòu)測試的圖神經(jīng)網(wǎng)絡(luò)在多個基準(zhǔn)數(shù)據(jù)集上取得了良好的效果，并不斷開創(chuàng)新的最先進技術(shù)性能。隨著ChebNet和GCN在頂點分類方面獲得成功，許多GNN變體被提出來解決社交網(wǎng)絡(luò)、生物學(xué)、化學(xué)、自然語言處理、計算機視覺和弱監(jiān)督學(xué)習(xí)方面的問題。
在半監(jiān)督頂點分類問題中，我們觀察到，圖卷積層(GCN)的參數(shù)只會導(dǎo)致過擬合。類似的觀察在簡單的架構(gòu)(如SGC)和更復(fù)雜的腳骨(如DGI)中都曾被報告。
基于這種現(xiàn)象，F(xiàn)elix Wu等人提出將圖神經(jīng)網(wǎng)絡(luò)簡單地看作是特征傳播(feature propagation)，并提出了一種在許多基準(zhǔn)數(shù)據(jù)集上具有最先進性能的高效模型。Kawamoto等人對圖分區(qū)設(shè)置下未經(jīng)訓(xùn)練的GCN-like GNNs進行了相關(guān)理論評述。
從這些先前的研究中，一個很自然的問題出現(xiàn)了：為什么、以及何時圖神經(jīng)網(wǎng)絡(luò)在頂點分類任務(wù)中表現(xiàn)很好？
換句話說，是否存在一個頂點特征向量的條件，使得圖神經(jīng)網(wǎng)絡(luò)模型即使沒有經(jīng)過訓(xùn)練也能很好地工作？
那么，我們能否找到基準(zhǔn)圖神經(jīng)網(wǎng)絡(luò)(如SGC或GCN)失敗的實際反例?
在本研究中，我們從圖信號處理的角度來回答上述問題。在形式上，我們考慮了一個圖的半監(jiān)督學(xué)習(xí)問題。
給定一個圖G = (V, E)，每個頂點i∈V都有一個特征x(i)∈x，和標(biāo)記y(i)∈y，其中x是d維歐氏空間R d, Y = R用于回歸， Y ={1，…， c}用于分類。任務(wù)是從特征x(i)中學(xué)習(xí)預(yù)測標(biāo)簽y(i)的假設(shè)。
然后，我們描述了這個問題的圖神經(jīng)網(wǎng)絡(luò)解決方案，并對最常用的基準(zhǔn)模型GCN及其簡化的變體SGC的機制提供了見解。
本研究三大貢獻
圖信號處理(Graph signal processing, GSP)將頂點上的數(shù)據(jù)視為信號，應(yīng)用信號處理技術(shù)來理解信號的特征。通過組合信號(特征向量)和圖結(jié)構(gòu)(鄰接矩陣或鄰接矩陣的變換)，GSP啟發(fā)了圖結(jié)構(gòu)數(shù)據(jù)學(xué)習(xí)算法的發(fā)展。在標(biāo)準(zhǔn)信號處理問題中，通常假設(shè)觀測值包含一些噪聲，并且底層的“真實信號”具有低頻。這里，我們對我們的問題提出了類似的假設(shè)。
假設(shè)1：輸入特征包括低頻真實特征和噪聲。真實特征為機器學(xué)習(xí)任務(wù)提供了足夠的信息。
本研究的第一個貢獻是驗證了常用數(shù)據(jù)集的假設(shè)1(第3節(jié))。圖1顯示了針對不同頻率成分(frequency components)的特征訓(xùn)練的2層感知器(MLPs)的性能。在所有基準(zhǔn)數(shù)據(jù)集中，我們看到只有少數(shù)頻率成分有助于學(xué)習(xí)。在特征向量中加入更多的頻率成分只會導(dǎo)致性能下降。反過來，當(dāng)我們將高斯噪聲N (0, σ2 ) 添加到特征中時，分類精度變得更糟了。

圖1：頻率成分的精度
最近的許多GNN都是建立在圖信號處理的基礎(chǔ)上的。最常見的做法是用(增強)規(guī)范化鄰接矩陣I L 和矩陣X的特性。在圖信號處理的文獻中，這種操作在圖上過濾信號(filters signals)，而不顯式地對標(biāo)準(zhǔn)化拉普拉斯矩陣進行特征分解。在這里，我們將這個增強的標(biāo)準(zhǔn)化鄰接矩陣及其變體稱為可互換的圖濾波器(graph filters)和傳播矩陣(propagation matrices)。
本研究的第二個貢獻表明，將圖信號與傳播矩陣相乘對應(yīng)于低通濾波(第4節(jié)，尤其是定理3)，此外，我們還證明了觀測信號與低通濾波器之間的矩陣乘積是真實信號優(yōu)化問題的解析解。與最近的圖神經(jīng)網(wǎng)絡(luò)設(shè)計原理相比，我們的結(jié)果表明圖卷積層只是低通濾波(low-pass filtering)。因此，不需要學(xué)習(xí)圖卷積層的參數(shù)。
在理論理解的基礎(chǔ)上，我們提出了一種新的基準(zhǔn)框架，稱為gfNN((graph filter neural network, 圖濾波神經(jīng)網(wǎng)絡(luò))，對頂點分類問題進行了實證分析。
gfNN由兩個步驟組成：
通過與圖濾波矩陣的乘法實現(xiàn)濾波特性;
通過機器學(xué)習(xí)模型學(xué)習(xí)頂點標(biāo)簽。
我們使用圖2中的一個簡單實現(xiàn)模型演示了框架的有效性。

圖2：gfNN的一個簡單實現(xiàn)
本研究的第三個貢獻是以下定理：
定理2：在假設(shè)1下，SGC、GCN和gfNN的結(jié)果與使用真實特征的相應(yīng)神經(jīng)網(wǎng)絡(luò)的結(jié)果相似。
定理7表明，在假設(shè)1下，gfNN和GCN具有相似的高性能。由于gfNN在學(xué)習(xí)階段不需要鄰接矩陣的乘法，因此它比GCN要快得多。此外，gfNN對噪聲的容忍度也更高。
最后，我們將gfNN與SGC模型進行了比較。雖然SGC在基準(zhǔn)數(shù)據(jù)集上計算速度快、精度高，但我們的分析表明，當(dāng)特征輸入是非線性可分的時，SGC會失敗，因為圖卷積部分對非線性流形學(xué)習(xí)沒有貢獻。為了實證證明這個觀點，我們創(chuàng)建了一個人工數(shù)據(jù)集。
實驗和結(jié)果
為了驗證前面提出的觀點，我們設(shè)計了兩個實驗。在實驗E1中，我們將不同水平的白噪聲加入到真實數(shù)據(jù)集的特征向量中，并比較不同基線模型的分類精度。
在實驗E2中，我們研究了一個具有復(fù)雜的特征空間的人工數(shù)據(jù)集，以證明SGC等簡單模型在分類時會失敗。
表1給出了每個數(shù)據(jù)集的概述。

表1：用于頂點分類的實際基準(zhǔn)數(shù)據(jù)集和合成數(shù)據(jù)集
神經(jīng)網(wǎng)絡(luò)

圖4:Cora(左)、Citeseer(中)和Pubmed(右)數(shù)據(jù)集上的基準(zhǔn)測試精度。噪聲水平通過在特征值上增加白噪聲的標(biāo)準(zhǔn)差來測量。
圖像濾波器的去噪效果
對于每個數(shù)據(jù)集表1中,我們介紹一個白噪聲N(0, 2)為特征向量?范圍內(nèi)(0.01,0.05)。根據(jù)定理8和定理7的含義，由于GCN的一階去噪特性，它對特征噪聲的容忍度較低。
隨著噪聲水平的增加，我們在圖4中可以看到，GCN、Logistic回歸(LR)和MLP更容易對噪聲進行過擬合。另一方面，gfNN和SGC對噪聲的容忍度差不多。
圖過濾器的表現(xiàn)力

圖5：基于兩個圓形圖案生成的500個數(shù)據(jù)樣本的決策邊界

表2：隨機train/val/test分段的平均測試精度(5次)
總結(jié)
很少有工作涉及GCN架構(gòu)的限制。Kawamoto等人采用平均場方法對一個簡單的GCN模型進行了統(tǒng)計物理分析。他們的結(jié)論是，反向傳播既不能提高基于GCN的GNN模型的準(zhǔn)確性，也不能提高其可檢測性。Li et al.在有限的標(biāo)簽數(shù)據(jù)設(shè)置下對多層的GCN模型進行了實證分析，指出如果標(biāo)簽數(shù)據(jù)太少或者疊加層太多，GCN的性能就會下降。雖然這些結(jié)果為GCN提供了很有洞察力的觀點，但是它們并沒有充分地回答這個問題：我們什么時候應(yīng)該使用GNN?
我們的結(jié)果表明，如果假設(shè)1成立，我們應(yīng)該使用GNN方法來解決給定的問題。從我們的角度來看，從GCN派生出來的GNNs只是簡單地執(zhí)行噪聲濾波，并從去噪數(shù)據(jù)中學(xué)習(xí)。
基于我們的分析，我們提出了GCN和SGC可能無法執(zhí)行的兩種情況：噪聲特征和非線性特征空間。然后，我們提出一個在這兩種情況下都能很好地工作的簡單方法。
近年來，基于GCN的神經(jīng)網(wǎng)絡(luò)在點云分析、弱監(jiān)督學(xué)習(xí)等領(lǐng)域得到了廣泛的應(yīng)用。隨著輸入特征空間的復(fù)雜化，我們提議重新審視當(dāng)前基于GCN的GNNs設(shè)計。在計算機視覺中，GCN層并不是卷積層，我們需要把它看作一種去噪機制。因此，簡單地疊加GCN層只會給神經(jīng)網(wǎng)絡(luò)設(shè)計帶來過擬合和復(fù)雜性。