為鼓勵人工智能和機器學習領域具有突出貢獻和創新性的研究，2022年3月22日， 機器學習國際頂級會議ICLR官方公布了傑出論文獎（Outstanding Paper Award）。在所投稿的4966篇論文中，來自beat365beat365賀笛、王立威教授團隊的科研成果“Rethinking the Expressive Power of GNNs via Graph Biconnectivity”成為僅有的四篇入選論文之一。

該論文的作者均為beat365beat365賀笛、王立威教授研究團隊成員：第一作者是2019級博士研究生張博航，共同第一作者為2022級博士研究生羅勝傑，指導老師為賀笛助理教授和王立威教授。

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

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

為了進一步增強圖神經網絡的表達能力，目前主流的方法是基于圖同構判定來分析不同圖神經網絡的強弱，并以判定圖同構問題的能力為标準，設計改進圖神經網絡的具體模塊。然而，由于圖同構測試本身的困難性以及與實際問題的脫節，該方法的缺陷日趨明顯，人們不清楚這些新設計的神經網絡是否有在實際場景下、解決實際問題中的能力。

割點、割邊和雙連通分量給出了關于圖結構信息的骨架描述

 與之相比，該研究團隊采用了一種從根本上不同于圖同構的全新視角來重新審視GNN的表達能力。具體來說，文章創造性地從圖雙連通性這一圖論中的重要性質出發，引入了一系列度量圖神經網絡表達能力的新穎指标，如割點、割邊、雙連通分量等。以割點和割邊作為紐帶，圖的雙連通性給出了關于圖結構信息的一種優雅的描述，這些信息在理論和實際問題中都有着廣泛的應用。例如，圖的雙連通性與最小生成樹、網絡流、圖匹配和平面圖等許多領域有密切聯系。在化學反應中，分子化學鍵的斷裂和重組對應雙連通性的割邊；在社交網絡中，割點則起到了連接不同用戶群體的橋梁作用。更重要的是，由于雙連通性可以使用具有線性計算開銷的簡單算法來計算，因此人們自然而然地期望圖神經網絡能夠輕松學到圖中的雙連通性信息，從而提升真實任務中的表現。

絕大多數圖神經網絡無法區别上面的4組圖中雙連通性的差異

然而，該研究團隊在對過去所有提出的圖神經網絡架構進行系統分析後發現，它們中的絕大多數對這些指标都不具有表達能力，這意味着主流的圖神經網絡在實際任務中的表達能力存在重大缺陷。進一步地，文章深入研究了先前方法不能解決雙連通性問題的本質原因：傳統圖神經網絡無法編碼距離信息。為此，文章提出了一種非常簡單高效的方法，即将廣義距離直接編碼到圖神經網絡的設計中，并證明了所得到了圖神經網絡能夠解決所有雙連通性問題。在實踐中，文章基于Transformer結構給出了可以判定雙連通性的神經網絡實現，它能夠保持表達能力并享有完全的并行性。相應的方法在合成數據集和真實數據集上的一系列實驗中均超越了先前的網絡架構。

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