論文の概要: Towards Understanding the Expressive Power of GNNs with Global Readout

• arxiv url: http://arxiv.org/abs/2604.22870v1
• Date: Thu, 23 Apr 2026 19:27:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-28 17:12:07.014491
• Title: Towards Understanding the Expressive Power of GNNs with Global Readout
• Title（参考訳）: グローバル読み出しによるGNNの表現力の理解に向けて
• Authors: Maurice Funk, Daumantas Kojelis,
• Abstract要約: メッセージパッシングアグリゲート-コンビイン-リードアウトグラフニューラルネットワーク(ACR-GNN)の表現力について検討する。 特に、この定式化によって表現できる一階(FO)特性に着目する。
• 参考スコア（独自算出の注目度）: 2.062593640149623
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the expressive power of message-passing aggregate-combine-readout graph neural networks (ACR-GNNs). Particularly, we focus on the first-order (FO) properties expressible by this formalism. While a tight logical characterisation remains a difficult open question, we make two contributions towards answering it. First, we show that sum aggregation and readout suffice for GNNs to capture FO properties that cannot be expressed in the logic C2 on both directed and undirected graphs. This strengthens known results by Hauke and Wał{\k e}ga (2026) where aggregation and readout functions are specially crafted for the task. Second, we identify two natural ways of restoring characterisability (with regard to C2) for ACR-GNNs. One option is to limit local aggregation (without imposing restrictions on global readout), whilst the second is to run ACR-GNNs over graphs of bounded degree (but unbounded size). In both cases, the FO properties captured by GNNs are exactly those definable by a formula in graded modal logic with global counting modalities. Our results thus establish an innate lower- and upper-bound in terms of how far (fragments of) C2 can be taken to characterise GNNs, and imply that is indeed the unbounded interaction of aggregation and readout that pushes the logical expressive power of GNNs above C2.
• Abstract（参考訳）: 本稿では,ACR-GNN(ACR-GNNs)におけるメッセージパッシングアグリゲート-コンビイン-リードアウトグラフニューラルネットワークの表現力について検討する。 特に、この定式化によって表現できる一階(FO)特性に着目する。 厳密な論理的特徴付けは依然として難しい問題であるが、それに対応するために2つの貢献をしている。 まず、GNNの和集合と読み出し集合が、方向グラフと非方向グラフの両方で論理C2で表現できないFO特性を捉えるのに十分であることを示す。 これにより、Hauke と Wał{\k e}ga (2026) の既知の結果が強化され、アグリゲーションとリードアウト関数が特別にタスクのために作成される。 第2に、ACR-GNNの2つの特性回復方法(C2)を同定する。 1つの選択肢は局所的な集約を制限すること(グローバルな読み出しの制限を含まない)、もう1つは有界なグラフ上でACR-GNNを実行すること(ただし、非有界なサイズ)である。 どちらの場合も、GNNによって捕捉されるFO特性は、大域的な数え上げモーダル性を持つ次数モーダル論理の式によって正確に定義できるものである。 以上の結果から,C2 が GNN を特徴づけるためにどの程度の距離(フラグメント)を取ることができるかという点において,本研究の結果は,C2 より上の GNN の論理的表現力を押し上げる集合と読み出しの非有界相互作用であることを示す。

関連論文リスト

• Aggregate-Combine-Readout GNNs Are More Expressive Than Logic C2 [0.0]
  GNN が C2 をはるかに上回っていることを証明した。 私たちの研究は、無限論理の表現力に関する純粋に論理的な洞察につながります。
  論文  参考訳（メタデータ） (2025-08-08T07:35:35Z)
• Logical Distillation of Graph Neural Networks [47.859911892875346]
  グラフを学習するための論理に基づく解釈可能なモデルと,このモデルをグラフニューラルネットワーク(GNN)から抽出するアルゴリズムを提案する。 最近の結果は、GNNの表現性と数量化器を用いた一階述語論理の2変数フラグメント(C2)の関連性を示している。
  論文  参考訳（メタデータ） (2024-06-11T10:18:58Z)
• The logic of rational graph neural networks [0.7614628596146602]
  我々は,GC2 の深度 3$ のクエリは,合理的なアクティベーション関数を持つ GNN では表現できないことを証明した。 これは、すべての非ポリノミカル活性化関数がGNNの最大表現性を参照しているわけではないことを示している。 また、一階述語論理(RGC2)の有理サブフラグメントを示し、すべてのグラフに対して有理GNNがRGC2クエリを均一に表現できることを証明する。
  論文  参考訳（メタデータ） (2023-10-19T20:32:25Z)
• The Descriptive Complexity of Graph Neural Networks [2.6728900378310514]
  グラフクエリはグラフニューラルネットワーク(GNN)の有界サイズファミリによって計算可能であることを示す。 GNNは、カウントとビルトインの関係を持つ一階述語論理のガードされた断片で定義できる。 GFO+Cでは1つのGNNで1つの線形アクティベーションと有理重みを持つクエリが組込み関係なく定義可能であることを示す。
  論文  参考訳（メタデータ） (2023-03-08T14:32:59Z)
• 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)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。 GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。 より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。 本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
  論文  参考訳（メタデータ） (2020-08-31T23:15:40Z)
• Can Graph Neural Networks Count Substructures? [53.256112515435355]
  グラフニューラルネットワーク(GNN)の能力について,属性付きグラフサブ構造をカウントする能力を用いて検討する。 我々は2種類のサブストラクチャカウントを区別する: インダクションサブグラフカウントとサブグラフカウント、および人気のあるGNNアーキテクチャに対する肯定的および否定的な回答である。
  論文  参考訳（メタデータ） (2020-02-10T18:53:30Z)

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

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