概述

我在本文將回答那些不熟悉圖或圖神經網絡的AI/ML/CV的用戶通常會問的問題。我提供了Pythorch的例子來澄清這種相對新穎和令人興奮的模型背後的思路。

問題

我在本部分教程中提出的問題是：

• 為什麼圖這種數據結構有用？
• 為什麼在圖上定義卷積是困難的？
• 什麼使神經網絡成為圖神經網絡？

為了回答這些問題，我將提供激勵性的示例、論文和python代碼，使其成為圖神經網絡（GNNs）的教程。讀者需要一些基本的機器學習和計算機視覺知識，但是，我隨著我的講述我也會提供一些背景和直觀的解釋。

首先，讓我們簡單回顧一下什麼是圖？圖是由有向/無向邊連接的一組節點（頂點）。節點和邊通常來自於關於問題的一些專家知識或直覺。因此，它可以是分子中的原子、社交網絡中的用戶、交通系統中的城市、團隊運動中的運動員、大腦中的神經元、動態物理系統中的相互作用對象、圖像中的像素、邊界框或分割遮罩。換言之，在許多實際情況下，實際上是您決定了什麼是圖中的節點和邊。

在許多實際情況下，實際上是你來決定圖中的節點和邊是什麼。

這是一個非常靈活的數據結構，它概括了許多其他的數據結構。例如，如果沒有邊，那麼它就成為一個集合；如果只有“垂直”邊，並且任何兩個節點正好由一條路徑連接，那麼我們就有一棵樹。這種靈活性是好的和壞的，我將在本教程中討論。

1 為什麼圖這種數據結構有用?

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

1. 我們可以更接近解決以前太具挑戰性的重要問題，例如：癌症的藥物發現（Veselkov等人，Nature，2019）；更好地理解人腦連接體（Diez&Sepulcre，Nature Communications，2019）；能源和環境挑戰的材料發現（Xie等人，自然通訊，2019）。
2. 在大多數cv/ml應用程序中，數據實際上可以看作是圖，即使您曾經將它們表示為另一個數據結構。將你的數據表示為圖形可以給你帶來很多靈活性，並且可以給你一個非常不同和有趣的視角來看待你的問題。例如，您可以從“超級像素”學習，而不是從圖像像素學習，如（Liang等人，ECCV2016）和我們即將發表的BMVC論文中所述。圖還允許您在數據中施加一種關係歸納偏差-一些關於該問題的先驗知識。例如，如果你想對人體姿勢進行推理，你的關係偏差可以是人體骨骼關節的圖（Yan等人，AAAI，2018）；或者如果你想對視頻進行推理，你的關係偏差可以是移動邊界框的圖（Wang&Gupta，ECCV2018）。另一個例子是將面部地標表示為圖（Antonakos等人，CVPR，2015），以對面部屬性和身份進行推理。
3. 您最喜歡的神經網絡本身可以看作是一個圖，其中節點是神經元，邊是權重，或者節點是層，邊表示向前/向後傳遞的流（在這種情況下，我們討論的是在tensorflow、pytorch和其他dl框架中使用的計算圖）。應用程序可以是計算圖的優化、神經結構搜索、分析訓練行為等。
4. 最後，您可以更有效地解決許多問題，其中數據可以更自然地表示為圖形。這包括但不限於分子和社會網絡分類（Knyazev et al.，Neurips-W，2018）和生成（Simonovsky&Komodakis，ICANN，2018）、三維網格分類和對應（Fey et al.，CVPR，2018）和生成（Wang et al.，ECCVV，2018）、動態交互對象的建模行為（Kipf et al.，ICML，2018），視覺場景圖建模（見即將召開的ICcv研討會）和問答（Narasimhan，Neurips，2018），程序合成（Allamanis等人，ICLR，2018），不同的強化學習任務（Bapst等人，ICML，2019）和許多其他令人興奮的問題。

由於我之前的研究是關於識別和分析面部和情緒的，所以我特別喜歡下面這個圖。

2 為什麼在圖上定義卷積是困難的?

為了回答這個問題，我首先給出了一般使用卷積的一些動機，然後用圖的術語來描述“圖像上的卷積”，這應該使向“圖上的卷積”的過渡更加平滑。

2.1 為什麼卷積有用？

讓我們理解為什麼我們如此關心卷積，為什麼我們想用它來繪製圖形。與完全連接的神經網絡（a.k.a.nns或mlps）相比，卷積網絡（a.k.a.cnns或convnets）具有以下根據一輛漂亮的老雪佛蘭的圖像解釋的某些優點。

