Rethinking the Expressive Power of GNNs via Graph Biconnectivity

在圖神經網路（Graph Neural Networks, GNNs）日益成為處理圖結構資料的主流工具背景下，如何提升其表示能力一直是學術界與工業界熱烈關注的課題。傳統上，GNN 的表現力多以 Weisfeiler-Lehman（WL）圖同構測試作為理論基礎，WL 測試強調透過節點特徵的反覆聚合來識別圖結構特徵的差異。然而，WL 測試雖已設為衡量 GNN 表現力的標準，卻也受到其內在限制，無法有效捕捉到圖中更細膩且複雜的結構資訊。

ICLR 2023 傑出論文《Rethinking the Expressive Power of GNNs via Graph Biconnectivity》由 Zhang 等人提出了一個全新視角：以「圖的雙連通性」（biconnectivity）作為衡量 GNN 表現力的基準。論文指出，過去多數提升 GNN 的方法皆聚焦於超越 WL 測試的某些變種，卻缺乏對「到底在結構層面還能捕捉到什麼更豐富訊息」的系統性探索。作者們創新性地提出一組基於雙連通性的表達力度量，並分析其在理論與實務上的重要性與應用潛力。

研究背景與動機

WL 測試作為圖同構判斷的有效工具雖然被廣泛應用於設計 GNN，但其本身存在無法辨識某些非同構圖結構的限制，尤其難以刻畫局部結構的韌性與關鍵節點的重要性。雙連通性是圖論中一個基本且經典的概念，反映了一個圖在刪除任意節點後仍能保持連通的能力，對理解節點和邊在整體結構中的關鍵性極為關鍵。作者們認為，若能讓 GNN 理解並學習雙連通性，即能捕捉對應於圖結構穩健性和脆弱性的更多層次訊息，這將是超越 WL 測試的新里程碑。

核心方法與創新

本論文的核心創新首先是定義了一套基於雙連通性的表達力衡量標準，包括但不限於節點是否為割點（articulation point）、邊是否為割邊（bridge）等指標。這些指標能以線性時間算法高效計算，理論上 GNN 應當能輕易學習。然而，作者系統性地回顧了當前多數主流及先進 GNN 架構，發現它們多數對這類雙連通性的指標存在表達力不足的現象，令人意外的是，只有最近提出的 ESAN 框架在理論上被證明具備完整捕捉這些雙連通性指標的能力。

基於對既有架構的限制洞察，作者進而提出一種全新且更有效率的 GNN 表達力提升方法，稱為 Generalized Distance Weisfeiler-Lehman (GD-WL)。GD-WL 將雙連通性的概念融入距離消息傳遞機制中，以距離泛化的角度超越傳統 WL 迭代聚合，從理論上證明該方法能完整表達所有雙連通性量測標準。此外，為了實務應用的可行性，作者展示GD-WL可利用類 Transformer 架構實現，不僅保有理論上高度表達力，更能實現完整的並行化運算，符合工業級別需求。

主要實驗結果

論文中，作者使用合成圖與真實圖數據集大規模驗證所提方法的有效性。合成實驗透過設計精巧的結構測試任務，嚴格檢驗了不同 GNN 架構於雙連通性判別上的準確度，結果顯示GD-WL明顯優於包括 ESAN 在內的先前多種架構。除此之外，在涵蓋節點分類、邊辨識及圖分類等多種下游任務的真實數據集上，GD-WL 在保持大幅提升模型表達力的同時，也展現良好的泛化能力與實際效能。

值得注意的是，GD-WL結合 Transformer 架構的設計，使得模型在大型圖資料處理中能有高度的併行效率，顯著降低運算時間，並維持較低的記憶體消耗，展示出此架構在產業應用中的潛力。

對 AI 領域的深遠影響

本論文突破過去以 WL 測試為唯一標準的 GNN 表達力研究框架，提出利用圖的雙連通性作為全新視角，不僅豐富了學術界對圖神經網路本質能力的認知，也為未來設計更強大、更理論紮實的 GNN 系統開闢新道路。所提出的 GD-WL 方法在理論嚴謹性及實際效能間取得難得平衡，並且透過 Transformer 類架構的封裝，有望成為實際應用的主流模型之一。

除此之外，雙連通性本身在社會網絡分析、分子結構預測、基礎設施網絡穩定性及生物資訊學等多領域均有重要應用，該論文提出的方法將直接推動這些領域中圖結構資料的深層分析與預測能力，提高關鍵節點與脆弱點辨識的準確率和效率，進而帶來更精確的決策支持。

最後，這項研究同時呼應了近年 GNN 發展趨勢，即從單純的節點層次聚合走向更高階結構特徵的提取與融合，強調理論基礎與實務需求並重，促進 GNN 技術從「黑盒」向「白盒」解釋能力的轉變，具有深遠的學術與實務意義。

綜合來看，Zhang 等人的這篇 ICLR 2023 傑出論文，不僅為圖神經網路的表達力問題帶來全新洞見，也奠定未來圖學習方法多維度創新的基石，是每位關注圖神經網路理論與應用者不可不讀的里程碑之作。

---

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