Fugu-MT 論文翻訳(概要): Verifying Graph Neural Networks with Readout is Intractable

論文の概要: 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モデルは, 非量子化モデルに対して高い精度と一般化能力を維持しつつ, 軽量であることを示す。

関連論文リスト

LoRAP: Low-Rank Aggregation Prompting for Quantized Graph Neural Networks Training [11.467461008058509]
グラフニューラルネットワーク(GNN)は、グラフデータを処理し、ノード間の関係と相互作用をキャプチャすることを目的としたニューラルネットワークである。本稿では,GNNにおける量子化学習(QAT)の性能向上のために,入力データを操作する即時学習を活用することを提案する。
論文参考訳（メタデータ） (2026-01-21T15:23:18Z)
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)
Continuous Spiking Graph Neural Networks [43.28609498855841]
連続グラフニューラルネットワーク(CGNN)は、既存の離散グラフニューラルネットワーク(GNN)を一般化する能力によって注目されている。本稿では,2階ODEを用いたCOS-GNNの高次構造について紹介する。我々は、COS-GNNが爆発や消滅の問題を効果的に軽減し、ノード間の長距離依存関係を捕捉できるという理論的証明を提供する。
論文参考訳（メタデータ） (2024-04-02T12:36:40Z)
MAG-GNN: Reinforcement Learning Boosted Graph Neural Network [68.60884768323739]
特定の研究の行は、GNNの表現性を向上させるためにサブグラフ情報を使用するサブグラフGNNを提案し、大きな成功を収めた。このような効果は、すべての可能な部分グラフを列挙することによって、GNNの効率を犠牲にする。本稿では,強化学習(RL)により強化されたGNNである磁気グラフニューラルネットワーク(MAG-GNN)を提案する。
論文参考訳（メタデータ） (2023-10-29T20:32:21Z)
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)
ProtGNN: Towards Self-Explaining Graph Neural Networks [12.789013658551454]
本稿では,プロトタイプ学習とGNNを組み合わせたプロトタイプグラフニューラルネットワーク(ProtGNN)を提案する。 ProtGNNとProtGNN+は、非解釈不能のものと同等の精度を保ちながら、本質的に解釈可能である。
論文参考訳（メタデータ） (2021-12-02T01:16:29Z)
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)

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