最新研究提出，圖神經(jīng)網(wǎng)絡(luò)僅對(duì)特征向量進(jìn)行低通濾波，不具有非線性流形學(xué)習(xí)特性。論文提出了一種基于圖形信號(hào)處理的理論框架，用于分析圖神經(jīng)網(wǎng)絡(luò)。

圖神經(jīng)網(wǎng)絡(luò)已成為解決圖結(jié)構(gòu)數(shù)據(jù)機(jī)器學(xué)習(xí)問題的最重要技術(shù)之一。

最近關(guān)于頂點(diǎn)分類(vertex classification)的工作提出了深度和分布式的學(xué)習(xí)模型，以實(shí)現(xiàn)高性能和可擴(kuò)展性。

但最近，一篇題為“Revisiting Graph Neural Networks: All We Have is Low-Pass Filters”的論文引起關(guān)注，文中提出，圖神經(jīng)網(wǎng)絡(luò)僅僅是對(duì)特征向量進(jìn)行低通濾波而已。

來(lái)自東京工業(yè)大學(xué)、RIKEN的兩位研究人員發(fā)現(xiàn)，基準(zhǔn)數(shù)據(jù)集的特征向量對(duì)于分類任務(wù)來(lái)說(shuō)已經(jīng)能提供很多有用信息，而圖結(jié)構(gòu)僅僅提供了一種對(duì)數(shù)據(jù)進(jìn)行去燥的方法。

論文提出了一種基于圖形信號(hào)處理的理論框架，用于分析圖神經(jīng)網(wǎng)絡(luò)。

作者稱，他們的結(jié)果表明，圖神經(jīng)網(wǎng)絡(luò)僅對(duì)特征向量進(jìn)行低通濾波(low-pass filtering)，不具有非線性流形學(xué)習(xí)特性。論文進(jìn)一步研究了它們對(duì)特征噪聲的適應(yīng)力，并對(duì)基于GCN的圖神經(jīng)網(wǎng)絡(luò)設(shè)計(jì)提出了一些見解。

什么時(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ò)。近年來(lái)，用于頂點(diǎn)分類和圖形同構(gòu)測(cè)試的圖神經(jīng)網(wǎng)絡(luò)在多個(gè)基準(zhǔn)數(shù)據(jù)集上取得了良好的效果，并不斷開創(chuàng)新的最先進(jìn)技術(shù)性能。隨著ChebNet和GCN在頂點(diǎn)分類方面獲得成功，許多GNN變體被提出來(lái)解決社交網(wǎng)絡(luò)、生物學(xué)、化學(xué)、自然語(yǔ)言處理、計(jì)算機(jī)視覺和弱監(jiān)督學(xué)習(xí)方面的問題。

在半監(jiān)督頂點(diǎn)分類問題中，我們觀察到，圖卷積層(GCN)的參數(shù)只會(huì)導(dǎo)致過擬合。類似的觀察在簡(jiǎn)單的架構(gòu)(如SGC)和更復(fù)雜的腳骨(如DGI)中都曾被報(bào)告。

基于這種現(xiàn)象，F(xiàn)elix Wu等人提出將圖神經(jīng)網(wǎng)絡(luò)簡(jiǎn)單地看作是特征傳播(feature propagation)，并提出了一種在許多基準(zhǔn)數(shù)據(jù)集上具有最先進(jìn)性能的高效模型。Kawamoto等人對(duì)圖分區(qū)設(shè)置下未經(jīng)訓(xùn)練的GCN-like GNNs進(jìn)行了相關(guān)理論評(píng)述。

從這些先前的研究中，一個(gè)很自然的問題出現(xiàn)了：為什么、以及何時(shí)圖神經(jīng)網(wǎng)絡(luò)在頂點(diǎn)分類任務(wù)中表現(xiàn)很好？

換句話說(shuō)，是否存在一個(gè)頂點(diǎn)特征向量的條件，使得圖神經(jīng)網(wǎng)絡(luò)模型即使沒有經(jīng)過訓(xùn)練也能很好地工作？

那么，我們能否找到基準(zhǔn)圖神經(jīng)網(wǎng)絡(luò)(如SGC或GCN)失敗的實(shí)際反例?

在本研究中，我們從圖信號(hào)處理的角度來(lái)回答上述問題。在形式上，我們考慮了一個(gè)圖的半監(jiān)督學(xué)習(xí)問題。

給定一個(gè)圖G = (V, E)，每個(gè)頂點(diǎn)i∈V都有一個(gè)特征x(i)∈x，和標(biāo)記y(i)∈y，其中x是d維歐氏空間R d, Y = R用于回歸， Y ={1，…， c}用于分類。任務(wù)是從特征x(i)中學(xué)習(xí)預(yù)測(cè)標(biāo)簽y(i)的假設(shè)。

