重新思考圖卷積網絡:GNN只是一種濾波器

2020-12-11 新智元

新智元報導

來源：arxiv

編輯：肖琴

【新智元導讀】最新研究提出，圖神經網絡僅對特徵向量進行低通濾波，不具有非線性流形學習特性。論文提出了一種基於圖形信號處理的理論框架，用於分析圖神經網絡。

圖神經網絡已成為解決圖結構數據機器學習問題的最重要技術之一。

最近關於頂點分類(vertex classification)的工作提出了深度和分布式的學習模型，以實現高性能和可擴展性。

但最近，一篇題為「Revisiting Graph Neural Networks: All We Have is Low-Pass Filters」的論文引起關注，文中提出，圖神經網絡僅僅是對特徵向量進行低通濾波而已。

來自東京工業大學、RIKEN的兩位研究人員發現，基準數據集的特徵向量對於分類任務來說已經能提供很多有用信息，而圖結構僅僅提供了一種對數據進行去燥的方法。

論文提出了一種基於圖形信號處理的理論框架，用於分析圖神經網絡。

作者稱，他們的結果表明，圖神經網絡僅對特徵向量進行低通濾波(low-pass filtering)，不具有非線性流形學習特性。論文進一步研究了它們對特徵噪聲的適應力，並對基於GCN的圖神經網絡設計提出了一些見解。

什麼時候應該使用圖神經網絡？

圖神經網絡(Graph neural networks, GNN)是一類能夠從圖結構數據中學習的神經網絡。近年來，用於頂點分類和圖形同構測試的圖神經網絡在多個基準數據集上取得了良好的效果，並不斷開創新的最先進技術性能。隨著ChebNet和GCN在頂點分類方面獲得成功，許多GNN變體被提出來解決社交網絡、生物學、化學、自然語言處理、計算機視覺和弱監督學習方面的問題。

在半監督頂點分類問題中，我們觀察到，圖卷積層(GCN)的參數只會導致過擬合。類似的觀察在簡單的架構(如SGC)和更複雜的腳骨(如DGI)中都曾被報告。

基於這種現象，Felix Wu等人提出將圖神經網絡簡單地看作是特徵傳播(feature propagation)，並提出了一種在許多基準數據集上具有最先進性能的高效模型。Kawamoto等人對圖分區設置下未經訓練的GCN-like GNNs進行了相關理論評述。

從這些先前的研究中，一個很自然的問題出現了：為什麼、以及何時圖神經網絡在頂點分類任務中表現很好？

換句話說，是否存在一個頂點特徵向量的條件，使得圖神經網絡模型即使沒有經過訓練也能很好地工作？

那麼，我們能否找到基準圖神經網絡(如SGC或GCN)失敗的實際反例?

在本研究中，我們從圖信號處理的角度來回答上述問題。在形式上，我們考慮了一個圖的半監督學習問題。

給定一個圖G = (V, E)，每個頂點i∈V都有一個特徵x(i)∈x，和標記y(i)∈y，其中x是d維歐氏空間R d, Y = R用於回歸， Y ={1，…， c}用於分類。任務是從特徵x(i)中學習預測標籤y(i)的假設。

然後，我們描述了這個問題的圖神經網絡解決方案，並對最常用的基準模型GCN及其簡化的變體SGC的機制提供了見解。

本研究三大貢獻

圖信號處理(Graph signal processing, GSP)將頂點上的數據視為信號，應用信號處理技術來理解信號的特徵。通過組合信號(特徵向量)和圖結構(鄰接矩陣或鄰接矩陣的變換)，GSP啟發了圖結構數據學習算法的發展。在標準信號處理問題中，通常假設觀測值包含一些噪聲，並且底層的「真實信號」具有低頻。這裡，我們對我們的問題提出了類似的假設。

假設1：輸入特徵包括低頻真實特徵和噪聲。真實特徵為機器學習任務提供了足夠的信息。

