前言

近年來，人們對(duì)深度學(xué)習(xí)方法在圖上的擴(kuò)展越來越感興趣。在多方因素的成功推動(dòng)下，研究人員借鑒了卷積網(wǎng)絡(luò)、循環(huán)網(wǎng)絡(luò)和深度自動(dòng)編碼器的思想，定義和設(shè)計(jì)了用于處理圖數(shù)據(jù)的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)，由此一個(gè)新的研究熱點(diǎn)——“圖神經(jīng)網(wǎng)絡(luò)（Graph Neural Networks，GNN）”應(yīng)運(yùn)而生。

圖1：來自(Bruna等人，ICLR，2014)的圖，描繪了3D領(lǐng)域內(nèi)的MNIST圖像。雖然卷積網(wǎng)絡(luò)很難對(duì)球面數(shù)據(jù)進(jìn)行分類，但是圖網(wǎng)絡(luò)可以很自然地處理它�？梢园阉�當(dāng)做是一個(gè)處理工具，但在實(shí)際應(yīng)用程序中會(huì)出現(xiàn)許多類似的任務(wù)。

最近，Graph Neural Network（GNN）在很多領(lǐng)域日益普及，包括社交網(wǎng)絡(luò)、知識(shí)圖譜、推薦系統(tǒng)甚至于生命科學(xué)。GNN在對(duì)節(jié)點(diǎn)關(guān)系建模方面表現(xiàn)十分突出，使得相關(guān)的研究領(lǐng)域取得了一定突破。本文將就“為什么圖有用”、“為什么很難在圖上定義卷積”、“是什么使神經(jīng)網(wǎng)絡(luò)成為了圖神經(jīng)網(wǎng)絡(luò)”這些問題進(jìn)行討論。

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

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

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

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

一．為什么圖有用

在計(jì)算機(jī)視覺(CV)和機(jī)器學(xué)習(xí)(ML)的背景下，研究圖以及學(xué)習(xí)當(dāng)中的模型至少可以給我們帶來以下四個(gè)好處：

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

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

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

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

我之前的研究是關(guān)于人臉識(shí)別和分析面部情緒，所以我很欣賞下面這個(gè)圖。

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

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

要回答這個(gè)問題，首先要理清一般使用卷積的動(dòng)機(jī)，然后用圖術(shù)語描述“圖像上的卷積”，這將使“圖卷積”的過渡更加流暢。

1. 為什么卷積有用

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

圖4

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

 （1）平移不變性，如果我們將上面圖像上的汽車平移到左/右/上/下，我們?nèi)匀荒軌蛘J(rèn)識(shí)到它是一輛汽車。這是通過在所有位置共享濾波器來實(shí)現(xiàn)的，也就是應(yīng)用卷積。

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

 （3）組合性(或?qū)哟谓Y(jié)構(gòu))，圖像中較大的區(qū)域通常都包含了較小區(qū)域的語義父級(jí)。例如，汽車是車門、車窗、車輪、駕駛員等的母體，而司機(jī)則是頭部、手臂等的母體。這是通過疊加卷積層和應(yīng)用池進(jìn)行的隱含表達(dá)。

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

理想情況下，我們的目標(biāo)是開發(fā)一個(gè)像圖神經(jīng)網(wǎng)絡(luò)一樣靈活的模型，它可以消化和學(xué)習(xí)任何數(shù)據(jù)，但同時(shí)我們希望通過打開或關(guān)閉某些先驗(yàn)來控制(正則)這種靈活性的元素。

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

2. 根據(jù)圖進(jìn)行圖像卷積

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

圖5：左側(cè)是MNIST數(shù)據(jù)集的圖像，右側(cè)是圖的示范。右側(cè)較暗和較大的節(jié)點(diǎn)對(duì)應(yīng)較高的像素強(qiáng)度。右圖的靈感來自圖6（Fey等人，CVPR，2018）

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

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

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

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

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

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

上面使用的點(diǎn)積就是所謂的“聚合算子”之一。廣義上來講，聚合算子的目標(biāo)是將數(shù)據(jù)歸納成簡單的形式。在上面的例子中，點(diǎn)積將一個(gè)3×3矩陣概括為單個(gè)值。另一個(gè)例子是在Convnet中進(jìn)行數(shù)據(jù)匯總。請(qǐng)記住，諸如最大值或和總計(jì)值的位置是不變的，也就是說，即使隨機(jī)地移動(dòng)該區(qū)域內(nèi)的所有像素，它們還是會(huì)在空間區(qū)域內(nèi)匯總成相同的值。為了說明這一點(diǎn)，點(diǎn)積不是置換不變的，因?yàn)樵谝话闱闆r下：X₁W₁+X₂W₂≠X₂W₁+X₁W₂。

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

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

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

