論文の概要: The Descriptive Complexity of Graph Neural Networks

• arxiv url: http://arxiv.org/abs/2303.04613v5
• Date: Tue, 03 Dec 2024 11:48:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-04 15:38:18.490962
• Title: The Descriptive Complexity of Graph Neural Networks
• Title（参考訳）: グラフニューラルネットワークの記述複雑性
• Authors: Martin Grohe,
• Abstract要約: グラフクエリはグラフニューラルネットワーク(GNN)の有界サイズファミリによって計算可能であることを示す。 GNNは、カウントとビルトインの関係を持つ一階述語論理のガードされた断片で定義できる。 GFO+Cでは1つのGNNで1つの線形アクティベーションと有理重みを持つクエリが組込み関係なく定義可能であることを示す。
• 参考スコア（独自算出の注目度）: 2.6728900378310514
• License:
• Abstract: We analyse the power of graph neural networks (GNNs) in terms of Boolean circuit complexity and descriptive complexity. We prove that the graph queries that can be computed by a polynomial-size bounded-depth family of GNNs are exactly those definable in the guarded fragment GFO+C of first-order logic with counting and with built-in relations. This puts GNNs in the circuit complexity class (non-uniform) $\text{TC}^0$. Remarkably, the GNN families may use arbitrary real weights and a wide class of activation functions that includes the standard ReLU, logistic "sigmoid", and hyperbolic tangent functions. If the GNNs are allowed to use random initialisation and global readout (both standard features of GNNs widely used in practice), they can compute exactly the same queries as bounded depth Boolean circuits with threshold gates, that is, exactly the queries in $\text{TC}^0$. Moreover, we show that queries computable by a single GNN with piecewise linear activations and rational weights are definable in GFO+C without built-in relations. Therefore, they are contained in uniform $\text{TC}^0$.
• Abstract（参考訳）: 我々はブール回路の複雑さと記述複雑性の観点からグラフニューラルネットワーク(GNN)のパワーを分析する。 GNNの多項式サイズ境界深度ファミリーで計算できるグラフクエリは、計算と組込み関係を持つ一階述語論理のガード付きフラグメント GFO+C で正確に定義可能であることを証明した。 これにより、GNNは回路複雑性クラス(非ユニフォーム)$\text{TC}^0$となる。 注目すべきことに、GNNファミリーは任意の実重みと、標準ReLU、ロジスティックな「シグモイド」、双曲的接形関数を含む幅広い種類の活性化関数を使用することができる。 GNNがランダム初期化とグローバル読み出し(いずれもGNNの標準機能)を許可されている場合、境界深さのブーリアン回路としきい値のゲートを持つのと全く同じクエリ、すなわち$\text{TC}^0$のクエリを計算できる。 さらに,GFO+Cでは,一括線形なアクティベーションと有理重みを持つ単一のGNNで計算可能なクエリが,組込み関係を伴わずに定義可能であることを示す。 したがって、それらは一様 $\text{TC}^0$ に含まれる。

関連論文リスト

• On the Expressive Power of Subgraph Graph Neural Networks for Graphs with Bounded Cycles [17.29046077604317]
  この研究は、最大$k$までの距離を持つ隣人からの情報を集約する$k$-hopサブグラフGNNを調査します。 我々は、$k$ホップ部分グラフ GNN がグラフ上の置換不変/同変連続関数を任意の誤差許容範囲内で2k+1$以上のサイクルなしで近似できることを証明した。
  論文  参考訳（メタデータ） (2025-02-06T01:25:22Z)
• Spatio-Spectral Graph Neural Networks [50.277959544420455]
  比スペクトルグラフネットワーク(S$2$GNN)を提案する。 S$2$GNNは空間的およびスペクトル的にパラメータ化されたグラフフィルタを組み合わせる。 S$2$GNNsは、MPGNNsよりも厳密な近似理論誤差境界を生じる。
  論文  参考訳（メタデータ） (2024-05-29T14:28:08Z)
• The logic of rational graph neural networks [0.7614628596146602]
  我々は,GC2 の深度 3$ のクエリは,合理的なアクティベーション関数を持つ GNN では表現できないことを証明した。 これは、すべての非ポリノミカル活性化関数がGNNの最大表現性を参照しているわけではないことを示している。 また、一階述語論理(RGC2)の有理サブフラグメントを示し、すべてのグラフに対して有理GNNがRGC2クエリを均一に表現できることを証明する。
  論文  参考訳（メタデータ） (2023-10-19T20:32:25Z)
• On the Correspondence Between Monotonic Max-Sum GNNs and Datalog [19.288835943223816]
  グラフニューラルネットワーク(GNN)に基づくデータ変換の研究 最大および総和集約関数を持つGNNのサブクラスをカバーするモノトニックマックスサムGNNの表現性について検討する。
  論文  参考訳（メタデータ） (2023-05-29T11:13:38Z)
• Logical Message Passing Networks with One-hop Inference on Atomic Formulas [57.47174363091452]
  本稿では,ニューラルネットワーク演算子から知識グラフの埋め込みを分解する,複雑な問合せ応答のためのフレームワークを提案する。 クエリグラフの上に、局所的な原子式上のワンホップ推論とグローバル論理的推論を結びつける論理メッセージパッシングニューラルネットワーク(LMPNN)を提案する。 我々のアプローチは、最先端のニューラルCQAモデルをもたらす。
  論文  参考訳（メタデータ） (2023-01-21T02:34:06Z)
• Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks [22.36443060418036]
  非同型グラフの識別におけるグラフニューラルネットワーク(GNN)の表現力は、Weisfeiler-Lehmanグラフテストと全く同じであることを示す。 本稿では,GNN 上での WL テストの高速化について述べる。
  論文  参考訳（メタデータ） (2022-11-06T22:38:49Z)
• 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)
• Graph Neural Networks: Architectures, Stability and Transferability [176.3960927323358]
  グラフニューラルネットワーク(GNN)は、グラフでサポートされている信号のための情報処理アーキテクチャである。 これらは、個々の層がグラフ畳み込みフィルタのバンクを含む畳み込みニューラルネットワーク(CNN)の一般化である。
  論文  参考訳（メタデータ） (2020-08-04T18:57:36Z)
• Expressive Power of Invariant and Equivariant Graph Neural Networks [10.419350129060598]
  Folklore Graph Neural Networks (FGNN) は、与えられたテンソル次数に対してこれまで提案されてきた最も表現力のあるアーキテクチャである。 FGNNはこの問題の解決方法を学ぶことができ、既存のアルゴリズムよりも平均的なパフォーマンスが向上する。
  論文  参考訳（メタデータ） (2020-06-28T16:35:45Z)
• Optimization and Generalization Analysis of Transduction through Gradient Boosting and Application to Multi-scale Graph Neural Networks [60.22494363676747]
  現在のグラフニューラルネットワーク(GNN)は、オーバースムーシング(over-smoothing)と呼ばれる問題のため、自分自身を深くするのは難しいことが知られている。 マルチスケールGNNは、オーバースムーシング問題を緩和するための有望なアプローチである。 マルチスケールGNNを含むトランスダクティブ学習アルゴリズムの最適化と一般化を保証する。
  論文  参考訳（メタデータ） (2020-06-15T17:06:17Z)

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

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