Rethinking the Expressive Power of GNNs via Graph Biconnectivity

近年來，圖神經網路（Graph Neural Networks, GNNs）因其在社交網路分析、分子結構預測、交通路網等多種場景中優秀的圖結構學習能力，成為機器學習與深度學習研究的重要方向。然而，如何衡量與提升 GNN 的表示能力（expressive power）一直是核心且具挑戰性的問題。傳統上大多數研究著眼於 GNN 能否區分不同圖結構，常用的理論基準為 Weisfeiler-Lehman（WL）同構測試，特別是 1-WL 的表示力被視為衡量 GNN 識別能力的關鍵標準。

本論文《Rethinking the Expressive Power of GNNs via Graph Biconnectivity》，由 Zhang 等人發表於 ICLR 2023 並獲得卓越論文獎，帶來了一個突破性的觀點：單憑提升 WL 測試能力，並不足以全面理解與衡量 GNN 的表達力；應該從圖的「雙連通性」（biconnectivity）來重新思考 GNN 的表達能力及其理論基礎。

研究背景與動機

WL 測試是目前主流用於判定 GNN 是否能區分非同構圖的理論工具。雖然提升 WL 測試的等級（如 k-WL）或改進消息傳遞機制能提高 GNN 表達力，但這些方法往往計算複雜度高，且在理論上存在表達盲點。此外，WL 測試主要側重於節點鄰域的結構相似性判斷，未必能涵蓋圖結構更深層的連通性與拓撲特性。

雙連通性是圖論中極具代表性的結構特性，描述了一個圖中的節點對其連通性的影響。具體來說，雙連通子圖是刪除任意一個節點後仍保持連通的部分。這種特性對於分子結構、社會網路中關鍵節點或橋樑節點的分析非常重要。由於雙連通性計算可用簡單且線性時間的算法實現，若 GNN 能有效捕捉該特性，將能提升其理論及應用的表示力。然而，現有大多數 GNN 架構是否能捕捉雙連通性，在文獻中並未明確揭示。

核心方法與創新

作者首創性地提出一組基於圖雙連通性的表達力指標，用以衡量 GNN 能否理解及辨識圖中的雙連通結構。透過理論證明和嚴謹的圖論分析，他們指出大多數經典 GNN 架構，包括基於 1-WL 和其變體，在這些雙連通性指標上表達力不足，無法區分一些具有不同雙連通結構但 WL 無法判別的圖對。

論文特別討論了ESAN（Expressive Subgraph Aggregation Network），這是一個早期嘗試提升 GNN 表示力的框架。作者給出理論證明說明 ESAN 透過子圖聚合，實際上能夠捕捉雙連通性，是少數能在這一新指標上具備表達力的架構。

為了克服現有方法的限制，作者進一步提出了一個全新方法 —— Generalized Distance Weisfeiler-Lehman (GD-WL)，這是一種結合距離信息與 WL 同構測試思想的算法。GD-WL 在理論層面被證明對所有雙連通性指標均具備表達能力，大幅超越傳統 GNN 的區辨能力。

在架構實現層面，GD-WL 可以透過 Transformer 類型的神經網路實現，藉由並行計算所有節點對的距離信息，維持了高效率與擴展性。此外，這樣的架構設計使得表達力不因批次大小或並行處理而降低，從而兼具理論與實務的優勢。

主要實驗結果

作者在多組合成數據集及實際圖資料集（例如社會網路、分子圖結構）上評估了 GD-WL 架構與多種基準 GNN（包含 GCN、GAT、GIN 及 ESAN 等）。

• 區分能力實驗：在設計的雙連通性區分任務中，GD-WL 精準辨識圖中細微的雙連通差異，顯著優於其他可比較模型，證實理論中的表達力提升。
• 圖分類任務：在多個公開數據集上，GD-WL 不僅在準確率方面取得最優表現，且收斂速度快，證明其架構在實際應用中的有效性與穩定性。
• 效率與可擴展性：實驗展示 GD-WL 利用 Transformer 架構可高效執行，且隨圖規模擴大亦能保持良好性能，充分滿足大型圖數據的需求。

對 AI 領域的深遠影響

本論文從圖論基本性質 —— 雙連通性，切入 GNN 表達力的全新視角，對學術界及產業界理解圖神經網路的能力提供了重要啟示。過去 GNN 的表達力多以 WL 測試為核心，本研究突破此框架，展現了 WL 無法覆蓋的圖結構判定盲點，提出了更全面的理論度量標準。

此外，提出的 GD-WL 框架不僅理論嚴謹，且可透過 Transformer 等高效架構實現，為未來 GNN 設計開啟了新的路徑，特別是在強調拓撲綜合與結構細節的問題中具有廣泛應用潛力，如化學分子設計、網路安全、知識圖譜推理等。

總結來說，這篇論文向業界與學界提醒，要發展下一代強表達力的 GNN，不該僅停留在 WL 測試的提升，更需重視圖的深層結構特性如雙連通性，並結合可擴展、高效的神經網路實作方式。這對 GNN 理論基礎的厚實與實務應用落地都具里程碑意義，必將推動圖機器學習領域進一步蓬勃發展。

---

論文資訊
📄 Rethinking the Expressive Power of GNNs via Graph Biconnectivity
👥 Zhang, Gai, Wang, Zhang, Li, Ma
🏆 ICLR 2023 · Outstanding Paper
🔗 arxiv.org/abs/2301.09505