圖1：來自（Bruna等人，ICLR，2014）的圖，描繪了3D領域內的MNIST圖像。雖然卷積網絡很難對球面數據進行分類，但是圖網絡可以很自然地處理它?？梢园阉斪鍪且粋€處理工具，但在實際應用程序中會出現許多類似的任務。

雷鋒網AI科技評論按：最近，Graph Neural Network（GNN）在很多領域日益普及，包括社交網絡、知識圖譜、推薦系統(tǒng)甚至于生命科學。GNN在對節(jié)點關系建模方面表現十分突出，使得相關的研究領域取得了一定突破。本文將就“為什么圖有用”、“為什么很難在圖上定義卷積”、“是什么使神經網絡成為了圖神經網絡”這些問題進行討論。

首先，讓我們簡單回顧一下什么是圖？圖 G 是由有向或無向邊連接的一組節(jié)點（頂點）。節(jié)點和邊通常是由專家依據知識經驗或是對問題的直覺進行設置的。因此，它可以是分子中的原子，社交網絡中的用戶，交通系統(tǒng)中的城市，團隊運動中的運動員，大腦中的神經元，動態(tài)物理系統(tǒng)中的交互對象，圖像中的像素、圖像邊界框或是圖像分割掩模。

換句話說，在很多情況下，實際上是由你來決定圖的節(jié)點和邊。

這是一種很靈活的數據結構，它囊括了很多其他的數據結構。例如，如果沒有邊，那么它就會變成一個集合；如果只有“垂直”邊，其中任意兩個節(jié)點都相連，那么我們就有了一個數據樹。當然正如我們接下來將要討論的，這種靈活性有利也有弊。

圖2：兩個分別有5和6個節(jié)點的無向圖，節(jié)點的順序是任意的。

一．為什么圖有用

在計算機視覺（CV）和機器學習（ML）的背景下，研究圖以及學習當中的模型至少可以給我們帶來以下四個好處：

1. 我們可以有機會解決以前解決不了的難題，例如：癌癥藥物發(fā)現（Veselkov等人，Nature，2019年）；更好地理解人腦結構（Diez&Sepulre，Nature，2019）；能源和環(huán)境友好材料的發(fā)現（Xie等人，Nature Communications，2019年）。

2. 在大多數CV/ML應用程序中，你可能曾經把它們看成是另一種數據結構，但數據實際上可以被看作是圖。將數據表示成圖可以提供很大的靈活性，并能在你處理問題的時候為你提供截然不同的視角。例如，你可以直接從“超像素”中學習，而不必從圖像像素中學習，在Liang等人2016年在ECCV發(fā)表的論文，以及我們即將發(fā)表的BMVC論文都可以找到依據。圖還允許你對數據施加關系歸納偏差，能使你在處理問題時具備一些先驗知識。例如，如果你想對人體的姿勢進行推理，你的關系偏差就可以是人體骨架關節(jié)的圖 （Yen等人，AAAI，2018）；或者如果你想對視頻進行推理，你的關系偏差可以是移動邊框的圖 （Wang&Gupta，ECCV，2018）。另一個例子是可以將面部標志表示為圖 （Antonakos等人，CVPR，2015），以便對面部特征和身份進行識別。

3. 神經網絡本身可以看作是一個圖，其中節(jié)點是神經元，邊是權重，或者節(jié)點是層，邊表示向前/向后傳遞的流程（在這種情況下，我們討論的是在TensorFlow中使用計算圖、PyTorch和其他DL框架）。應用程序可以是計算圖的優(yōu)化、神經結構搜索和訓練行為分析等。

4. 最后一點，你可以更高效的解決很多問題，在這些問題中數據可以更自然地表示成圖。 這包括但又不限于分子和社會網絡分類（Knyazev等人，NeurIPS-W，2018），3D Mesh的分類及對應（Fey等人，CVPR 2018），動態(tài)交互對象的建模行為（Kipf等人，ICML，2018），視景圖建模（詳見即將到來的ICCV研討會）和問答（Narasimhan， NeurIPS，2018），程序綜合（Allamanis等人，ICLR，2018），不同的強化學習任務（Bapst等人，ICML，2019）和許多其他問題。

我之前的研究是關于人臉識別和分析面部情緒，所以我很欣賞下面這個圖。

