Categories
程式開發

淺談圖神經網絡的局限性


此前,本文作者曾寫了一篇《2020 年圖機器學習的熱門趨勢》的文章,總結了圖機器學習今年可能的發展方向。本文,作者為我們帶來了一篇新作,講述了圖神經網絡的局限性。

本文經原作者授權,由 InfoQ 中文站翻譯並發布,未經許可禁止任何形式的轉載。

圖表示有兩種範式:圖核(graph kernel)和圖神經網絡(graph neural network)。圖核通常以無監督的方式基於分解創建圖嵌入。例如,我們可以計算一個圖中每種類型的三角形數量,或者更一般的三元組的數量,然後用這些計數來獲得嵌入。這是眾所周知的 Graphlet 核的實例。

淺談圖神經網絡的局限性 1

所有大小為 4 的 Graphlet。計算一個圖所有四元組中每個 Graphlet 的數量,將得到 Graphlet 核。來源:《用於大圖比較的高效 Graphlet 核》(Efficient graphlet kernels for large graph comparison

該範式的主要研究動機是,創建一種能夠保持圖之間同構的嵌入,即當且僅當兩個圖的對應嵌入相同時,兩個圖才是同構的。如果我們有這樣的嵌入,就能解決圖同構問題。這是目前已知的比 P 問題更難的問題。然而,還有一些嵌入,比如 Anonymous Walk Embeddings(匿名步行嵌入),它就保留了同構,當然,這是以運行時間計算為代價的。儘管如此,本文的主要信息是,圖核是用來解決圖同構問題的,嵌入能區分的圖越多,嵌入就越好。

譯註:P 問題:如果一個問題可以找到能在多項式的時間裡解決它的算法,那麼這個問題就屬於 P 問題。 P 是英文單詞多項式的第一個字母。具體請參見維基百科的詞條 P/NP 問題

隨著圖神經網絡的出現,這一原則發生了改變。我們可以嘗試解決任何給定的問題,例如尋找最短路徑或檢測循環,而不是解決一類問題,即圖同構。這是很有前途的,因為它使我們用它能解決的問題來指導我們的網絡設計。這聽起來像是魔法:你只需訓練你的網絡,它就能為你找到解決方案,而不是使用一些成熟的組合算法。但它也有令人存疑之處:神經網絡通過 SGD 算法搜索解決方案,並涉及到許多其他技術細節,如果你陷入了糟糕的局部最優,那該怎麼辦呢?它如何才能解決任何問題呢?事實上,圖神經網絡存在一些局限性。

圖神經網絡強大的條件

我將從《圖神經網絡有多強大》(How Powerful are Graph Neural Networks)這篇論文開始,它引發了有關圖神經網絡理論解釋的大量研究。特別是,將圖神經網絡與研究成熟的圖同構算法——Weisfelier-Lehman(WL)算法進行了比較。

關於 WL 算法

這個算法很容易描述,可以從圖開始。其中,每個節點都有對應的顏色(如果沒有顏色的,就放置一個度數)。在每次迭代中,每個節點都會獲得其鄰居的一組顏色,並以特定方式更新其顏色。具體地說,存在一個單射函數(Injective function),根據節點的前一個顏色 C 和鄰域的顏色 X 的有序列表,創建節點的新顏色 C’,該算法在 n 次迭代之後停止,並對圖進行更新著色。

淺談圖神經網絡的局限性 2

注意,WL 算法使用單射函數很重要,因為它保證了不同的輸入將會得到不同的輸出。 WL 使用的一個特殊的單射函數 是為每個輸入參數創建了之前未遇到過的新顏色。因為它在分類(可數)域(顏色)中運行,因此始終可以創建這樣的映射。

淺談圖神經網絡的局限性 3從左到右依次為單射、雙射、滿射、映射(來源:https://en.wikipedia.org/)

該算法的主要用途是測試兩個圖之間的同構性。如果最終的著色不同,則說明兩個圖不是同構的。如果兩個圖具有相同的最終著色,那麼 WL 算法輸出它們可能是同構的,這意味著它們仍然不是同構的可能性非常小。

這個算法是 20 世紀 70 年代在蘇聯的秘密實驗室設計的,當時計算機還在使用穿孔卡片。但從那時起,世界各地的研究者都在研究它的屬性,特別是當 WL 算法失敗時,我們由此知道了存在不同的圖族。例如,對於任何具​​有 n 個頂點的 2- 正則圖(regular graphs),最終的顏色將是相同的。儘管如此,這是對同構非常有力的檢驗,並且有定理指出,當 n 趨於無窮時,WL 失敗的可能性變為 0。因此,這是一個相當強大的算法。

回到圖神經網絡

如果你研究過圖神經網絡,你會注意到圖神經網絡的更新節點特徵的方式與 WL 算法更新節點顏色之間有許多相似之處。具體地說,圖神經網絡使用消息傳遞機制更新特徵。

淺談圖神經網絡的局限性 4

不同圖神經網絡之間的區別在於所使用的聚合函數和讀出函數。但是很容易理解的是,如果聚合函數是單射的,那麼如果 WL 將圖映射到不同的顏色,則圖神經網絡也會將這些圖映射到不同的嵌入。定理 3 是表達這種說法的一種正式方式。

淺談圖神經網絡的局限性 5

也就是說,圖神經網絡有參數化函數 φf,如果它們是單射的,則可以保證圖神經網絡的強冪。這並不奇怪,因為 WL 算法也要求它的函數是單射的,而且在其他方​​面,這兩個過程是等價的。

注意,這裡有一種更新節點嵌入的特殊方式。我們得到先前嵌入 h_v^(k-1),以及鄰居先前嵌入的多重集,這是兩個不同的參數,這一點很重要。

因此,你可以使用圖神經網絡來確定圖是否同構,這將等同於使用 WL 算法。

圖神經網絡突然變成眾所周知的算法,它的局限性又在哪裡呢?

關於圖神經網絡的局限性

前文提到的主要限制是,需要有單射函數 φf 。這些是將嵌入的多重集映射到新嵌入的函數。例如,你可以使用均值函數。這個函數將獲取嵌入的平均值,並將其分配為新的嵌入。但是,很容易看出,對於某些不同的圖,它們會給出相同的嵌入,所以,均值函數並不是單射的。

淺談圖神經網絡的局限性 6

即使圖不同,節點 v 和 v’ 的平均嵌入聚合(此處嵌入對應於不同的顏色)將給出相同的嵌入。來源:《圖神經網絡有多強大》(How Powerful are Graph Neural Networks

但是,如果你以一種特定的方式進行求和並變換嵌入,那麼就有可能得到單射。這是引理 5:

淺談圖神經網絡的局限性 7

這裡真正重要的是,你可以先用某個函數 f(x) 將每個嵌入映射到一個新的嵌入,然後進行求和,得到一個單射函數。在證明中,它們實際上顯式地聲明了這個函數 f,這需要兩個額外條件,即 X 是可數的,且任何多重集都是有界的。我認為這兩個假設都不強,因為無論如何,我們將圖神經網絡應用於有限圖,其中,特徵和鄰域的基數都是有限的。但至少我們現在知道,如果我們使用變換 f,然後進行加法運算,我們就可以得到一個單射映射。

但是,根據上面的定理 3(條件 a),應該存在一個特定的聚合方案,該方案除了對鄰居進行聚合外,還對當前節點 h_v^(k-1) 使用先前的嵌入。要包含它,我們需要另一個聲明:

淺談圖神經網絡的局限性 8

注意,這裡的函數 h 如前所述,取變換後的鄰居特徵之和,但除此之外,加上 (1+eps)f(c),這個 eps 是任意無理數。這樣函數 h 是單射的。

到這一步,我們知道聚合函數 φf 應該是單射的,而且,我們有一個函數 h 是單射的。如果目標是構建強大的嵌入,那麼已經完成了目標。但是,我們要嘗試的不只是構建嵌入,還要嘗試以有監督的方式來解決下游任務,如節點分類。並且函數 h 並沒有可學習的參數來對數據進行擬合(也許 eps除外)。

GIN 架構提出的替代方案是用 MLP 替換函數 φf,並且由於通用近似定理(universal approximation theorem),我們知道,MLP 可以近似任何函數,包括單射函數。因此,具體地說,GIN 的嵌入更新具有以下形式:

淺談圖神經網絡的局限性 9

注意,MLP 內部的東西並不能保證是單射的,而且 MLP 本身也不能保證是單射的。事實上,對於第一層,如果輸入特徵是獨熱編碼(one-hot encode),那麼 MLP 內部的和將是單射的,原則上,MLP 可以學習單射函數。但是在第二層及後面的層,節點嵌入變得不合理,很容易舉出一個例子,其中嵌入的和將不再是單射的(例如,有一個嵌入等於2 的鄰居,或有兩個嵌入等於1 的鄰居)。

因此,當 MLP 和嵌入和都是單射函數時,GIN 算法的性能與 WL 算法相當。

但事實上,在訓練中並沒有任何東西可以保證這種單射性,而且可能還會有一些圖是 GIN 無法區分的,但 WL 可以。所以這是對 GIN 的一個很強的假設,如果違反了這一假設,那麼 GIN 的性能將受到限制。

這種局限性,後來在《判別結構圖分類》(Discriminative structural graph classification)論文中進行了討論,論文表明,為了使 MLP 單射,輸出嵌入的大小應與輸入特徵的大小成指數關係,儘管分析是無界鄰域進行的(即無限圖)。找到具有單射聚合併且能夠充分錶達下游任務的架構是一個有待解決的問題,儘管有幾種架構將GIN 推廣到更高維的WL 算法以及其他問題;然而,還不能保證所學到的圖神經網絡架構能夠解決所有輸入圖的特定任務。論文《圖神經網絡表達能力研究綜述》(A Survey on The Expressive Power of Graph Neural Networks ),很好地解釋了近年來在圖神經網絡表達能力的理論解釋方面取得的進展。

結語

圖神經網絡屬性的研究現在是一個活躍的研究領域(你可以查看最近的趨勢),有許多懸而未決的問題需要解決。本文的主要目的是向讀者說明,目前,圖神經網絡並不能保證能夠收斂到像 WL 算法一樣強大的狀態,儘管一般情況下,當圖神經網絡變得同樣強大時,通常會有一組參數。圖神經網絡可以解決圖形上的不同問題,但到目前為止,研究的重點主要集中在它們能夠解決或不能解決的問題上,這將是下一篇研究論文的重點。

作者介紹:

Sergei Ivanov,機器學習研究科學家,專注於圖機器學習和建議。

原文鏈接:

https://towardsdatascience.com/limitations-of-graph-neural-networks-2412fffe677