圖10：一個(gè)28×28濾波器(左)和該濾波器與數(shù)字7圖像的2D卷積結(jié)果。(右)

正如我前面提到的，當(dāng)你嘗試將卷積應(yīng)用到圖時(shí)，就會(huì)遇到很多問題。

節(jié)點(diǎn)是一個(gè)集合，該集合的任何排列都不會(huì)改變它。因此，人們應(yīng)用的聚合算子應(yīng)該是置換不變的.

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

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

例如，左側(cè)的圖，節(jié)點(diǎn)1的求和聚合器的輸出為X₁=(X₁+X₂+X₃+X₄)W₁，節(jié)點(diǎn)2：X₂=(X₁+X₂+X₃+X₅)W₁等，即我們需要對(duì)所有節(jié)點(diǎn)應(yīng)用此聚合器。因此，我們將得到具有相同結(jié)構(gòu)的圖，節(jié)點(diǎn)現(xiàn)在包含了所有鄰值的功能。我們可以用同樣的方法處理右邊的圖。

通俗地說，人們稱這種平均或求和為“卷積”，因?yàn)槲覀円彩菑囊粋�(gè)節(jié)點(diǎn)“滑動(dòng)”到另一個(gè)節(jié)點(diǎn)，并在每一步中應(yīng)用聚合算子。但是，重要的一點(diǎn)，這是一種非常特殊的卷積形式，在這里，濾波器沒有方向感。下面我將展示這些濾波器的外觀，并給出如何使它們更好的建議。

三．是什么使神經(jīng)網(wǎng)絡(luò)成為了圖神經(jīng)網(wǎng)絡(luò)

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

圖12：全連通層具有可學(xué)習(xí)權(quán)值W�！巴耆�連接”是指X⁽ˡ⁺1 1⁾中的每個(gè)輸出值取決于或“連接到”所有輸入X⁽ˡ⁾。通常情況下，雖然也不總是這樣，但我們?cè)谳敵鲋刑砑恿艘粋�(gè)偏差項(xiàng)。

MNIST中的信號(hào)非常強(qiáng)，只要使用上面的公式和交叉熵?fù)p失，精準(zhǔn)度就可以達(dá)到91%以上，而且不需要任何非線性和其他技巧(我是使用了一個(gè)略微修改過的PyTorch代碼做到了這一點(diǎn))。這種模型稱為多項(xiàng)式(或多類，因?yàn)槲覀冇?0類數(shù)字)Logistic回歸。

現(xiàn)在，如何將我們的神經(jīng)網(wǎng)絡(luò)轉(zhuǎn)換成圖神經(jīng)網(wǎng)絡(luò)？正如你已經(jīng)知道的，GNN背后的核心思想是聚合“鄰值”。在這里，重點(diǎn)是要理解，在很多情況下，實(shí)際上是你指定了“鄰值”。

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

圖13：圖及其鄰接矩陣的例子。我們?cè)谶@兩種情況下定義的節(jié)點(diǎn)順序都是隨機(jī)的，而圖仍然是相同的。

現(xiàn)在，讓我們根據(jù)像素的坐標(biāo)為我們的MNIST示例創(chuàng)建一個(gè)鄰接矩陣A(文章末尾提供了完整的代碼)：

這是定義視覺任務(wù)中鄰接矩陣的典型方法但并非是唯一的方法(Defferrard等人，2016年；Bronstein等人，2016年)。這個(gè)鄰接矩陣是我們的先驗(yàn)，或者說是我們的歸納偏差，我們根據(jù)經(jīng)驗(yàn)施加到模型上，應(yīng)該連接附近的像素，遠(yuǎn)程像素不應(yīng)該有邊緣，即使有也應(yīng)該是非常薄的邊緣(小值的邊緣)。這是因?yàn)槲覀冇^察到，在自然圖像中的鄰近像素通常對(duì)應(yīng)于同一個(gè)或多個(gè)經(jīng)常交互的對(duì)象(我們前面提到的局部性原則)，因此連接這些像素很有意義。

圖14：鄰接矩陣(NxN)的所有節(jié)點(diǎn)對(duì)之間的距離(左)和相鄰矩陣(中間) (右) 具有16個(gè)相鄰像素的子圖，其對(duì)應(yīng)于中間的鄰接矩陣。既然它是一個(gè)完整的子圖，它也被稱為“集團(tuán)”。

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

記住，我們的特征矩陣X有