論文の概要: Repetition Makes Perfect: Recurrent Graph Neural Networks Match Message Passing Limit

• arxiv url: http://arxiv.org/abs/2505.00291v2
• Date: Wed, 30 Jul 2025 16:27:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-31 14:05:51.056273
• Title: Repetition Makes Perfect: Recurrent Graph Neural Networks Match Message Passing Limit
• Title（参考訳）: リカレントグラフニューラルネットワークはメッセージの通過制限にマッチする
• Authors: Eran Rosenbluth, Martin Grohe,
• Abstract要約: 我々は、計算可能リカレントグラフニューラルネットワーク(リカレントGNN)の表現性を特徴付ける。 有限精度パラメータ、和アグリゲーション、ReLUアクティベーションを持つ繰り返しGNNが任意のグラフアルゴリズムを計算できることを証明する。
• 参考スコア（独自算出の注目度）: 2.2625389420008624
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: We precisely characterize the expressivity of computable Recurrent Graph Neural Networks (recurrent GNNs). We prove that recurrent GNNs with finite-precision parameters, sum aggregation, and ReLU activation, can compute any graph algorithm that respects the natural message-passing invariance induced by the Color Refinement (or Weisfeiler-Leman) algorithm. While it is well known that the expressive power of GNNs is limited by this invariance [Morris et al., AAAI 2019; Xu et al., ICLR 2019], we establish that recurrent GNNs can actually match this limit. This is in contrast to non-recurrent GNNs, which have the power of Weisfeiler-Leman only in a very weak, "non-uniform", sense where each graph size requires a different GNN to compute with. Our construction introduces only a polynomial overhead in both time and space. Furthermore, we show that by incorporating random initialization, for connected graphs recurrent GNNs can express all graph algorithms. In particular, any polynomial-time graph algorithm can be emulated on connected graphs in polynomial time by a recurrent GNN with random initialization.
• Abstract（参考訳）: 計算可能リカレントグラフニューラルネットワーク(リカレントGNN)の表現性を正確に評価する。 有限精度パラメータ、和アグリゲーション、ReLUアクティベーションを持つ繰り返しGNNは、カラーリファインメント(またはWeisfeiler-Leman)アルゴリズムによって誘導される自然なメッセージ通過不変性に敬意を表したグラフアルゴリズムを計算可能であることを証明した。 GNNの表現力はこの不変性(Morris et al , AAAI 2019; Xu et al , ICLR 2019)によって制限されていることはよく知られているが、繰り返しGNNが実際にこの制限に適合できることは確かである。 これは、Weisfeiler-Lemanのパワーを持つ非リカレントGNNとは対照的である。 我々の構成は時間と空間の両方で多項式オーバーヘッドしか導入しない。 さらに、ランダム初期化を組み込むことで、連結グラフに対して繰り返しGNNが全てのグラフアルゴリズムを表現できることが示される。 特に、任意の多項式時間グラフアルゴリズムは、ランダム初期化を伴う繰り返しGNNによって多項式時間で連結グラフ上でエミュレートすることができる。

関連論文リスト

• Spatio-Spectral Graph Neural Networks [50.277959544420455]
  比スペクトルグラフネットワーク(S$2$GNN)を提案する。 S$2$GNNは空間的およびスペクトル的にパラメータ化されたグラフフィルタを組み合わせる。 S$2$GNNsは、MPGNNsよりも厳密な近似理論誤差境界を生じる。
  論文  参考訳（メタデータ） (2024-05-29T14:28:08Z)
• How Graph Neural Networks Learn: Lessons from Training Dynamics [80.41778059014393]
  グラフニューラルネットワーク(GNN)の関数空間におけるトレーニングダイナミクスについて検討する。 GNNの勾配勾配勾配最適化は暗黙的にグラフ構造を利用して学習関数を更新する。 この発見は、学習したGNN関数が一般化した時期と理由に関する新たな解釈可能な洞察を提供する。
  論文  参考訳（メタデータ） (2023-10-08T10:19:56Z)
• The Descriptive Complexity of Graph Neural Networks [2.6728900378310514]
  グラフクエリはグラフニューラルネットワーク(GNN)の有界サイズファミリによって計算可能であることを示す。 GNNは、カウントとビルトインの関係を持つ一階述語論理のガードされた断片で定義できる。 GFO+Cでは1つのGNNで1つの線形アクティベーションと有理重みを持つクエリが組込み関係なく定義可能であることを示す。
  論文  参考訳（メタデータ） (2023-03-08T14:32:59Z)
