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