然后，我們描述了這個(gè)問題的圖神經(jīng)網(wǎng)絡(luò)解決方案，并對(duì)最常用的基準(zhǔn)模型GCN及其簡(jiǎn)化的變體SGC的機(jī)制提供了見解。

本研究三大貢獻(xiàn)

圖信號(hào)處理(Graph signal processing, GSP)將頂點(diǎn)上的數(shù)據(jù)視為信號(hào)，應(yīng)用信號(hào)處理技術(shù)來(lái)理解信號(hào)的特征。通過組合信號(hào)(特征向量)和圖結(jié)構(gòu)(鄰接矩陣或鄰接矩陣的變換)，GSP啟發(fā)了圖結(jié)構(gòu)數(shù)據(jù)學(xué)習(xí)算法的發(fā)展。在標(biāo)準(zhǔn)信號(hào)處理問題中，通常假設(shè)觀測(cè)值包含一些噪聲，并且底層的“真實(shí)信號(hào)”具有低頻。這里，我們對(duì)我們的問題提出了類似的假設(shè)。

假設(shè)1：輸入特征包括低頻真實(shí)特征和噪聲。真實(shí)特征為機(jī)器學(xué)習(xí)任務(wù)提供了足夠的信息。

本研究的第一個(gè)貢獻(xiàn)是驗(yàn)證了常用數(shù)據(jù)集的假設(shè)1(第3節(jié))。圖1顯示了針對(duì)不同頻率成分(frequency components)的特征訓(xùn)練的2層感知器(MLPs)的性能。在所有基準(zhǔn)數(shù)據(jù)集中，我們看到只有少數(shù)頻率成分有助于學(xué)習(xí)。在特征向量中加入更多的頻率成分只會(huì)導(dǎo)致性能下降。反過來(lái)，當(dāng)我們將高斯噪聲N (0, σ2 ) 添加到特征中時(shí)，分類精度變得更糟了。

圖1：頻率成分的精度

最近的許多GNN都是建立在圖信號(hào)處理的基礎(chǔ)上的。最常見的做法是用(增強(qiáng))規(guī)范化鄰接矩陣I ? L? 和矩陣X的特性。在圖信號(hào)處理的文獻(xiàn)中，這種操作在圖上過濾信號(hào)(filters signals)，而不顯式地對(duì)標(biāo)準(zhǔn)化拉普拉斯矩陣進(jìn)行特征分解。在這里，我們將這個(gè)增強(qiáng)的標(biāo)準(zhǔn)化鄰接矩陣及其變體稱為可互換的圖濾波器(graph filters)和傳播矩陣(propagation matrices)。

本研究的第二個(gè)貢獻(xiàn)表明，將圖信號(hào)與傳播矩陣相乘對(duì)應(yīng)于低通濾波(第4節(jié)，尤其是定理3)，此外，我們還證明了觀測(cè)信號(hào)與低通濾波器之間的矩陣乘積是真實(shí)信號(hào)優(yōu)化問題的解析解。與最近的圖神經(jīng)網(wǎng)絡(luò)設(shè)計(jì)原理相比，我們的結(jié)果表明圖卷積層只是低通濾波(low-pass filtering)。因此，不需要學(xué)習(xí)圖卷積層的參數(shù)。

在理論理解的基礎(chǔ)上，我們提出了一種新的基準(zhǔn)框架，稱為gfNN((graph filter neural network, 圖濾波神經(jīng)網(wǎng)絡(luò))，對(duì)頂點(diǎn)分類問題進(jìn)行了實(shí)證分析。

gfNN由兩個(gè)步驟組成：

通過與圖濾波矩陣的乘法實(shí)現(xiàn)濾波特性;

通過機(jī)器學(xué)習(xí)模型學(xué)習(xí)頂點(diǎn)標(biāo)簽。

我們使用圖2中的一個(gè)簡(jiǎn)單實(shí)現(xiàn)模型演示了框架的有效性。

圖2：gfNN的一個(gè)簡(jiǎn)單實(shí)現(xiàn)

本研究的第三個(gè)貢獻(xiàn)是以下定理：

定理2：在假設(shè)1下，SGC、GCN和gfNN的結(jié)果與使用真實(shí)特征的相應(yīng)神經(jīng)網(wǎng)絡(luò)的結(jié)果相似。

定理7表明，在假設(shè)1下，gfNN和GCN具有相似的高性能。由于gfNN在學(xué)習(xí)階段不需要鄰接矩陣的乘法，因此它比GCN要快得多。此外，gfNN對(duì)噪聲的容忍度也更高。

最后，我們將gfNN與SGC模型進(jìn)行了比較。雖然SGC在基準(zhǔn)數(shù)據(jù)集上計(jì)算速度快、精度高，但我們的分析表明，當(dāng)特征輸入是非線性可分的時(shí)，SGC會(huì)失敗，因?yàn)閳D卷積部分對(duì)非線性流形學(xué)習(xí)沒有貢獻(xiàn)。為了實(shí)證證明這個(gè)觀點(diǎn)，我們創(chuàng)建了一個(gè)人工數(shù)據(jù)集。

