作為脫胎於圖論研究的熱門研究領域，圖神經網路（GNN）與經典的 WL 演算法有諸多相似之處。眾所周知，強大的 WL 演算法對於聚合函式的單射性質有很強的要求，那麼強大的 GNN 應該具備哪些性質呢？本文從對 WL 演算法的分析入手，介紹了 GNN 的侷限性，指出了未來可能的重點研究方向。
圖 1：通往更強大的 GNN 的道路
對於圖表徵任務，我們有兩種常用的正規化：圖核（Graph Kernel）和圖神經網路（Graph Neural Network，GNN）。通常，圖核基於圖分解以一種無監督的方式建立圖的嵌入。例如，我們可以計算一張圖中三角形或更一般的三元組的個數，然後使用該計數結果來得到嵌入。眾所周知，這是圖元核（ Graphlet Kernel）的一個例項。
圖 2：以上所有圖元的尺寸為 4。計算圖中所有四元組的每種 圖元 的個數可以得到一個 圖元核。
這種正規化主要的研究動機是：建立一種保持圖之間同構關係的嵌入（即兩張圖是同構的，當且僅當與它們相對應的嵌入是相同的）。顯然，如果有這樣的嵌入，我們就可以解決圖的同構問題。
而在當前看來，我們知道這個問題要比「P 問題」（存在多項式時間複雜度解法的問題）更難解決。然而，也存在諸如「Anonymous Walk Embeddings」（相關論文：https://arxiv.org/abs/1805.11921）這樣保持了同構性的嵌入方法（當然，這是以計算時間為代價的）。
儘管如此，在這裡本文想傳達的主要資訊是：人們曾經設計圖核來解決圖同構問題。如果嵌入能夠將更多種類的圖區分開來，那麼嵌入就越好。曾經，這種原則被大家奉為圭臬。
圖神經網路誕生後，這種原則產生了改變。除了解決圖同構這一問題之外，我們可以試著解決任意給定的問題（例如，找到最短路徑或者檢測環結構）。這是十分有發展前景的，因為它讓我們可以根據網路能夠解決的問題來指導我們的網路設計。這聽起來似乎很神奇：你可以直接訓練你的網路，然後它就會為你找到合適的解，而不需要使用一些成熟的組合最佳化演算法。
但我們也不禁要問：神經網路是透過隨機梯度下降（SGD）搜尋可行解的，它涉及許多其它的技術問題，如果你被困在了一個糟糕的區域性最優點該怎麼辦？它如何才能解決任意的問題呢？事實上，圖神經網路存在一些侷限性，本文將在下面娓娓道來。
一、GNN 變得強大的條件本文將基於論文「How Powerful are Graph Neural Networks」（論文連結：https://arxiv.org/abs/1810.00826）開始討論。這篇論文引發了大量關於 GNN 的理論解釋的研究。具體而言，作者將 GNN 與一種曾經被深入研究的圖同構演算法「Weisfeiler-Lehman」（WL 演算法）做了比較。
何為 WL 演算法 ？
這種演算法描述起來很簡單。給定一張圖，圖中每個節點都有一些顏色（如果沒有，則它有關於度的資訊）。在每一輪迭代中，每個節點都會獲取一組其鄰居節點的顏色資訊，並以特定的方式更新其顏色。
具體而言，存在一種單射函式，它根據節點之前的顏色 c 以及鄰居節點顏色 X 的有序列表為該節點建立一種新的顏色 c'。該演算法在 n 輪迭代之後停止執行，並更新圖的著色情況。
注：WL 使用單射函式是非常重要的，因為它保證不同的輸入會得到不同的輸出。一種 WL 使用的特定的單射函式是：它為每個輸入的物件建立一種之前沒有用到過的新顏色。由於該演算法在離散域（可數的顏色）中執行，所以總是可以建立這樣的對映。
圖 3：上圖從左到右分別為單射（但非滿射）、雙射、滿射（但非單射）。
該演算法主要的用途是檢驗兩圖是否同構。如果最後的著色情況不同，則這兩張圖「非同構」。如果兩張圖有相同的最終著色結果，那麼 WL 將輸出它們「可能同構」，但這仍然意味著它們有很小的機率不是同構的。
這種演算法是上世紀 70 年代在蘇聯的秘密實驗室裡設計出來的，當時計算機仍然在使用打孔程式卡。但從那時起，世界各地的研究者們就開始研究它的性質，尤其是我們知道了各種應用 WL 演算法將失效的圖。
例如，對於任意兩個包含 n 個頂點的「d-正則圖」，最終的著色情況將是相同的。儘管如此，這是一種非常強大的檢驗同構性的方法。有些定理認為當 n 趨於無窮大時，WL 演算法失敗的可能性為 0，所以這是一種相當強大的演算法。
再看 GNN
如果你研究過 GNN，你會注意到 GNN 更新節點特徵的方式和 WL 演算法更新節點顏色的方式有諸多相似之處。具體而言，GNN 使用一種訊息傳遞機制更新特徵。
不同的 GNN 之間的區別在於它們使用的聚合函式和讀出函式。但是很容易理解的是，當聚合函式是單射函式時，那麼如果 WL 將圖對映到不同的著色方案上，則 GNN 也會將這些圖對映到不同的嵌入上。
定理 3 是這種機制的形式化定義：
換而言之，GNN 有引數化的方程 φ 和 f，如果它們是單射的，那麼它們保證 GNN 有很強的能力。這並不難理解，因為 WL 演算法也要求其函式是單射的，而且在其它方面這兩個程式是等價的。
請注意，在這裡我們使用了一種特殊的方法更新節點的嵌入。我們得到之前的嵌入「h_v^(k-1)」和之前鄰居節點的嵌入的多重集，將它們作為兩個不同的引數， 而不是將二者合併時作為同一個引數。這一點對於下游任務是十分重要的。
因此，可以使用 GNN 來判斷圖是否是同構的，這與使用 WL 演算法是等價的。
這就是它的神奇之處。GNN 突然變得與眾所周知的演算法等價了。但是它的侷限在哪裡呢？
二、GNN 的侷限性何在？上面提到的主要的侷限性在於，你需要有單射函式 φ 和 f。那麼這些函式是什麼呢？這些函式將一個嵌入的多重集對映到新的嵌入上。例如，你可以使用「mean」函式。該函式將獲取嵌入的均值，並將其賦予新的嵌入。然而，很容易看出，對於一些不同的圖，這些函式會給出相同的嵌入，因此「mean」函式不是單射的。
圖 4：即使圖是不同的，節點 v 和 v' 嵌入的平均聚合函式（這裡的嵌入對應於不同的顏色）將給出相同的嵌入。
但是，如果你以一種特定的方式獲取嵌入的求和和變換結果，那麼就有可能得到單射函式。引理 5 如下：
在這裡，真正重要的是：你可以首先使用一個函式 f(x) 將每個求和符號下的嵌入對映到一個新的嵌入上，然後對其進行求和並得到一個單射函式。在證明過程中，他們實際上顯式地聲明瞭這個函式 f，它還需要兩個額外的條件：（1）x 是可數的。（2）任意的多重集是有界的。
但這兩個假設都不強，因為無論如何，我們都是將我們的 GNN 應用於有限圖，其中特徵和鄰居節點的技術是有限的。但至少我們現在知道，如果我們使用了變換 f，並使用加法，我們可以得到一個單射對映。
然而，上面的定理 3（條件 a）中應該有一個特定的聚合方案，除了鄰居節點的聚合函式之外，還應該使用當前節點「h_v^(k-1)」先前的嵌入。為了將其包含在內，我們需要使用另一個宣告推論 6：
請注意，這裡的函式 h 像之前那樣，會取變換後的鄰居特徵之和，但是還額外地加入了「(1 eps)f(c)」，這個 eps 是任意的無理數。這樣得到的函式 h 就是單射的。
那麼，我們知道了聚合函式 φ 和 f 應該是單射函式，而且我們有單射函式 h。如果我們的目標是構建強大的嵌入，那麼我們的目標就達成了。
但是，我們不僅嘗試構建嵌入，而且還嘗試解決一些下游任務（如透過一種有監督的方式進行節點分類）。函式 h 沒有科學系的引數來擬合數據（也許 eps 除外）。
然而，GIN 架構提出使用多層感知機（MLP）替換函式 φ 和 f。根據通用近似定理，我們知道 MLP 可以近似任何函式，包括單射函式。因此，具體而言，GIN 的嵌入更新有以下的形式：
請注意，MLP 內部的東西並不一定是單射的，而且 MLP 本身也不一定是單射的。事實上，對於第一層來說，如果輸入特徵是獨熱編碼，那麼 MLP 中的求和將是單射的。從原則上來說，MLP 可以學到一個單射函式。但是在第二層和更高層中，節點嵌入將會變得不合理。一個很容易得到的例子是，嵌入的總和可能並不再是單射函式（例如，擁有一個嵌入等於 2 的鄰居，或者有一兩個嵌入等於 1 的鄰居）。
因此，如果 MLP 和嵌入的和都是單射函式，那麼 GIN 就和 WL 演算法同樣強大了。
但是，事實上，在訓練過程中，沒有任何東西可以保證這種單射性質，而且可能有一些圖是 GIN 無法區分的，而 WL 演算法可以。所以，對於 GIN 來說，這是一個過於強的假設。如果違反了該假設，則 GIN 的能力就是有限的。
後來，論文「Discriminative structural graph classification」（論文連結：https://arxiv.org/abs/1905.13422）對這種侷限性進行了討論，它指出嵌入的輸出的尺寸應該與輸入特徵的尺寸成指數關係，從而使 MLP 成為單射的，儘管這裡的分析是針對無界的鄰居（無限圖）進行的。
找到一種擁有單射聚合函式並且對於下游任務有充分的表達能力的架構是一個有待探索的問題，儘管有幾種架構將 GIN 推廣到了高維 WL 演算法以及其它問題上；然而，並不能保證學習到的 GNN 架構對於所有的輸入圖都可以解決特定的任務。
此外，論文「The Expressive Power of Graph Neural Networks」（論文連結：https://arxiv.org/abs/2003.04078）便很好地解釋了近年來在 GNN 的能力的理論性解釋方面的研究進展。
三、結語如今，對 GNN 的特性的研究是一個非常活躍的研究領域（讀者可以前往該連結跟進最新的發展趨勢：https://towardsdatascience.com/top-trends-of-graph-machine-learning-in-2020-1194175351a3），有許多開放性問題有待解決。
本文要傳達的主要資訊是：目前 GNN 並不一定能收斂到與 WL 演算法一樣強大的狀態，儘管往往會有一組引數使 GNN 變得強大。GNN 可以解決圖上的各種問題，但目前的研究主要集中在它們可以解決/無法解決哪些問題，而不是它如何才能對得到的解有所保障，這才是今後的研究重點。
via https://towardsdatascience.com/limitations-of-graph-neural-networks-2412fffe677 雷鋒網雷鋒網雷鋒網