Rethinking the Expressive Power of GNNs via Graph Biconnectivity

隨著圖神經網絡（Graph Neural Networks，簡稱 GNNs）在處理圖結構資料上的廣泛應用，如何提升其表達能力（expressive power）成為研究熱點。過去多數文獻多從 Weisfeiler-Lehman (WL) 同構測試角度出發，嘗試設計 GNN 架構以提升識別不同圖的能力。然而，這些方式雖然在理論上有一定侷限，但對 GNNs 在更複雜結構特徵的理解仍較為混沌，缺乏系統性、可證明的理論支持。本篇來自 Zhang 等學者於 ICLR 2023 提出的獲獎論文《Rethinking the Expressive Power of GNNs via Graph Biconnectivity》即從根本角度「重思考」GNN的表達力，透過圖的「雙連通性（biconnectivity）」提供全新洞見與創新方法。

研究背景與動機

圖神經網絡的表達能力通常被視為與 WL 測試等價。WL測試是一種基於鄰居訊息聚合的節點顏色浸染演算法，能分辨大部分但非全部的圖同構問題。近年來各類基於改良WL或超越WL的模型相繼誕生，如 k-WL、GNN with random features 等，但多數研究仍聚焦於節點層面結構區分，未充分捕捉更高階拓撲特性。

論文作者指出，「雙連通性」作為圖論中描述圖結構韌性與關鍵節點的理論基石，對於理解圖的整體拓撲結構具有重要意義。雙連通性指在移除任意一個節點後，圖仍保持連通的性質，關乎橋樑節點（articulation points）與雙連通分量（biconnected components）的劃分。儘管計算雙連通性所需算法如 Tarjan 演算法具線性時間複雜度，然而主流 GNN 架構其實無法學習或區分此類拓撲特徵，這一現象引起作者深入探討。

核心方法與創新

本論文的核心貢獻在於：提出一組基於雙連通性的新型 GNN 表達力評估指標，檢驗現有 GNN 架構在這些指標上的效能，並針對表現不佳的限制提出一種新穎且理論上可證明的架構 —— 廣義距離 Weisfeiler-Lehman（Generalized Distance Weisfeiler-Lehman, GD-WL）。GD-WL 不僅能完整捕捉雙連通性指標，且具備計算效率與可擴展性。

首先，論文系統化定義了三種基於雙連通性的表達能力指標，這些指標涵蓋判斷橋樑節點、雙連通分量劃分等問題，這些任務重要於許多實際應用中的魯棒性分析和網路結構洞察。作者透徹分析了代表性的幾類 GNN，包括基於消息傳遞（Message Passing Neural Networks）、基於圖同構測試的 WL-GNN，以及 ESAN（Edge-augmented Subgraph Aggregation Network），指出除 ESAN 外，多數 GNN 無法正確學習這些雙連通結構特徵。

GD-WL 方法則是一套加權距離信息擴展的 WL 流程。不同於傳統 WL 僅匯聚鄰居資訊，GD-WL 導入了一種「圖距離與結構關聯」的嵌入策略，理論證明其能將雙連通性特徵精確映射至節點表示空間。在架構設計上，GD-WL 可由類 Transformer 結構實現，具備高度的並行運算能力，兼顧訓練效率與模型容量，這使其相較於逐層消息傳遞的 GNN，擁有更優的計算速度與擴展性。

主要實驗結果

論文在多個合成數據集及真實世界圖數據上進行嚴謹實驗驗證。合成數據中，主要設計判斷橋樑節點和雙連通分量的分類任務，實驗結果清晰展示 GD-WL 在雙連通結構判別任務上的顯著優勢，超越包括傳統訊息傳遞 GNN、WL-GNN 以及 ESAN 等先進模型。

在真實圖數據上，例如社群結構分析和蛋白質交互網絡中，GD-WL 同樣展現了提昇性能的潛力。這間接說明雙連通結構特徵在複雜網路理解中扮演關鍵角色。論文還進一步展示 GD-WL 可平行計算的設計大幅降低訓練時間，適合現實大規模圖資料集。

對 AI 領域的深遠影響

本論文從圖論基礎的雙連通性出發，重塑 GNN 表達力的研究範式，具有多層面啟示。首先，它突破了 WL 等同構測試作為 GNN 表達能力「終極標準」的思維框架，提出具有理論深度又實用可行的新指標。在此基礎上，GD-WL 不僅是新演算法，也開創結合圖距離信息與 Transformer 式設計的路徑，為後續混合拓撲推理模型提供範本。

從實務角度看，雙連通結構對於網絡安全（如橋樑節點脆弱性分析）、社會網絡（社群穩定性）及生物網絡結構理解極為重要，GD-WL 提供了一套強大工具，能讓 AI 系統更深入、精確地把握圖數據的高階結構語義。

最後，該工作激發了學界重新思考如何設計既有效率又具強表達能力的 GNN，推進圖神經網絡在理論與實務的協同發展。這份獲得 ICLR Outstanding Paper 的研究成果，不但在理論建構上具突破性貢獻，也為產業級圖 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