本研究的第一個貢獻是驗證了常用數據集的假設1(第3節)。圖1顯示了針對不同頻率成分(frequency components)的特徵訓練的2層感知器(MLPs)的性能。在所有基準數據集中，我們看到只有少數頻率成分有助於學習。在特徵向量中加入更多的頻率成分只會導致性能下降。反過來，當我們將高斯噪聲N (0, σ2 ) 添加到特徵中時，分類精度變得更糟了。

圖1：頻率成分的精度

最近的許多GNN都是建立在圖信號處理的基礎上的。最常見的做法是用(增強)規範化鄰接矩陣I L 和矩陣X的特性。在圖信號處理的文獻中，這種操作在圖上過濾信號(filters signals)，而不顯式地對標準化拉普拉斯矩陣進行特徵分解。在這裡，我們將這個增強的標準化鄰接矩陣及其變體稱為可互換的圖濾波器(graph filters)和傳播矩陣(propagation matrices)。

本研究的第二個貢獻表明，將圖信號與傳播矩陣相乘對應於低通濾波(第4節，尤其是定理3)，此外，我們還證明了觀測信號與低通濾波器之間的矩陣乘積是真實信號優化問題的解析解。與最近的圖神經網絡設計原理相比，我們的結果表明圖卷積層只是低通濾波(low-pass filtering)。因此，不需要學習圖卷積層的參數。

