深度學習在圖像分類，機器翻譯等領域都展示了其強大的能力，但是在因果推理方面，深度學習依然是短板。圖神經網絡在因果推理方面有巨大的潛力，有望成為 AI 的下一個拐點。本文將深入了解圖神經網絡背后的原理和其強大的表征能力。

圖神經網絡（GNNs）廣泛應用于圖的表征學習，其遵循鄰域聚合框架，通過遞歸聚合和轉換相鄰節點的特征向量來計算節點的表征向量。已經提出了許多 GNN 的變體，并在節點和圖形分類任務上取得比較好的結果。然而，盡管 GNN 使圖形表征學習發生了革命性的變化，但是，對其表示屬性和局限性的理解還很有限。

本文譯介自MIT、斯坦福大學的ICLR-19論文：HOW POWERFUL ARE GRAPH NEURAL NETWORKS。

論文地址：https://arxiv.org/pdf/1810.00826.pdf

論文提出了一個在分析 GNN 捕獲不同圖結構表現力的理論框架。本論文描述了各種流行的 GNN 變體的判別能力，如 Graph Convolutional Networks (圖卷積神經網絡) 和 GraphSAGE，并表明他們無法學會區分某些簡單的圖結構。然后，本論文開發了一個簡單的體系結構，可以證明其在 GNNs 類中是最具表現力的，并且它和 Weisfeiler-Lehman (圖同構測試) 方法一樣強大。在許多圖分類基準測試上，通過經驗驗證了該理論發現，并證明本論文的模型達到了最佳的性能。

介紹

學習圖結構數據，例如：分子、社會、生物和金融網絡等，需要有效的表征圖的結構。最近，研究者們對使用Graph Neural Network (GNN)方法來對圖進行表征學習產生了極大的興趣。GNN 大部分都遵循循環遞歸鄰域聚合（或者消息傳遞）的模式，其中每個節點聚合其相鄰節點的特征向量以計算其新的特征向量。在 k 輪聚合迭代后，通過其轉換的特征向量來表示該節點，該向量捕獲節點的 k-hop 網絡鄰節點的結構信息。然后，可以通過 pooling 來獲得整個圖結構的表征，例如對圖中所有節點的表征向量求和。許多基于不同 neighborhod aggregation 的 GNN 變體和 graph-level 的 pooling scheme 已經被許多學者提出。

根據經驗，這些 GNNs 已經在許多任務中達到最佳的性能，如節點分類，鏈接預測和圖分類。然而，新 GNN 的設計主要是基于經驗直覺，啟發式和實驗試錯。對于 GNN 的性質和局限性，目前理論層面的解釋還比較少。GNN 的表征能力的正式分析還是有限的。

本論文提出了一個分析 GNN 表征能力的理論框架。從形式上描述了不同 GNN 變體在學習表征和區分各種圖結構方面的表現力。該框架是受 GNNs 和 WL 測試（Weisfeiler-Lehman 圖同構測試）緊密聯系的啟發，WL 測試是以其強大的區分各種圖結構能力而聞名。與 GNNs 相似，WL 測試通過聚合給定節點的鄰近節點的特征向量迭代更新其特征向量。WL 測試的強大之處是其注入聚合（injective aggregation）更新，它映射不同節點的鄰近節點到不同的特征向量。主要觀點是，如果 GNN 的聚合模式具有高度的表現力和能夠為注入函數建模的話，它就同 WL 測試一樣具有強大的區分能力。

為了數學形式化上述觀點，首先抽象出一個節點的鄰近節點的特征向量作為多重集，該集合中可能有重復元素。然后，在 GNNS 中的領域聚合（neighbor aggregation）可以抽象為多集上的函數。我們嚴格學習不同多集函數的變體，并從理論上描述其識別能力，即不同的聚合函數可以區分不同的多重集。越具有區分力的多重集函數，GNN 的潛在表征能力就越強。

本論文的主要結果總結如下：

1）我們發現在區分圖結構方面，GNN 跟 WL 測試能力一樣強大。

2）我們發現在建立領域聚合（neighbor aggregation）和圖池函數（graph pooling）的情況下，得到的 GNN 和 WL 測試一樣強大。

