論文の概要: Aggregate-Combine-Readout GNNs Are More Expressive Than Logic C2

• arxiv url: http://arxiv.org/abs/2508.06091v1
• Date: Fri, 08 Aug 2025 07:35:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-11 20:39:06.123025
• Title: Aggregate-Combine-Readout GNNs Are More Expressive Than Logic C2
• Title（参考訳）: Aggregate-Combine-Readout GNNはLogic C2より表現力が高い
• Authors: Stan P Hauke, Przemysław Andrzej Wałęga,
• Abstract要約: GNN が C2 をはるかに上回っていることを証明した。 私たちの研究は、無限論理の表現力に関する純粋に論理的な洞察につながります。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In recent years, there has been growing interest in understanding the expressive power of graph neural networks (GNNs) by relating them to logical languages. This research has been been initialised by an influential result of Barcel\'o et al. (2020), who showed that the graded modal logic (or a guarded fragment of the logic C2), characterises the logical expressiveness of aggregate-combine GNNs. As a ``challenging open problem'' they left the question whether full C2 characterises the logical expressiveness of aggregate-combine-readout GNNs. This question has remained unresolved despite several attempts. In this paper, we solve the above open problem by proving that the logical expressiveness of aggregate-combine-readout GNNs strictly exceeds that of C2. This result holds over both undirected and directed graphs. Beyond its implications for GNNs, our work also leads to purely logical insights on the expressive power of infinitary logics.
• Abstract（参考訳）: 近年,グラフニューラルネットワーク(GNN)の表現力の理解への関心が高まっている。 この研究は Barcel\'o et al (2020) の影響力のある結果によって初期化され、次数付きモーダル論理(または論理 C2 のガードされた断片)が集約合成 GNN の論理的表現性を特徴付けることを示した。 として、彼らは完全なC2がアグリゲート・コンビイン・リードアウトGNNの論理的表現性を特徴付けるかどうかという問題を残した。 この問題はいくつかの試みにもかかわらず未解決のままである。 本稿では,GNN の論理的表現性が C2 の論理的表現性を超えていることを証明することによって,上記のオープンな問題を解く。 この結果は、無向グラフと有向グラフの両方に当てはまる。 我々の研究は、GNNが持つ意味以外にも、無限論理の表現力に関する純粋に論理的な洞察につながります。

関連論文リスト

• Position: Message-passing and spectral GNNs are two sides of the same coin [60.47572761832418]
  グラフニューラルネットワーク(GNN)は通常、メッセージパッシングニューラルネットワーク(MPNN)とスペクトルグラフニューラルネットワーク(SGN)に分けられる。 本稿は、この分割が主に人工的であり、この分野の進歩を妨げると主張している。
  論文  参考訳（メタデータ） (2026-02-10T17:53:40Z)
• Enhancing Logical Expressiveness in Graph Neural Networks via Path-Neighbor Aggregation [22.086161213961244]
  本稿では,GNNの論理的表現力を高めるため,PN-GNN(Path-Neighbor enhanced GNN)を提案する。 まず,既存のGNN手法の論理表現力を分析し,これらの手法の欠点を指摘する。 そこで理論的にPN-GNNの論理表現力について検討し、C-GNNよりも強い表現力を持つだけでなく、$(k+1)$-hop論理表現性が$k$-hopよりも厳密に優れていることを示す。
  論文  参考訳（メタデータ） (2025-11-11T08:59:10Z)
• The Correspondence Between Bounded Graph Neural Networks and Fragments of First-Order Logic [8.430502131775723]
  本稿では,一階述語論理(FO)の顕著な断片に対応するGNNアーキテクチャを提案する。 FO内のGNNの論理的表現性を理解するための統一的なフレームワークを提供する。
  論文  参考訳（メタデータ） (2025-05-12T19:45:45Z)
• Logical Distillation of Graph Neural Networks [47.859911892875346]
  グラフを学習するための論理に基づく解釈可能なモデルと,このモデルをグラフニューラルネットワーク(GNN)から抽出するアルゴリズムを提案する。 最近の結果は、GNNの表現性と数量化器を用いた一階述語論理の2変数フラグメント(C2)の関連性を示している。
  論文  参考訳（メタデータ） (2024-06-11T10:18:58Z)
• A Manifold Perspective on the Statistical Generalization of Graph Neural Networks [84.01980526069075]
  我々は、スペクトル領域の多様体からサンプリングされたグラフ上のGNNの統計的一般化理論を確立するために多様体の視点を取る。 我々はGNNの一般化境界が対数スケールのグラフのサイズとともに線形に減少し、フィルタ関数のスペクトル連続定数とともに線形的に増加することを証明した。
  論文  参考訳（メタデータ） (2024-06-07T19:25:02Z)
• Logical Characterizations of Recurrent Graph Neural Networks with Reals and Floats [6.176021290715425]
  本稿では,2つのシナリオにおいて,繰り返しグラフニューラルネットワーク(GNN)の正確な論理的特徴について述べる。 フロートに対して、繰り返しGNNと一致する形式主義は数えられるルールベースのモーダル論理であり、実数に対しては適切な無限のモーダル論理を用いる。 キャラクタリゼーションを適用することで、モナディック二階述語論理で定義可能なグラフ特性と比較して、無限論理と規則論理は等しく表現力があることが証明できる。
  論文  参考訳（メタデータ） (2024-05-23T14:19:21Z)
• A Logic for Reasoning About Aggregate-Combine Graph Neural Networks [11.313331046805365]
  各式が等価グラフニューラルネットワーク(GNN)に変換可能であることを示す。 また, 満足度問題はPSPACE完全であることを示す。
  論文  参考訳（メタデータ） (2024-04-30T21:16:38Z)
• The logic of rational graph neural networks [0.7614628596146602]
  我々は,GC2 の深度 3$ のクエリは,合理的なアクティベーション関数を持つ GNN では表現できないことを証明した。 これは、すべての非ポリノミカル活性化関数がGNNの最大表現性を参照しているわけではないことを示している。 また、一階述語論理(RGC2)の有理サブフラグメントを示し、すべてのグラフに対して有理GNNがRGC2クエリを均一に表現できることを証明する。
  論文  参考訳（メタデータ） (2023-10-19T20:32:25Z)
• Discourse-Aware Graph Networks for Textual Logical Reasoning [142.0097357999134]
  パッセージレベルの論理関係は命題単位間の係り合いまたは矛盾を表す(例、結論文) 論理的推論QAを解くための論理構造制約モデリングを提案し、談話対応グラフネットワーク(DAGN)を導入する。 ネットワークはまず、インラインの談話接続とジェネリック論理理論を利用した論理グラフを構築し、その後、エッジ推論機構を用いて論理関係を進化させ、グラフ機能を更新することで論理表現を学習する。
  論文  参考訳（メタデータ） (2022-07-04T14:38:49Z)
• 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)
• Efficient Probabilistic Logic Reasoning with Graph Neural Networks [63.099999467118245]
  マルコフ論理ネットワーク(MLN)は、多くの知識グラフ問題に対処するために用いられる。 MLNの推論は計算集約的であり、MLNの産業規模での応用は非常に困難である。 本稿では,表現力とモデルの単純さとのバランスのよいグラフニューラルネット(GNN)モデルであるExpressGNNを提案する。
  論文  参考訳（メタデータ） (2020-01-29T23:34:36Z)

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

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