作為脫胎于圖論研究的熱門研究領域，圖神經(jīng)網(wǎng)絡（GNN）與經(jīng)典的 WL 算法有諸多相似之處。眾所周知，強大的 WL 算法對于聚合函數(shù)的單射性質有很強的要求，那么強大的 GNN 應該具備哪些性質呢？本文從對 WL 算法的分析入手，介紹了 GNN 的局限性，指出了未來可能的重點研究方向。

圖 1：通往更強大的 GNN 的道路

對于圖表征任務，我們有兩種常用的范式：圖核（Graph Kernel）和圖神經(jīng)網(wǎng)絡（Graph Neural Network，GNN）。通常，圖核基于圖分解以一種無監(jiān)督的方式創(chuàng)建圖的嵌入。例如，我們可以計算一張圖中三角形或更一般的三元組的個數(shù)，然后使用該計數(shù)結果來得到嵌入。眾所周知，這是圖元核（ Graphlet Kernel）的一個實例。       

     

圖 2：以上所有圖元的尺寸為 4。計算圖中所有四元組的每種 圖元 的個數(shù)可以得到一個 圖元核。

這種范式主要的研究動機是：創(chuàng)建一種保持圖之間同構關系的嵌入（即兩張圖是同構的，當且僅當與它們相對應的嵌入是相同的）。顯然，如果有這樣的嵌入，我們就可以解決圖的同構問題。

而在當前看來，我們知道這個問題要比「P 問題」（存在多項式時間復雜度解法的問題）更難解決。然而，也存在諸如「Anonymous Walk Embeddings」（相關論文：https://arxiv.org/abs/1805.11921）這樣保持了同構性的嵌入方法（當然，這是以計算時間為代價的）。

盡管如此，在這里本文想傳達的主要信息是：人們曾經(jīng)設計圖核來解決圖同構問題。如果嵌入能夠將更多種類的圖區(qū)分開來，那么嵌入就越好。曾經(jīng)，這種原則被大家奉為圭臬。

圖神經(jīng)網(wǎng)絡誕生后，這種原則產(chǎn)生了改變。除了解決圖同構這一問題之外，我們可以試著解決任意給定的問題（例如，找到最短路徑或者檢測環(huán)結構）。這是十分有發(fā)展前景的，因為它讓我們可以根據(jù)網(wǎng)絡能夠解決的問題來指導我們的網(wǎng)絡設計。這聽起來似乎很神奇：你可以直接訓練你的網(wǎng)絡，然后它就會為你找到合適的解，而不需要使用一些成熟的組合優(yōu)化算法。

但我們也不禁要問：神經(jīng)網(wǎng)絡是通過隨機梯度下降（SGD）搜索可行解的，它涉及許多其它的技術問題，如果你被困在了一個糟糕的局部最優(yōu)點該怎么辦？它如何才能解決任意的問題呢？事實上，圖神經(jīng)網(wǎng)絡存在一些局限性，本文將在下面娓娓道來。

一、GNN 變得強大的條件

本文將基于論文「How Powerful are Graph Neural Networks」（論文鏈接：https://arxiv.org/abs/1810.00826）開始討論。這篇論文引發(fā)了大量關于 GNN 的理論解釋的研究。具體而言，作者將 GNN 與一種曾經(jīng)被深入研究的圖同構算法「Weisfeiler-Lehman」（WL 算法）做了比較。

何為 WL 算法 ？

這種算法描述起來很簡單。給定一張圖，圖中每個節(jié)點都有一些顏色（如果沒有，則它有關于度的信息）。在每一輪迭代中，每個節(jié)點都會獲取一組其鄰居節(jié)點的顏色信息，并以特定的方式更新其顏色。

具體而言，存在一種單射函數(shù)，它根據(jù)節(jié)點之前的顏色 c 以及鄰居節(jié)點顏色 X 的有序列表為該節(jié)點創(chuàng)建一種新的顏色 c'。該算法在 n 輪迭代之后停止運行，并更新圖的著色情況。        

     

