# 【論文筆記】Graph Neural Networks are Inherently Good Generalizers: Insights by Bridging GNNs and MLPs

論文連結：https://arxiv.org/abs/2212.09034
發表於 ICLR 2023

## Overview
本篇論文透過實驗，指出 GNN 在 node-level 預測任務上表現良好的原因主要因為 GNN 本身的 generalization 能力，而非 expressivity。
- Expressivity：指模型在訓練集上學習 representation 的能力
- Generalization：指模型泛化到新數據的能力，可以用測試集和訓練集兩者的 loss 之間的差異來表示

作者設計了一個新的模型架構 PMLP (Propagational MLP)，這個模型在訓練階段和一般的 MLP 相同，但在測試階段加入了 GNN 的 message passing layers。他們將 PMLP 訓練於各種 node classification benchmarks 上，發現以下兩個現象：
1. PMLP 在測試集上表現比 MLP 來得好
因為 PMLP 和 MLP 共享相同的 model weight，差別只在於測試階段有沒有使用 message passing，因此第一個觀察告訴我們 **message passing 可以提升模型的 generalization 能力**。
3. PMLP 表現與 GNN 相當或甚至更好
PMLP 和 GNN 在訓練時使用的模型架構是有差異的，卻可以得到差不多的表現，反之 PMLP 和 MLP 在訓練集上表達能力相同，測試集上表現卻不同，因此我們可以總結，**GNN 表現比 MLP 好的主要原因是 GNN 的 generalization 能力**。


## Model Formulation

GNN 架構一般而言可以拆解成兩個部分，分別是 message-passing (MP) operation 和 feed-forward (FF) operation：

$$
\text{MP}: \tilde{h}^{(l-1)}_u = \sum_{v \in N_u \cup \{u\}} a_{u, v} \cdot h^{(l-1)}_v
$$

$$
\text{FF}: h^{(l)}_u = \psi^{(l)}(\tilde{h}^{(l-1)}_u)
$$

其中 $a_{u, v}$ 是 aggregation function ，用以將鄰居節點的訊息聚集，可以是任易形式的的。

而 MLP 其實就是忽略 message-passing，將一系列的 feed-forward layers 串接在一起得到的模型：
$$
\hat{y}_u = \psi^{(L)}(...(\psi^{(1)}(x_u))) = \psi(x_u)
$$

論文中提出的模型 PMLP，具有和 MLP 完全相同的 feed-forward 架構，然而在測試階段，會加上 non-parametric message-passing layers。下表總結了對應不同種類的 GNN 所設計出來的 PMLP 在訓練和測試階段的架構。


## Evaluation

作者在 node-level prediction benchmarks 上進行實驗，為了公平起見，同一個 dataset 的 GNN、MLP 和 PMLP 會使用相同的 layer 數量和 hidden dimension。下表顯示各種模型的 testing accuracy，可以看到無論是哪種變形的 PMLP，表現都比 MLP 來得好，這個發現告訴我們 message passing 的確對 generalization 有貢獻。另外我們也可以看到 PMLP 可以有和 GNN 差不多的表現，暗示說 GNN 表現優於 MLP 最主要是源自於 message passing 所帶來的 generalization 能力。


下面的實驗使用更為龐大的 dataset。從結果可以看到 PMLP 依然表現比 MLP 來得好，然而和 GNN 之間卻有一些差距，作者推測這可能是因為對於大的 dataset 而言，節點之間的關係可能會更加複雜，就會需要更 expressive 的模型架構來去學習節點的 representation。這個想法也可以透過 train loss 來印證，可以看到 GNN 的 train loss 比起 PMLP 來得低許多。


## Discussions
為了要印證以上的發現在不同 model setting 之下都可以成立，以下又進行了各種實驗：

下面的實驗探討不同 number of layers 和 size hidden dimension 對結果的影響，可以看到 GNN、PMLP 和 MLP 三者表現的相對高低和 layers 或 hidden dimension 數量是無關的。


下圖（左）探討 training proportion 對結果的影響，可以看到這個因素和三者的相對表現也是無關的。

下圖（中）探討 graph sparsity 對結果的影響，隨著 graph sparsity ratio 變高，GNN 和 PMLP 的 testing accuracy 下降了，也就是說 graph 的品質的確會影響 testing result，但兩者之間的相對關係是沒有改變的。

下圖（右）的實驗加入了隨機的 edge 到 graph 中。如果加入隨機的 edge 到 graph 之中，GNN 和 PMLP 的表現都會下降，但 PMLP 對這些 noise 的忍受度較高。這是因為 PMLP 在訓練階段是不會受到 noise 的影響，但這些 noisy edge 對 GNN 的訓練和測試都會有影響。


## Practical Significance
作者指出 PMLP 可以作為一個新的模型架構進行使用：
- PMLP 表現和 GNN 差不多，但在訓練時可以比 GNN 快上 5~17 倍，更有效率
- 根據先前實驗結果，PMLP 更能忍受 noisy edges
- PMLP 因為連結了 MLP 和 GNN 之間的關係，也可以用在研究 GNN-related problems