圖3：來自（Antonakos等人，CVPR，2015）的圖，將臉部標志提取出來。這是一種有趣的方法，但在很多情況下它并不能全面的表示出一個人的面部特征，因此可以通過卷積網絡從面部紋理中出捕捉到更多信息。相反，與2D標志相比，基于人臉的3D網格的推理看起來更合理（Ranjan等人，ECCV，2018）。

二．為什么很難在圖上定義卷積

要回答這個問題，首先要理清一般使用卷積的動機，然后用圖術語描述“圖像上的卷積”，這將使“圖卷積”的過渡更加流暢。

1. 為什么卷積有用

我們應該理解為什么我們要注意到卷積，以及為什么我們要用它來處理圖？與完全連接的神經網絡（NNS或MLP）相比，卷積網絡（CNN或Convnet）具有一定的優(yōu)勢。

圖4

首先，Convnet利用圖像中的一種自然先驗，在Bronstein等人在2016年發(fā)布的論文中有了更正式的描述，例如：

（1）平移不變性，如果我們將上面圖像上的汽車平移到左/右/上/下，我們仍然能夠認識到它是一輛汽車。這是通過在所有位置共享濾波器來實現的，也就是應用卷積。

（2）局域性，附近的像素是密切相關的，通常表示一些語義概念，如車輪或車窗。這是通過使用相對較大的濾波器來實現的，它可以捕捉到局部空間鄰域中的圖像特征。

（3）組合性（或層次結構），圖像中較大的區(qū)域通常都包含了較小區(qū)域的語義父級。例如，汽車是車門、車窗、車輪、駕駛員等的母體，而司機則是頭部、手臂等的母體。這是通過疊加卷積層和應用池進行的隱含表達。

其次，卷積層中可訓練參數（即濾波器）的數目并不取決于輸入維數，因此在技術上我們可以在28×28和512×512圖像上訓練完全相同的模型。換句話說，模型是參數化的。

理想情況下，我們的目標是開發(fā)一個像圖神經網絡一樣靈活的模型，它可以消化和學習任何數據，但同時我們希望通過打開或關閉某些先驗來控制（正則）這種靈活性的元素。

所有這些良好的特性使得ConvNet不太容易過度擬合（訓練集的高精度和驗證/測試集的低精度），在不同的視覺任務中更精確，并且易于擴展到大型圖像和數據集。因此，當我們想要解決輸入數據是圖結構的重要任務時，將這些屬性全部轉移到圖神經網絡（GNN）上，以規(guī)范它們的靈活性并使它們具有可擴展性。理想情況下，我們的目標是開發(fā)一個像GNN一樣靈活的模型，可以消化和學習任何數據，但同時我們希望通過打開或關閉某些先驗來控制（正則化）這種靈活性的元素。這可以在很多創(chuàng)新的方向上進行研究。然而，想要控制它并且達到一種平衡狀態(tài)還是很有挑戰(zhàn)性的。

2. 根據圖進行圖像卷積

我們先來考慮一下具有N個節(jié)點的無向圖G，邊E表示節(jié)點之間的無向連接。節(jié)點和邊通常是由你自己設定的。關于圖像，我們認為節(jié)點應該是像素或超像素（一組形狀怪異的像素），邊是它們之間的空間距離。例如，左下方的MNIST圖像通常表示為28×28維矩陣。我們也可以用一組N=28*28=784像素來表示它。因此，我們的圖G應該有N=784個節(jié)點，而對于位置較近的像素，邊會有一個較大的值（下圖中較厚的邊），對于較遠的像素，則相應的有較小的值（較薄的邊）。

圖5：左側是MNIST數據集的圖像，右側是圖的示范。右側較暗和較大的節(jié)點對應較高的像素強度。 右圖的靈感來自圖6（Fey等人，CVPR，2018）

當我們在圖像上訓練神經網絡或Convnet時，潛意識里我們在圖上就已經將圖像定義成了一個規(guī)則的2D網格，如下圖所示。這個網格對于所有的訓練和測試圖像是相同且規(guī)則的，也就是說，網格的所有像素都以完全相同的方式在所有圖像之間連接（即具有相同的連接數、邊緣長度等），所以這個規(guī)則的網格圖沒辦法幫我們從一幅圖像中分辨出另一幅圖像。下面我可視化了一些2D和3D規(guī)則網格，其中節(jié)點的順序是彩色編碼的。順便說一句，我是在Python代碼中使用了NetworkX來實現的，例如G=networkx.Grid_Graph（［4，4］）。

圖6：規(guī)則的2D和3D網格的例子。圖像在2D網格上的表現，視頻在3D網格上的表現。