3）我們識別無法通過流行的 GNN 變體區分的圖結構，例如 GCN（Kipf＆Welling，2017）和 GraphSAGE（Hamilton 等，2017a），并且我們對基于 GNN 模型可以捕獲的各種圖結構進行了精確的描述。

4）我們開發了一個簡單的神經網絡架構，圖同構網絡（Graph Isomorphism Network）GIN，并證明其判別 / 表征能力等同于 WL 測試。

在圖分類數據集上，通過實驗驗證我們的理論，其中 GNN 的表達能力對于捕獲圖結構至關重要。特別是，我們對基于各種聚合函數的 GNN 性能進行了對比。我們的結果證實了最強大的 GNN（我們的圖同構網絡 GIN）具有很強的表征能力，可以近乎完美的擬合訓練數據，然而較弱的 GNN 變體有嚴重的欠擬合問題。此外，在許多圖分類的基準測試集上，它的表征能力和性能優于其他的 GNNs。

預備知識

首先，我們總結一些常見的 GNN 模型，順便介紹一下相關數學符號的含義。假設 G = (V, E) 表示一個圖，圖的節點向量用 X (v) 表示，其中，v ∈ V 。有兩個比較感興趣的任務：（1）節點分類，其中每個節點 v ∈ V 都有一個相關的標簽 y (v)，目標是學習節點 v 的表征向量 h (v)，節點 v 的標簽可以被函數 y (v)=f (h (v)) 所預測。（2）圖分類，其中給定一組圖 {G1, ..., GN }? G 及其標簽 {y1, ..., yN } ? Y，我們的目標是學習一個表征向量 h (G)，它有助于預測整個圖的標簽 y (G) = g (h (G))。

圖神經網絡

GNNs 利用圖結構和節點特征 X (v) 來學習一個節點的表征向量 h (v)，或者整個圖的表征向量 h (G)。

新式的 GNNs 都遵循領域聚合（neighborhood aggregation）策略，其中我們通過聚合它的鄰近節點的表征向量來迭代更新節點的表征向量。在 k 次迭代后，節點的表征可以在它的 k-hop 網絡鄰居中捕獲結構信息。形式上，GNN 的第 k 層是：

其中，h {k}(v) 是節點 v 在第 k 的迭代 / 層的特征向量。我們初始化 h {0}(v)=X (v)，N (v) 是與 v 節點鄰近的一組節點。在 GNNs 中選擇函數 AGGREGATE {k}(?) 和 COMBINE {k}(?) 非常關鍵。已經提出了許多用于聚合的體系結構。在 GraphSAGE 的 pooling 變體（Hamilton et al., 2017a），AGGREGATE 函數形式如下：

其中，W 是可以學習的矩陣，MAX 表示一個 element-wise 的 max-pooling。在 GraphSAGE 的 COMBINE 步是一個線性映射的連接 W?[h {k-1}(v)|a {k}(v)]。在圖卷積網絡中（GCN）(Kipf & Welling, 2017)，element-wise 的 mean pooling 被替代，AGGREGATE 和 COMBINE 步集成在一體如下：

許多其他的 GNNs 可以類似的表示為 Eq. 2.1 (Xu et al., 2018; Gilmer et al., 2017)。

對于節點分類問題，最后一次迭代的節點表征向量 h {K}(v) 用來做預測。對于圖分類問題，READOUT 函數從最后一次迭代中聚合節點特征來獲取整個圖的表征向量 h (G)：

READOUT 函數可以是一個簡單的置換不變函數，例如求和或者 graph-level 級別的 pooling 函數 (Ying et al., 2018; Zhang et al., 2018)。

Weisfeiler-Lehman 測試

圖同構問題指的是驗證兩個圖在拓撲結構上是否相同。這是一個具有挑戰性的問題：因為現在很難知道計算的時間復雜度。WL（Weisfeiler-Lehman）測試是一種非常有效的一測試圖同構的方法，它可以區分各種圖。

