作為脫胎於圖論研究的熱門研究領域，圖神經網絡（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 雷鋒網雷鋒網雷鋒網
