論文の概要: Repetition Makes Perfect: Recurrent Sum-GNNs Match Message Passing Limit

• arxiv url: http://arxiv.org/abs/2505.00291v1
• Date: Thu, 01 May 2025 04:27:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-02 19:15:55.221117
• Title: Repetition Makes Perfect: Recurrent Sum-GNNs Match Message Passing Limit
• Title（参考訳）: 繰り返しが完璧になる: Sum-GNNsのリカレントがメッセージパッシングの制限にマッチ
• Authors: Eran Rosenbluth, Martin Grohe,
• Abstract要約: 本稿では,有限精度パラメータを持つリカレントグラフニューラルネットワーク(リカレントGNN)の表現性について,第1の厳密なバウンダリを提供する。 累積アグリゲーションとReLUアクティベーションの繰り返しGNNが任意のグラフアルゴリズムをエミュレートできることを証明する。
• 参考スコア（独自算出の注目度）: 2.2625389420008624
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: We provide first tight bounds for the expressivity of Recurrent Graph Neural Networks (recurrent GNNs) with finite-precision parameters. We prove that recurrent GNNs, with sum aggregation and ReLU activation, can emulate 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 reach 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 every graph size requires a different GNN model to compute with. The emulation we construct introduces only a polynomial overhead in both time and space. Furthermore, we show that by incorporating random initialization, recurrent GNNs can emulate all graph algorithms, implying in particular that any graph algorithm with polynomial-time complexity can be emulated by a recurrent GNN with random initialization, running in polynomial time.
• Abstract（参考訳）: 本稿では,有限精度パラメータを持つリカレントグラフニューラルネットワーク(リカレントGNN)の表現性について,第1の厳密なバウンダリを提供する。 我々は、累積アグリゲーションと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)

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

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