考慮到這是個4×4的規(guī)則網格，我們可以簡單地看看2D卷積是如何工作的，就可以理解為什么很難將算子轉換成圖。規(guī)則網格上的濾波器具有相同的節(jié)點級，但現代卷積網絡通常有小濾波器，例如下面的例子中的3×3。這個濾波器有9個值：W?，W?，…，W?，這是由于我們在訓練過程中使用了backprop工具進行更新以盡量減少損失和解決下游任務的問題。在下面的例子中，我們只是受到啟發(fā)將濾波器初始化成了邊緣檢測器（請參閱這里的其他可能的濾波器）：

圖7：在規(guī)則2D網格上的3×3濾波器的例子，左側是任意權值w，右側是邊緣檢測器。

當我們進行卷積的時候，要從兩個方向滑動這個濾波器：向右和向下，可以從底角開始，重要的是要滑過所有可能的位置。在每個位置，計算網格上值之間的點積（表示為X）和濾波器的值W：X?W?+X?W?+…+X?W?，并將結果存儲在輸出圖像中。在我們的可視化過程中，改變節(jié)點在滑動過程中的顏色，以匹配網格中節(jié)點的顏色。在常規(guī)網格中，我們始終將濾波器的節(jié)點與網格的節(jié)點相匹配。但這并不適用于圖，我將在下面進行解釋。

圖8：規(guī)則網格上2D卷積的2個步驟。如果我們不應用填充的話，一共會有4個步驟，因此結果是2×2圖像。為了使得到的圖像更大，我們需要應用填充。在這里，請參閱關于深度學習中卷積的全面指南。

上面使用的點積就是所謂的“聚合算子”之一。廣義上來講，聚合算子的目標是將數據歸納成簡單的形式。在上面的例子中，點積將一個3×3矩陣概括為單個值。另一個例子是在Convnet中進行數據匯總。請記住，諸如最大值或和總計值的位置是不變的，也就是說，即使隨機地移動該區(qū)域內的所有像素，它們還是會在空間區(qū)域內匯總成相同的值。為了說明這一點，點積不是置換不變的，因為在一般情況下：X?W?+X?W?≠X?W?+X?W?。

現在，讓我們使用MNIST圖像，來定義規(guī)則網格、濾波器和卷積?？紤]到我們的圖術語，這個規(guī)則的28×28網格將是我們的圖G，因此這個網格中的每個單元都是一個節(jié)點，節(jié)點特征是一個實際的圖像X，也就是說每個節(jié)點只有一個特征，像素強度從0（黑色）到1（白色）。

圖9：規(guī)則28×28網格（左）和該網格上的圖像（右）。

接下來，我們要定義濾波器，并讓它成為具有 （幾乎）任意參數的著名Gabor濾波器。一旦我們有了圖像和濾波器，我們就可以通過在圖像上滑動濾波器 （在我們的例子中是數字7），并在每一步之后將點積的結果放到輸出矩陣中來執(zhí)行卷積。

圖10：一個28×28濾波器（左）和該濾波器與數字7圖像的2D卷積結果。（右）

正如我前面提到的，當你嘗試將卷積應用到圖時，就會遇到很多問題。

節(jié)點是一個集合，該集合的任何排列都不會改變它。因此，人們應用的聚合算子應該是置換不變的。

正如我前面提到的，用于計算每一步卷積的點積對順序是敏感的。這種靈敏度使我們能夠學習與Gabor濾波器相似的邊緣檢測器，這對于捕獲圖像特征非常重要。問題在于，在圖中沒有明確定義的節(jié)點順序，除非你學會給它們排序，或者想出其他一些啟發(fā)式的方法，能在圖與圖之間形成規(guī)范的順序。簡而言之，節(jié)點是一個集合，該集合的任何排列都不會改變它。因此，人們應用的聚合算子應該是置換不變的。最受歡迎的選擇是平均值（GCN、Kipf&Wling、ICLR，2017）和對所有相鄰數值求和（GIN、XU等人、ICLR，2019），也就是求和或均值池，然后由可訓練向量W進行推測，其他聚合器參見Hamilton等人，NIPS， 2017。

圖11：說明節(jié)點特征X的“圖卷積”，濾波器W以節(jié)點1（深藍色）為中心。

例如，左側的圖，節(jié)點1的求和聚合器的輸出為X?=（X?+X?+X?+X?）W?，節(jié)點2：X?=（X?+X?+X?+X?）W?等，即我們需要對所有節(jié)點應用此聚合器。因此，我們將得到具有相同結構的圖，節(jié)點現在包含了所有鄰值的功能。我們可以用同樣的方法處理右邊的圖。

