論文の概要: Verifying Graph Neural Networks with Readout is Intractable

• arxiv url: http://arxiv.org/abs/2510.08045v1
• Date: Thu, 09 Oct 2025 10:29:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-10 17:54:15.010771
• Title: Verifying Graph Neural Networks with Readout is Intractable
• Title（参考訳）: 読み出し可能なグラフニューラルネットワークの検証
• Authors: Artem Chernobrovkin, Marco Sälzer, François Schwarzentruber, Nicolas Troquard,
• Abstract要約: グローバルリードアウト(ACR-GNN)を用いた量子化集約-組合せグラフニューラルネットワークの論理言語を導入する。 我々は、読み出しを伴う量子化GNNの検証タスクが(co)NEXPTIME完全であることを証明した。 また, 量子化ACR-GNNモデルは, 非量子化モデルに対して高い精度と一般化能力を維持しつつ, 軽量であることを示す。
• 参考スコア（独自算出の注目度）: 12.54120224317171
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce a logical language for reasoning about quantized aggregate-combine graph neural networks with global readout (ACR-GNNs). We provide a logical characterization and use it to prove that verification tasks for quantized GNNs with readout are (co)NEXPTIME-complete. This result implies that the verification of quantized GNNs is computationally intractable, prompting substantial research efforts toward ensuring the safety of GNN-based systems. We also experimentally demonstrate that quantized ACR-GNN models are lightweight while maintaining good accuracy and generalization capabilities with respect to non-quantized models.
• Abstract（参考訳）: 本稿では,グローバルリードアウト(ACR-GNN)を用いた量子化集約-組合せグラフニューラルネットワークの論理言語を提案する。 本稿では、論理的特徴付けを行い、読み出しを伴う量子化GNNの検証タスクが(co)NEXPTIME完全であることを証明するために利用する。 この結果から,量子化GNNの検証は計算に難航し,GNNベースのシステムの安全性確保に向けた研究が盛んに進められた。 また, 量子化ACR-GNNモデルは, 非量子化モデルに対して高い精度と一般化能力を維持しつつ, 軽量であることを示す。

関連論文リスト

• Graph Neural Networks at a Fraction [1.8175282137722093]
  本稿では、四元数空間を利用してノード表現を計算するフレームワークである四元数メッセージパッシングニューラルネットワーク(QMPNN)を紹介する。 GNN や QMPNN のコンテキストにおける適用性を再定義する。
  論文  参考訳（メタデータ） (2025-02-10T03:55:09Z)
• Rethinking GNN Expressive Power from a Distributed Computational Model Perspective [29.47675861430167]
  事前処理と後処理を明確に指定した修正 CONGEST モデルなど,明確に定義された計算モデルを使用することによって,GNN 表現性を分析するためのより健全なフレームワークが提供される,と我々は主張する。 制約のない事前処理を許可したり、外部に計算された機能を組み込んだりすることは、これらの事前計算によって表現性が向上し、時には問題を引き起こす可能性があることを示す。 これらの否定的な結果にもかかわらず、計算モデルの観点から仮想ノードとエッジの効果を特徴付ける肯定的な結果も提示する。
  論文  参考訳（メタデータ） (2024-10-02T08:01:50Z)
• Graph Neural Networks are Inherently Good Generalizers: Insights by Bridging GNNs and MLPs [71.93227401463199]
  本稿では、P(ropagational)MLPと呼ばれる中間モデルクラスを導入することにより、GNNの性能向上を本質的な能力に向ける。 PMLPは、トレーニングにおいてはるかに効率的でありながら、GNNと同等(あるいはそれ以上)に動作することを観察する。
  論文  参考訳（メタデータ） (2022-12-18T08:17:32Z)
• A Unified View on Graph Neural Networks as Graph Signal Denoising [49.980783124401555]
  グラフニューラルネットワーク(GNN)は,グラフ構造化データの学習表現において顕著に普及している。 本研究では,代表的GNNモデル群における集約過程を,グラフ記述問題の解法とみなすことができることを数学的に確立する。 UGNNから派生した新しいGNNモデルADA-UGNNをインスタンス化し、ノード間の適応的滑らかさでグラフを処理する。
  論文  参考訳（メタデータ） (2020-10-05T04:57:18Z)
• 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)
• Attentive Graph Neural Networks for Few-Shot Learning [74.01069516079379]
  グラフニューラルネットワーク(GNN)は、数ショットの学習タスクを含む多くの困難なアプリケーションにおいて、優れたパフォーマンスを示している。 少数のサンプルからモデルを学習し、一般化する能力があるにもかかわらず、GNNは通常、モデルが深くなるにつれて、過度な過度な適合と過度なスムーシングに悩まされる。 本稿では,三重注意機構を組み込むことにより,これらの課題に対処するための新しい注意型GNNを提案する。
  論文  参考訳（メタデータ） (2020-07-14T07:43:09Z)
• Efficient Probabilistic Logic Reasoning with Graph Neural Networks [63.099999467118245]
  マルコフ論理ネットワーク(MLN)は、多くの知識グラフ問題に対処するために用いられる。 MLNの推論は計算集約的であり、MLNの産業規模での応用は非常に困難である。 本稿では,表現力とモデルの単純さとのバランスのよいグラフニューラルネット(GNN)モデルであるExpressGNNを提案する。
  論文  参考訳（メタデータ） (2020-01-29T23:34:36Z)

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

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