論文の概要: Logical Characterizations of GNNs with Mean Aggregation

• arxiv url: http://arxiv.org/abs/2507.18145v1
• Date: Thu, 24 Jul 2025 07:21:49 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-25 15:10:43.12577
• Title: Logical Characterizations of GNNs with Mean Aggregation
• Title（参考訳）: 平均集約によるGNNの論理的特徴
• Authors: Moritz Schönherr, Carsten Lutz,
• Abstract要約: 本稿では,グラフニューラルネットワーク(GNN)の集約関数の平均表現力について検討する。 非均一な設定では、そのようなGNNは比モーダル論理と全く同じ表現力を持つことを示す。 均一な設定では、MSO に対する表現力は、修正自由なモーダル論理と全く同じであることを示す。
• 参考スコア（独自算出の注目度）: 7.582794029746496
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the expressive power of graph neural networks (GNNs) with mean as the aggregation function. In the non-uniform setting, we show that such GNNs have exactly the same expressive power as ratio modal logic, which has modal operators expressing that at least a certain ratio of the successors of a vertex satisfies a specified property. The non-uniform expressive power of mean GNNs is thus higher than that of GNNs with max aggregation, but lower than for sum aggregation--the latter are characterized by modal logic and graded modal logic, respectively. In the uniform setting, we show that the expressive power relative to MSO is exactly that of alternation-free modal logic, under the natural assumptions that combination functions are continuous and classification functions are thresholds. This implies that, relative to MSO and in the uniform setting, mean GNNs are strictly less expressive than sum GNNs and max GNNs. When any of the assumptions is dropped, the expressive power increases.
• Abstract（参考訳）: 本稿では,グラフニューラルネットワーク(GNN)の集約関数の平均表現力について検討する。 非一様設定では、そのようなGNNが比モーダル論理と全く同じ表現力を持つことを示す。 したがって、平均GNNの非一様表現力は、最大アグリゲーションを持つGNNよりも高いが、アグリゲーションの合計よりも低い。 一様設定では、組合せ関数が連続であり、分類関数がしきい値であるという自然な仮定の下で、MSO に対する表現力は、正確には交互なモジュラー論理のものであることを示す。 これは、MSOと均一な設定では、GNN は GNN と max GNN の合計よりも厳密に表現的でないことを意味する。 いずれかの仮定が下がれば、表現力は増大する。

関連論文リスト

• Logical Characterizations of Recurrent Graph Neural Networks with Reals and Floats [6.176021290715425]
  本稿では,2つのシナリオにおいて,繰り返しグラフニューラルネットワーク(GNN)の正確な論理的特徴について述べる。 フロートに対して、繰り返しGNNと一致する形式主義は数えられるルールベースのモーダル論理であり、実数に対しては適切な無限のモーダル論理を用いる。 キャラクタリゼーションを適用することで、モナディック二階述語論理で定義可能なグラフ特性と比較して、無限論理と規則論理は等しく表現力があることが証明できる。
  論文  参考訳（メタデータ） (2024-05-23T14:19:21Z)
• The expressive power of pooling in Graph Neural Networks [6.5268245109828005]
  グラフプーリングがグラフニューラルネットワーク(GNN)の表現性に与える影響について検討する。 プーリング演算子がMP層の表現力を完全に維持できる十分な条件を導出する。 本稿では,プール層を備えたGNNの表現力を実証的に検証するための実験装置を提案する。
  論文  参考訳（メタデータ） (2023-04-04T07:03:08Z)
• Some Might Say All You Need Is Sum [2.226803104060345]
  グラフニューラルネットワーク(GNN)の表現性は、採用する集約関数に依存する。 我々は,Mean や Max GNN によって正確に計算できる基本関数が任意の Sum GNN によって近似できないことを証明した。
  論文  参考訳（メタデータ） (2023-02-22T19:01:52Z)