在 1 維的情況下，它類似于在 GNN 中的領域聚合。假設每個節點都有一個分類標簽，WL 測試（1）迭代聚合節點標簽和他們的鄰近節點，（2）將聚合的標簽 hash 成唯一的新標簽。如果在某些迭代中兩個圖的節點標簽不同，則該算法判定它們是不同的。

基于 WL 試驗，Shervashidze 等人（2011）提出了 WL 子樹內核來測量圖之間的相似性。內核使用在 WL 測試不同迭代中的節點標簽計數作為圖的特征向量。直觀的來看，在 WL 測試的第 k 次迭代中，一個節點的標簽表征該根節點的高度為 k 的子樹結構（Figure 1）。因此，WL 子樹所考慮的圖的特征本質上是圖中不同根子樹的計數。

理論框架：概述

我們首先概述了分析 GNNs 表達能力的框架。GNN 遞歸地更新每個節點的特征向量，以捕獲其周圍其他節點的網絡結構和特征，即其根子樹結構（圖 1）。在本文中，我們假設節點輸入特征是一個宇宙內可數的數。對于有限圖，我們可以遞歸地證明在任何固定模型的深層節點特征向量也是一個宇宙內可數的數。為了簡化符號，我們可以為每個特征向量分配一個唯一的標簽∈{a，b，c……}。 然后，一組相鄰節點的特征向量形成多重集：同一元素可以出現多次，因為不同的節點可以具有相同的特征向量。

多重集定義：多重集是集合的一個廣義概念，它允許其元素有多個實例。更正式地講，多重集是一個二元組 X =（S，m），其中 S 是由其不同元素組成的 X 的基礎集合，而 m：S→N (≥1) 給出了元素的多樣性。

為了分析 GNN 的表達能力，我們分析了 GNN 何時將兩個節點映射到嵌入空間中的相同位置。直觀地說，最強大的 GNN 僅當兩個節點具有相同的子樹結構，并且在對應的節點上具有相同的特征時，才會將它們映射到相同的位置。由于子樹結構是通過節點鄰域遞歸定義的（圖 1），因此當 GNN 將兩個鄰域映射到相同的嵌入時，我們可以遞歸地減少我們的分析。最強大的 GNN 永遠不會將兩個不同的鄰域（即，特征向量的多重集）映射到相同的位置。這意味著它的聚合方案是單射的。 因此，我們將 GNN 的聚合方案抽象為其神經網絡可以表示的多重集合上的一類函數，并分析它們是否能夠表示單射的多重集函數。

接下來，我們使用這種推理開發一個最強大的 GNN。 在第 5 節中，我們研究了流行的 GNN 變體，并發現它們的聚合方案本質上不是單射的，因此功能較弱，但它們可以捕獲圖形的其他有趣屬性。

構建強大的圖神經網絡

理想情況下，GNN 能夠（1）通過將它們映射到嵌入空間中的不同位置來區分不同的圖結構，以及（2）在嵌入空間中捕獲它們的結構相似性。在本文中，我們主要關注第一部分，我們將簡要討論第二部分。然而，將不同的圖映射到不同的嵌入空間的能力意味著可以解決圖同構問題。

在我們的分析中，通過一個稍微弱一點的標準來描述 GNN 的表達能力：魏斯費勒 - 雷曼（WL）圖同構測試，除少數特例外，該測試通常工作得很好，特別是規則圖（Cai 等人，1992；Douglas，2011；Evdokimov&Ponomarenko，1999）。

引理 2. 設 G1 和 G2 為任何非同構圖。如果一個圖神經網絡 A: G → R (d) 遵循領域聚合方案，將 G1 和 G2 映射到不同的嵌入，Weisfeiler-Lehman 圖同構檢驗也判定 G1 和 G2 不是同構的。

因此，在區分不同圖方面任何基于聚合的 GNN 都至多與 WL 測試一樣強大。一個自然的問題是，在原則上是否存與 WL 測試一樣強大的 GNN？ 我們在定理 3 中得到的答案是肯定的：如果鄰居聚合和圖池化函數是單射的，那么得到的 GNN 就像 WL 測試一樣強大。