在理論理解的基礎上，我們提出了一種新的基準框架，稱為gfNN((graph filter neural network, 圖濾波神經網絡)，對頂點分類問題進行了實證分析。

gfNN由兩個步驟組成：

通過與圖濾波矩陣的乘法實現濾波特性;通過機器學習模型學習頂點標籤。

我們使用圖2中的一個簡單實現模型演示了框架的有效性。

圖2：gfNN的一個簡單實現

本研究的第三個貢獻是以下定理：

定理2：在假設1下，SGC、GCN和gfNN的結果與使用真實特徵的相應神經網絡的結果相似。

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

最後，我們將gfNN與SGC模型進行了比較。雖然SGC在基準數據集上計算速度快、精度高，但我們的分析表明，當特徵輸入是非線性可分的時，SGC會失敗，因為圖卷積部分對非線性流形學習沒有貢獻。為了實證證明這個觀點，我們創建了一個人工數據集。

實驗和結果

為了驗證前面提出的觀點，我們設計了兩個實驗。在實驗E1中，我們將不同水平的白噪聲加入到真實數據集的特徵向量中，並比較不同基線模型的分類精度。

在實驗E2中，我們研究了一個具有複雜的特徵空間的人工數據集，以證明SGC等簡單模型在分類時會失敗。

表1給出了每個數據集的概述。

表1：用於頂點分類的實際基準數據集和合成數據集

神經網絡

圖4:Cora(左)、Citeseer(中)和Pubmed(右)數據集上的基準測試精度。噪聲水平通過在特徵值上增加白噪聲的標準差來測量。

圖像濾波器的去噪效果

對於每個數據集表1中,我們介紹一個白噪聲N(0, 2)為特徵向量?範圍內(0.01,0.05)。根據定理8和定理7的含義，由於GCN的一階去噪特性，它對特徵噪聲的容忍度較低。

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

圖過濾器的表現力

圖5：基於兩個圓形圖案生成的500個數據樣本的決策邊界

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

總結

很少有工作涉及GCN架構的限制。Kawamoto等人採用平均場方法對一個簡單的GCN模型進行了統計物理分析。他們的結論是，反向傳播既不能提高基於GCN的GNN模型的準確性，也不能提高其可檢測性。Li et al.在有限的標籤數據設置下對多層的GCN模型進行了實證分析，指出如果標籤數據太少或者疊加層太多，GCN的性能就會下降。雖然這些結果為GCN提供了很有洞察力的觀點，但是它們並沒有充分地回答這個問題：我們什麼時候應該使用GNN?

我們的結果表明，如果假設1成立，我們應該使用GNN方法來解決給定的問題。從我們的角度來看，從GCN派生出來的GNNs只是簡單地執行噪聲濾波，並從去噪數據中學習。

基於我們的分析，我們提出了GCN和SGC可能無法執行的兩種情況：噪聲特徵和非線性特徵空間。然後，我們提出一個在這兩種情況下都能很好地工作的簡單方法。

近年來，基於GCN的神經網絡在點雲分析、弱監督學習等領域得到了廣泛的應用。隨著輸入特徵空間的複雜化，我們提議重新審視當前基於GCN的GNNs設計。在計算機視覺中，GCN層並不是卷積層，我們需要把它看作一種去噪機制。因此，簡單地疊加GCN層只會給神經網絡設計帶來過擬合和複雜性。

論文地址：

https://arxiv.org/pdf/1905.09550.pdf

相關焦點

  • 圖卷積網絡GCN的理解與介紹
    卷積網絡的卷積, 本質是通過濾波器來對某個空間區域的像素點進行加權求和,得到新的特徵表示的過程.3.1 簡單的類比例子我們用特例(圖片像素點構造的拓撲圖)來思考頂點域角度的GCN.之前所說每個節點聚合鄰居的節點值, 這和平滑空間濾波器的操作特別相似 (用於模糊處理或降低噪聲,如均值濾波). 但是, 節點的一些突變信息也很重要(比如說破產/暴發戶節點).
  • 深入了解VGG卷積神經網絡濾波器
    網絡可以進一步抽象，如下圖所示： 神經網絡內部就是這樣表示一隻鳥的。這是一種虛幻的形象，但這正是在沒有人為幹預的情況下該神經網絡自然學到的東西！然而，卷積網絡的真正威力在於，模型中的網絡越深入，越能推斷出更複雜的特徵。解讀分析keras-vis 可視化密集層的關鍵思想是生成一個輸入圖像以最大化對應於鳥類的最終密集層輸出。所以實際上這個模塊做的是反轉這個過程。給定一個特定的訓練密集層與它的權重，生成一個新的最適合該層本身的合成圖像。每個卷積濾波器都使用類似的思路。
  • 【GNN教程】圖神經網絡「開山之作」!
    「開山之作」，因為GCN利用了近似的技巧推導出了一個簡單而高效的模型，使得圖像處理中的卷積操作能夠簡單得被用到圖結構數據處理中來，後面各種圖神經網絡層出不窮，或多或少都受到這篇文章的啟發。顯然，這樣的學習策略基於圖中的相鄰節點標籤可能相同的假設（因為損失函數要求相鄰節點的特徵向量儘量相似，如何他們的標籤不相似的話，那麼不能學習到一個從特徵向量到標籤的有效映射）。然而，這個假設可能會限制模型的能力，因為圖的邊在語義上不一定代表所連接節點相似。還有一種可能是圖中有大量的噪聲邊。
  • 卷積神經網絡(一)——卷積、邊緣化與池化層
    (Convolutional Neural Network，CNN)，是一種神經網絡的模型，在計算機視覺（computer vision，CV）領域運用廣泛。邊緣檢測的方法，是通過構建過濾器，令圖片的rgb值和過濾器進行卷積，得到的結果即檢測出的結果。1、卷積計算這裡先考慮黑白圖片，則沒有rgb三個值，只有1個值，表示這個點的亮度。假定濾波器是一個3*3的矩陣，值如下圖所示，原圖的灰度值矩陣為下圖左邊那副圖所示，則進行卷積計算：
  • 定義圖上的各向異性、動態、頻譜和多尺度濾波器
    如果K等於節點數N,那麼Chebyshev卷積近似於頻譜卷積，濾波器的接收域就是整個圖。但是，就卷積網絡而言，我們不希望我們的濾波器和輸入的圖像一樣大，原因很久之前我就已經討論過了，所以實際上，K取的值會比較小。以我的經驗來看，這是功能最強大的GNN之一，在很多的關於圖的任務中都取得了很好的效果。
  • 重新發現語義分割,一文簡述全卷積網絡
    全卷積網絡自 2012 年出現以來，在圖像分類和圖像檢測領域取得了巨大成功。本文利用筆記本電腦構建了一個小型全卷積網絡，詳細介紹了全卷積網絡的思路、過程等等，值得一看語義分割是一種學習如何識別圖像中對象範圍的機器學習技術。語義分割賦予機器學習系統與人類相似的理解圖像內容的能力。
  • 用 Pytorch 理解卷積網絡
    藉助卷積神經網絡（CNN），這一切都是可能的，卷積神經網絡是一種特定類型的神經網絡，也稱為卷積網絡。如果您是一名深度學習愛好者，那麼您可能已經聽說過卷積神經網絡，也許您甚至自己開發了一些圖像分類器。像Tensorflow和PyTorch這樣的現代深度學習框架使向機器學習圖像變得容易，但是，仍然存在一些問題：數據如何通過神經網絡的人工層傳遞？計算機如何從中學習？
  • 圖解:卷積神經網絡的數學原理分析
    不幸的是，為了使該網絡能夠處理特定的智慧型手機照片，我們的網絡必須包含數千萬甚至數億個神經元。另一方面，我們可以縮小照片，但是在此過程中，我們將丟失一些有用的信息。我們立即意識到傳統策略對我們沒有影響。我們需要一種新的有效方法來充分利用儘可能多的數據，但同時減少必要的計算量和參數量。這是CNN發揮作用的時候。首先讓我們花一些時間來解釋數字圖像的存儲方式。
  • 圖解:卷積神經網絡數學原理解析
    圖2. 數字圖像的數據結構卷積核卷積不僅用於神經網絡，而且是許多其他計算機視覺算法的關鍵一環。核卷積的例子將過濾器放置在選定的像素上之後，我們從kernel中提取每個相應位置的值，並將它們與圖像中相應的值成對相乘。最後，我們總結了所有內容，並將結果放在輸出特性圖的對應位置。上面我們可以看到這樣的操作在細節上是怎麼實現的，但是更讓人關注的是，我們通過在一個完整的圖像上執行核卷積可以實現什麼應用。圖4顯示了幾種不同濾波器的卷積結果。
  • 深度學習元老Yann Lecun詳解卷積神經網絡
    註：卷積神經網絡（Convolutional Neural Network）是一種前饋神經網絡，它的人工神經元可以響應一部分覆蓋範圍內的周圍單元，對於大型圖像處理有出色表現。卷積神經網絡的結構卷積神經網絡的卷積運算過程大致如下：輸入圖像通過三個可訓練的濾波器組進行非線性卷積
  • 深度| 一文概覽圖卷積網絡基本結構和最新進展
    大綱神經網絡圖模型的簡要介紹譜圖卷積和圖卷積網絡（GCNs）演示：用一個簡單的一階 GCN 模型進行圖嵌入將 GCNs 視為 Weisfeiler-Lehman 算法的可微泛化如果你已經對 GCNs 及其相關方法很熟悉了的話，你可以直接跳至「GCNs 第 Ⅲ 部分：嵌入空手道俱樂部網絡」部分。
  • CNN卷積方法一覽
    目前大多數深度學習教程很少對卷積的含義進行細述，大部分只是對圖像的卷積操作進行了闡述。以至於卷積的數學意義和物理意義很多人並不是很清楚，究竟為什麼要這樣設計，這麼設計的原因如何。     追本溯源，我們先回到數學教科書中來看卷積。在泛函分析中，卷積也叫旋積或者褶積，是一種通過兩個函數x(t)和h(t)生成的數學算子。
  • 2D卷積網絡模型
    這裡NIN提出了一種全新的思路：由多個由卷積層+全連接層構成的微型網絡(mlpconv)來提取特徵，用全局平均池化層來輸出分類。這種思想影響了後面一系列卷積神經網絡的設計,例如Inception.5.2論文摘要我們提出一種新的深層網絡結構，稱為「網絡中的網絡」(NIN)，以提高模型對感受野內局部特徵塊的辨識能力。傳統的卷積層使用線性濾波器和非線性激活函數對處理輸入。
  • CNN 卷積方法一覽
    目前大多數深度學習教程很少對卷積的含義進行細述，大部分只是對圖像的卷積操作進行了闡述。以至於卷積的數學意義和物理意義很多人並不是很清楚，究竟為什麼要這樣設計，這麼設計的原因如何。     追本溯源，我們先回到數學教科書中來看卷積。在泛函分析中，卷積也叫旋積或者褶積，是一種通過兩個函數x(t)和h(t)生成的數學算子。其計算公式如下：連續形式：
  • 卷積神經網絡CNN:卷積的來源和原理
    卷積神經網絡（Convolutional Neural Network，簡稱為CNN或ConvNet）是一種具有
  • 一份完全解讀:是什麼使神經網絡變成圖神經網絡?
    二．為什麼很難在圖上定義卷積要回答這個問題，首先要理清一般使用卷積的動機，然後用圖術語描述「圖像上的卷積」，這將使「圖卷積」的過渡更加流暢。1. 為什麼卷積有用我們應該理解為什麼我們要注意到卷積，以及為什麼我們要用它來處理圖？與完全連接的神經網絡（NNS或MLP)相比，卷積網絡(CNN或Convnet)具有一定的優勢。
  • 圖神經網絡概述第三彈:來自IEEE Fellow的GNN綜述
    在本文中，圖神經網絡代表的是所有用於圖數據的深度學習方法。受到卷積網絡在計算機視覺領域所獲巨大成功的激勵，近來出現了很多為圖數據重新定義卷積概念的方法。這些方法屬於圖卷積網絡（GCN）的範疇。Bruna 等人（2013）提出了關於圖卷積網絡的第一項重要研究，他們基於譜圖論（spectral graph theory）開發了一種圖卷積的變體。自此，基於譜的圖卷積網絡不斷改進、拓展、進階。由於譜方法通常同時處理整個圖，並且難以並行或擴展到大圖上，基於空間的圖卷積網絡開始快速發展。這些方法通過聚集近鄰節點的信息，直接在圖結構上執行卷積。
  • 詳述Deep Learning中的各種卷積(四)
    首先典型的2D卷積步驟如下圖所示。 而在分組卷積中，濾波器被分成不同的組。每個組負責具有一定深度的2D卷積。下圖展示了具有兩個濾波器分組的分組卷積。在每個濾波器組中，每個濾波器只有原2D卷積的一半數目。
  • GCN (Graph Convolutional Network) 圖卷積網絡解析
    ，所以重點學習了一遍GCN，廣泛地參考了很多技術性文章，把一些我覺得比較有用的知識總結出來，加深對圖卷積網絡的理解，重要的內容也會貼出相應的連結方便大家學習，歡迎大家隨時和我分享學習體會和心得。1.2 特徵提取更詳細內容參考：https://www.zhihu.com/question/54504471卷積提取特徵GCN的本質目的就是用來提取拓撲圖的空間特徵，那麼實現這個目標只有graph convolution這一種途徑嗎？
  • 形象理解深度學習中八大類型卷積
    1 x 1卷積，濾波器大小為1 x 1 x D最初，在網絡網絡文件中提出了1 x 1卷積。舉一個具體的例子，假設輸入層的大小為7 x 7 x 3（高x寬x通道），濾波器的大小為3 x 3 x 3。使用一個濾波器進行2D卷積後，輸出層為尺寸為5 x 5 x 1（僅有1個通道）。標準2D卷積，使用1個濾波器創建1層輸出通常，在兩個神經網絡層之間應用多個濾波器。