論文の概要: The Expressive Power of Random-Feature MPNNs Across Graph Sizes

• arxiv url: http://arxiv.org/abs/2610.12809v1
• Date: Thu, 08 Oct 2026 23:38:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-13 04:06:29.319659
• Title: The Expressive Power of Random-Feature MPNNs Across Graph Sizes
• Title（参考訳）: グラフサイズにまたがるランダム機能MPNNの表現力
• Abstract要約: 連続ランダムノード特徴は、メッセージパッシングニューラルネットワーク(MPNN)の表現性を増大させる 連続的なランダムな特徴は、期待出力において任意に小さな均一誤差で有限個の色に量子化可能であることを示す。 我々はこれらのMPNNがサイズ一様ではないことを証明するためにこのフレームワークを使用し、色と独立トライアルからの表現率の利得を分析し、ランダムカラーMPNNと高次Weisfeiler-Leman手法の非互換性を確立する。
• 参考スコア（独自算出の注目度）: 13.817853443975892
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Continuous random node features increase the expressivity of message-passing neural networks (MPNNs), but existing theoretical analyses are not fine-grained enough to capture their limitations, particularly in approximating functions across graph sizes or under a fixed number of random bits. We develop a population-level framework for size-uniform approximation. For MPNNs with a graph-size-independent Lipschitz bound in their initial features, including standard mean, max, and order-normalized sum architectures, we show that continuous random features can be quantized to finitely many colors with arbitrarily small uniform error in expected output. This reduction lets us transfer limitations on finite-color distinguishability to limitations on size-uniform approximation with continuous random features. We use this framework to prove that these MPNNs are not size-uniformly universal, analyze the expressivity gains from colors and independent trials, and establish incomparability between random-color MPNNs and higher-order Weisfeiler-Leman methods. We also give finite-color MPNN constructions for tree subgraph isomorphism via color coding and a local MST task.
• Abstract（参考訳）: 連続ランダムノードの特徴は、メッセージパッシングニューラルネットワーク(MPNN)の表現性を増大させるが、既存の理論的分析は、特にグラフサイズをまたいだ近似関数や固定数のランダムビットの下で、それらの制限を捉えるのに十分な粒度ではない。 我々はサイズ一様近似のための集団レベルのフレームワークを開発する。 標準平均値,最大値,次数正規化和アーキテクチャを含む初期特徴量で有界なグラフサイズ非依存のMPNNに対して、予測出力において任意の一様誤差を伴って、連続乱数特徴を有限個の色に量子化できることが示される。 この削減により、有限色の微分可能性に関する制限を連続的なランダムな特徴を持つサイズ・ユニフォーム近似の制限に転送できる。 我々はこれらのMPNNがサイズ一様ではないことを証明するためにこのフレームワークを使用し、色と独立トライアルからの表現性向上を分析し、ランダムカラーMPNNと高次Weisfeiler-Leman手法の非互換性を確立する。 また,木部分グラフアイソモーフィズムに対する有限色MPNNの構成をカラー符号化と局所MSTタスクにより行う。

関連論文リスト

• Universality and Approximation Rates of Graph Neural Networks with Random Features [5.394466899760558]
  ランダムノードの特徴は、理論的にも経験的にもグラフニューラルネットワーク(GNN)の表現性を高めることが知られている。 PENNと部分的にランダムなノードの特徴を組み合わせることで、測定可能な置換不変あるいは置換同変関数の確率を任意に近似できることを示す。
  論文  参考訳（メタデータ） (2026-07-29T09:46:07Z)
• Lost in Aggregation: On a Fundamental Expressivity Limit of Message-Passing Graph Neural Networks [2.233624388203003]
  グラフグラフニューラルネット(MP-GNN)のほとんどの認識可能なアグリゲーションをキャプチャする関数の一般的なクラスを定義する。 そのようなアグリゲーションを持つMP-GNNモデルは、すべてのグラフ上の同値クラスの2変量しか引き起こさないことを証明している。
  論文  参考訳（メタデータ） (2026-03-16T05:45:25Z)
• On the Hölder Stability of Multiset and Graph Neural Networks [3.396731589928944]
  リプシッツとホルダーのパラメトリック関数への適応に基づくペアワイズ分離品質解析フレームワークを提案する。 一般的な和モデルでは,ネットワークの深さとともに急速に減衰する指数が期待値よりも低いことが証明される。 これらのMPNNは、敵の例を簡単に分類でき、標準的なグラフ学習タスクにおける標準MPNNと良好に比較できることを示す。
  論文  参考訳（メタデータ） (2024-06-11T06:28:21Z)
• Spatio-Spectral Graph Neural Networks [50.277959544420455]
  比スペクトルグラフネットワーク(S$2$GNN)を提案する。 S$2$GNNは空間的およびスペクトル的にパラメータ化されたグラフフィルタを組み合わせる。 S$2$GNNsは、MPGNNsよりも厳密な近似理論誤差境界を生じる。
  論文  参考訳（メタデータ） (2024-05-29T14:28:08Z)
• Scaling Structured Inference with Randomization [64.18063627155128]
  本稿では、構造化されたモデルを数万の潜在状態に拡張するためにランダム化された動的プログラミング(RDP)のファミリを提案する。 我々の手法は古典的DPベースの推論に広く適用できる。 また、自動微分とも互換性があり、ニューラルネットワークとシームレスに統合できる。
  論文  参考訳（メタデータ） (2021-12-07T11:26:41Z)
• 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)
• Breaking the Limits of Message Passing Graph Neural Networks [6.175401630947573]
  グラフニューラルネットワーク(MPNN)は、スパースグラフに適用する場合のノード数に関して線形複雑である。 本稿では, 固有値の非線形なカスタム関数により, グラフ畳み込みサポートがスペクトル領域で設計されている場合, MPNNは1-WLテストよりも理論的に強力であることを示す。
  論文  参考訳（メタデータ） (2021-06-08T13:26:56Z)
• Counting Substructures with Higher-Order Graph Neural Networks: Possibility and Impossibility Results [58.277290855841976]
  グラフニューラルネットワーク(GNN)の計算コストと表現力のトレードオフについて検討する。 新しいモデルでは、$k$のサブグラフをカウントでき、低次GNNの既知の制限を克服できることを示す。 いくつかの場合において、提案アルゴリズムは既存の高階$k$-GNNに比べて計算量を大幅に削減することができる。
  論文  参考訳（メタデータ） (2020-12-06T03:42:54Z)
• Multipole Graph Neural Operator for Parametric Partial Differential Equations [57.90284928158383]
  物理系をシミュレーションするためのディープラーニングベースの手法を使用する際の大きな課題の1つは、物理ベースのデータの定式化である。 線形複雑度のみを用いて、あらゆる範囲の相互作用をキャプチャする、新しいマルチレベルグラフニューラルネットワークフレームワークを提案する。 実験により, 離散化不変解演算子をPDEに学習し, 線形時間で評価できることを確認した。
  論文  参考訳（メタデータ） (2020-06-16T21:56:22Z)

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

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