實(shí)驗(yàn)和結(jié)果

為了驗(yàn)證前面提出的觀點(diǎn)，我們?cè)O(shè)計(jì)了兩個(gè)實(shí)驗(yàn)。在實(shí)驗(yàn)E1中，我們將不同水平的白噪聲加入到真實(shí)數(shù)據(jù)集的特征向量中，并比較不同基線模型的分類精度。

在實(shí)驗(yàn)E2中，我們研究了一個(gè)具有復(fù)雜的特征空間的人工數(shù)據(jù)集，以證明SGC等簡(jiǎn)單模型在分類時(shí)會(huì)失敗。

表1給出了每個(gè)數(shù)據(jù)集的概述。

表1：用于頂點(diǎn)分類的實(shí)際基準(zhǔn)數(shù)據(jù)集和合成數(shù)據(jù)集

神經(jīng)網(wǎng)絡(luò)

圖4:Cora(左)、Citeseer(中)和Pubmed(右)數(shù)據(jù)集上的基準(zhǔn)測(cè)試精度。噪聲水平通過在特征值上增加白噪聲的標(biāo)準(zhǔn)差來(lái)測(cè)量。

圖像濾波器的去噪效果

對(duì)于每個(gè)數(shù)據(jù)集表1中,我們介紹一個(gè)白噪聲N(0, 2)為特征向量?范圍內(nèi)(0.01,0.05)。根據(jù)定理8和定理7的含義，由于GCN的一階去噪特性，它對(duì)特征噪聲的容忍度較低。

隨著噪聲水平的增加，我們?cè)趫D4中可以看到，GCN、Logistic回歸(LR)和MLP更容易對(duì)噪聲進(jìn)行過擬合。另一方面，gfNN和SGC對(duì)噪聲的容忍度差不多。

圖過濾器的表現(xiàn)力

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

表2：隨機(jī)train/val/test分段的平均測(cè)試精度(5次)

總結(jié)

很少有工作涉及GCN架構(gòu)的限制。Kawamoto等人采用平均場(chǎng)方法對(duì)一個(gè)簡(jiǎn)單的GCN模型進(jìn)行了統(tǒng)計(jì)物理分析。他們的結(jié)論是，反向傳播既不能提高基于GCN的GNN模型的準(zhǔn)確性，也不能提高其可檢測(cè)性。Li et al.在有限的標(biāo)簽數(shù)據(jù)設(shè)置下對(duì)多層的GCN模型進(jìn)行了實(shí)證分析，指出如果標(biāo)簽數(shù)據(jù)太少或者疊加層太多，GCN的性能就會(huì)下降。雖然這些結(jié)果為GCN提供了很有洞察力的觀點(diǎn)，但是它們并沒有充分地回答這個(gè)問題：我們什么時(shí)候應(yīng)該使用GNN?

我們的結(jié)果表明，如果假設(shè)1成立，我們應(yīng)該使用GNN方法來(lái)解決給定的問題。從我們的角度來(lái)看，從GCN派生出來(lái)的GNNs只是簡(jiǎn)單地執(zhí)行噪聲濾波，并從去噪數(shù)據(jù)中學(xué)習(xí)。

基于我們的分析，我們提出了GCN和SGC可能無(wú)法執(zhí)行的兩種情況：噪聲特征和非線性特征空間。然后，我們提出一個(gè)在這兩種情況下都能很好地工作的簡(jiǎn)單方法。

近年來(lái)，基于GCN的神經(jīng)網(wǎng)絡(luò)在點(diǎn)云分析、弱監(jiān)督學(xué)習(xí)等領(lǐng)域得到了廣泛的應(yīng)用。隨著輸入特征空間的復(fù)雜化，我們提議重新審視當(dāng)前基于GCN的GNNs設(shè)計(jì)。在計(jì)算機(jī)視覺中，GCN層并不是卷積層，我們需要把它看作一種去噪機(jī)制。因此，簡(jiǎn)單地疊加GCN層只會(huì)給神經(jīng)網(wǎng)絡(luò)設(shè)計(jì)帶來(lái)過擬合和復(fù)雜性。