Rethinking the Expressive Power of GNNs via Graph Biconnectivity

隨著圖神經網路（Graph Neural Networks, GNNs）在處理結構化圖數據上的廣泛應用，如何提升 GNN 的辨識能力（expressive power）成為學術界與產業界關注的核心議題。大部分先前研究均以 Weisfeiler-Lehman (WL) 測試為基礎，嘗試設計更強大的 GNN 架構，以提升對圖結構的區分能力。然而，這種基於 WL 的方法存在本質限制，且對 GNN 在更複雜圖結構上的表現力仍缺乏系統且可證明的深刻理解。在此論文《Rethinking the Expressive Power of GNNs via Graph Biconnectivity》中，Zhang 等人跳脫傳統 WL 框架，從圖的「雙連通性」（biconnectivity）角度重新審視 GNN 的表達能力，並提出創新方法大幅提升 GNN 對圖結構的鑑別力，獲得 ICLR 2023 傑出論文獎，成為此領域的突破性貢獻。

研究背景與動機

圖結構資料在社會網路、生物資訊、化學分子等領域中普遍存在，而 GNN 作為一種能夠直接處理圖節點和邊緣資訊的神經網路架構，具有強大實用價值。過去多年中，WL 測試，尤其是 1-WL（又稱為顏色標籤傳播演算法），成為衡量 GNN 表達力的標準工具。經典理論指出，傳統的 GNN 架構最多相當於 1-WL 的表達能力，這限制了 GNN 對某些不可分辨結構的辨識。

然而，WL 理論主要關注節點的「等價類」辨別，較少觸及圖的更深層連通結構特徵。例如，雙連通分量是表示一個圖在刪除任一節點後仍連通的最大子結構，對圖的魯棒性及結構性特徵有著關鍵意義。儘管雙連通性算法計算簡單且效率高，但現有多數 GNN 模型卻無法有效捕獲這類信息。論文正是基於此觀察，探討 GNN 對雙連通性結構的學習表現，提出全新觀點和方法。

核心方法與創新點

本論文的中心創新在於提出一組基於圖雙連通性的新穎表達力度量指標，並系統性研究 GNN 在該指標下的表達能力。具體而言，作者從理論上證明，雖然雙連通性計算本身低成本且直觀，但現有主流 GNN 卻無法有效辨別相關結構，唯有較為複雜的 ESAN 架構具備部分能力。為此，作者設計了Generalized Distance Weisfeiler-Lehman (GD-WL)算法，從算法機理上擴展傳統 WL 方法，引入距離度量泛化，從而覆蓋所有雙連通性指標。

GD-WL 的核心機制是結合距離信息與結構標籤傳播，使 GNN 不僅能根據鄰近節點的標籤判斷區分度，更能藉由結點間廣義距離度量敏感於雙連通子圖。該方法理論上具備 對所有雙連通性結構強表達力，擺脫了傳統 WL 限制。同時，作者巧妙地證明 GD-WL 可被一種 Transformer 類神經網絡所實現，該架構保持模型的全局視野與並行計算能力，提升效率且易於擴展。

此設計亦耳目一新地結合了圖結構學習與 Transformer 計算圖的優點，使得 GD-WL 既有強大的理論支撐，也具備落地應用的可行性。此外，針對 ESAN 框架，其能夠部分捕捉雙連通特性，作者給予了嚴謹的理論闡述，補全先前工作在理解其表達力上的空白。

主要實驗結果

在實驗部分，作者針對合成圖數據與多個真實世界圖基準（如化學分子、生物網絡等）進行系統評測。結果顯示，GD-WL 架構的 GNN 在精度、泛化能力和效率方面都顯著優於多種主流 GNN 架構（包括 GIN、GAT、ESAN 等）。尤其在那些需要捕捉雙連通子圖細節的任務上，GD-WL 展現出明顯的優勢，證明了其在理論證明之外的實用價值。

具體數據顯示，GD-WL 在結構異質性高、魯棒性要求嚴格的圖分類、圖表示學習任務上平均提升了 5-10% 的性能，且執行效率亦維持在合理範圍，充分展現了「表達力與效率」的良好平衡。此外，Transformer-like 的實現架構亦驗證了其易於擴展和硬體加速的潛力。

對 AI 領域的深遠影響

此論文不僅在圖神經網路理論基礎上做出重大推進，更開闢了表現力度量新視角，促使整個 GNN 研究社群必須重新思考並超越 WL 測試的局限。透過引入圖雙連通性作為衡量標準，作者開創了一條兼具實用價值與理論深度的新路徑，加強了 GNN 對圖結構複雜性的感知和利用能力。

在應用層面，提升 GNN 表達力對於藥物分子設計、社會網絡分析及知識圖譜構建等領域意義重大。這些場域中，細微的雙連通結構往往影響資料的功能性和表現分布。GD-WL 的設計啟發後續模型設計者將更多結構性特徵納入考量，並擴展了 Transformer 與 GNN 技術的融合路徑，具示範效應。

長遠來看，論文亦激勵未來在圖結構學習中探索更多結構性指標，並從理論與實踐兩端推動圖神經網路向更高層次的普適性與表達能力邁進。它標誌著 GNN 從「同構鑑別」向「結構語意」理解的關鍵轉折，促進 AI 對複雜資料的更深層次掌握與推理能力提升。

總結而言，《Rethinking the Expressive Power of GNNs via Graph Biconnectivity》通過理論創新與實證驗證，有效突破傳統 GNN 表達能力瓶頸，提供了可操作且可擴展的新方法，深刻影響圖神經網路未來研究方向與應用實踐，是近年 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