Rethinking the Expressive Power of GNNs via Graph Biconnectivity

近年來，圖神經網絡（Graph Neural Networks, GNNs）成為處理圖結構數據的主力架構，廣泛應用於社交網絡分析、分子結構預測、推薦系統等多個領域。然而，GNN 的表達能力（expressive power）一直是學術界與業界共同關注的核心問題。大部分研究集中在以 Weisfeiler-Lehman (WL) 同構測試來衡量和提升 GNN 的判別能力，但 WL 測試及其變體在捕捉圖結構的細節時仍有一定限制。ICLR 2023 傑出論文《Rethinking the Expressive Power of GNNs via Graph Biconnectivity》由 Zhang 等人提出了一個全新的視角，從圖的雙連通性（biconnectivity）切入，重新定義並拓展了 GNN 的表達範疇，帶來理論與實踐雙重突破。

研究背景與動機

傳統基於 WL 1-階測試的 GNN 在判別不同圖結構時已被證明具有限制，例如對於某些結構異構的圖對仍判斷不出差異。相關改進方案如 k-WL 測試、高階 GNN 架構雖然提升了表達力，卻面臨計算複雜度飆升的困境。更重要的是，學界缺少關於 GNN 能夠系統性且可證明地獲得哪些新型圖結構資訊的深入理解。

本文提出從「圖的雙連通性」角度探討 GNN 的表達能力。雙連通性強調圖中結點和邊在維持整體連通性上的重要性，比如鑑別圖中的割點（articulation points）與橋（bridges），這些資訊在許多真實場景中對圖結構理解至關重要。例如在社交網絡中，割點反映關鍵人物節點，在交通網絡中橋則代表重要樞紐路段。基於此，作者希望突破 WL 測試框架限制，提出能捕捉雙連通性特性的 GNN 設計，提供理論保證與實務優越性。

核心方法與創新

本論文的核心貢獻可分為三個創新層面：

1. 引入雙連通性相關的表達力度量
   作者首次正式將圖的雙連通性作為評估 GNN 表達能力的新指標。雙連通性的判定可以透過割點和割邊的檢測完成，相關演算法具有線性時間複雜度，理論上相對簡單。此角度不同於傳統以 WL 同構測試為基礎的表達能力框架，提供一套更能反映真實世界圖結構的衡量尺度。
2. 理論分析現有 GNN 架構的局限與 ESAN 的獨特性
   作者詳細檢視多種主流 GNN 架構（如 GCN、GAT、GIN 等）並發現，大多數架構對雙連通性相關的度量幾乎無表達力，無法有效區分含有不同割點或割邊的圖。唯一例外是近期提出的 ESAN（Edge and Subgraph Aggregation Network）框架，本文進一步從理論層面證明其具備雙連通性判別能力，為嶄新架構提供數學依據。
3. 開發 Generalized Distance Weisfeiler-Lehman (GD-WL) 框架
   為克服現有架構不足，作者創造性提出 GD-WL，透過將距離資訊納入 WL 色彩更新過程，使得新的 WL 版本具備完整雙連通性判別能力。GD-WL 不僅擴展了傳統 WL 框架，且能被有效地用 Transformer 式網絡實現。在此設計下，模型不僅保有理論保證的表達力，也支持完全並行化處理，大幅加速訓練與推理。

實驗結果

作者針對合成數據集和多個真實圖資料集進行實驗，對比 GD-WL 與包括 GCN、GIN、GAT 以及 ESAN 的表現。結果顯示：

• 雙連通性任務中，GD-WL 完全正確辨識不同結構
  傳統 GNN 多無法區分重要割點或割邊造成的圖差異，GD-WL 則表現出明顯優勢，準確率達到理論上可達到的理想水準。
• 實務任務（如圖分類、分子屬性預測）中，GD-WL 領先現有架構
  由於更深刻理解圖結構的本質，GD-WL 透過 Transformer 實現後，模型在多個資料集均取得更高的準確度與泛化能力，同時運算效率亦優於部分高階 GNN。
• 架構的可擴展性與並行化優勢明顯
  基於 Transformer 的設計，GD-WL 支持大規模並行計算，能應對更大型的圖資料，符合工業需求。

對 AI 領域的深遠影響

這篇論文不僅在理論層面改寫了 GNN 表達力的認知，更推動了圖神經網絡設計思想的升級。首先，透過引入雙連通性作為核心指標，研究者與工程師能更準確評估與設計適合複雜圖結構的模型，突破WL測試的瓶頸。

其次，理論對現有架構如 ESAN 的功效進行正名，促進未來新型 GNN 架構基於更嚴謹的數學基礎建構。最後，GD-WL 框架示範了如何將光譜式、傳統圖算法結合最新的 Transformer 架構，既兼顧理論深度，又滿足實際應用的效率需求，為圖神經網絡發展提供了新範式。

未來，雙連通性及類似拓撲特徵的深入融入有望在生物資訊學、交通網路分析、金融風險控制等諸多領域推動更強大且可靠的圖學習模型，也為圖神經網絡的理論和應用搭建橋樑，成為推動 AI 在結構化數據領域前沿的重要里程碑。

---

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