論文の概要: The Polynomial Counting Capabilities of Message Passing Neural Networks

• arxiv url: http://arxiv.org/abs/2605.10393v1
• Date: Mon, 11 May 2026 11:38:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-12 23:28:50.770918
• Title: The Polynomial Counting Capabilities of Message Passing Neural Networks
• Title（参考訳）: メッセージパッシングニューラルネットワークの多項式カウント機能
• Authors: Marco Sälzer, Pascal Bergsträßer, Anthony W. Lin,
• Abstract要約: 線形算術を超えたMPNNのカウント機能について検討する。 ノードラベル付きグラフのグローバルカウント制限は平均MPNNを用いてチェック可能であることを示す。 また,木状構造を持つグラフ上の平均MPNNにより,ネストモードの式をキャプチャする方法を示す。
• 参考スコア（独自算出の注目度）: 4.61988967916659
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The counting power of Message Passing Neural Networks (MPNN) has been the subject of many recent papers, showing that they can express logic that involves counting up to a threshold or more generally satisfy a linear arithmetic constraint. In this paper, we study the counting capabilities of MPNN beyond linear arithmetic, primarily utilising local and global mean aggregations. In particular, our goal is to tease out conditions required to express extensions of graded modal logic with polynomial counting constraints. We show that global polynomial counting constraints in node-labelled graphs can be checked using mean MPNN under mild assumptions. Checking local constraints is also possible, if we consider formulas with no nested modalities and additionally either (i) permit sum/max aggregations, or (ii) only restrict to regular graphs. We also show how formulas with nested modalities can be captured by mean MPNN over graphs with tree-like structures and similar assumptions.
• Abstract（参考訳）: メッセージパッシングニューラルネットワーク(MPNN)のカウント能力は近年多くの論文で取り上げられており、しきい値までのカウントや、より一般に線形算術制約を満たすロジックを表現できることが示されている。 本稿では,主に局所的および大域的平均アグリゲーションを利用した線形算術を超えたMPNNのカウント機能について検討する。 特に、多項式数制約で次数修飾論理の拡張を表現するのに必要な条件をティーズアウトすることが目的である。 ノードラベル付きグラフにおける大域多項式カウント制約は,軽度仮定の下で平均MPNNを用いて検証可能であることを示す。 局所的制約のチェックも可能であり、ネストしたモダリティを持たない公式を考えるか、追加するかを考える。 i)sum/maxアグリゲーションを許可する、又は (ii)正規グラフのみに制限する。 また、木のような構造を持つグラフ上の平均MPNNにより、ネストしたモダリティを持つ公式をキャプチャする方法を示す。

関連論文リスト

• Recurrent Neural Language Models as Probabilistic Finite-state Automata [66.23172872811594]
  RNN LMが表現できる確率分布のクラスについて検討する。 単純なRNNは確率的有限状態オートマトンの部分クラスと同値であることを示す。 これらの結果は、RNN LMが表現できる分布のクラスを特徴付けるための第一歩を示す。
  論文  参考訳（メタデータ） (2023-10-08T13:36:05Z)
• On the Correspondence Between Monotonic Max-Sum GNNs and Datalog [19.288835943223816]
  グラフニューラルネットワーク(GNN)に基づくデータ変換の研究 最大および総和集約関数を持つGNNのサブクラスをカバーするモノトニックマックスサムGNNの表現性について検討する。
  論文  参考訳（メタデータ） (2023-05-29T11:13:38Z)
• The Descriptive Complexity of Graph Neural Networks [2.6728900378310514]
  グラフクエリはグラフニューラルネットワーク(GNN)の有界サイズファミリによって計算可能であることを示す。 GNNは、カウントとビルトインの関係を持つ一階述語論理のガードされた断片で定義できる。 GFO+Cでは1つのGNNで1つの線形アクティベーションと有理重みを持つクエリが組込み関係なく定義可能であることを示す。
  論文  参考訳（メタデータ） (2023-03-08T14:32:59Z)
• Counting Substructures with Higher-Order Graph Neural Networks: Possibility and Impossibility Results [58.277290855841976]
  グラフニューラルネットワーク(GNN)の計算コストと表現力のトレードオフについて検討する。 新しいモデルでは、$k$のサブグラフをカウントでき、低次GNNの既知の制限を克服できることを示す。 いくつかの場合において、提案アルゴリズムは既存の高階$k$-GNNに比べて計算量を大幅に削減することができる。
  論文  参考訳（メタデータ） (2020-12-06T03:42:54Z)
• An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
  データから制約をマイニングするための一般的なフレームワークを提案する。 特に、構造化された出力予測の推論を整数線形プログラミング(ILP)問題とみなす。 提案手法は,9×9のスドクパズルの解法を学習し,基礎となるルールを提供することなく,例からツリー問題を最小限に分散させることが可能であることを示す。
  論文  参考訳（メタデータ） (2020-06-18T20:09:53Z)
• Efficient Probabilistic Logic Reasoning with Graph Neural Networks [63.099999467118245]
  マルコフ論理ネットワーク(MLN)は、多くの知識グラフ問題に対処するために用いられる。 MLNの推論は計算集約的であり、MLNの産業規模での応用は非常に困難である。 本稿では,表現力とモデルの単純さとのバランスのよいグラフニューラルネット(GNN)モデルであるExpressGNNを提案する。
  論文  参考訳（メタデータ） (2020-01-29T23:34:36Z)

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

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