論文の概要: What Expressivity Theory Misses: Message Passing Complexity for GNNs

• arxiv url: http://arxiv.org/abs/2509.01254v1
• Date: Mon, 01 Sep 2025 08:44:49 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-04 15:17:03.604833
• Title: What Expressivity Theory Misses: Message Passing Complexity for GNNs
• Title（参考訳）: 表現性理論の欠如:GNNにおけるメッセージパッシングの複雑さ
• Authors: Niklas Kemper, Tom Wollschläger, Stephan Günnemann,
• Abstract要約: 我々は、ほとんどの実世界のタスクにおいて高い表現性は必要ないと論じ、基本的なWLテスト以上の表現性はめったに要求されない。 本稿では,GNNアーキテクチャがメッセージパッシングによって与えられたタスクを解くことの難しさを定量化する手法であるMessage Passing Complexity (MPC)を提案する。 MPCは、表現性理論による理論上の不合理性を保ちながら、オーバースカッシングのような現実的な限界を捉えている。
• 参考スコア（独自算出の注目度）: 51.20749443004513
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Expressivity theory, characterizing which graphs a GNN can distinguish, has become the predominant framework for analyzing GNNs, with new models striving for higher expressivity. However, we argue that this focus is misguided: First, higher expressivity is not necessary for most real-world tasks as these tasks rarely require expressivity beyond the basic WL test. Second, expressivity theory's binary characterization and idealized assumptions fail to reflect GNNs' practical capabilities. To overcome these limitations, we propose Message Passing Complexity (MPC): a continuous measure that quantifies the difficulty for a GNN architecture to solve a given task through message passing. MPC captures practical limitations like over-squashing while preserving the theoretical impossibility results from expressivity theory, effectively narrowing the gap between theory and practice. Through extensive validation on fundamental GNN tasks, we show that MPC's theoretical predictions correlate with empirical performance, successfully explaining architectural successes and failures. Thereby, MPC advances beyond expressivity theory to provide a more powerful and nuanced framework for understanding and improving GNN architectures.
• Abstract（参考訳）: GNNが区別できるグラフを特徴付ける表現性理論は、GNNを解析するための主要なフレームワークとなり、より高表現性を目指す新しいモデルとなった。 第一に、これらのタスクは基本的なWLテスト以上の表現性を必要とすることはめったにないため、ほとんどの実世界のタスクには高い表現性は必要ない。 第二に、表現性理論のバイナリ特性と理想化された仮定は、GNNの実用能力の反映に失敗する。 これらの制限を克服するため、GNNアーキテクチャがメッセージパッシングによって与えられたタスクを解くのが困難であることを示す連続測度であるMessage Passing Complexity (MPC)を提案する。 MPCは、過剰なスカッシングのような現実的な制限を捉えながら、表現性理論の理論的不合理性を保ち、理論と実践の間のギャップを効果的に狭める。 基本的GNNタスクの広範な検証を通じて、MPCの理論的予測は経験的性能と相関し、アーキテクチャの成功と失敗をうまく説明できることを示す。 これにより、MPCは表現性理論を超えて、GNNアーキテクチャの理解と改善のためのより強力でニュアンスのあるフレームワークを提供する。

関連論文リスト

• Demystifying MPNNs: Message Passing as Merely Efficient Matrix Multiplication [4.002604752467421]
  グラフニューラルネットワーク(GNN)は目覚ましい成功を収めており、その設計は理論的な理解よりも経験的な直観に大きく依存している。 本稿では,3つの基本的側面からGNN行動の包括的解析を行う。 過度なスムースではなく、勾配に関連した問題がスパースグラフの性能に著しく影響を及ぼすことを示した。 また,正規化方式の違いがモデル性能にどのように影響するか,GNNが一様ノード特徴を持つ予測を行うかについても分析する。
  論文  参考訳（メタデータ） (2025-01-31T19:48:03Z)
• Towards Bridging Generalization and Expressivity of Graph Neural Networks [11.560730203511111]
  グラフニューラルネットワーク(GNN)における表現性と一般化の関係について検討する。 本稿では,GNNの一般化と,それらが捉えることのできるグラフ構造の分散を結合する新しいフレームワークを提案する。 我々は,クラス内濃度とクラス間分離のトレードオフを明らかにする。
  論文  参考訳（メタデータ） (2024-10-14T00:31:16Z)
• Rethinking GNN Expressive Power from a Distributed Computational Model Perspective [21.723600297533835]
  事前処理と後処理を明確に指定した修正 CONGEST モデルなど,明確に定義された計算モデルを使用することによって,GNN 表現性を分析するためのより健全なフレームワークが提供される,と我々は主張する。 制約のない事前処理を許可したり、外部に計算された機能を組み込んだりすることは、これらの事前計算によって表現性が向上し、時には問題を引き起こす可能性があることを示す。 これらの否定的な結果にもかかわらず、計算モデルの観点から仮想ノードとエッジの効果を特徴付ける肯定的な結果も提示する。
  論文  参考訳（メタデータ） (2024-10-02T08:01:50Z)
• Uncertainty in Graph Neural Networks: A Survey [47.785948021510535]
  グラフニューラルネットワーク(GNN)は、様々な現実世界のアプリケーションで広く使われている。 しかし、多様な情報源から生じるGNNの予測的不確実性は、不安定で誤った予測につながる可能性がある。 本調査は,不確実性の観点からGNNの概要を概観することを目的としている。
  論文  参考訳（メタデータ） (2024-03-11T21:54:52Z)
• Hierarchical Invariance for Robust and Interpretable Vision Tasks at Larger Scales [54.78115855552886]
  本稿では、畳み込みニューラルネットワーク(CNN)のような階層型アーキテクチャを用いて、オーバーコンプリート不変量を構築する方法を示す。 オーバーコンプリート性により、そのタスクはニューラルアーキテクチャサーチ(NAS)のような方法で適応的に形成される。 大規模で頑健で解釈可能な視覚タスクの場合、階層的不変表現は伝統的なCNNや不変量に対する効果的な代替物とみなすことができる。
  論文  参考訳（メタデータ） (2024-02-23T16:50:07Z)
• Expressivity of Graph Neural Networks Through the Lens of Adversarial Robustness [42.129871250427016]
  我々は、理論的に可能であり、実証的に達成された表現力の間の大きなギャップを明らかにするためのツールとして、敵の頑健性を用いる。 また,グラフ構造に対する小さな摂動に対しても,より強力なGNNが一般化できないことを示す。
  論文  参考訳（メタデータ） (2023-08-16T07:05:41Z)
• Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depth [57.10183643449905]
  グラフニューラルネットワーク(GNN)は表現力と一般化のレンズから研究されている。 GNNのダイナミクスを深部スキップ最適化により研究する。 本研究は,GNNの成功に対する最初の理論的支援を提供する。
  論文  参考訳（メタデータ） (2021-05-10T17:59:01Z)
• Optimization and Generalization Analysis of Transduction through Gradient Boosting and Application to Multi-scale Graph Neural Networks [60.22494363676747]
  現在のグラフニューラルネットワーク(GNN)は、オーバースムーシング(over-smoothing)と呼ばれる問題のため、自分自身を深くするのは難しいことが知られている。 マルチスケールGNNは、オーバースムーシング問題を緩和するための有望なアプローチである。 マルチスケールGNNを含むトランスダクティブ学習アルゴリズムの最適化と一般化を保証する。
  論文  参考訳（メタデータ） (2020-06-15T17:06:17Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。