通俗地說，人們稱這種平均或求和為“卷積”，因為我們也是從一個節(jié)點“滑動”到另一個節(jié)點，并在每一步中應用聚合算子。但是，重要的一點，這是一種非常特殊的卷積形式，在這里，濾波器沒有方向感。下面我將展示這些濾波器的外觀，并給出如何使它們更好的建議。

三．是什么使神經網絡成為了圖神經網絡

你應該知道典型的神經網絡是怎么工作的，我們將C維特征X作為網絡的輸入。用我們正在運行的MNIST舉例，X將是我們的C=784維像素特征（即“扁平”圖像）。這些特征乘以我們在訓練過程中更新的C×F維度權值W，使輸出能更接近我們預期的結果。這個結果可以直接用于解決任務（例如，在回歸的情況下），也可以進一步反饋到一些非線性（激活），如relu，或其他可微分（或更準確地說，是次微分）函數，從而形成多層網絡。一般來說，l 層的輸出是：

圖12：全連通層具有可學習權值W。“完全連接”是指X???1 1?中的每個輸出值取決于或“連接到”所有輸入X???。通常情況下，雖然也不總是這樣，但我們在輸出中添加了一個偏差項。

MNIST中的信號非常強，只要使用上面的公式和交叉熵損失，精準度就可以達到91%以上，而且不需要任何非線性和其他技巧（我是使用了一個略微修改過的PyTorch代碼做到了這一點）。這種模型稱為多項式（或多類，因為我們有10類數字）Logistic回歸。

現在，如何將我們的神經網絡轉換成圖神經網絡？正如你已經知道的，GNN背后的核心思想是聚合“鄰值”。在這里，重點是要理解，在很多情況下，實際上是你指定了“鄰值”。

讓我們先來考慮一個簡單的情況，當你得到一些圖。例如，這可以是5人的社交網絡的一個片段（子圖），節(jié)點之間的邊緣表示兩個人是否是朋友（或者他們中至少有一個人這樣認為）。右邊圖中的鄰接矩陣（通常表示為A）是一種以矩陣形式表示這些邊的方法，便于構建我們的深度學習框架。矩陣中的黃色代表邊緣，藍色代表邊緣的缺失。

圖13：圖及其鄰接矩陣的例子。我們在這兩種情況下定義的節(jié)點順序都是隨機的，而圖仍然是相同的。

現在，讓我們根據像素的坐標為我們的MNIST示例創(chuàng)建一個鄰接矩陣A（文章末尾提供了完整的代碼）：

這是定義視覺任務中鄰接矩陣的典型方法但并非是唯一的方法（Defferrard等人，2016年；Bronstein等人，2016年）。這個鄰接矩陣是我們的先驗，或者說是我們的歸納偏差，我們根據經驗施加到模型上，應該連接附近的像素，遠程像素不應該有邊緣，即使有也應該是非常薄的邊緣（小值的邊緣）。這是因為我們觀察到，在自然圖像中的鄰近像素通常對應于同一個或多個經常交互的對象（我們前面提到的局部性原則），因此連接這些像素很有意義。

圖14：鄰接矩陣（NxN）的所有節(jié)點對之間的距離（左）和相鄰矩陣（中間） （右） 具有16個相鄰像素的子圖，其對應于中間的鄰接矩陣。 既然它是一個完整的子圖，它也被稱為“集團”。

所以，現在不是只有特征X，還有一些值在［0，1］范圍內的奇特的矩陣A。需要注意的是，一旦我們知道輸入是一個圖，我們就假設在數據集中的所有其他圖節(jié)點的順序都是一致的。就圖像而言，這意味著假定像素被隨機調整。在實踐中，想要找到節(jié)點的規(guī)范順序是根本無法解決的。盡管對于MNIST來說，我們可以通過假定這個順序來進行操作（因為數據最初來自一個常規(guī)網格），但它不適用于實際的圖數據集。

記住，我們的特征矩陣X有？行和C列。因此，就圖而言，每一行對應于一個節(jié)點，C是節(jié)點特征的維度。但現在的問題是，我們不知道節(jié)點的順序，所以我們不知道應該在哪一行中放置特定節(jié)點的特征。

