作者 | Mr Bear

編輯 | 叢 末

近年來，隨著圖神經網絡在各個領域的火熱應用，越來越多的學者試圖從圖論的角度對圖神經網絡的表達能力進行理論分析，并基于這些理論分析開發(fā)出了性能強大的模型。然而，在實際應用中，這些在理論上非常強大的模型的性能往往會受到計算復雜度等因素的限制。

本文作者 Michael Bronstein 是一名來 自帝國理工學院的教授，同時也是 Twitter 圖機器學習項目組的負責人。在本文中，他深入淺出地介紹了近年來分析圖神經網絡表達能力的工作，并介紹了他們對于該領域未來發(fā)展方向的思考。

1圖神經網絡和 WL 圖同構測試之間的關系

眾所周知，傳統(tǒng)的前饋神經網絡（多層感知機）是一種通用函數(shù)近似器：它們能夠以任意的準確率逼近任意的平滑函數(shù)。對于近期興起的圖神經網絡來說，其表征性質還不太為人所知。在實驗中，我們經常可以看到圖神經網絡在某些數(shù)據(jù)集上性能優(yōu)異，但同時又在另一些數(shù)據(jù)集上表現(xiàn)令人失望。

為了探究造成這種現(xiàn)象的根本原因，我們不得不思考一個問題：圖神經網絡究竟有多強大？

在探究這一問題的過程中，我們所面臨的一個挑戰(zhàn)是：實際應用場景下使用的圖往往是連續(xù)結構和離散結構（節(jié)點、邊特征、連通性）的組合。因此，該問題可以被表述為不同的形式。一種可能的形式化定義是：圖神經網絡是否能夠區(qū)分不同類型的圖結構。在圖論中，這是一種被稱為「圖同構問題」的經典問題，旨在判斷兩個圖在拓撲意義上是否等價。兩個同構的圖擁有相同的連通性，其差別僅僅可能是節(jié)點的排列不同。

稍令人驚訝的是，我們尚不知曉精確的圖同構問題的復雜度級別。該問題在多項式時間內不可解，它也不是一個 NP 完全（NPC）問題。有時，我們將其復雜度稱為一種特殊的「GI 級」（GI class）。

1、Weisfeiler-Lehman 測試

Boris Weisfeiler 和 Andrey Lehman 于 1968 年發(fā)表的具有開創(chuàng)性意義的論文「The reduction of a graph to canonical form and the algebra which Appears therein 」），提出了一種高效的啟發(fā)式算法，我們現(xiàn)在將其稱為「WL 測試」。

最初，人們認為 WL 測試可以在多項式時間內求解圖同構問題。但一年之后，人們就舉出了一個反例。然而，從概率意義上說，似乎 WL 測試對于幾乎所有的圖都有效。

圖 1：在兩個同構圖上執(zhí)行 WL 測試的示例。包含弧線的 hash 圓括號代表多重集。在著色情況不再變化后算法會終止，并給出輸出結果（顏色直方圖）。若將兩圖輸入給該算法得到的輸出相同，則說明兩圖可能同構。

WL 測試是建立在迭代式的圖重著色（圖論中的「著色」指的是一種離散的節(jié)點標簽）基礎上的，在初始狀態(tài)下，每個節(jié)點的顏色均不相同。在每一步迭代中，算法會聚合節(jié)點及其鄰居節(jié)點的顏色，并將它們表征為多重集，然后將聚合得到的顏色多重集通過 Hash 函數(shù)映射到某種唯一的新顏色上。當達到穩(wěn)定的著色狀態(tài)（各節(jié)點著色狀態(tài)不再變化）后，算法終止。當算法終止后，若兩圖的著色情況不同，則我們認為它們「非同構」。如果兩圖著色情況相同，它們可能（但并不一定）是同構的。換句話說，WL 測試是圖同構的必要非充分條件。有一些非同構的圖在接受 WL 測試后得到的著色情況也是相同的，而在這種情況下 WL 測試就失效了，因此我們只能認為它們「可能同構」。下圖展示了其中的一種可能性：

圖 2：顯然，WL 圖同構測試會為上面的兩個非同構圖生成相同的著色結果，此時 WL 測試失效。在化學領域中，這兩個圖分別代表兩種不同的化合物「decalin」（左圖）和「bicyclopentyl」（右圖）的分子結構。

2、圖同構網絡（GIN）

Keyulu Xu 等人發(fā)表的論文「 How powerful are graph neural networks?」和 Christopher Morris 等人發(fā)表的論文，以及 Thomas 在他至少兩年前撰寫的博客「GRAPH CONVOLUTIONAL NETWORKS」，中注意到，WL 測試與圖消息傳遞神經網絡有驚人的相似之處，它們都在圖上進行了一種類似于卷積的操作。

相關論文/文章鏈接：

https://arxiv.org/abs/1810.00826

https://tkipf.github.io/graph-convolutional-networks/

在一個消息傳遞層中，每個節(jié)點的特征會以聚合其鄰居節(jié)點特征的方式被更新。對聚合和更新操作的選擇是十分重要的：只有使用多重集的單射函數(shù)才能使其與 WL 算法等價。在前人的研究中，「取最最大值」或「取均值」等聚合操作都是一定弱于 WL 的能力，它們甚至不能區(qū)分非常簡單的圖結構：

圖 3：通過「取最大值」操作無法區(qū)分左圖、中圖、右圖，通過「取均值」聚合函數(shù)可以區(qū)分左圖和中圖、通過「取最大值」和「取均值」操作均無法區(qū)分左圖和右圖。這是因為通過這些方法從黑色節(jié)點的鄰居中聚合而來的特征將會是相同的。

Xu 提出了一種聚合和更新函數(shù)的選擇方案，它使得消息傳遞神經網絡與 WL 算法等價，該網絡被稱為「圖同構網絡」（GIN）。該網絡和標準的消息傳遞神經網絡一樣強大。但是，GIN 不僅僅是一種新的網絡架構，其主要影響在于它通過一種簡單的設定形式化定義了圖神經網絡表達能力的問題，這種設定與圖論中的經典問題相關。該網絡的思路也啟發(fā)了許多后續(xù)的工作。

3、Weisfeiler-Lehman 層次結構

使用更加強大的圖同構測試，是擴展 Xu 和 Morris 等人工作的一個方向。因此，László Babai 提出了 k-WL 測試，這是 WL 算法在高階上的擴展，它在 k 元組上進行操作，而非操作單個節(jié)點。除了 1-WL 和 2-WL 測試是等價的，(k+1)-WL 始終嚴格強于 k-WL（k≥2），即對于某些圖而言 k-WL 測試失效，而 (k+1)-WL 測試可以成功判定圖是否同構，但反之則不然。因此，k-WL 是一種層次結構的或隨著 k 的增大而逐漸更加強大的圖同構測試，有時被稱為「Weisfeiler-Lehman 層次結構」。

我們可以設計出遵循 k-WL 測試的圖神經網絡，這種網絡是一定比消息傳遞架構更加強大的。Morris 等人在論文「 Weisfeiler and Leman go neural: Higher-order graph neural networks 」中提出了第一種這樣的架構 k-GNN。

相關論文鏈接：

https://aaai.org/ojs/index.php/AAAI/article/view/4384/4262

傳統(tǒng)的消息傳遞神經網絡和這種高階圖神經網絡之間最關鍵的區(qū)別在于：由于 k-WL 算法在節(jié)點的 k 元組上進行操作，所以這種高階圖神經網絡是非局部的（non-local）。這對算法的實現(xiàn)及其計算復雜度和存儲復雜度都有重要的影響：k-GNN 需要