論文の概要: Exact Verification of Graph Neural Networks with Incremental Constraint Solving

• arxiv url: http://arxiv.org/abs/2508.09320v1
• Date: Tue, 12 Aug 2025 20:10:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-14 20:42:00.681594
• Title: Exact Verification of Graph Neural Networks with Incremental Constraint Solving
• Title（参考訳）: 漸進的制約解法を用いたグラフニューラルネットワークの厳密な検証
• Authors: Minghao Liu, Chia-Hsuan Lu, Marta Kwiatkowska,
• Abstract要約: グラフニューラルネットワーク(GNN)は、不正検出や医療といった高度なアプリケーションにますます採用されているが、敵の攻撃の影響を受けやすい。 我々は,GNNに対して,属性や構造的摂動に対する保証を計算するための,正確な(健全で完全な)検証手法を開発した。 我々は、メッセージパッシングニューラルネットワークのための汎用的な解法であるGNNevを実装し、合計、最大、平均の3つのアグリゲーション機能をサポートしている。
• 参考スコア（独自算出の注目度）: 17.378319742808856
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph neural networks (GNNs) are increasingly employed in high-stakes applications, such as fraud detection or healthcare, but are susceptible to adversarial attacks. A number of techniques have been proposed to provide adversarial robustness guarantees, but support for commonly used aggregation functions in message-passing GNNs is still lacking. In this paper, we develop an exact (sound and complete) verification method for GNNs to compute guarantees against attribute and structural perturbations that involve edge addition or deletion, subject to budget constraints. Focusing on node classification tasks, our method employs constraint solving with bound tightening, and iteratively solves a sequence of relaxed constraint satisfaction problems while relying on incremental solving capabilities of solvers to improve efficiency. We implement GNNev, a versatile solver for message-passing neural networks, which supports three aggregation functions, sum, max and mean, with the latter two considered here for the first time. Extensive experimental evaluation of GNNev on two standard benchmarks (Cora and CiteSeer) and two real-world fraud datasets (Amazon and Yelp) demonstrates its usability and effectiveness, as well as superior performance compared to existing {exact verification} tools on sum-aggregated node classification tasks.
• Abstract（参考訳）: グラフニューラルネットワーク(GNN)は、不正検出や医療といった高度なアプリケーションにますます採用されているが、敵の攻撃の影響を受けやすい。 対向的ロバスト性を保証するためにいくつかの技術が提案されているが、メッセージパッシングGNNでよく使われる集約機能のサポートはいまだに不足している。 本稿では,予算制約の下で,エッジの追加や削除を含む特性および構造的摂動に対する保証を計算するための,GNNの正確な(健全で完全な)検証手法を開発する。 ノード分類タスクに焦点をあてて, 拘束的解法と拘束的解法を併用し, 反復的に緩和された制約満足度問題の列を解き, 解法の漸進的解法能力に頼って効率を向上する。 我々は、メッセージパッシングニューラルネットワークのための汎用的な解法であるGNNevを実装し、3つのアグリゲーション関数、和、最大、平均をサポートし、後者の2つを初めて検討した。 2つの標準ベンチマーク(CoraとCiteSeer)と2つの実世界の不正データセット(AmazonとYelp)に対するGNNevの大規模な実験的評価は、そのユーザビリティと有効性を示し、合計ノード分類タスクの既存の{exact verification}ツールよりも優れたパフォーマンスを示している。

関連論文リスト

• Using Subgraph GNNs for Node Classification:an Overlooked Potential Approach [13.947915030994851]
  SubGND(Subgraph GNN for NoDe)はノード分類のための新しいサブグラフベースの分類フレームワークである。 我々は,SubGNDがグローバルメッセージパスGNNに匹敵する,あるいは超越した性能を達成することを示す。
  論文  参考訳（メタデータ） (2025-03-09T13:37:38Z)
• Grimm: A Plug-and-Play Perturbation Rectifier for Graph Neural Networks Defending against Poisoning Attacks [53.972077392749185]
  近年の研究では、ノード分類タスクに対する敵対的中毒攻撃に対するグラフニューラルネットワーク(GNN)の脆弱性が明らかにされている。 ここでは、最初のプラグアンドプレイディフェンスモデルであるGrimmを紹介します。
  論文  参考訳（メタデータ） (2024-12-11T17:17:02Z)
• Verifying message-passing neural networks via topology-based bounds tightening [3.3267518043390205]
  我々は、メッセージパッシングニューラルネットワーク(MPNN)のための堅牢な証明書を提供するための、計算学的に効果的なアプローチを開発する。 私たちの研究は混合整数最適化に基づいており、様々なサブプロブレムをエンコードしています。 ノード分類とグラフ分類の両方の問題を検証し、エッジの追加と削除の両方を行うトポロジ的攻撃について検討する。
  論文  参考訳（メタデータ） (2024-02-21T17:05:27Z)
• Graph Agent Network: Empowering Nodes with Inference Capabilities for Adversarial Resilience [50.460555688927826]
  グラフニューラルネットワーク(GNN)の脆弱性に対処するグラフエージェントネットワーク(GAgN)を提案する。 GAgNはグラフ構造化エージェントネットワークであり、各ノードは1-hop-viewエージェントとして設計されている。 エージェントの限られたビューは、悪意のあるメッセージがGAgNでグローバルに伝播するのを防ぎ、グローバル最適化ベースのセカンダリアタックに抵抗する。
  論文  参考訳（メタデータ） (2023-06-12T07:27:31Z)
• Robust Graph Neural Networks via Probabilistic Lipschitz Constraints [7.359962178534361]
  グラフニューラルネットワーク(GNN)は、最近、さまざまなネットワークベースのタスクでうまく機能することが実証されている。 GNNは入力のシフトや摂動の影響を受けやすく、ノード属性とグラフ構造の両方を含むことができる。
  論文  参考訳（メタデータ） (2021-12-14T17:33:32Z)
• Neural Network Branch-and-Bound for Neural Network Verification [26.609606492971967]
  本稿では,効率的な分岐戦略を設計するための新しい機械学習フレームワークを提案する。 グラフ入力として検証したいネットワークを直接扱う2つのグラフニューラルネットワーク(GNN)を学習する。 我々のGNNモデルは、より大きな未確認ネットワーク上での厳しい特性に対してよく一般化されていることを示す。
  論文  参考訳（メタデータ） (2021-07-27T14:42:57Z)
• Global Optimization of Objective Functions Represented by ReLU Networks [77.55969359556032]
  ニューラルネットワークは複雑で非敵対的な関数を学ぶことができ、安全クリティカルな文脈でそれらの正しい振る舞いを保証することは困難である。 ネットワーク内の障害を見つけるための多くのアプローチ(例えば、敵の例)があるが、これらは障害の欠如を保証できない。 本稿では,最適化プロセスを検証手順に統合し,本手法よりも優れた性能を実現する手法を提案する。
  論文  参考訳（メタデータ） (2020-10-07T08:19:48Z)

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

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