定理 3.設 A：G→R (d) 是一個遵循鄰域聚合方案的 GNN。 通過足夠的迭代，如果滿足以下條件，則 A 可以將通過 Weisfeiler-Lehman 測試的圖 G1 和 G2 為非同構圖映射到不同的嵌入：

a) A 每次迭代聚合更新節點特征向量

b）A 的圖級別的 readout 函數，運行在節點特征的多重集上｛h (k)(v)｝，是一個單射函數。

在可數集上，單射性很好地描述了一個函數是否保留了輸入的區別性。在不可數集上，節點特征是連續的，內射性和判別性的概念被 “削弱”。在本文中，我們假設輸入節點特征來自可數集。鑒于輸入節點特征的可計數性假設，人們可能會問，GNN 更深層的節點特征的可數性是否仍然適用？ 引理 4 表示是，即可數性可以跨層傳播。

引理 4. 假設輸入特征空間 X 是可數的，g (k) 是由 GNN 的第 k 層參數化的函數，k=1,..,L。其中，g (1) 被定義在有限多重集 X ? X 上，g (k) 的范圍，節點的隱含特征 h {k}(v) 空間，在 k=1,...,L 都是可數的。

在這里，除了區分不同的圖之外，還值得討論 GNN 的一個重要好處，也就是說，捕捉圖結構的相似性。注意，WL 測試中的節點特征向量本質上是一種獨熱編碼（one-hot 編碼），因此不能捕獲子樹之間的相似性。相反，滿足定理 3 標準的 GNN，通過學習將子樹嵌入低維空間來推廣 WL 測試。這使得 GNN 不僅可以區分不同的結構，而且可以學習將相似的圖結構映射到相似的嵌入，并捕獲圖結構之間的依賴關系。捕捉節點標簽的結構相似性對泛化有幫助，特別是在不同的圖中當子樹的共現稀疏或存在噪聲邊和節點特征時（Yanardag 和 Vishwanathan，2015）。

圖異構網絡（GIN）

接下來，我們開發了一個可證明滿足定理 3 中條件的模型，從而推廣了 WL 測試。 我們將結果體系結構命名為 Graph Isomorphism Network（GIN）。為了模擬領域聚合的單射多重集函數，我們發展了一個 “深多重集” 的理論，即用神經網絡參數化通用多重集函數。我們的下一個引理表明，求和聚合器可以代表多重集合的單射，事實上，是多重集上的通用函數。

引理 5. 定義如下：

該引理擴展了設置 (Zaheer et al., 2017) 從集合到多重集。深多重集和集合之間的一個重要區別是某些單射集合函數，例如均值聚合器，不是多重集函數。利用引理 5 中通用多重集函數的建模機制作為構建塊，現在我們提出一種聚合方案，可以表示節點對和其鄰居的多重集合上的通用函數，從而滿足定理 3a 中的單射性條件。 我們的下一個推論在許多這樣的聚合方案中提供了簡單而具體的公式。

推論 6. 定義如下：

由于通用逼近定理（Hornik 等，1989; Hornik，1991），我們可以使用多層感知器（MLP）來推導和學習推論 6 中的 f 和 φ，在實際應用中，我們用一個 MLP 對 f (k+1) ? φ (k) 進行建模，因為 MLP 可以表示函數的組成。在第一個迭代中，如果輸入特征是一個熱編碼，那么在求和之前不需要 MLP，因為它們的求和是單射的。我們可以制作一個可學習的參數或固定的標量。然后，GIN 更新節點表征如下：

通常，可能存在許多其他強大的 GNNs。 雖然 GIN 很簡單，但是它是最強大的 GNN 中的一個。

讀取不同部分的子樹結構

圖級讀出（readout）的一個重要方面是，隨著迭代次數的增加，對應于子樹結構的節點表征變得更加精細和全局。足夠數量的迭代是實現良好區分力的關鍵。 然而，特征的早期迭代有時可能更好地泛化。為了考慮所有的結構信息，GIN 從模型的所有深度 / 迭代使用信息。 我們通過類似于跳躍知識網絡（JK-Nets）（Xu 等人，2018）的架構來實現這一點，其中在所有的迭代中我們使用連接后的圖的表征向量替換了 Eq.2.4：