注：WL 使用單射函數(shù)是非常重要的，因為它保證不同的輸入會得到不同的輸出。一種 WL 使用的特定的單射函數(shù)是：它為每個輸入的對象創(chuàng)建一種之前沒有用到過的新顏色。由于該算法在離散域（可數(shù)的顏色）中運行，所以總是可以創(chuàng)建這樣的映射。   

     

圖 3：上圖從左到右分別為單射（但非滿射）、雙射、滿射（但非單射）。

該算法主要的用途是檢驗兩圖是否同構。如果最后的著色情況不同，則這兩張圖「非同構」。如果兩張圖有相同的最終著色結果，那么 WL 將輸出它們「可能同構」，但這仍然意味著它們有很小的概率不是同構的。

這種算法是上世紀 70 年代在蘇聯(lián)的秘密實驗室里設計出來的，當時計算機仍然在使用打孔程序卡。但從那時起，世界各地的研究者們就開始研究它的性質，尤其是我們知道了各種應用  WL 算法將失效的圖。

例如，對于任意兩個包含 n 個頂點的「d-正則圖」，最終的著色情況將是相同的。盡管如此，這是一種非常強大的檢驗同構性的方法。有些定理認為當 n 趨于無窮大時，WL 算法失敗的可能性為 0，所以這是一種相當強大的算法。

再看 GNN

如果你研究過 GNN，你會注意到 GNN 更新節(jié)點特征的方式和 WL 算法更新節(jié)點顏色的方式有諸多相似之處。具體而言，GNN 使用一種消息傳遞機制更新特征。

   

不同的 GNN 之間的區(qū)別在于它們使用的聚合函數(shù)和讀出函數(shù)。但是很容易理解的是，當聚合函數(shù)是單射函數(shù)時，那么如果 WL 將圖映射到不同的著色方案上，則 GNN 也會將這些圖映射到不同的嵌入上。

定理 3 是這種機制的形式化定義：      

     

換而言之，GNN 有參數(shù)化的方程 φ 和 f，如果它們是單射的，那么它們保證 GNN 有很強的能力。這并不難理解，因為 WL 算法也要求其函數(shù)是單射的，而且在其它方面這兩個程序是等價的。

請注意，在這里我們使用了一種特殊的方法更新節(jié)點的嵌入。我們得到之前的嵌入「h_v^(k-1)」和之前鄰居節(jié)點的嵌入的多重集，將它們作為兩個不同的參數(shù)， 而不是將二者合并時作為同一個參數(shù)。這一點對于下游任務是十分重要的。

因此，可以使用 GNN 來判斷圖是否是同構的，這與使用 WL 算法是等價的。

這就是它的神奇之處。GNN 突然變得與眾所周知的算法等價了。但是它的局限在哪里呢？

二、GNN 的局限性何在？

上面提到的主要的局限性在于，你需要有單射函數(shù) φ 和 f。那么這些函數(shù)是什么呢？這些函數(shù)將一個嵌入的多重集映射到新的嵌入上。例如，你可以使用「mean」函數(shù)。該函數(shù)將獲取嵌入的均值，并將其賦予新的嵌入。然而，很容易看出，對于一些不同的圖，這些函數(shù)會給出相同的嵌入，因此「mean」函數(shù)不是單射的。       

     

圖 4：即使圖是不同的，節(jié)點 v 和 v' 嵌入的平均聚合函數(shù)（這里的嵌入對應于不同的顏色）將給出相同的嵌入。

但是，如果你以一種特定的方式獲取嵌入的求和和變換結果，那么就有可能得到單射函數(shù)。引理 5 如下：

           

在這里，真正重要的是：你可以首先使用一個函數(shù) f(x) 將每個求和符號下的嵌入映射到一個新的嵌入上，然后對其進行求和并得到一個單射函數(shù)。在證明過程中，他們實際上顯式地聲明了這個函數(shù) f，它還需要兩個額外的條件：（1）x 是可數(shù)的。（2）任意的多重集是有界的。

但這兩個假設都不強，因為無論如何，我們都是將我們的 GNN 應用于有限圖，其中特征和鄰居節(jié)點的技術是有限的。但至少我們現(xiàn)在知道，如果我們使用了變換 f，并使用加法，我們可以得到一個單射映射。

