論文の概要: We Cannot Guarantee Safety: The Undecidability of Graph Neural Network Verification

• arxiv url: http://arxiv.org/abs/2206.05070v1
• Date: Fri, 10 Jun 2022 13:04:14 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-13 21:12:38.541012
• Title: We Cannot Guarantee Safety: The Undecidability of Graph Neural Network Verification
• Title（参考訳）: 安全を保証できない:グラフニューラルネットワーク検証の不確定性
• Authors: Marco S\"alzer and Martin Lange
• Abstract要約: グラフニューラルネットワーク(GNN)は、(全体)グラフ分類とノード分類の2つのタスクに一般的に使用される。 ノード分類の場合の検証は、検討されたグラフの度合いを制限するとすぐに決定可能であることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph Neural Networks (GNN) are commonly used for two tasks: (whole) graph classification and node classification. We formally introduce generically formulated decision problems for both tasks, corresponding to the following pattern: given a GNN, some specification of valid inputs, and some specification of valid outputs, decide whether there is a valid input satisfying the output specification. We then prove that graph classifier verification is undecidable in general, implying that there cannot be an algorithm surely guaranteeing the absence of misclassification of any kind. Additionally, we show that verification in the node classification case becomes decidable as soon as we restrict the degree of the considered graphs. Furthermore, we discuss possible changes to these results depending on the considered GNN model and specifications.
• Abstract（参考訳）: グラフニューラルネットワーク(gnn)は、グラフ分類とノード分類の2つのタスクで一般的に使用される。 GNN、有効な入力の仕様、有効な出力の仕様が与えられた場合、出力仕様を満たす有効な入力が存在するかどうかを判断する。 次に、グラフ分類器の検証が一般に決定不能であることを証明し、いかなる種類の誤分類もないことを確実に保証するアルゴリズムが存在しないことを示唆する。 さらに,ノード分類の場合の検証は,検討されたグラフの度合いを制限するとすぐに決定可能であることを示す。 さらに,検討したgnnモデルと仕様による結果の変更の可能性について検討する。

関連論文リスト

• Degree-based stratification of nodes in Graph Neural Networks [66.17149106033126]
  グラフニューラルネットワーク(GNN)アーキテクチャを変更して,各グループのノードに対して,重み行列を個別に学習する。 このシンプルな実装変更により、データセットとGNNメソッドのパフォーマンスが改善されているようだ。
  論文  参考訳（メタデータ） (2023-12-16T14:09:23Z)
• GNNEvaluator: Evaluating GNN Performance On Unseen Graphs Without Labels [81.93520935479984]
  本稿では,ラベル付きおよび観測されたグラフに基づいて学習した特定のGNNモデルの性能を評価することを目的とした,新しい問題であるGNNモデル評価について検討する。 本稿では,(1) DiscGraph セット構築と(2) GNNEvaluator トレーニングと推論を含む2段階の GNN モデル評価フレームワークを提案する。 DiscGraphセットからの効果的なトレーニング監督の下で、GNNEvaluatorは、評価対象であるGNNモデルのノード分類精度を正確に推定することを学ぶ。
  論文  参考訳（メタデータ） (2023-10-23T05:51:59Z)
• DEGREE: Decomposition Based Explanation For Graph Neural Networks [55.38873296761104]
  我々は,GNN予測に対する忠実な説明を提供するためにDGREEを提案する。 GNNの情報生成と集約機構を分解することにより、DECREEは入力グラフの特定のコンポーネントのコントリビューションを最終的な予測に追跡することができる。 また,従来の手法で見過ごされるグラフノード間の複雑な相互作用を明らかにするために,サブグラフレベルの解釈アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2023-05-22T10:29:52Z)
• On the approximation capability of GNNs in node classification/regression tasks [4.141514895639094]
  グラフニューラルネットワーク(GNN)は、グラフ処理のための幅広い種類の接続モデルである。 GNNはノード分類/回帰タスクの確率の普遍近似であることを示す。
  論文  参考訳（メタデータ） (2021-06-16T17:46:51Z)
• Watermarking Graph Neural Networks by Random Graphs [38.70278014164124]
  GNNモデルに透かしを施す動機となるGNNモデルの所有権を保護する必要がある。 提案手法では,ランダムなノード特徴ベクトルとラベルを持つエルドス・レニー(ER)ランダムグラフを,GNNを訓練するためのトリガとしてランダムに生成する。 モデル検証において、マークされたGNNをトリガーERグラフで活性化することにより、ウォーターマークを出力から再構成してオーナシップを検証することができる。
  論文  参考訳（メタデータ） (2020-11-01T14:22:48Z)
• A Unified View on Graph Neural Networks as Graph Signal Denoising [49.980783124401555]
  グラフニューラルネットワーク(GNN)は,グラフ構造化データの学習表現において顕著に普及している。 本研究では,代表的GNNモデル群における集約過程を,グラフ記述問題の解法とみなすことができることを数学的に確立する。 UGNNから派生した新しいGNNモデルADA-UGNNをインスタンス化し、ノード間の適応的滑らかさでグラフを処理する。
  論文  参考訳（メタデータ） (2020-10-05T04:57:18Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。 GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。 より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。 本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
  論文  参考訳（メタデータ） (2020-08-31T23:15:40Z)
• Efficient Robustness Certificates for Discrete Data: Sparsity-Aware Randomized Smoothing for Graphs, Images and More [85.52940587312256]
  本稿では,初期作業を想定したランダム化平滑化フレームワークに基づくモデル非依存の証明書を提案する。 このアプローチがさまざまなモデル、データセット、タスクに対して有効であることを示します。
  論文  参考訳（メタデータ） (2020-08-29T10:09:02Z)
• Graph Sequential Network for Reasoning over Sequences [38.766982479196926]
  シーケンスから構築されたグラフよりも推論が必要な場合を考える。 既存のGNNモデルは、まずノード列を固定次元ベクトルに要約し、次にこれらのベクトルにGNNを適用することで、この目標を達成する。 本稿では,グラフシーケンスネットワーク(GSN)と呼ばれる新しいタイプのGNNを提案する。
  論文  参考訳（メタデータ） (2020-04-04T19:18:54Z)

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

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