首先，ConvNets利用圖像中的自然先驗，在（Bronstein等人，2016）中對此進行了更正式的描述，例如

1. 平移不變性-如果我們將上圖中的汽車向左/向右/向上/向下平移，我們仍然應該能夠將其識別為汽車。通過在所有位置共享過濾器，即應用卷積，可以利用這一點。
2. 位置-附近的像素緊密相關，通常代表某種語義概念，例如滾輪或窗戶。通過使用相對較大的濾波器可以利用這一點，該濾波器可以捕獲局部空間鄰域中的圖像特徵。
3. 組成性（或層次結構）-圖像中較大的區域通常是其包含的較小區域的語義父級。例如，汽車是車門、車窗、車輪、駕駛員等的父對象，而駕駛員是頭部、手臂等的父對象。這是通過疊加捲積層和應用池隱式利用的。

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

理想情況下，我們的目標是開發一種與Graph Neural Nets一樣靈活的模型，可以從任何數據中進行摘要和學習，但是與此同時，我們希望通過打開/關閉某些先驗條件來控制（調節）這種靈活性的因素。

所有這些出色的屬性使ConvNets不太容易過度擬合（訓練集的準確性較高，而驗證/測試集的準確性較低），在不同的視覺任務中更為準確，並且可以輕鬆地擴展到大型圖像和數據集。 因此，當我們要解決輸入數據採用圖結構的重要任務時，將所有這些屬性轉移到圖神經網絡GNN以規範其靈活性並使其具有可擴展性就很有吸引力。 理想情況下，我們的目標是開發一種與GNN一樣靈活的模型，並且可以從任何數據中進行摘要和學習，但是與此同時，我們希望通過打開/關閉某些先驗條件來控制（調節）這種靈活性的因素。 這可以打開許多有趣方向的研究。 然而，控制這種折衷是具有挑戰性的。

2.2 用圖對圖像進行卷積

讓我們考慮一個具有N個節點的無向圖G。 邊E表示節點之間的無向連接。 節點和邊通常來自您對問題的直覺。 對於圖像，我們的直覺是節點是像素或超像素（一組怪異形狀的像素），邊緣是它們之間的空間距離。 例如，左下方的MNIST圖像通常表示為28×28尺寸的矩陣。 我們也可以將其表示為一組N = 28 * 28 = 784像素。 因此，我們的圖形G將具有N = 784個節點，並且邊緣位置較近的像素的邊緣將具有較大的值（下圖中的較厚邊緣），而遠程像素的邊緣將具有較小的值（較薄的邊緣）。

當我們在圖像上訓練神經網絡或ConvNets時，我們在圖上隱式定義了圖像-下圖是一個規則的二維網格。 由於此網格對於所有訓練和測試圖像都是相同的，並且是規則的，即，網格的所有像素在所有圖像上都以完全相同的方式彼此連接（即，具有相同的鄰居數，邊長等）。 ），則此規則網格圖沒有任何信息可幫助我們將一個圖像與另一個圖像區分開。 下面，我可視化一些2D和3D規則網格，其中節點的順序用顏色編碼。 順便說一句，我正在Python中使用NetworkX來做到這一點，e.g. G = networkx.grid_graph([4, 4]).

有了這個4×4的規則網格，讓我們簡要地看一下2D卷積的工作原理，以瞭解為什麼很難將此運算符轉換為圖形。 規則網格上的過濾器具有相同的節點順序，但是現代卷積網絡通常具有較小的濾波器，例如下面的示例中的3×3。 該濾波器具有9個值：W 1，W 2，…，W 3，這是我們在使用反向傳播器進行訓練期間正在更新的值，以最大程度地減少損耗並解決下游任務。 在下面的示例中，我們試探性地將此過濾器初始化為邊緣檢測器.

當我們進行卷積時，我們會在兩個方向上滑動該濾波器：向右和向底部滑動，但是沒有什麼可以阻止我們從底角開始—重要的是要在所有可能的位置滑動。 在每個位置，我們計算網格上的值（用X表示）與濾鏡值W之間的點積：W：X₁W₁+ X₂W₂ +…+X₉W₉，並將結果存儲在輸出圖像中。 在我們的可視化中，我們在滑動過程中更改節點的顏色以匹配網格中節點的顏色。 在常規網格中，我們總是可以將X₂W₂的節點與網格的節點進行匹配。 不幸的是，對於圖而言，情況並非如此，我將在下面進行解釋。

