論文の概要: 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が持つ意味以外にも、無限論理の表現力に関する純粋に論理的な洞察につながります。

関連論文リスト

• Logical Distillation of Graph Neural Networks [47.859911892875346]
  グラフを学習するための論理に基づく解釈可能なモデルと,このモデルをグラフニューラルネットワーク(GNN)から抽出するアルゴリズムを提案する。 最近の結果は、GNNの表現性と数量化器を用いた一階述語論理の2変数フラグメント(C2)の関連性を示している。
  論文  参考訳（メタデータ） (2024-06-11T10:18:58Z)
• 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)

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

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