論文の概要: Lost in Aggregation: On a Fundamental Expressivity Limit of Message-Passing Graph Neural Networks

• arxiv url: http://arxiv.org/abs/2603.14846v1
• Date: Mon, 16 Mar 2026 05:45:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-17 16:19:36.073438
• Title: Lost in Aggregation: On a Fundamental Expressivity Limit of Message-Passing Graph Neural Networks
• Title（参考訳）: 集約の損失:メッセージパッシンググラフニューラルネットワークの基本表現性限界について
• Authors: Eran Rosenbluth,
• Abstract要約: グラフグラフニューラルネット(MP-GNN)のほとんどの認識可能なアグリゲーションをキャプチャする関数の一般的なクラスを定義する。 そのようなアグリゲーションを持つMP-GNNモデルは、すべてのグラフ上の同値クラスの2変量しか引き起こさないことを証明している。
• 参考スコア（独自算出の注目度）: 2.233624388203003
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: We define a generic class of functions that captures most conceivable aggregations for Message-Passing Graph Neural Networks (MP-GNNs), and prove that any MP-GNN model with such aggregations induces only a polynomial number of equivalence classes on all graphs - while the number of non-isomorphic graphs is doubly-exponential (in number of vertices). Adding a familiar perspective, we observe that merely 2-iterations of Color Refinement (CR) induce at least an exponential number of equivalence classes, making the aforementioned MP-GNNs relatively infinitely weaker. Previous results state that MP-GNNs match full CR, however they concern a weak, 'non-uniform', notion of distinguishing-power where each graph size may required a different MP-GNN to distinguish graphs up to that size. Our results concern both distinguishing between non-equivariant vertices and distinguishing between non-isomorphic graphs.
• Abstract（参考訳）: 我々は、メッセージパッシンググラフニューラルネットワーク(MP-GNN)のほとんどの集合をキャプチャする関数の一般的なクラスを定義し、そのようなアグリゲーションを持つMP-GNNモデルは、全てのグラフ上の同値クラスの多項式数だけを誘導するのに対し、非同型グラフの数は二重指数(頂点数)であることを示す。 慣れ親しんだ視点を加えると、カラーリファインメント(CR)は少なくとも指数関数的な数の同値類を誘導し、上記のMP-GNNは相対的に無限に弱くなる。 以前の結果では、MP-GNNは完全なCRと一致するが、各グラフサイズが異なるMP-GNNを必要とするような、弱い「一様ではない」概念を懸念している。 この結果は、非同変頂点の区別と非同型グラフの区別の両方に関係している。

関連論文リスト

• Generalization, Expressivity, and Universality of Graph Neural Networks on Attributed Graphs [53.27010448621372]
  ノード属性を持つ属性グラフ上でのグラフニューラルネットワーク(GNN)の普遍性と一般化を解析する。 我々は、GNNに対する普遍近似定理と、属性グラフの任意のデータ分布上のGNNの有界一般化を証明した。 我々の研究は、属性のないグラフのみの導出理論、GNNが連続だが分離パワーのない導出コンパクトなメトリクス、GNNが連続かつ分離ポイントである導出指標を拡張・統合する。
  論文  参考訳（メタデータ） (2024-11-08T10:34:24Z)
• Permutation-Invariant Graph Partitioning:How Graph Neural Networks Capture Structural Interactions? [2.7398542529968477]
  グラフニューラルネットワーク(GNN)は、グラフ関連学習タスクの基盤となるための道を開いた。 しかし、グラフ内の構造的相互作用を捕捉するGNNの能力は、まだ解明されていない。 構造的相互作用の学習において,GNNの表現力を効率的に向上する新しいアーキテクチャであるグラフ分割ニューラルネットワーク(GPNN)を提案する。
  論文  参考訳（メタデータ） (2023-12-14T06:08:35Z)
• Fine-grained Expressivity of Graph Neural Networks [15.766353435658043]
  我々は1ドルWLとMPNNの連続的な拡張をグラファイトに検討する。 連続的な1ドルWLの変動は,MPNNのグラフ上での表現力の正確なトポロジ的特徴を与えることを示す。 また,グラフ距離の保存能力に基づいて,異なるMPNNアーキテクチャの評価を行った。
  論文  参考訳（メタデータ） (2023-06-06T14:12:23Z)
• Seq-HGNN: Learning Sequential Node Representation on Heterogeneous Graph [57.2953563124339]
  本稿では,シーケンシャルノード表現,すなわちSeq-HGNNを用いた新しい異種グラフニューラルネットワークを提案する。 Heterogeneous Graph Benchmark (HGB) と Open Graph Benchmark (OGB) の4つの広く使われているデータセットについて広範な実験を行った。
  論文  参考訳（メタデータ） (2023-05-18T07:27:18Z)
• A Topological characterisation of Weisfeiler-Leman equivalence classes [0.0]
  グラフニューラルネットワーク(GNN)は、グラフと信号をグラフ上で処理することを目的とした学習モデルである。 本稿では、GNNが区別できないグラフのクラスを完全に特徴づけるために、被覆空間の理論に依存する。 データセット内の識別不能グラフの数は,ノード数とともに指数関数的に増加することを示す。
  論文  参考訳（メタデータ） (2022-06-23T17:28:55Z)
• On Graph Neural Networks versus Graph-Augmented MLPs [51.23890789522705]
  Graph-Augmented Multi-Layer Perceptrons (GA-MLPs)は、まずグラフ上の特定のマルチホップ演算子でノード機能を拡張する。 我々は,GA-MLPとGNNの表現力の分離を証明し,指数関数的に成長することを示す。
  論文  参考訳（メタデータ） (2020-10-28T17:59:59Z)
• Permutation-equivariant and Proximity-aware Graph Neural Networks with Stochastic Message Passing [88.30867628592112]
  グラフニューラルネットワーク(GNN)は、グラフ上の新たな機械学習モデルである。 置換等価性と近接認識性は、GNNにとって非常に望ましい2つの重要な特性である。 既存のGNNは、主にメッセージパッシング機構に基づいており、同時に2つの特性を保存できないことを示す。 ノードの近さを保つため,既存のGNNをノード表現で拡張する。
  論文  参考訳（メタデータ） (2020-09-05T16:46:56Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。 GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。 より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。 本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
  論文  参考訳（メタデータ） (2020-08-31T23:15:40Z)
• Let's Agree to Degree: Comparing Graph Convolutional Networks in the Message-Passing Framework [5.835421173589977]
  我々は、グラフ上に定義されたニューラルネットワークをメッセージパッシングニューラルネットワーク(MPNN)としてキャストした。 匿名MPNNと学位対応MPNNの2種類のMPNNについて検討する。 Wesfeiler-Lehman (WL)アルゴリズムの差分パワーの観点から,MPNNの差分パワーの下位値と上位値を求める。
  論文  参考訳（メタデータ） (2020-04-06T12:14:00Z)

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

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