本文最初發表在 TowardsDataScience 博客，經原作者 Michael Bronstein 授權，InfoQ 中文站翻譯並分享。
前文回顧：《圖深度學習：成果、挑戰與未來》
傳統的前饋網絡（多層感知器）是已知的通用逼近器：它們可以將任何平滑函數近似到任何所需的精度。對於相對最近才出現的圖神經網絡，其表示特性還不是很了解。人們在實驗中經常會觀察到，圖神經網絡在某些數據集上表現出色，但同時在其他數據集上的表現卻令人失望。為找到這種行為的根源，我們必須回答這樣一個問題：圖神經網絡有多強大？
其中挑戰之一是，應用程式中遇到的圖是亂序和離散結構（分別是節點和邊緣特徵以及連通性）的組合，因此，這個問題可以用不同的方式提出。一種可能的表述是圖神經網絡是否能夠區分不同類型的圖結構。這是圖論中的一個經典問題，稱為圖同構問題，目的是確定兩個圖在拓撲上是否等價【1】。兩個同構圖具有相同的連通性，不同之處只是它們節點的排列。
令人驚訝的是，圖同構問題的精確複雜度類別是未知的。我們不知道它在 多項式時間 內是可解的，也不知道它是 NP 完全（ NP-complete）的，有時被歸因於一種特殊的「GI 類」【2】
Weisfeiler-Lehman 測試。Boris Weisfeiler 和 Andrey Lehman【3】在 1968 年發表的具有開創性意義的論文中提出了一種有效的啟發式方法，即 Weisfeiler-Lehman 測試。最初被認為是圖同構問題的多項式時間解【4】。一年後發現了一個反例；然而，從概率意義上看，Weisfeiler-Lehman 測試似乎適用於幾乎所有的圖【5】。
對兩個同構圖上執行 Weisfeiler-Lehman 測試的示例。花括號表示多組。算法在顏色不變後停止，並生成輸出（顏色直方圖）。這兩個圖的輸入相等表明它們可能是同構的。
Weisfeiler-Lehman 測試基於迭代圖重新著色【6】（圖論中的「顏色」是指一個離散節點標籤），並從所有顏色相同的節點開始。在每一步中，該算法將節點及其鄰域的顏色聚合為多集【7】，並將聚合的顏色多集散列為唯一的新顏色。當達到穩定的著色時，算法即停止。如果在這一點上兩個圖的著色不同，則認為這兩個圖是非同構的。但是，如果著色是相同的，這些圖可能（但不一定）是同構的。換句話說，Weisfeiler-Lehman 測試是圖同構的一個必要但不充分的條件。有一些非同構圖的 Weifeiler-Lehman 測試可以產生相同的著色，因此認為它們「可能是同構的」；據說在這種情況下，測試失敗了。下圖就顯示了一個這樣的例子：
Weisfeiler-Lehman 圖同構測試失敗的兩個非同構圖，從它產生的相同著色可以明顯看出。在化學中，這些圖代表兩種不同化合物的分子結構，十氫化萘（左）和雙環戊基（右）。圖摘自【14】。
圖同構網絡。Keyulu Xu【9】和 Christopher Morris【10】（至少在兩年前，Thomas Kipf 在他的 博客 中曾提到）注意到，Weisfeiler-Lehman 測試與圖消息傳遞神經網絡【8】有著驚人的相似之處，後者是一種對圖進行類似卷積運算的方式。在消息傳遞層中，通過聚合相鄰節點的特徵來更新每個節點的特徵。聚合和更新操作的選擇至關重要：只有多集內射函數才能使其等同於 Weisfeiler-Lehman 算法。一些文獻中常用的聚合器選擇，例如，最大值或均值，實際上嚴格來說沒有 Weisfeiler-Lehman 強大，並且無法區分非常簡單的圖結構：
圖結構的示例，不能用最大值來區分，但可以用均值聚合器（第一和第二）來區分，並且既不能用最大值也不能用均值（第一和第三）來區分。原因在於，以這種方式從黑色節點的鄰居聚合的特徵將是相同的。圖改編自【9】。
Xu 提出了一種聚合和更新函數的選擇，使消息傳遞神經網絡與 Weisfeiler-Lehman 算法等價，稱之為圖同構網絡（Graph Isomorphism Networks，GIN）。這和標準的消息傳遞神經網絡一樣強大。但是，比起一個新的架構，主要的影響是在一個簡單的設置中系形成表達能力的問題，這可能與圖論中的一個景點問題有關。這一想法已經激發了許多後續研究。
Weisfeiler-Lehman 層次結構。對 Xu 和 Morris 的結果進行擴展的一個方向是使用更強大的圖同構測試。由 László Baba 提出的 k-WL 測試是 Weisfeiler-Lehman 算法的高階擴展，該算法適用於 k 元組而不是單個節點。除了等價的 1-WL 和 2-WL 測試之外，對於任何 k≥2，(k+1)-WL 嚴格強於 k-WL，即存在 k-WL 失敗而 (k+1)-WL 成功的圖的例子，但反之則不然。因此，k-WL 是一個層次結構或越來越強大的圖同構測試，有時被稱為 Weisfeiler-Lehman 層次結構【10】。
設計遵循 k-WL 測試的圖神經網絡是可能的，因此嚴格來說，比消息傳遞架構更強大。其中一個這樣的第一個架構，k-GNN，是由 Morris【11】提出的。傳統消息傳遞神經網絡和高階 GNN 之間的關鍵區別在於它們是非局部的，因為 k-WL 算法是在節點的 k 元組上進行操作的。這對算法的實現及其計算和內存複雜性都有重要的影響：k-GNN 需要 𝒪(nᵏ) 內存。作為一種降低複雜性的方法，Morris 設計了一種基於局部鄰域聚集的 k-GNN 局部版本，但它的表現能力不如 k-WL。
在 2019 年 9 月，我有幸參與了 Haggai Maron 在魏茨曼科學研究學院（Weizmann Institute） 的博士論文答辯，他提出了略有不同的高階圖架構。Maron 基於 k 階張量【12】定義了一類不變圖網絡（Invariant Graph Network，IGN），並證明了它們與 k-WL 一樣強大。IGN 源自 k-WL 的不同變體【10】，並且就其複雜性而言，與 k-GNN 相比更有優勢。尤其是，等價於 3-WL 的 IGN「只有」二次元的複雜度，這可能是唯一一種實用的圖神經網絡架構，嚴格的說，它比消息傳遞更強大，但與前者的線性複雜度仍相去甚遠【16】。
從理論的角度來看，可證明功能強大的圖神經網絡提供了一個嚴格的數學框架，可以幫助解釋和比較不同的算法。已經有很多後續工作使用圖論和分布式局部算法的方法擴展了這些結果【14】。
然而，從實踐的角度來看，這些新的架構幾乎沒有什麼重大影響：例如，最新的基準測試【15】表明，最近被證明功能強大的算法實際上性能並不如舊的技術。這在機器學習中並不少見，因為理論和實踐之間往往存在很大差距。其中一個解釋可能是基準本身的缺陷。但也許更為深刻的原因是，更好的表達能力並不一定提供更好的泛化（有時恰恰相反），此外，圖同構模型可能無法正確地捕捉特定應用程式中圖相似性的實際概念，我想在下一篇文章中討論這一點。可以肯定的是，這一領域的研究工作是卓有成效的，它為其他學科搭建了橋梁，並帶來了以前在圖深度學習領域未使用過的方法。
【1】 即在兩個圖的節點之間存在一個保邊雙射（edge-preserving bijection）。
【2】 因此，圖同構可能是 NP- 中間 複雜度類。對於一些特殊的圖族（如樹、平面圖或有界最大度圖），存在多項式時間算法。
【3】 《圖的標準型化簡及其代數》（The reduction of a graph to canonical form and the algebra which appears therein），B. Weisfeiler、A. Lehman，1968 年，Nauchno-Technicheskaya Informatsia 2(9):12–16。英文版、俄文版：文中包含了一個雙關語，以一種不尋常的西裡爾字母（Операция „Ы「）的形式出現，指的是三年前 前蘇聯的同名電影。另請參閱這篇博文中一個流行的論述。Lehman 有時也被拼寫成「Leman」，然而，鑑於這個姓氏的日耳曼起源，我更喜歡前者更準確的變體。
【4】 I. Ponomarenko，Weisfeiler Lehman 寫的原始論文。提供了這篇經典論文的歷史背景。他指出，這項研究的動機來自於化學應用。
【5】 《隨機圖同構》（Random graph isomorphism），L. Babai 等人，1980 年，SIAM J. Computing 9(3):628–635。
【6】 Weisfeiler 和 Lehman 的原始論文實際上描述了 2-WL 變體，但它等價於 1-WL，也被稱為色彩細化算法。作為一個歷史性的注釋，這樣的算法早在 20 世紀計算化學中就已為人所知，參見 H.L.Morgan。《為化學結構生成獨特的機器描述——化學文摘社（Chemical Abstracts Service，CAS）開發的一種技術》（The generation of a unique machine description for chemical structures — a technique developed at chemical abstracts service ），1965 年， J. Chem，Doc. 5(2):107–113，這是摩根分子指紋在化學中廣泛應用的基礎。
【7】 多集是一個集合，其中，同一個元素可能出現多次，但元素的順序並不重要。
【8】 《量子化學中的神經信息傳遞》（Neural message passing for quantum chemistry），Gilmer 等人，2017 年，Proc. ICML。
【9】 《圖神經網絡有多強大？》（How powerful are graph neural networks?），K. Xu 等人，2019 年，Proc. ICLR。
【10】 Weisfeiler-Lehman 測試存在多重變體，它們具有不同的計算和理論特性，而且屬於相當混亂：建議讀者清楚地理解不同作者對「k-WL」一詞的確切含義。有些作者，路 Sato 和 Maron，就區分了 WL 和「民俗」WL（FWL）測試，這兩種測試的主要不同之處在於色彩細化步驟。k-FWL 測試等價於 (k+1)-WL。Morris 使用的集合 k-WL 算法是另一種變體，具有較低的內存複雜度，但嚴格弱於 k-WL 算法。
【11】 《Weisfeiler 和 Leman Go 神經網絡：高階圖神經網絡》（Weisfeiler and Leman go neural: Higher-order graph neural networks），C. Morris 等人，2019 年，Proc. AAAI。
【12】 《不變圖網絡和等變圖網絡》（Invariant and equivariant graph networks），H. Maron，2019 年，Proc. ICLR.
【13】 《可證明功能強大的圖神經網絡》（Provably powerful graph neural networks），H. Maron 等人，Proc. NeurIPS。另請參閱作者的 博文/>)。
【14】 《圖神經網絡表達能力研究綜述》（A survey on the expressive power of graph neural networks），R. Sato，2020 年，arXiv: 2003.04078。提供了有關不同 Weisfeiler-Lehman 測試和等價圖神經網絡結構的一個非常全面的回顧，並提供了與分布式計算算法的連結。
【15】 《基準圖神經網絡》（Benchmarking graph neural networks），V. P. Dwivedi 等人，2020 年，arXiv: 2003.00982。
【16】更準確地說，消息傳遞的複雜性與邊數呈線性關係，而不是與節點數呈線性關係。在稀疏圖中，情況大致相同。在稠密圖中，邊數可以是 𝒪(n²)。出於這一原因，Maron 認為他的架構可以用於稠密圖。
【17】 從歷史上講，Weisfeiler-Lehman 的形式主義在機器學習社區中並不新鮮。《圖的快速子樹核》（Fast subtree kernels on graphs），N. Shervashidze 和 K. M. Borgwardt 合著的開創性論文，2009 年，Proc. NIPS，就我所知，在深度神經網絡的復甦之前，該論文是第一個使用這種架構的，比本文所討論的工作早了近十年。
作者介紹：
Michael Bronstein，倫敦帝國理工學院教授，Twitter 圖機器學習研究負責人，CETI 項目機器學習領導、Twitter 圖機器學習負責人、研究員、教師、企業家和投資者。
原文連結：
https://towardsdatascience.com/expressive-power-of-graph-neural-networks-and-the-weisefeiler-lehman-test-b883db3c7c49
你也「在看」嗎？👇