如果我們直接忽略這個問題，并像以前一樣直接將X提供給MLP，效果與將每個圖像隨機打亂像素進行重新組合形成的圖像相同，令人驚訝的是，神經網絡在原則上是可以擬合這樣的隨機數據的（Zhang等人，ICLR，2017），但是測試性能將接近隨機預測。其中一個解決方案是簡單地使用前面創(chuàng)建的鄰接矩陣A，方法如下：

圖15： 圖神經層具有鄰接矩陣A，輸入或輸出特征X，可學習權值W

我們只需要確保A中的第一行對應于X的第一行中節(jié)點的特征。這里，我使用的是？而不是普通的A，因為你想將A規(guī)范化，如果？=A，矩陣乘法？X???將等價于鄰值的求和特征，這在許多任務中都是有用的（Xu等人，ICLR，2019）。最常見的情況是，你將其規(guī)范化，使？X???具有平均鄰值的特性，即？=A/Σ?A?。規(guī)范矩陣A的更好方法可在（Kipf&Wling，ICLR，2017）中找到。

以下是NN和GNN在PyTorch代碼方面的比較：

這里有完整的PyTorch代碼訓練上面的兩個模型：Pythonmnist_fc.py-model fc訓練NN模型；python mnist_fc.py-模型圖訓練GNN模型。作為一個練習，可以嘗試在模型圖中隨機打亂代碼中的像素（不要忘記以同樣的方式對A進行調整），并確保它不會影響結果。對-FC模式的模型來說會是可行的嗎？

運行代碼后，你可能會注意到在分類的準確性上實際上是相同的。那還有什么問題嗎？圖形網絡不應該運行得更好嗎？其實在大多數情況下，它們都是可以正常運行，但是在這個例子中出現了特殊情況，因為我們添加的？X???運算符實際上就是一個高斯濾波器：

圖16：圖神經網絡中濾波器的2D可視化及其對圖像的影響。

我們的圖神經網絡被證明是等同于具有單個高斯濾波器的卷積神經網絡，在訓練過程中我們從不更新，然后是完全連接的層。這個濾波器基本上顯示模糊或是清晰的圖像，這并不是一件特別有用的事情（見上圖右邊）。然而，這是圖神經網絡的最簡單的變體，盡管如此，它在圖結構的數據上仍然運行得很好。為了使GNN更好地在規(guī)則圖上工作，（比如圖像），我們需要應用一些技巧。例如，我們可以通過使用如下可微函數來學習預測任意一對像素之間的邊，而不是使用預定義的高斯濾波器：

為了使GNN更好地在規(guī)則圖上工作，（比如圖像），我們需要應用一些技巧。例如，我們可以通過使用如下可微函數來學習預測任意一對像素之間的邊，而不是使用預定義的高斯濾波器。

這一想法類似于動態(tài)濾波器網絡（Brabander等人，NIP，2016年）、邊緣條件圖網絡（ECC、Simonovsky&Komodakis、CVPR，2017）和（Knyazev等人，NeurIPS-W，2018）。如果想用我們的代碼進行嘗試，只需要添加-pred_Edge標志，所以完整的指令就是python mnist_fc.py --model graph --pred_edge。下面我展示了預定義的高斯濾波器和學習濾波器的動畫。你可能會注意到，我們剛剛學到的濾波器（在中間）看起來很奇怪。這是因為任務相當復雜，我們同時優(yōu)化了兩個模型：預測邊緣的模型和預測數字類的模型。為了更好的學習濾波器（如右圖所示），我們需要從BMVC論文中應用一些其他技巧，這已經超出了這個教程范疇。

圖17：以紅點為中心的2D神經網絡濾波器。平均（左92.2 4%），坐標學習（中91.05%），坐標學習（右92.39%）。

生成這些GIF的代碼非常簡單：

我還分享了一個IPython代碼筆記，它用Gabor濾波器顯示了圖像的2D卷積（使用鄰接矩陣），而不是使用循環(huán)矩陣，循環(huán)矩陣通常用于信號處理。

在本教程的下一部分中，我將詳解更高級的圖層，這些圖層可以對圖進行更好的篩選。

四、總結

圖神經網絡是一個非常靈活且有趣的神經網絡家族，可以應用于非常復雜的數據。當然，這種靈活性也要付出一定的代價。在GNN的情況下，難以通過將這樣的運算符定義為卷積來使模型正規(guī)化。但這方面的研究進展很快，相信不久會得到完善的解決，GNN將會在機器學習和計算機視覺領域得到越來越廣泛的應用。