根據定理 3 和推論 6，如果 GIN 使用對來自相同迭代的所有節點特征求和來取代 Eq.4.2 中的 READOUT（在求和之前我們不需要額外的 MLP，原因與方程 4.1 相同），它可以推廣 WL 測試和 WL 子樹核。

能力不強但仍然有趣的其他 GNNs

接下來我們研究不滿足定理 3 中條件的 GNN，包括GCN（Kipf＆Welling，2017）和GraphSAGE（Hamilton 等，2017a）。

我們對 Eq. 4.1 中聚合器的兩個方面進行消融研究：（1）使用 1 層的感知器代替 MLP；（2）利用平均或最大池而不是求和。

令人驚訝的是我們觀察到這些 GNN 變體被簡單的圖所迷惑，并且沒有 WL 測試強大。 盡管如此，使用平均聚合器的模型像 GCN 在節點分類任務中還是表現良好。 為了更好地理解這一點，我們精確地描述了不同 GNN 變體能夠和不能夠捕獲圖的哪些內容，并討論學習圖的含義。

1- 層的感知機并不充分

引理 5 中的函數 f 有助于將不同的多重集合映射到唯一的嵌入。它可以通過 MLP 通過通用逼近定理參數化（Hornik，1991）。盡管如此，許多現有的 GNN 使用 1- 層感知器 σ°W 代替（Duvenaud 等人，2015; Kipf＆Welling，2017; Zhang 等人，2018），線性映射后跟非線性激活函數，如 ReLU。 這種 1- 層映射是廣義線性模型的例子（Nelder＆Wedderburn，1972）。因此，我們對了解 1- 層感知器是否足以進行圖學習非常感興趣。引理 7 表明確實存在網絡鄰域（多重集合），具有 1- 層感知器的模型永遠無法區分。

引理 7. 定義如下：

引理 7 證明的主要思想是 1 層感知器的行為很像線性映射，因此 GNN 層退化為簡單地對鄰域特征求和。我們的證據建立在線性映射中缺少偏差項的事實上。利用偏差項和足夠大的輸出維數，1- 層感知器可能能夠區分不同的多重集。 盡管如此，與使用 MLP 的模型不同，1- 層感知器（即使具有偏置項）也不是多重集函數的通用逼近器。

因此，即使具有 1- 層感知器的 GNN 在某種程度上可以將不同的圖嵌入到不同的位置，這種嵌入也可能不能充分地捕獲結構相似性，并且對于簡單的分類器（例如，線性分類器）來說可能難以擬合。 在第 7 節中，我們將憑經驗看到具有 1- 層感知器的 GNN，當應用于圖分類時，有時會嚴重欠擬合，并且在測試精度方面通常表現不及 MLP 的 GNN。

混淆平均值和最大池的結構

如果我們將 h (X)=sum (f (x)) ，其中 x∈X，中的求和替換為 GCN 和 GraphSAGE 中的均值或最大池，會發生什么？平均和最大池聚合器仍然是定義良好的多重集函數，因為它們是置換不變的。但是，它們不是單射的。

圖 2 根據三個聚合器的表示能力對其進行排序，圖 3 說明了平均池和最大池聚合器對結構對無法區分。在這里，節點顏色表示不同的節點特征，我們假設 GNN 在將它們與中心節點組合之前先聚合鄰居。

在圖 3a 中，每個節點具有相同的特征 a，并且 f (a) 在所有節點上是相同的（對于任何函數 f）。當執行鄰域聚合時，f (a) 上的均值或最大值仍為 f (a)，并且通過歸納，我們總是在任何地方獲得相同的節點表示。因此，均值和最大池聚合器無法捕獲任何結構信息。相反，求和聚合器可以區分結構，因為 2?f (a) 和 3?f (a) 給出了不同的值。相同的參數可以應用于任何未標記的圖。如果節點度不是常量值，則可以用作節點輸入特征，原則上，均值可以覆蓋求，但最大池不能。