然而，上面的定理 3（條件 a）中應該有一個特定的聚合方案，除了鄰居節(jié)點的聚合函數(shù)之外，還應該使用當前節(jié)點「h_v^(k-1)」先前的嵌入。為了將其包含在內，我們需要使用另一個聲明推論 6：       

     

請注意，這里的函數(shù) h 像之前那樣，會取變換后的鄰居特征之和，但是還額外地加入了「(1+eps)f(c)」，這個 eps 是任意的無理數(shù)。這樣得到的函數(shù) h 就是單射的。

那么，我們知道了聚合函數(shù) φ 和 f 應該是單射函數(shù)，而且我們有單射函數(shù) h。如果我們的目標是構建強大的嵌入，那么我們的目標就達成了。

但是，我們不僅嘗試構建嵌入，而且還嘗試解決一些下游任務（如通過一種有監(jiān)督的方式進行節(jié)點分類）。函數(shù) h 沒有科學系的參數(shù)來擬合數(shù)據(jù)（也許 eps 除外）。

然而，GIN 架構提出使用多層感知機（MLP）替換函數(shù) φ 和 f。根據(jù)通用近似定理，我們知道 MLP 可以近似任何函數(shù)，包括單射函數(shù)。因此，具體而言，GIN 的嵌入更新有以下的形式：

請注意，MLP 內部的東西并不一定是單射的，而且 MLP 本身也不一定是單射的。事實上，對于第一層來說，如果輸入特征是獨熱編碼，那么 MLP 中的求和將是單射的。從原則上來說，MLP 可以學到一個單射函數(shù)。但是在第二層和更高層中，節(jié)點嵌入將會變得不合理。一個很容易得到的例子是，嵌入的總和可能并不再是單射函數(shù)（例如，擁有一個嵌入等于 2 的鄰居，或者有一兩個嵌入等于 1 的鄰居）。

因此，如果 MLP 和嵌入的和都是單射函數(shù)，那么 GIN 就和 WL 算法同樣強大了。

但是，事實上，在訓練過程中，沒有任何東西可以保證這種單射性質，而且可能有一些圖是 GIN 無法區(qū)分的，而 WL 算法可以。所以，對于 GIN 來說，這是一個過于強的假設。如果違反了該假設，則 GIN 的能力就是有限的。

后來，論文「Discriminative structural graph classification」（論文鏈接：https://arxiv.org/abs/1905.13422）對這種局限性進行了討論，它指出嵌入的輸出的尺寸應該與輸入特征的尺寸成指數(shù)關系，從而使 MLP 成為單射的，盡管這里的分析是針對無界的鄰居（無限圖）進行的。

找到一種擁有單射聚合函數(shù)并且對于下游任務有充分的表達能力的架構是一個有待探索的問題，盡管有幾種架構將 GIN 推廣到了高維 WL 算法以及其它問題上；然而，并不能保證學習到的 GNN 架構對于所有的輸入圖都可以解決特定的任務。

此外，論文「The Expressive Power of Graph Neural Networks」（論文鏈接：https://arxiv.org/abs/2003.04078）便很好地解釋了近年來在 GNN 的能力的理論性解釋方面的研究進展。

三、結語

如今，對 GNN 的特性的研究是一個非?；钴S的研究領域（讀者可以前往該鏈接跟進最新的發(fā)展趨勢：https://towardsdatascience.com/top-trends-of-graph-machine-learning-in-2020-1194175351a3），有許多開放性問題有待解決。

本文要傳達的主要信息是：目前 GNN 并不一定能收斂到與 WL 算法一樣強大的狀態(tài)，盡管往往會有一組參數(shù)使 GNN 變得強大。GNN 可以解決圖上的各種問題，但目前的研究主要集中在它們可以解決/無法解決哪些問題，而不是它如何才能對得到的解有所保障，這才是今后的研究重點。

via https://towardsdatascience.com/limitations-of-graph-neural-networks-2412fffe677 雷鋒網(wǎng)雷鋒網(wǎng)雷鋒網(wǎng)

雷峰網(wǎng)原創(chuàng)文章，未經(jīng)授權禁止轉載。詳情見轉載須知。