Fugu-MT 論文翻訳(概要): Verifying Quantized Graph Neural Networks is PSPACE-complete

論文の概要: Verifying Quantized Graph Neural Networks is PSPACE-complete

arxiv url: http://arxiv.org/abs/2502.16244v1
Date: Sat, 22 Feb 2025 14:32:30 GMT
ステータス: 翻訳完了
システム内更新日: 2025-02-25 15:51:44.492532
Title: Verifying Quantized Graph Neural Networks is PSPACE-complete
Title（参考訳）: PSPACE完全である量子グラフニューラルネットワークの検証
Authors: Marco Sälzer, François Schwarzentruber, Nicolas Troquard,
Abstract要約: 本稿では,GNN特性を検証するための線形制約付き妥当性 (LVP) 問題を提案する。妥当なアクティベーション関数に対して,LPPがPSPACEに含まれることを示す。また、PSPACEの硬さを証明し、量子化GNNの推論は実現可能であるが、一般には計算が困難であることを示す。
参考スコア（独自算出の注目度）: 12.359001424473934
License:
Abstract: In this paper, we investigate verification of quantized Graph Neural Networks (GNNs), where some fixed-width arithmetic is used to represent numbers. We introduce the linear-constrained validity (LVP) problem for verifying GNNs properties, and provide an efficient translation from LVP instances into a logical language. We show that LVP is in PSPACE, for any reasonable activation functions. We provide a proof system. We also prove PSPACE-hardness, indicating that while reasoning about quantized GNNs is feasible, it remains generally computationally challenging.
Abstract（参考訳）: 本稿では,数値化グラフニューラルネットワーク(GNN)の検証について検討する。本稿では,GNN特性を検証するための線形制約付き妥当性(LVP)問題を導入し,LVPインスタンスから論理言語への効率的な翻訳を行う。妥当なアクティベーション関数に対して,LVP は PSPACE に含まれることを示す。私たちは証明システムを提供します。また、PSPACEの硬さを証明し、量子化GNNの推論は実現可能であるが、一般には計算が困難であることを示す。

関連論文リスト

Rethinking GNN Expressive Power Research in the Machine Learning Community: Limitations, Issues, and Corrections [21.683245760896313]
我々は、よく定義された計算モデルを使用することが、GNNの表現力の特徴付けと探索に妥当なアプローチであると論じる。 We show that the WL test is not local computerable and is misaligned with the message-passing GNNs。我々は、さらなる探索のために、GNN表現力に関するいくつかのオープンな問題を強調する。
論文参考訳（メタデータ） (2024-10-02T08:01:50Z)
A Manifold Perspective on the Statistical Generalization of Graph Neural Networks [84.01980526069075]
我々は、スペクトル領域の多様体からサンプリングされたグラフ上のGNNの統計的一般化理論を確立するために多様体の視点を取る。我々はGNNの一般化境界が対数スケールのグラフのサイズとともに線形に減少し、フィルタ関数のスペクトル連続定数とともに線形的に増加することを証明した。
論文参考訳（メタデータ） (2024-06-07T19:25:02Z)
A Logic for Reasoning About Aggregate-Combine Graph Neural Networks [11.313331046805365]
各式が等価グラフニューラルネットワーク(GNN)に変換可能であることを示す。また, 満足度問題はPSPACE完全であることを示す。
論文参考訳（メタデータ） (2024-04-30T21:16:38Z)
MAG-GNN: Reinforcement Learning Boosted Graph Neural Network [68.60884768323739]
特定の研究の行は、GNNの表現性を向上させるためにサブグラフ情報を使用するサブグラフGNNを提案し、大きな成功を収めた。このような効果は、すべての可能な部分グラフを列挙することによって、GNNの効率を犠牲にする。本稿では,強化学習(RL)により強化されたGNNである磁気グラフニューラルネットワーク(MAG-GNN)を提案する。
論文参考訳（メタデータ） (2023-10-29T20:32:21Z)
How Graph Neural Networks Learn: Lessons from Training Dynamics [80.41778059014393]
グラフニューラルネットワーク(GNN)の関数空間におけるトレーニングダイナミクスについて検討する。 GNNの勾配勾配勾配最適化は暗黙的にグラフ構造を利用して学習関数を更新する。この発見は、学習したGNN関数が一般化した時期と理由に関する新たな解釈可能な洞察を提供する。
論文参考訳（メタデータ） (2023-10-08T10:19:56Z)
How does over-squashing affect the power of GNNs? [39.52168593457813]
グラフニューラルネットワーク(GNN)は、グラフ構造化データ上での機械学習のための最先端モデルである。与えられた容量のMPNNがどのノード特徴の関数クラスを学習できるかを決定するための厳密な分析を提供する。一対のノード間の十分な通信を保証するために、MPNNの容量は十分大きすぎることを証明する。
論文参考訳（メタデータ） (2023-06-06T11:15:53Z)
A Unified View on Graph Neural Networks as Graph Signal Denoising [49.980783124401555]
グラフニューラルネットワーク(GNN)は,グラフ構造化データの学習表現において顕著に普及している。本研究では,代表的GNNモデル群における集約過程を,グラフ記述問題の解法とみなすことができることを数学的に確立する。 UGNNから派生した新しいGNNモデルADA-UGNNをインスタンス化し、ノード間の適応的滑らかさでグラフを処理する。
論文参考訳（メタデータ） (2020-10-05T04:57:18Z)
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)
Efficient Probabilistic Logic Reasoning with Graph Neural Networks [63.099999467118245]
マルコフ論理ネットワーク(MLN)は、多くの知識グラフ問題に対処するために用いられる。 MLNの推論は計算集約的であり、MLNの産業規模での応用は非常に困難である。本稿では,表現力とモデルの単純さとのバランスのよいグラフニューラルネット(GNN)モデルであるExpressGNNを提案する。
論文参考訳（メタデータ） (2020-01-29T23:34:36Z)

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