圖 3a 表明均值和最大值難以區分具有重復特征的節點的圖。假設 h (color)（r 代表紅色，g 代表綠色）表示由 f 轉換后的節點特征。圖 3b 顯示藍色節點附近的最大值產生 max (h (g),h (r)) 和 max (h (g),h (r),h (r))，這兩個值折疊成相同的表示。因此，最大池無法區分它們。相比之下，求和聚合器仍然有效，因為 1/2*(h (g)+h (r)) 和 1/3*(h (g)+h (r)+h (r)) 通常是不等同的。同樣地，在圖 3c 中，平均值和最大值均為失敗 1/2*(h (g)+h (r)) 和 1/4*(h (g)+h (g)+h (r)+h (r))。

平均學習分布

為了描述平均聚合器可以區分多重集的類，考慮示例 X1 = (S, m) and X2 = (S, k?m)，其中 X1 和 X2 具有相同的一組不同元素的集合，但 X2 包含 X1 的每個元素的 k 個副本。任何平均聚合器都將 X1 和 X2 映射到相同的嵌入，因為它只需要對單個元素的特征取平均值。因此，平均值可以捕獲多重集中元素的分布（或者比例），而不是精確的多重集。

推論 8.定義如下：

對于任務而言，如果圖中的統計和分布信息比精確的結構更為重要，則平均聚合器可能表現良好。此外，當節點特征多樣且很少重復時，平均聚合器與求和聚合器一樣強大。這就可以解釋為什么，盡管存在第 5.2 節中提到的一些限制，但帶有平均聚合器的 GNN 對于節點分類任務還是有效，例如對文章主題進行分類和社區檢測，其中節點特征豐富，并且鄰域特征的分布為任務提供了一個強有力的信號。

具有不同元素的最大池學習集

圖 3 中的示例說明最大池認為具有相同的特征的多個節點僅為一個節點（即，將多重集合視為一個集合）。 最大池不捕獲確切的結構和分布。 但是，它可能適用于某些識別任務，這些任務中識別元素或 “骨架” 更重要，而不是區分確切的結構或分布。（ 齊等人.2017）憑經驗表明，最大池聚合器學習識別 3D 點云的骨架，并且它對噪聲和異常值具有魯棒性。 為了完整起見，下一個推論顯示最大池聚合器捕獲多重集的基礎集。

推論 9. 定義如下

實驗設置

我們評估和比較 GIN 和不太強大的 GNN 變體的訓練和測試性能。

數據集

我們使用 9 個圖分類基準：4 個生物信息學數據集（MUTAG，PTC，NCI1，PROTEINS）和 5 個社交網絡數據集（COLLAB，IMDB-BINARY，IMDB-MULTI，REDDIT-BINARY 和 REDDIT-MULTI5K）（Yanardag＆Vishwanathan，2015）。

在生物信息圖中，節點具有分類輸入特征；在社交網絡中，它們沒有任何特征。 對于 REDDIT 數據集，我們將所有節點特征向量設置為相同（因此，這里的特征是無信息的）; 對于其他社交圖，我們使用節點度的獨熱編碼。

模型和配置

我們評估 GIN（方程 4.1 和 4.2）和不太強大的 GNN 變體。在 GIN 框架下，我們考慮兩種變體：1）通過梯度下降，學習方程式 4.1 中的 ε 的 GIN，我們稱之為 GIN-ε；（2）更簡單（稍微不那么強大）的 GIN，其中 ε 在方程式中 4.1 固定為 0，我們稱之為 GIN-0。

正如我們將要看到的，GIN-0 顯示出強大的經驗性能：GIN-0 不僅與 GIN-ε 一樣擬合的訓練數據好，它還表現出良好的泛化性，在測試精度方面略微但始終優于 GIN-ε。對于能力較弱的 GNN 變體，我們考慮使用 mean 或 max-pooling 替換 GIN-0 聚合中的求和的架構，或者用 1- 層感知器替換 MLP，即線性映射后面接 ReLU。在圖 4 和表 1 中，模型由它使用的聚合器 / 感知器命名。我們對 GIN 和所有 GNN 變體應用相同的圖級 readout（公式 4.2 中的 READOUT），特別是生物信息學數據集的求和 readout 以及由于更好的測試性能而在社交數據集上的平均 readout。