上面使用的點積是所謂的“聚合運算符”之一。 廣義上講，聚合運算符的目標是將數據彙總為簡化形式。 在上面的示例中，點積將3×3矩陣彙總為單個值。 另一個示例是ConvNets中的池化。 請記住，最大池或總池之類的方法是置換不變的，即，即使您隨機改組該區域內的所有像素，它們也會從空間區域中合併相同的值。 為了明確起見，點積不是排列不變的，僅僅是因為通常：X₁W₁+X₂W₂ ≠X₂W₁+X₁W₂.

現在，讓我們使用我們的MNIST圖像並說明常規網格，濾波器和卷積的含義。 請記住我們的圖形術語，這個規則的28×28網格將成為我們的圖形G，因此該網格中的每個單元都是一個節點，並且節點特徵是實際的圖像X，即每個節點將只有一個特徵-像素 強度從0（黑色）到1（白色）。

接下來，我們定義一個濾波器，並使其成為具有一些（幾乎）任意參數的著名Gabor濾波器。 一旦有了圖像和濾波器，我們就可以通過在該圖像上滑動濾波器（在本例中為7位）並將點積的結果放置到輸出矩陣上來執行卷積。

這一切都很酷，但是正如我之前提到的，當您嘗試將卷積推廣到圖時，這變得很棘手。

節點是一個集合，該集合的任何排列都不會更改它。因此，人們應用的聚合運算符應該是不變排列的

正如我已經提到的，上面用於計算每個步驟的卷積的點積對順序很敏感。 這種靈敏度使我們能夠學習類似於Gabor濾波器的邊緣檢測器，這對於捕獲圖像特徵很重要。 問題在於，在圖中沒有明確定義的節點順序，除非您學會對節點進行排序，或者想出一些啟發式方法，否則將導致圖與圖之間的順序一致（規範）。 簡而言之，節點是一個集合，並且此集合的任何排列都不會更改它。 因此，人們應用的聚合運算符應該是不變排列的。 最受歡迎的選擇是所有鄰居的平均值（GCN，Kipf＆Welling，ICLR，2017）和求和（GIN，Xu et al。，ICLR，2019），即求和或均值合併，然後通過可訓練向量W進行投影。 有關其他聚合器，請參見（Hamilton等人，NIPS，2017）。

例如，對於上面左上方的圖，節點1的求和聚合器的輸出為X₁=（X₁+X₂ +X₃+X₄）W₁，對於節點2：X₂ =（X₁+ X₂ +X₃+X₅） W₁等對於節點3、4和5，即我們需要將此聚合器應用於所有節點。 結果，我們將獲得具有相同結構的圖，但是節點特徵現在將包含鄰居特徵。 我們可以使用相同的想法在右邊處理圖形。

通俗地講，人們稱這種平均或求和為“卷積”，因為我們也從一個節點“滑動”到另一個節點，並在每個步驟中應用一個聚合運算符。 但是，請務必記住，這是一種非常特殊的卷積形式，其中的濾波器沒有方向感。 下面，我將展示這些濾波器的外觀，並給出如何使它們變得更好的想法。

3 是什麼使神經網絡成為圖神經網絡

您知道經典神經網絡是如何工作的，對嗎？ 我們有一些C維特徵X作為網絡的輸入。 使用我們正在運行的MNIST示例，X將成為我們的C = 784維像素特徵（即“展平”的圖像）。 這些特徵乘以我們在訓練期間更新的C×F維度權重W，以使輸出更接近我們的期望。 結果可以直接用於解決任務（例如，在迴歸的情況下），也可以進一步饋入某種非線性（激活），如ReLU或其他可微分（或更精確地，可微分）的函數以形成多層網絡。 通常，某些層的輸出為：

MNIST中的信號是如此強大，以至於只要使用上面的公式和交叉熵損失，就可以得到91％的準確度，而沒有任何非線性和其他技巧（我使用了經過稍微修改的PyTorch示例來做到這一點）。 這種模型稱為多項式（或多類，因為我們有10類數字）邏輯迴歸。現在，我們如何把普通的神經網絡轉換成圖神經網絡呢?正如您已經知道的，GNNs背後的核心思想是通過“鄰居”進行聚合。在這裡，重要的是要理解，在許多情況下，實際上是您指定了“鄰居”.讓我們先考慮一個簡單的情況，當您得到一些圖形時。 例如，這可以是一個具有5個人的社交網絡的片段（子圖），一對節點之間的一條邊表示兩個人是否是朋友（或者其中至少一個人是這樣認為的）。 右下圖中的鄰接矩陣（通常表示為A）是一種以矩陣形式表示這些邊的方法，對於我們的深度學習框架而言非常方便。 矩陣中的黃色單元格代表邊緣，而藍色表示沒有邊緣。

