為鼓勵人工智能和機器學習領域具有突出貢獻和創新性的研究，2024年5月7日， 機器學習國際頂級會議ICLR官方公布了傑出論文獎（Outstanding Paper Award）。在所投稿的7262篇論文中，來自beat365beat365王立威、賀笛教授團隊的科研成果“Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness”經層層選拔最終榮獲傑出論文獎提名，成為11篇榮獲傑出論文獎提名的論文之一。該論文的共同第一作者是2019級beat365博士研究生張博航與2021級數學學院本科生蓋景初，指導老師為王立威教授和賀笛助理教授。

圖神經網絡（GNN）是近年來興起的一種機器學習算法，由于其巨大的普适性，已經在各種圖數據任務上（如分子性質預測、社交網絡分析等）取得了廣泛的應用。由于圖數據結構上的複雜性，如何設計具有強大表達能力的圖神經網絡是圖機器學習領域的一個核心話題。然而，不同于傳統神經網絡結構（如多層感知機、卷積神經網絡等），主流的圖神經網絡表達能力非常受限，甚至無法區分一些結構上完全不同的簡單圖。

主流的圖神經網絡無法區分上面兩張完全不同的圖

目前研究者們已經提出了大量的工作來理解和增強圖神經網絡的表達能力。一類代表性的工作基于圖同構判定來分析不同圖神經網絡的強弱，并以判定圖同構問題的能力為标準，設計改進圖神經網絡的具體模塊。然而，由于圖同構測試本身的困難性以及與實際問題的脫節，該方法的缺陷日趨明顯。另一類代表性工作則聚焦實用場景下的圖神經網絡表達能力，如子圖計數，通過将子圖計數信息引入圖神經網絡的節點特征中來增強模型在實際中的表現。然而，子圖計數并不能全面的衡量圖神經網絡的表達能力，且相應的模型架構沒有理論上的表達能力保證。

與之相比，該研究團隊提出了一種新穎的框架來研究GNN的表達能力。具體來說，文章提出了一種定量的表達能力指标，稱為同态表達能力，它衡量了GNN對子結構進行同态計數的能力。同态是圖論中的基礎性概念，與圖上的染色、匹配、計數等問題具有密切聯系。通過研究GNN對哪些子結構能夠同态計數，同态表達能力可被定義為包含所有能夠被同态計數的子結構的集合。那麼，不同圖神經網絡的表達能力便可以由集合之間的包含關系和集合差來簡單的定量比較。

文章證明了對于四大類圖神經網絡，如消息傳遞GNN、子圖GNN、局域GNN和Folklore GNN，同态表達能力是完整的，即同态信息能夠完全決定GNN所輸出的圖表示。文章進一步通過嵌套耳分解的概念對各類GNN的同态表達能力給出了優雅的描述。

嵌套耳分解示意圖以及不同耳之間所誘導的關系樹。

接下來，文章通過三種不同的角度說明了這些理論結果的重要意義。首先，同态表達能力提供了一種極為簡單的方法來定量比較不同網絡架構的表達能力差異，這回答了先前工作所遺留的一系列開放性問題。第二，同态表達能力能夠完全決定圖神經網絡的子圖計數能力，從而理解其在實際應用中的能力，如分子圖中苯環的計數。第三，同态表達能力與圖神經網絡計算圖上多項式的能力具有密切聯系。這些結果為之前的一系列工作提供了新穎的見解，在不同子領域之間建立了橋梁，并解決了一些開放性的問題。文章最後通過實驗表明，GNN 模型的實際性能與所提出的指标非常吻合。

論文地址：https://openreview.net/forum?id=r9hNv76KoT3