• Equivariant Polynomials for Graph Neural Networks [38.15983687193912]
  グラフネットワーク(GNN)は本質的に表現力に制限がある。 本稿では、GNNがある程度の同変を計算する能力に基づく代替パワー階層を提案する。 これらの強化されたGNNは、複数のグラフ学習ベンチマークの実験において最先端の結果を示す。
  論文  参考訳（メタデータ） (2023-02-22T18:53:38Z)
• Training Graph Neural Networks on Growing Stochastic Graphs [114.75710379125412]
  グラフニューラルネットワーク(GNN)は、ネットワーク化されたデータの意味のあるパターンを活用するために、グラフ畳み込みに依存している。 我々は,成長するグラフ列の極限オブジェクトであるグラフオンを利用して,非常に大きなグラフ上のGNNを学習することを提案する。
  論文  参考訳（メタデータ） (2022-10-27T16:00:45Z)
• VQ-GNN: A Universal Framework to Scale up Graph Neural Networks using Vector Quantization [70.8567058758375]
  VQ-GNNは、Vector Quantization(VQ)を使用して、パフォーマンスを損なうことなく、畳み込みベースのGNNをスケールアップするための普遍的なフレームワークである。 我々のフレームワークは,グラフ畳み込み行列の低ランク版と組み合わせた量子化表現を用いて,GNNの「隣の爆発」問題を回避する。
  論文  参考訳（メタデータ） (2021-10-27T11:48:50Z)
• On the Universality of Graph Neural Networks on Large Random Graphs [22.720758067273195]
  グラフニューラルネットワーク(GNN)の潜在位置乱数グラフに対する近似能力について検討する。 大きなグラフ極限では、GNNはc-GNNとして知られるある種の連続的なモデルに収束することが知られている。 我々は,c-SGNNが連続限界におけるc-GNNよりも厳格に強力なことを示す。
  論文  参考訳（メタデータ） (2021-05-27T12:52:36Z)
• Counting Substructures with Higher-Order Graph Neural Networks: Possibility and Impossibility Results [58.277290855841976]
  グラフニューラルネットワーク(GNN)の計算コストと表現力のトレードオフについて検討する。 新しいモデルでは、$k$のサブグラフをカウントでき、低次GNNの既知の制限を克服できることを示す。 いくつかの場合において、提案アルゴリズムは既存の高階$k$-GNNに比べて計算量を大幅に削減することができる。
  論文  参考訳（メタデータ） (2020-12-06T03:42:54Z)
• The Surprising Power of Graph Neural Networks with Random Node Initialization [54.4101931234922]
  グラフニューラルネットワーク(GNN)は、関係データ上での表現学習に有効なモデルである。 標準 GNN はその表現力に制限があり、Weisfeiler-Leman グラフ同型(英語版)の能力以外の区別はできない。 本研究では,ランダムノード(RNI)を用いたGNNの表現力の解析を行う。 我々はこれらのモデルが普遍的であることを証明し、GNNが高次特性の計算に頼らない最初の結果である。
  論文  参考訳（メタデータ） (2020-10-02T19:53:05Z)
• Expressive Power of Invariant and Equivariant Graph Neural Networks [10.419350129060598]
  Folklore Graph Neural Networks (FGNN) は、与えられたテンソル次数に対してこれまで提案されてきた最も表現力のあるアーキテクチャである。 FGNNはこの問題の解決方法を学ぶことができ、既存のアルゴリズムよりも平均的なパフォーマンスが向上する。
  論文  参考訳（メタデータ） (2020-06-28T16:35:45Z)
• Random Features Strengthen Graph Neural Networks [40.60905158071766]
  グラフニューラルネットワーク(GNN)は、さまざまなグラフ学習タスクのための強力な機械学習モデルである。 本稿では,各ノードにランダムな特徴を加えるだけで,GNNが強力になることを示す。 本稿では, グラフ畳み込みネットワーク (GCN) やグラフ同型ネットワーク (GIN) など, 通常のGNNでは解けない様々な問題を, ランダムな特徴の追加によりGNNが解決できることを示す。
  論文  参考訳（メタデータ） (2020-02-08T12:47:29Z)

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

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