論文：《HOW POWERFUL ARE GRAPH NEURAL NETWORKS？ 》
ABSTRACT
圖神經網路（GNNs）是一種有效的圖表示學習框架。GNN遵循鄰域聚合方案，透過遞迴聚合和轉換鄰域節點的表示向量來計算節點的表示向量。許多GNN變體已經被提出，並且在節點和圖分類任務上都取得了最新的結果。然而，儘管GNNs給圖形表示學習帶來了革命性的變化，但是對於它們的表示性質和侷限性的理解還是有限的。在這裡，我們提出了一個理論框架來分析GNNs捕捉不同圖形結構的表現力。我們的結果描述了流行的GNN變體，如圖卷積網路和GraphSAGE的辨別能力，並且表明它們不能學習辨別某些簡單的圖結構。然後，我們開發了一個簡單的體系結構，它可以證明是GNNs類中最具表現力的，並且與Weisfeiler-Lehman圖同構測試一樣強大。我們在一些圖形分類任務基準上實證驗證了我們的理論發現，並證明我們的模型達到了最先進的效能。
INTRODUCTION
在這裡，我們本文提出了一個分析GNNs表徵力的理論框架。我們正式地描述了不同GNN變體在學習表示和區分不同圖形結構中的表現力，受到GNNs和Weisfeiler-Lehman（WL）圖同構測試（Weisfeiler&Lehman，1968）之間的緊密聯絡的啟發，WL測試之所以如此強大，是因為它的單射聚合更新將不同的節點鄰域對映到不同的特徵向量。我們的關鍵見解是，如果GNN的聚合方案具有很強的表現力，並且可以對單射函式建模，則GNN可以具有與WL測試一樣大的判別能力。
Contributions
1） 我們證明了在區分圖結構方面，GNNs最多隻能和WL測試一樣強大。
2） 我們建立了鄰域聚集和圖形READOUT函式的條件，在這些條件下，得到的GNN與WL測試一樣強大。
3） 我們識別出了一些流行的GNN變體無法區分的圖形結構，例如GCN（Kipf&Welling，2017）和GraphSAGE（Hamilton等人，2017a），並且我們精確地描述了這些基於GNN的模型能夠捕獲的圖形結構的型別。
4） 我們開發了一個簡單的神經網路結構，圖同構網路（GIN），並證明了它的判別/表徵能力等於WL檢驗的能力。
PRELIMINARIES
GNNs 基本思想：鄰域聚集函式+更新函式
GraphSAGE 模型：
GCN模型：
對於節點分類任務來說，最後迭代的節點表示hv（K）直接用於預測。對於圖分類來說，還需要READOUT函式將節點向量轉化為影象，可以是簡單的置換不變函式如求和，或更復雜的圖形級池函式。
THEORETICAL FRAMEWORK： OVERVIEW
為了研究GNN的表示能力，我們分析了什麼時候GNN會將兩個節點對映到嵌入空間中的同一位置。直觀地說，一個最強大的GNN，只有當兩個節點具有相同的子樹結構，而且子樹結構在相應的節點上具有相同的特徵時，才會對映兩個節點到相同的位置。由於子樹結構是透過節點鄰域遞迴定義的（圖1），我們可以將分析簡化為一個GNN是否將兩個鄰域（即兩個多集）對映到同一個嵌入或表示的問題。一個最強大的GNN將從不對映兩個不同的鄰域，即多個特徵向量集，到相同的表示。這意味著它的聚合方案必須是單射的。因此，我們將GNN的聚合方案抽象為其神經網路能夠表示的多集上的一類函式，並分析它們對於多集是否是單射。
BUILDING POWERFUL GRAPH NEURAL NETWORKS
理想狀態成立（捕捉圖結構最強）的條件：
在GNN層數足夠的情況下，滿足下列兩個條件：
1、
其中作用於多集的函式f、Ø和都是單射函式。
2、作用在節點表示{hv（k）}上的readout函式也是單射函式。
上述結論只對於可數集有效，節點特徵連續的不可數集需要進一步考慮。
GRAPH
ISOMORPHISM
NETWORK
(GIN)
READOUT函式選擇使用所有層的表示拼接來代替只使用最後一層的表示。
LESS POWERFUL BUT STILL INTERESTING GNNS
我們對公式4。1中的聚合器的兩個方面進行了消融研究：
（1）用單層感知器代替MLPs；（2）用平均或最大池代替和。
我們將看到，這些GNN變體被令人驚訝的簡單圖形所混淆，並且不如WL測試強大。儘管如此，具有平均聚合器（如GCN）的模型在節點分類任務中表現良好。為了更好地理解這一點，我們精確地描述了不同GNN變體可以捕獲和不能捕獲的圖形，並討論了使用圖形學習的含義。
1-LAYER PERCEPTRONS ARE NOT SUFFICIENT
1層感知器的行為很像線性對映，因此GNN層退化為簡單的鄰域特徵求和。我們的證明建立在偏差項缺少線性對映的事實上。利用偏差項和足夠大的輸出維數，單層感知器可能可以區分不同的多集。因此，即使具有1層感知器的GNNs可以在一定程度上將不同的圖嵌入到不同的位置，這樣的嵌入也可能無法充分捕獲結構相似性，並且對於簡單的分類器（例如線性分類器）來說很難擬合。
STRUCTURES THAT CONFUSE MEAN AND MAX-POOLING
圖2按表示能力對三個聚合器進行了排序，多集上求和、平均和最大聚合器的表示能力排序。左面板顯示輸入多集，即要聚合的網路鄰居。接下來的三個面板說明了給定聚合器能夠捕獲的多集的各個方面：sum捕獲完整的多集，mean捕獲給定型別元素的比例/分佈，max聚合器忽略多重性（將多集減少為簡單集）。
圖3顯示了平均池聚合器和最大池聚合器無法區分的結構對。在這裡，節點顏色表示不同的節點特徵，我們假設GNNs在與標記為v和v′的中心節點組合之前先聚集鄰居。
3（a）中，每個節點都有相同的特徵a，所有節點上的f（a）都相同（對於任何函式f）。當執行鄰域聚合時，f（a）上的均值或最大值保持f（a），並且透過歸納，我們總是處處獲得相同的節點表示。因此，在這種情況下，mean和max池聚合器無法捕獲任何結構資訊。相同的理論可以應用於任何未標記的圖。如果使用節點度而不是常量作為節點輸入特徵，原則上，mean可以恢復sum，但max pooling不能。
圖3a表明，mean和max難以區分具有重複特徵的節點的圖。設hcolor（r表示紅色，g表示綠色）表示f變換後的節點特徵。圖3b表示出出在藍色節點V和V’的鄰域中的最大值產生MAX（Hg，HR）和MAX（Hg，HR，HR），它們會得到相同的表示（即使對應的圖形結構是不同的）。
MEAN LEARNS DISTRIBUTIONS （平均聚合器學習的是分佈）
對於任務來說，如果圖中的統計和分佈資訊比精確的結構更重要，則平均聚合器可能表現良好。此外，當節點特徵多樣且很少重複時，平均聚合器與和聚合器一樣強大。這也許可以解釋為什麼儘管第5。2節中指出了限制，但具有平均聚合器的GNNs對於節點分類任務（例如分類文章主題和社群檢測）是有效的，在這些任務中，節點特徵豐富，並且鄰域特徵的分佈為任務提供了強訊號。
MAX-POOLING LEARNS SETS WITH DISTINCT ELEMENTS （MAX-POOLING學習具有不同元素的集合）
然而，它可能適用於需要確定代表性元素或“骨架”的任務，而不是區分確切的結構或分佈。
齊等人。（2017）經驗表明，max pooling聚合器能夠識別3D point cloud的骨架，並且對噪聲和異常值具有魯棒性
REMARKS ON OTHER AGGREGATORS
本文研究不包括其他非標準鄰居聚集方案，例如，透過關注加權平均（Velickovic等人，2018）和LSTM池（Hamilton等人，2017a；Murphy等人，2018）。
EXPERIMENTS
Datasets。 4個生物資訊學資料集MUTAG， PTC， NCI1， PROTEINS
5個社交網路資料集COLLAB， IMDB-BINARY， IMDB-MULTI， REDDIT- BINARY and REDDIT-MULTI5K
重要的是，我們的目標不是讓模型依賴於輸入節點的特徵，而是主要從網路結構中學習，因此，在生物資訊圖中，節點具有分類輸入特徵，而在社會網路中，節點沒有特徵。對於社交網路，我們建立節點特徵如下：對於REDDIT資料集，我們將所有節點特徵向量設定為相同（因此，這裡的特徵是無資訊的）；對於其他社交圖，我們使用節點度的one-hot編碼。
社交網路資料集。IMDB-BINARY和IMDB-MULTI是電影協作資料集。每個圖對應於每個演員/女演員的自我網路，其中節點對應於演員/女演員，如果兩個演員/女演員出現在同一部電影中，則在兩個演員/女演員之間繪製一條邊。每個圖都是從預先指定的電影型別派生的，任務是對其派生的型別圖進行分類。REDDIT-BINARY和REDDIT-MULTI5K是平衡的資料集，其中每個圖對應於一個線上討論執行緒，節點對應於使用者。如果兩個節點中至少有一個對另一個節點的評論做出響應，則在兩個節點之間繪製一條邊。任務是將每個圖分類到它所屬的社群或子社群。COLLAB是一個科學協作資料集，來源於3個公共協作資料集，即高能物理、凝聚態物理和天體物理。每一張圖都對應於一個由各個領域的不同研究者組成的自我網路。任務是將每個圖分類到相應研究人員所屬的欄位。
生物資訊學資料集。MUTAG是一個包含188個突變芳香族和雜芳香族硝基化合物的資料集，有7個離散的標籤。PROTEINS是一個數據集，其中的節點是二級結構元素（SSEs），如果它們是氨基酸序列或三維空間中的相鄰節點，則在兩個節點之間有一條邊。它有3個離散的標籤，分別代表螺旋線、板材或車削。PTC是一個包含344種化合物的資料集，報告了雄性和雌性大鼠的致癌性，它有19個離散的標籤。NCI1是國家癌症研究所（NCI）公開提供的一個數據集，是一個平衡的化合物資料集的子集，篩選出抑制或抑制一組具有37個離散標籤的人類腫瘤細胞系生長的能力。
RESULTS
