論文の概要: 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（参考訳）: メッセージパッシングニューラルネットワークの多項式カウント機能
• 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により、ネストしたモダリティを持つ公式をキャプチャする方法を示す。

関連論文リスト

• A Logic for Reasoning About Aggregate-Combine Graph Neural Networks [11.313331046805365]
  各式が等価グラフニューラルネットワーク(GNN)に変換可能であることを示す。 また, 満足度問題はPSPACE完全であることを示す。
  論文  参考訳（メタデータ） (2024-04-30T21:16:38Z)
• 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)
• 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)
• An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
  データから制約をマイニングするための一般的なフレームワークを提案する。 特に、構造化された出力予測の推論を整数線形プログラミング(ILP)問題とみなす。 提案手法は,9×9のスドクパズルの解法を学習し,基礎となるルールを提供することなく,例からツリー問題を最小限に分散させることが可能であることを示す。
  論文  参考訳（メタデータ） (2020-06-18T20:09:53Z)
• Can Graph Neural Networks Count Substructures? [53.256112515435355]
  グラフニューラルネットワーク(GNN)の能力について,属性付きグラフサブ構造をカウントする能力を用いて検討する。 我々は2種類のサブストラクチャカウントを区別する: インダクションサブグラフカウントとサブグラフカウント、および人気のあるGNNアーキテクチャに対する肯定的および否定的な回答である。
  論文  参考訳（メタデータ） (2020-02-10T18:53:30Z)
• Efficient Probabilistic Logic Reasoning with Graph Neural Networks [63.099999467118245]
  マルコフ論理ネットワーク(MLN)は、多くの知識グラフ問題に対処するために用いられる。 MLNの推論は計算集約的であり、MLNの産業規模での応用は非常に困難である。 本稿では,表現力とモデルの単純さとのバランスのよいグラフニューラルネット(GNN)モデルであるExpressGNNを提案する。
  論文  参考訳（メタデータ） (2020-01-29T23:34:36Z)

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

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