現在，讓我們基於像素座標為我們的MNIST示例創建一個鄰接矩陣A（文章末尾提供了完整的代碼）：

import numpy as np
from scipy.spatial.distance import cdist
img_size = 28 # MNIST 圖片長寬
col, row = np.meshgrid(np.arange(img_size), np.arange(img_size))
coord = np.stack((col, row), axis=2).reshape(-1, 2) / img_size
dist = cdist(coord, coord) # 見左下圖
sigma = 0.2 * np.pi # 高斯分佈寬度
A = np.exp(- dist / sigma ** 2) # 見下圖中間

這是為視覺任務定義鄰接矩陣的一種典型方法，但並非唯一方法（Defferrard等，NIPS，2016； Bronstein等，2016）。 該鄰接矩陣是我們的先驗矩陣，也就是我們的歸納偏差，我們根據直覺將附近的像素連接在一起，而遠端像素則不應該或應該具有非常薄的邊緣（較小的邊緣），以此強加給模型。 這是由於觀察的結果，即在自然圖像中，附近的像素通常對應於同一對象或頻繁交互的對象（我們在第2.1節中提到的局部性原理），因此連接此類像素非常有意義。

因此，現在，不僅有特徵X，我們還有一些花哨的矩陣A，其值在[0,1]範圍內。 重要的是要注意，一旦我們知道輸入是一個圖，我們就假定沒有規範的節點順序在數據集中的所有其他圖上都是一致的。 就圖像而言，這意味著假定像素是隨機混洗的。 在實踐中，找到節點的規範順序在組合上是無法解決的。 即使從技術上來說，對於MNIST，我們可以通過知道此順序來作弊（因為數據最初來自常規網格），但它不適用於實際的圖數據集。

請記住，我們的特徵矩陣X具有行和C列。 因此，就圖形而言，每一行對應一個節點，C是節點特徵的維數。 但是現在的問題是我們不知道節點的順序，所以我們不知道將特定節點的特徵放在哪一行。 如果我們只是假裝忽略此問題並像以前一樣直接將X饋送到MLP，則效果將與饋送具有隨機混排像素的圖像相同，並且每個圖像具有獨立的（每個時期都相同）混排！ 令人驚訝的是，神經網絡原則上仍可以擬合此類隨機數據（Zhang等人，ICLR，2017年），但是測試性能將接近於隨機預測。 解決方案之一是通過以下方式簡單地使用我們之前創建的鄰接矩陣A

我們只需要確保A中的第i行對應於X中第i行中的節點的特徵即可。在這裡，我使用而不是普通的A，因為您經常要對A進行歸一化。如果= A，則矩陣乘法 X 相當於對鄰居的特徵求和，這在許多任務中很有用（Xu et al。，ICLR，2019）。 最常見的是對它進行歸一化，以便X對鄰居的特徵取平均，即= A /ΣᵢAᵢ。 可以在（Kipf＆Welling，ICLR，2017）中找到標準化矩陣A的更好方法。

以下是根據PyTorch代碼對NN和GNN進行的比較：

import torch
import torch.nn as nn
C = 2 # 輸入要素維數
F = 8 # 輸出要素維數
W = nn.Linear(in_features=C, out_features=F) # 可訓練的重量
# 全連接層
X = torch.randn(1, C) # 輸 入特徵
Z = W(X) # 輸出特徵 : torch.Size([1, 8])
#G圖神經網絡層
N = 6 # Number of nodes in a graph
X = torch.randn(N, C) # 輸入特徵
A = torch.rand(N, N) # 鄰接矩陣 (圖中的邊)
Z = W(torch.mm(A, X)) # 輸出特徵: torch.Size([6, 8])

https://github.com/bknyaz/examples/blob/master/fc_vs_graph_train.py是完整的PyTorch代碼，可以訓練以上兩種模型： python mnistfc.py --model fc 來訓練神經網絡; python mnistfc.py --model graph 來訓練圖神經網絡，作為練習，嘗試隨機調整圖神經網絡代碼中的像素，不要忘記以相同的方式調整矩陣A，並確保它不會影響結果。