• Equivariant Polynomials for Graph Neural Networks [38.15983687193912]
  グラフネットワーク(GNN)は本質的に表現力に制限がある。 本稿では、GNNがある程度の同変を計算する能力に基づく代替パワー階層を提案する。 これらの強化されたGNNは、複数のグラフ学習ベンチマークの実験において最先端の結果を示す。
  論文  参考訳（メタデータ） (2023-02-22T18:53:38Z)
• Representation Power of Graph Neural Networks: Improved Expressivity via Algebraic Analysis [124.97061497512804]
  標準グラフニューラルネットワーク (GNN) はWeisfeiler-Lehman (WL) アルゴリズムよりも差別的な表現を生成する。 また、白い入力を持つ単純な畳み込みアーキテクチャは、グラフの閉経路をカウントする同変の特徴を生じさせることを示した。
  論文  参考訳（メタデータ） (2022-05-19T18:40:25Z)
• Generalizing Graph Neural Networks on Out-Of-Distribution Graphs [51.33152272781324]
  トレーニンググラフとテストグラフの分散シフトを考慮せずにグラフニューラルネットワーク(GNN)を提案する。 このような環境では、GNNは、たとえ素早い相関であるとしても、予測のためのトレーニングセットに存在する微妙な統計的相関を利用する傾向がある。 本稿では,スプリアス相関の影響を排除するため,StableGNNと呼ばれる一般的な因果表現フレームワークを提案する。
  論文  参考訳（メタデータ） (2021-11-20T18:57:18Z)
• Equivariant Neural Network for Factor Graphs [83.26543234955855]
  因子同変ニューラルネットワーク(FE-NBP)と因子同変グラフニューラルネットワーク(FE-GNN)の2つの推論モデルを提案する。 FE-NBPは小さなデータセットで最先端のパフォーマンスを達成する一方、FE-GNNは大規模なデータセットで最先端のパフォーマンスを達成する。
  論文  参考訳（メタデータ） (2021-09-29T06:54:04Z)
• On the approximation capability of GNNs in node classification/regression tasks [4.141514895639094]
  グラフニューラルネットワーク(GNN)は、グラフ処理のための幅広い種類の接続モデルである。 GNNはノード分類/回帰タスクの確率の普遍近似であることを示す。
  論文  参考訳（メタデータ） (2021-06-16T17:46:51Z)
• Counting Substructures with Higher-Order Graph Neural Networks: Possibility and Impossibility Results [58.277290855841976]
  グラフニューラルネットワーク(GNN)の計算コストと表現力のトレードオフについて検討する。 新しいモデルでは、$k$のサブグラフをカウントでき、低次GNNの既知の制限を克服できることを示す。 いくつかの場合において、提案アルゴリズムは既存の高階$k$-GNNに比べて計算量を大幅に削減することができる。
  論文  参考訳（メタデータ） (2020-12-06T03:42:54Z)
• 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)
• Permutation-equivariant and Proximity-aware Graph Neural Networks with Stochastic Message Passing [88.30867628592112]
  グラフニューラルネットワーク(GNN)は、グラフ上の新たな機械学習モデルである。 置換等価性と近接認識性は、GNNにとって非常に望ましい2つの重要な特性である。 既存のGNNは、主にメッセージパッシング機構に基づいており、同時に2つの特性を保存できないことを示す。 ノードの近さを保つため,既存のGNNをノード表現で拡張する。
  論文  参考訳（メタデータ） (2020-09-05T16:46:56Z)
• Efficient Probabilistic Logic Reasoning with Graph Neural Networks [63.099999467118245]
  マルコフ論理ネットワーク(MLN)は、多くの知識グラフ問題に対処するために用いられる。 MLNの推論は計算集約的であり、MLNの産業規模での応用は非常に困難である。 本稿では,表現力とモデルの単純さとのバランスのよいグラフニューラルネット(GNN)モデルであるExpressGNNを提案する。
  論文  参考訳（メタデータ） (2020-01-29T23:34:36Z)

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

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