雷鋒網AI科技評論編者按：本篇文章的內容是「計算機視覺及圖神經網絡教程」的一部分，將概述重要的圖神經網絡方面的工作進展。通過提取關鍵思想並解釋使用Python和PyTorch這樣經典的方法背後的所思所想。
本文來自Boris Knyazev的文章《Anisotropic, Dynamic, Spectral and Multiscale Filters Defined on Graphs》在不改變原文意思的基礎上，雷鋒網AI科技評論的編譯如下：
圖1：圖神經網絡圖（GNN）及其相關工作進展。為了避免造成進一步的混亂，有一部分研究成果的邊緣並沒有突出顯示，例如，有關動態圖所做的大量工作值得單獨概述。
20多年的圖神經網絡歷程
在之前的「圖神經網絡圖（GNN）以及相關的成果」中，添加了我去年遇到的關於圖的論文。在這個圖中，兩項研究成果之間的有向邊表示一篇文章是以另一篇文章為基礎的，而這個圖的顏色則表示：
紅色-頻譜方法（需要對拉普拉斯圖進行特徵分解，將在下面進行解釋）綠色-在空間域中的有效方法（不需要對拉普拉斯圖進行特徵分解）藍色-等效於頻譜方法，但不需要進行特徵分解（因此，真正有效的是空間方法）黑色-是GNN的補充方法，但與GNN本身的選擇無關(也就是池化和關注點的問題)。請注意，有一部分其他重要的研究成果的邊緣沒有突出顯示，是為了避免造成進一步的混亂，其中一小部分用粗體框標出來的，將在這篇文章中進行重點討論。免責聲明：我仍然找到了提煉我們近期研究成果的空間。
這裡有一份簡單的研究成果清單涵蓋了大多數重要方法：
知識圖的關係機器學習綜述（Nicket 等人, 2015）https://arxiv.org/abs/1503.00759幾何深度學習:超越歐幾裡德數據（Hamilton等人，2017）https://arxiv.org/abs/1611.08097結構化的深度模型：在圖上進行深度學習以及其他內容（Kipf等人，2018 ） 通過演示幻燈片的形式進行展現。http://tkipf.github.io/misc/SlidesCambridge.pdf歸納關係偏差，深度學習和圖網絡（Battaglia等人，2018）https://arxiv.org/abs/1806.01261在圖上進行深度學習：一項調查（Zhang等人，2018）https://arxiv.org/abs/1812.04202圖神經網絡：方法與應用綜述（Zhou等人，2018）https://arxiv.org/abs/1812.08434圖神經網絡的綜合研究（Wu等人，2019）https://arxiv.org/abs/1901.00596深度神經網絡中結構的復興（Petar Velikovi, 2019）博士論文https://www.repository.cam.ac.uk/handle/1810/292230NIPS和CVPR視頻教程https://sungsoo.github.io/2018/02/01/geometric-deep-learning.html第一次出現使用神經網絡對圖進行分類工作的似乎是Alessandro Sperduti和Antonina Starita在1997年發表的關於「結構分類的監督神經網絡」的論文中提出的（https://ieeexplore.ieee.org/document/572108）。
圖2：這是Sperduti和Starita在1997提供一組的數字，與20多年後我們現在正在做的工作不謀而合。
Sperduti和Starita在1997指出：「到目前為止，神經網絡已經被用來對非結構化模式和序列進行分類。然而，由於它們是基於特徵產生的方法，在處理複雜結構的時候，標準的神經網絡和統計方法還存在著些許不足。」
自1997年起，從圖中進行學習的研究成果在數量上已經增長了很多，而且涉及到了很多不同的方向，如果沒有一些智能化的自動化系統，就很難找到它們。我相信我們正在趨於使用基於神經網絡的方法（基於本教程第一部分中解釋的公式（2）），或者將神經網絡與其他方法結合使用。
圖3：這是在本教程的第一部分中製作出來的圖神經層的公式(2)，在這一部分中我們也會用到。請記住，如果我們需要計算輸出特性的特定損耗，或者需要將這些圖層堆疊起來，那麼就可以應用諸如ReLU或Softmax之類的激活方法。
回顧一下我們在第一部分中使用的表示法，我們有一些具有N個節點的無向圖G。圖中的每個節點都有一個C維特徵向量，所有節點的特徵表示為N×C維矩陣X。在典型的圖網絡中，例如GCN(Kipf和Wling，ICLR，2017)，我們將這些特徵X提供給具有C×F維可訓練權值W的圖神經層，從而使該層的輸出是一個N×F矩陣中Xl+1編碼更新的節點特徵(希望在某種意義上能更好)。?是一個N×N的矩陣，其中?表示節點i是否連接到（相鄰）節點j，這個矩陣稱為相鄰矩陣。我使用?而不是普通的A來強調這個矩陣可以被規範化，以便於在深度網絡中的特徵傳播。就本教程而言，我們可以假設?=A，也就是矩陣乘積?X的每i行都包含節點i相鄰數據特徵的和。
在本教程的其餘部分中，我將簡要解釋一些研究成果，它們在概覽圖中用粗體標記出來了。我建議對Bronstein等人的綜述進行更全面、更正式的分析。
請注意，儘管我在下文中詳細介紹了頻譜圖卷積的一些技術細節，但是最近的很多研究成果(如Xu等人的GIN, ICLR, 2019)都是在沒有頻譜卷積的情況下構建的，並且還在一些任務中取得了很好的效果。但是，了解譜卷積的工作原理仍然有助於我們理解和避免出現其他方法存在的潛在問題。
一. 頻譜圖卷積
Bruna 等人, 2014, ICLR 2014（https://arxiv.org/abs/1312.6203）
我在另一篇文章中詳細的解釋了頻譜圖卷積。
在本教程的這一部分中，我將簡要地總結一下。頻譜圖卷積的正式定義與信號/圖像處理中的卷積定理非常相似，可以寫成：
圖4：頻譜圖卷積，其中⊙表示按特徵方向的乘積。
公式中的V表示特徵向量，Λ是拉普拉斯圖 L的特徵值，通過特徵分解可以發現：l=VΛV；W_頻譜是濾波器。在本教程中，我假設將「拉普拉斯算子對稱歸一化」。它僅基於圖的相鄰矩陣A進行計算，可以通過幾行Python代碼完成，如下所示：
在這裡，我們假設A是對稱的，即A=A，並且我們的圖是無向的，否則節點度不能明確的定義，並且在計算拉普拉斯算子的時候必須要做一些假設。在計算機視覺和機器學習的背景中，拉普拉斯圖定義了如果我們以公式(2)的形式疊加多個圖神經層，那麼節點特徵應當如何更新。
因此，給定拉普拉斯圖L，節點特徵X和濾波器w_頻譜，在Python中，圖的頻譜卷積看起來非常簡單：
假設我們的節點特徵X是一維的，例如MNIST像素，但是它可以擴展到C維的情況：我們只需要對每個信息通道重複這個卷積，然後像信號或圖像卷積一樣在C上求和。
公式（3）在本質上與使用傅立葉變換的規則網格上對信號進行的頻譜卷積是一樣的，因此也為機器學習帶來了一些問題：
1.可訓練權值(濾波器)w_頻譜的維數取決於圖中的節點數N;
2. W_頻譜也取決於以特徵向量V編碼的圖結構。
這些問題有助於防止數據擴展到具有大型可變結構的圖的數據集中。
為了解決第一個問題，Bruna等人根據頻譜理論，提出了在頻譜域中滑動濾波器的方法，使濾波器在空間域上更具有局部性。其主題思想就是，你可以將公式(3)中的濾波器W_頻譜表示為?個預定義函數(如樣條曲線)的和，並不是學習N個W的值，而是學習K係數α的總和：
圖5：我們可以將N維濾波器W_頻譜近似為K個函數f的有限和，如下所示。因此，我們可以學習這些函數的K個係數（alpha），而不是學習W_頻譜的N個值。 當K << N時，它變得有效。
儘管fk的維數取決於節點N的數量，但這些函數是固定的，因此我們不需要學習它們。我們唯一需要了解的是係數α，所以W_頻譜也不再依賴於N。為了使我們在公式(4)中的近似值變得合理，我們希望K<<N能將可訓練參數的數量從N減少到K，更重要的是使它獨立於N，這樣我們的GNN就可以消化任意大小的圖。
在解決第一個問題所用到的這種平滑方法並不適用於解決第二個問題。
二.Chebyshev圖卷積
Defferrard等人，NeurIPS, 2016（https://arxiv.org/abs/1606.09375）
頻譜卷積及其平滑形式的主要缺點在於，它仍然需要對N×N維拉普拉斯圖L進行特徵分解，這就產生了兩個主要問題：
1.本徵分解是非常複雜的，O（N）。 另外，對於比較大的圖，在RAM中保持拉普拉斯圖的密集格式是不可行的。其中一種解決方案是使用稀疏矩陣並使用Python中的scipy.sparse.linalg.eigs查找特徵向量。此外，你可以在具有大量RAM和CPU內核的專用伺服器上預處理所有的訓練圖。在很多的應用程式中，你的測試圖都可以預先進行預處理，但是如果不斷有大量新的大型圖湧入，特徵分解的效果可能也會不那麼好。
2. 另一個問題是，你訓練的模型最終與圖的特徵向量V會緊密的聯繫起來。如果你的訓練圖和測試圖的結構相差很大（節點和邊的數量），那麼這可能是一個大問題。另一方面，如果所有圖都非常相似，那麼所遇到的問題就小得多了。而且，如果你在頻域中使用的是某些平滑的濾波器，例如上面討論的樣條，那麼濾波器會變得更加局部化，並且在適應新圖的問題上似乎就更加不明顯了。然而，這些模型仍然非常有限。
那麼，到現在為止Chebyshev圖卷積與所有這些內容又有什麼關係呢？
事實證明，它可以同時解決這兩個問題！
也就是說，它避免了計算代價高昂的特徵分解，濾波器也不再「附加」於特徵向量(但它們仍然是特徵值Λ的函數)。此外，它具有非常有用的參數，通常表示為K，憑直覺講應該與我們上面公式(4)中的K相似，它決定了濾波器的位置。通俗地講：對於K=1，我們只將節點特徵X提供給我們的GNN；對於K=2，我們輸入X和?X；對於K = 3，我們輸入X，?X和?X； 對於較大的K，依此類推（希望你也注意到了這種模式）請查看Defferrard等人提出的更準確和正式的定義。下面是我的代碼，以及其他分析，參見(Knyazev等人，NeurIPS-W，2018)。
由於相鄰矩陣的功率特性，當我們在執行?2×的時候，我們實際上是對2-hop相鄰的數據求平均值(或與?的歸一化方式有關)，類似於?X中的任意n，如下圖所示，這裡我們就是對n-hop的相鄰數據求平均值。
圖6：對於節點1(深藍色)，是K=3的Chebyshev卷積。帶圓圈的節點表示影響節點1特徵表示的節點，[，]運算符表示特徵維度上的連接。W為3C×F維權值。
請注意，為了滿足Chebyshev基的正交性，?假定在圖中不設循環，因此在矩陣乘積?X中的每i行中，我們將具有節點i的鄰域特徵，而不是節點i本身的特徵。單獨提供給矩陣X。
如果K等於節點數N,那麼Chebyshev卷積近似於頻譜卷積，濾波器的接收域就是整個圖。但是，就卷積網絡而言，我們不希望我們的濾波器和輸入的圖像一樣大，原因很久之前我就已經討論過了，所以實際上，K取的值會比較小。
以我的經驗來看，這是功能最強大的GNN之一，在很多的關於圖的任務中都取得了很好的效果。主要缺點是在前進或者後退的時候需要循環遍歷K（由於Chebyshev多項式是遞歸的，因此無法並行化它們），這會減慢模型的速度。
和上面討論一樣，我們不需要訓練濾波器，只需訓練係數，這次訓練的是Chebyshev多項式的係數。
圖7：Chebyshev基用於近似頻譜域中的卷積。
要生成Chebyshev基，可以使用以下Python代碼：
生成的樣條和Chebyshev基的完整代碼在我的 github repo中。
為了說明Chebyshev濾波器是如何在不規則網格上顯示的，我遵循Bruna等人的實驗。再次以與我展示拉普拉斯圖的特徵向量相同的方式，從MNIST網格中抽取400個隨機點，我在這400個位置採樣的MNIST圖像上訓練了Chebyshev圖卷積模型(所有圖像都使用相同的不規則網格)，下面顯示了當K=1和K=20時的濾波器之一。
圖8：在MNIST上訓練了一個單獨的Chebyshev濾波器(左側k=3，右側K=20)，並將其應用於具有400個點的不規則網格中的不同位置(顯示為紅色像素)。與標準ConvNets的過濾器相比，GNN過濾器根據應用節點的不同而具有不同的形狀，因為每個節點都具有不同的鄰域結構。
二. GCN
Kipf 和 Welling, ICLR, 2017（https://arxiv.org/abs/1609.02907）
你們可能已經注意到了，如果增加Chebyshev卷積的K，可訓練參數的總數就會相應增加。例如,對於K = 2,我們的權值W將會是2C×F，而不僅僅是C×F。這是因為我們將特徵X和?X連接到了單個N×2C的矩陣中。更多的訓練參數也就意味著模型會更加難以訓練，必須標記更多的數據進行訓練。圖的數據集通常會非常小。
在計算機視覺領域中，MNIST被認為是一個很小的數據集，因為圖像只有28×28維，並且只有60k訓練圖像，但是對於圖網絡而言，MNIST卻是相當大的，因為每個圖有N=784個節點，60k是大量的訓練圖。與計算機視覺任務相比，很多圖數據集只有大約20-100個節點和200-1000個訓練示例。這些圖可以表示特定的小分子，而標記化學或生物數據通常比標記圖像的成本更昂貴。
因此，訓練Chebyshev卷積模型可能會導致訓練集嚴重過擬合(即模型的訓練損失接近於0，但驗證或測試誤差較大)。因此，Kipf和Welling的GCN本質上將節點特徵X和?X的矩陣「合併」為單個N×C矩陣。結果，與K = 2的Chebyshev卷積相比，該模型要訓練的參數少了兩倍，但具有相同的1 hop接受域。主要技巧是通過添加一個由I到?的單位矩陣並以特定方式對其進行規範化將自循環添加到圖中，因此，現在在矩陣乘積?X?的每i行中，我們將擁有節點i及其相鄰數據的特徵。
由於這個模型具有輕量級、良好的性能和對較大圖的延展性，因此該模型似乎是適合許多應用程式的標準基線選擇。
1. GCN與Chebyshev圖層
GCN與Chebyshev卷積的區別如下
上面的代碼遵循與教程第一部分相同的結構，在第一部分中，我比較了經典的NN和GNN。GCN和Chebyshev卷積的主要步驟之一是計算重新縮放拉普拉斯圖L。進行重新縮放的目的是使特徵值在[-1,1]範圍內進行，以方便訓練(這在實踐中可能不是很重要的步驟，因為權值可以在訓練過程中適應)。在GCN中，在計算拉普拉斯算子之前，先通過添加單位矩陣將自循環添加到圖中。兩種方法的主要區別在於，在Chebyshev卷積中，我們遞歸地在K上循環，以捕獲K-hop附近的特徵。我們可以將這樣的GCN層或Chebyshev圖層與非線性層疊加，建立一個圖神經網絡。
現在,請允許我禮貌地打斷一下頻譜的討論，並給出其他兩個令人興奮的方法背後的總體思路: ：Simonovsky和Komodakis，CVPR，2017年的邊緣條件濾波器（https://arxiv.org/abs/1704.02901）和Monti等人，CVPR，2017年的MoNet（https://arxiv.org/abs/1611.08402），它們具有相似的概念。
四. 邊緣條件濾波器
Simonovsky 和 Komodakis, CVPR, 2017（https://arxiv.org/abs/1704.02901）
就像你知道的那樣，在ConvNets中，我們通過優化諸如交叉熵之類的損失來學習權值(濾波器)。同樣，我們在GNN中學習W。想像一下，你不用學習這些權值，而是擁有另外一個可以預測權值的網絡。因此，在訓練過程中，我們將學習該輔助網絡的權值，它以圖像或圖作為輸入，並返回工作中的權值W(Θ)作為輸出。這一想法基於動態濾波器網絡(Brabandere等人，NIP，2016)，其中「動態」意味著濾波器W將因輸入不同而有所不同，不再是訓練結束後固定(或靜態)濾波器的標準模型。
圖9：使用輔助「濾波器生成網絡」F預測主要網絡的邊緣特定權值Θ。X是輸入節點的特性，X是輸出特性。這個圖顯示了節點1的「動態卷積」的單次迭代(黃色)。標準GNN通常只會平均(或求和)節點1相鄰的節點(節點2、3、4、5)的特徵,這相當於各向同性濾波器(Θ將是一個常數向量)。相比之下,這個模型還具有各向異性濾波器,因為它基於邊緣標籤L可以預測節點1及其所有相鄰數據之間的不同邊緣值,因此將特徵X(1)計算為相鄰數據特徵的加權平均值。圖來自(Simonovsky 和 Komodakis, CVPR, 2017)。
這是一種非常普遍的卷積形式，除了圖像以外，還可以很容易地應用到圖或點雲上，就像他們在CVPR論文中所做的那樣，而且還獲得了很好的效果。但是，沒有「免費的午餐」，訓練這樣的模型是相當具有挑戰性的，因為現在對常規的網格約束已經放鬆，並且解決方案的範圍顯著擴大。
對於有許多邊的較大圖，或者對於更深層次的卷積尤其如此，這些圖通常有數百個通道(特徵數量，C)，所以你可能最終會為每個輸入生成數千個數字!在這方面，標準的ConvNets的表現就非常好，因為我們沒有浪費模型的功能來預測這些權值，而是直接強制所有輸入的濾波器都相同。但是，這種先驗條件也使ConvNets受到了限制，我們不能直接將它們應用於圖或點雲。因此，與往常一樣，在特定的任務中，靈活性和性能之間需要權衡取捨。
當模型需要應用於像MNIST這樣的圖像時，邊緣條件模型可以學習預測各向異性濾波器例如對方向敏感的濾波器，邊緣檢測器。與我在本教程第一部分中討論的高斯濾波器相比，這些濾波器能夠更好地捕捉圖像中的某些模式，比如數字筆畫。
圖10：在MNIST上學習的卷積濾波器以低（左）和高（右）的解析度採樣。圖來自(Simonovsky和Komodakis, CVPR, 2017)。
我想再強調一次，每當我們有了一個帶有輔助網絡的複雜模型時，從某種意義上講，它就變成了先有雞還是先有蛋的問題。為了解決這個問題，其中一個網絡（輔助網絡或主要網絡）應該接收到非常強的信號，以便它可以隱蔽地監控另一個網絡。 在我們的BMVC論文中，有類似於Simonovsky和Komodakis的研究工作的內容，為了促進訓練，我們對邊緣生成網絡添加了額外的限制條件。 我將在以後的文章中詳細描述我們的研究工作。
五.MoNet
Monti 等人, CVPR, 2017（https://arxiv.org/abs/1688.08420）
MoNet與本文討論的其他研究工作不同，因為MoNet假定了具有節點坐標的概念，因此它更適合諸如3D網格分析或圖像/視頻推理之類的幾何任務。這有點類似於Simonovsky和Komodakis的邊緣條件濾波器，因為他們還引入了一個輔助可學的函數?(?,?ρ)可以預測權值（?，?，ρ）。
不同之處在於這些權值取決於節點的極坐標（?角和半徑ρ）；高斯的均值和方差可以約束這個具有可訓練參數為w的函數，因此我們不需要學習N×N矩陣，而僅需要學習獨立於圖大小，N的固定大小向量（均值和方差）。對於ConvNets，這與為每個濾波器僅學習2個值（高斯的均值和方差）相同，而不是分別為3×3、5×5或11×11維濾波器學習9、25或121個值。這種參數化將大大減少ConvNet中的參數數量，但濾波器捕捉圖像特徵的能力將非常有限。
Monti等人。訓練?高斯的均值和方差，以及節點坐標的轉換過程類似於將它們擬合到高斯混合模型中。如果我們希望我們的濾波器能夠更加全局化，那麼該模型需要大量的計算訓練，但它對於可視任務來說會是一個不錯的選擇（請參閱我們的BMVC文章進行比較），但是在非可視任務上它的表現比簡單的GCN還要差。（Knyazev等人，NeurIPS-W，2018）。 由於函數D取決於坐標，因此生成的濾波器也是各向異性的，並且具有定向和拉長高斯曲線的形狀，如下圖所示。
圖11：用MoNet訓練的極坐標為?和ρ的濾波器。 每個橢圓對應於某個固定水平的高斯切片。這裡有個想法是，如果第i個節點的坐標接近第j個高斯的中點，則在索引（i，j）處生成的權值將接近1。
總結：
儘管經過了這麼長時間的討論，但我們也只是了解到了一點皮毛。圖神經網絡的應用已經遠遠超出了典型的圖推理任務，比如分子分類。不同的圖神經層的數量正在迅速增加，就像是幾年前卷積網絡出現的情況，所以很難追蹤它們。在這一點上，PyTorch geometry (PyG)是一個很好的學習圖的工具，它經常使用新的圖層和技巧填充它的集合。
雷鋒網擴展閱讀：
手把手解釋頻譜圖卷積https://www.leiphone.com/news/201909/UBlc5tduQD9yjnnC.html?type=preview&sign=rqhxr4R4oqeDpqKqg3V6koDLo5OBn4-WhIbMoQ
原文連結：https://towardsdatascience.com/tutorial-on-graph-neural-networks-for-computer-vision-and-beyond-part-2-be6d71d70f49