運行代碼後，您可能會注意到分類精度實際上是相同的。 有什麼問題？ 圖形網絡不是應該更好地工作嗎？ 好吧，在許多情況下都是這樣。 但不是在這一本書中，因為我們添加的X⁽ˡ⁾運算符實際上不算什麼，而是一個高斯濾波器：

因此，我們的圖神經網絡等效於帶有單個高斯濾波器的卷積神經網絡，我們在訓練期間從不更新，其次是完全連接的層。 該濾鏡基本上可以模糊/平滑圖像，這並不是一件特別有用的事情（請參見右上方的圖像）。 但是，這是圖神經網絡的最簡單變體，但它在圖結構化數據上的效果很好。 為了使GNN在圖像之類的規則圖上更好地工作，我們需要應用許多技巧。 例如，代替使用預定義的高斯濾波器，我們可以學習使用類似這樣的微分函數來預測任意一對像素之間的邊緣：

import torch.nn as nn # 使用 PyTorch
nn.Sequential(nn.Linear(4, 64), # 將座標映射到隱藏層
 nn.ReLU(), # 非線性
 nn.Linear(64, 1), # 將隱藏的表示映射到邊緣
 nn.Tanh()) # 將邊值壓縮為[-1，1]

為了使GNN在圖像之類的規則圖上更好地工作，我們需要應用許多技巧。例如，代替使用預定義的高斯濾波器，我們可以學習預測任何一對像素之間的邊緣

這個想法類似於動態過濾器網絡（Brabander等，NIPS，2016），邊緣條件圖網絡（ECC，Simonovsky＆Komodakis，CVPR，2017）和（Knyazev等，NeurIPS-W，2018）。要使用我的代碼進行嘗試,您只需要添加--prededge標誌，因此整個命令是python mnistfc.py --model graph --pred_edge. 下面，我顯示了預定義的高斯和學習濾波器的動畫。 您可能會注意到，我們剛剛學習的過濾器（在中間）看起來很奇怪。 這是因為任務很複雜，因為我們同時優化了兩個模型：預測邊緣的模型和預測數字類的模型。 要學習更好的過濾器（如右邊的過濾器），我們需要應用BMVC論文中的其他技巧，而這超出了本教程的範圍。

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

import imageio # to save GIFs
import matplotlib as mpl
import matplotlib.pyplot as plt
import numpy as np
from scipy.spatial.distance import cdist
import cv2 # 可選 (調整濾波器大小以使其看起來更好)
img_size = 28
# 創建/加載一些鄰接矩陣A(例如，基於座標)
col, row = np.meshgrid(np.arange(img_size), np.arange(img_size))
coord = np.stack((col, row), axis=2).reshape(-1, 2) / img_size
dist = cdist(coord, coord) # 所有像素對之間的距離
sigma = 0.2 * np.pi # 高斯寬度 (訓練模型時可以是超參數)
A = np.exp(- dist / sigma ** 2) # 空間相似度鄰接矩陣
scale = 4
img_list = []
cmap = mpl.cm.get_cmap('viridis')
for i in np.arange(0, img_size, 4): # 對於第4步的每一行
 for j in np.arange(0, img_size, 4): # 對於第4步中的每個col
 k = i*img_size + j
 img = A[k, :].reshape(img_size, img_size)
 img = (img - img.min()) / (img.max() - img.min())
 img = cmap(img)
 img[i, j] = np.array([1., 0, 0, 0]) # 加紅點
 img = cv2.resize(img, (img_size*scale, img_size*scale))
 img_list.append((img * 255).astype(np.uint8))
imageio.mimsave('filter.gif', img_list, format='GIF', duration=0.2)

我還分享了一個https://nbviewer.jupyter.org/github/bknyaz/examples/blob/master/2d_convolution.ipynb，該筆記本顯示了使用Gabor濾波器對圖像進行2D卷積的圖表（使用鄰接矩陣）與使用循環矩陣的情況（通常用於信號處理）的對比.

在本教程的https://towardsdatascience.com/tutorial-on-graph-neural-networks-for-computer-vision-and-beyond-part-2-be6d71d70f49中，我將介紹能夠在圖上生成更好的過濾器的更高級的圖層.

結語

Graph Neural Networks是一個非常靈活和有趣的神經網絡系列，可以應用於真正的複雜數據。 與往常一樣，這種靈活性必須付出一定的代價。 在GNN的情況下，很難通過將此類算子定義為卷積來規範化模型。 朝著這個方向的研究正在迅速發展，因此GNN將在越來越廣泛的機器學習和計算機視覺領域中得到應用。