重新思考圖神經網路的表現力：基於圖的雙連通性分析

在圖結構化資料的學習領域中，設計具備強大表現力的圖神經網路（Graph Neural Networks, GNNs）一直是研究的核心課題。GNN 的表現力往往被用 Weisfeiler-Lehman（WL）同構測試作為標準，這種測試衡量模型是否能鑑別不同的圖結構。然而，過去的多數研究主要聚焦於提升 GNN 對於 WL 測試的能力，對於 GNN 在 WL 測試外能獲得什麼「額外」且「系統性」的表現力提升，尚缺乏深入且可證明的理論分析。針對此現象，Zhang 等學者於 ICLR 2023 發表的論文《Rethinking the Expressive Power of GNNs via Graph Biconnectivity》提出一個全新的視角，藉由圖的雙連通性（biconnectivity）來重新探討 GNN 的表現力。

研究背景與動機

在圖神經網路的發展歷程中，WL 同構測試被廣泛用來作為評估 GNN 可鑑別力的理論基準。標準的 1-WL 同構測試對於某些圖結構無法區分，導致 GNN 的表現力有其侷限，因此業界和學界嘗試設計更高階的 WL 測試變種或融入外部訊息，力求突破現有限制。

然而，WL 測試本身是一種中樞思想，在表現力的檢驗上具有侷限性，其測試焦點主要集中在節點的鄰域結構聚合是否足以區分異質圖形。這使得許多現代 GNN 儘管形式多變，仍然未能明確突破 WL 的理論壁壘。更重要的是，WL 測試忽略了圖中另一重要的全局結構性質：圖的雙連通性，即圖中任兩個節點間至少存在兩條不共用邊的獨立路徑，使圖結構更為穩健且復雜。雙連通性具有豐富的理論涵義，在網絡科學、系統故障分析及生物網路中皆有重要應用價值，因此衡量 GNN 是否能夠識別並利用雙連通性成為一項極具意義的挑戰。

核心方法與理論創新

論文中，作者首次提出一套基於圖的雙連通性的新型表現力度量標準，這不僅拓展傳統 WL 同構測試的視角，更將 GNN 的學習能力與圖的結構韌性緊密聯繫起來：

• 雙連通性表現力度量：作者定義了一系列與雙連通性相關的指標，這些指標能反映圖中強連通子結構及其脆弱邊界，成為新的判別圖是否可被 GNN 區分的理論基石。
• 現有 GNN 架構的回顧與理論分析：論文指出，目前大多數主流GNN框架（例如 GCN、GraphSAGE、GIN）對這些雙連通性度量的表現力皆有限，無法有效識別和利用雙連通性特徵。唯有 ESAN 框架具備相當的表現力，且作者提供了嚴謹的理論證明支持這一點。
• GD-WL 演算法：一種普適的雙連通性表現力手段
  為突破現有框架的限制，作者提出一種命名為 Generalized Distance Weisfeiler-Lehman（GD-WL）的新型 WL 擴展算法，GD-WL 基於距離被廣義定義，能以同一框架同時捕捉圖的局部與全局雙連通結構。理論上，GD-WL 對所有提出的雙連通性度量均具備完整且可證明的表現力。
• Transformer 類架構的實現：為了兼具表現力與實務可行性，GD-WL 可藉由 Transformer 模型架構實現。此設計利用自注意力機制，實現全圖全域訊息聚合，同時保留對雙連通性特徵的敏銳感知。此外，Transformer 架構天生支持高度平行計算，提升了訓練與推論效率，是對傳統 GNN 消息傳遞模式的重要補充。

主要實驗結果

為驗證GD-WL的理論優勢，作者在多項合成及真實圖數據集上進行實驗，涵蓋結構判別、圖分類及節點分類任務，結果顯示：

• 優異的雙連通性鑑別能力：GD-WL 相較傳統 GNN，能更明確分辨具有複雜雙連通結構的圖形，提高了對圖結構異質性的辨識度。
• 較高的任務表現：在多個真實資料集（如化學分子圖、社交網絡）上，GD-WL 具備顯著超越其它先進 GNN 架構的分類準確率和泛化性能。
• 可擴展且高效實現：透過 Transformer 類架構實現的 GD-WL 不僅理論上支持全圖層級訊息融合，實驗也證明其訓練效率和推論速度均優於多數複雜的圖神經模型，適合大規模圖數據應用。

對 AI 領域的深遠影響

本論文的貢獻不僅限於提出一套新的GNN表現力評估標準，更從結構理論與模型設計兩方面推動了圖神經網路研究的新方向：

• 突破 WL 理論框架的侷限：GD-WL 擴展了 WL 測試的視野，將重點從局部鄰域聚合移向圖的深層結構韌性，為理論界提供了更廣泛且嚴謹的分析工具。
• 促進 GNN 架構的多樣化發展：結合 Transformer 機制的 GD-WL 在保證表現力的同時解決了並行運算的限制，示範了圖學習與自然語言處理架構融合的可能性，激勵後續研究探索更多跨模態混合架構。
• 加深對圖結構資訊的理解：雙連通性作為衡量圖結構穩健性與冗餘度的指標，透過本研究讓 AI 模型能敏感此類資訊，有助於在網絡安全、系統故障診斷及分子設計等應用領域獲得更精確可解釋的結果。
• 推動理論與實務的結合：論文不僅具備豐富的理論分析，實驗中亦證明 GD-WL 模型在真實應用中具有優異的性能，促使 GNN 研究不再局限於理論指標，而是可直接惠及多種實際場景。

總而言之，Zhang 等人通過引入圖的雙連通性作為 GNN 表現力的新視角，理論嚴謹且實驗扎實地展示了現有 GNN 架構在這方面的不足，並創新性地提出 GD-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