以下（Yanardag＆Vishwanathan，2015; Niepert 等，2016），我們使用 LIB-SVM 進行 10 倍交叉驗證（Chang＆Lin，2011）。我們公布了通過 cv 進行的 10- 交叉驗證 validate 集的準確度的平均值和標準差。對于所有的配置，應用 5 個 GNN 層（包括輸入層），并且所有 MLP 具有 2 個層。BN 標準化（Ioffe＆Szegedy，2015）應用于每個隱藏層。我們使用 Adam 優化器（Kingma＆Ba，2015），初始學習率為 0.01，并且每 50 個 epochs 將學習率衰減 0.5。我們針對每個數據集調優的超參數是：（1）生物信息圖的 hidden units 的大小∈{16,32} 和社交圖的大小為 64; （2）批量大小（batch size）∈{32,128}; （3）在 dense 層后，dropout 率∈{0,0.5}（Srivastava 等，2014）; （4）epochs 的數量。

基準線

我們將上面的 GNN 與一些性能最佳的圖分類基線進行了比較：

（1）WL 子樹內核（Shervashidze 等，2011），其中使用了 C-SVM（Chang&Lin，2011） 作為分類器。 我們調優的超參數是 SVM 中的 C 和 WL 迭代的數量∈{1,2，...，6};

（2）性能最佳的深度學習架構擴散 - 卷積神經網絡（DCNN）（Atwood＆Towsley，2016）、PATCHY-SAN（Niepert 等，2016）和 Deep Graph CNN（DGCNN）（Zhang et al.，2018）;

（3）Anonymous Walk Embeddings（AWL）（Ivanov＆Burnaev，2018）。

對于深度學習方法和 AWL，我們報告了原始論文中報告的準確性。

實驗結果

訓練集性能

通過比較它們的訓練精度，我們驗證了 GNNs 的強大表征能力的理論分析。圖 4 顯示了具有相同超參數設置的 GIN 和不太強大的 GNN 變種的訓練曲線。

首先，理論上最強大的 GNN，即 GIN-ε (Sum–MLP)，和 GIN-0 能夠完美擬合所有的訓練數據。在我們的實驗中，與在 GIN-0 中把 ε 固定為 0 相比，在擬合訓練數據時，用 GIN-ε 顯式學習 ε 沒有任何收益。相比之下，在許多數據集中，使用平均 / 最大池或 1- 層感知機的 GNN 變體嚴重欠擬合。特別是，訓練精度模式與我們通過模型的表征能力進行的排名一致：具有 MLP 的 GNN 變體比具有 1- 層感知器的 GNN 變體具有更高的訓練精度，具有求和聚合器的 GNN 比具有平均和最大池聚合器的 GNN 更好的擬合訓練集。

然而，在我們的數據集上，GNN 的訓練精度從未超過 WL 子樹內核的精度，后者具有與 WL 測試相同的區分能力。例如，在 IMDBBINARY 上，沒有一個模型能夠完全擬合訓練集，而且 GNN 最多能達到與 wl 內核相同的訓練精度。此模式與我們的結果一致，即 WL 測試為基于聚合的 GNN 的表示能力提供了一個上限。我們的理論結果集中在表征能力上，還沒有考慮到優化（例如局部極小）。盡管如此，實驗結果與我們的理論非常吻合。

測試集性能

接下來，我們比較測試集精度。雖然我們的理論結果并不能直接說明 GNN 的泛化能力，但有理由期待具有較強表達力的 GNN 能夠準確地捕獲感興趣的圖結構，因此泛化能力非常好。表 1 比較了 GINs (SUM-MLP)、其他 GNN 變種以及最佳基準線的測試精度。

結論

在本文中，我們建立了 GNN 表達能力推理的理論基礎，并對流行的 GNN 變體的表達能力進行了嚴格的論證。在此過程中，我們還在鄰域聚合框架下設計了一個可以證明是最強大的 GNN。未來工作的一個有趣方向是超越鄰域聚合（或消息傳遞）框架，以追求更強大的圖學習架構。理解和改進 GNN 的泛化性質也是很有意思的。