論文の概要: Graph Protection under Multiple Simultaneous Attacks: A Heuristic Approach

• arxiv url: http://arxiv.org/abs/2403.17108v1
• Date: Mon, 25 Mar 2024 18:46:13 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-27 19:55:36.484192
• Title: Graph Protection under Multiple Simultaneous Attacks: A Heuristic Approach
• Title（参考訳）: 複数の同時攻撃によるグラフ保護 : ヒューリスティックアプローチ
• Authors: Marko Djukanovic, Stefan Kapunac, Aleksandar Kartelj, Dragan Matic,
• Abstract要約: この研究は、グラフを用いてモデル化されたネットワークのノードに対する同時攻撃から保護するための効果的なメタヒューリスティックなアプローチの開発に焦点を当てる。 具体的には、グラフ上のよく知られたローマ支配問題の一般化である$k$-strong Roman支配問題に焦点を当てる。 本稿では,準実現可能性の概念を導入して,その実現可能性を確認する可変近傍探索アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 41.94295877935867
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: This work focuses on developing an effective meta-heuristic approach to protect against simultaneous attacks on nodes of a network modeled using a graph. Specifically, we focus on the $k$-strong Roman domination problem, a generalization of the well-known Roman domination problem on graphs. This general problem is about assigning integer weights to nodes that represent the number of field armies stationed at each node in order to satisfy the protection constraints while minimizing the total weights. These constraints concern the protection of a graph against any simultaneous attack consisting of $k \in \mathbb{N}$ nodes. An attack is considered repelled if each node labeled 0 can be defended by borrowing an army from one of its neighboring nodes, ensuring that the neighbor retains at least one army for self-defense. The $k$-SRD problem has practical applications in various areas, such as developing counter-terrorism strategies or managing supply chain disruptions. The solution to this problem is notoriously difficult to find, as even checking the feasibility of the proposed solution requires an exponential number of steps. We propose a variable neighborhood search algorithm in which the feasibility of the solution is checked by introducing the concept of quasi-feasibility, which is realized by careful sampling within the set of all possible attacks. Extensive experimental evaluations show the scalability and robustness of the proposed approach compared to the two exact approaches from the literature. Experiments are conducted with random networks from the literature and newly introduced random wireless networks as well as with real-world networks. A practical application scenario, using real-world networks, involves applying our approach to graphs extracted from GeoJSON files containing geographic features of hundreds of cities or larger regions.
• Abstract（参考訳）: この研究は、グラフを用いてモデル化されたネットワークのノードに対する同時攻撃から保護するための効果的なメタヒューリスティックなアプローチの開発に焦点を当てる。 具体的には、グラフ上のよく知られたローマ支配問題の一般化である$k$-strong Roman支配問題に焦点を当てる。 この一般的な問題は、全重量を最小化しながら保護制約を満たすために各ノードに駐留する野戦部隊の数を表すノードに整数重みを割り当てることである。 これらの制約は、$k \in \mathbb{N}$ノードからなる同時攻撃に対するグラフの保護に関するものである。 攻撃は、隣接するノードの1つから軍隊を借りることで、0とラベル付けされた各ノードを防御できるとされ、近隣のノードが少なくとも1つの軍隊を自己防衛のために保持することを保証する。 k$-SRD問題は、対テロ戦略の開発やサプライチェーンの破壊管理など、様々な分野で実用化されている。 この問題に対する解決策は、提案されたソリューションの実現可能性を確認する場合でも指数関数的なステップを必要とするため、見つからないことが知られている。 本稿では, 準実現可能性の概念を導入して, 実現可能性を確認する可変近傍探索アルゴリズムを提案する。 大規模な実験的評価は,提案手法のスケーラビリティとロバスト性を示し,文献からの2つの正確なアプローチと比較した。 文献からのランダムネットワークと、新たに導入されたランダム無線ネットワーク、および実世界のネットワークを用いて実験を行う。 実世界のネットワークを用いた実践的な応用シナリオは、数百の都市や大地域の地理的特徴を含むGeoJSONファイルから抽出したグラフに我々のアプローチを適用することである。

関連論文リスト

• Minimum Topology Attacks for Graph Neural Networks [70.17791814425148]
  グラフニューラルネットワーク(GNN)は、敵対的トポロジ攻撃に対する堅牢性において大きな注目を集めている。 本稿では,各ノードに対する攻撃を成功させるのに十分な最小摂動を適応的に見つけることを目的とした,最小予算トポロジ攻撃という新しいタイプのトポロジ攻撃を提案する。
  論文  参考訳（メタデータ） (2024-03-05T07:29:12Z)
• Self-Guided Robust Graph Structure Refinement [37.235898707554284]
  本稿では,GNNを敵攻撃から守るための自己誘導グラフ構造改善(GSR)フレームワークを提案する。 本稿では,非標的攻撃,標的攻撃,機能攻撃,eコマース詐欺,ノイズの多いノードラベルなど,様々なシナリオにおけるSG-GSRの有効性を実証する。
  論文  参考訳（メタデータ） (2024-02-19T05:00:07Z)
• 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)
• LGTBIDS: Layer-wise Graph Theory Based Intrusion Detection System in Beyond 5G [9.63617966257402]
  侵入検知は、通信ネットワークのセキュリティを確保するための中心的なアプローチを示す。 The Layerwise Graph Theory-Based Intrusion Detection System (LGTBIDS) algorithm is designed to detect the attacked node。 結果は、より良いパフォーマンス、低い時間計算、低い複雑さを検証します。
  論文  参考訳（メタデータ） (2022-10-06T05:32:03Z)
• GUARD: Graph Universal Adversarial Defense [54.81496179947696]
  GUARD(Graph Universal Adversarial Defense)という,シンプルで効果的な手法を提案する。 GUARDは、各ノードを共通の防御パッチで攻撃から保護する。 GUARDは、複数の敵攻撃に対する複数の確立されたGCNの堅牢性を大幅に改善し、最先端の防御手法を大きなマージンで上回る。
  論文  参考訳（メタデータ） (2022-04-20T22:18:12Z)
• Sparse and Imperceptible Adversarial Attack via a Homotopy Algorithm [93.80082636284922]
  少数の敵対的攻撃は、数ピクセルを摂動するだけでディープ・ネットワーク(DNN)を騙すことができる。 近年の取り組みは、他の等級のl_infty摂動と組み合わせている。 本稿では,空間的・神経的摂動に対処するホモトピーアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-06-10T20:11:36Z)
• Online Adversarial Attacks [57.448101834579624]
  我々は、実世界のユースケースで見られる2つの重要な要素を強調し、オンライン敵攻撃問題を定式化する。 まず、オンライン脅威モデルの決定論的変種を厳格に分析する。 このアルゴリズムは、現在の最良の単一しきい値アルゴリズムよりも、$k=2$の競争率を確実に向上させる。
  論文  参考訳（メタデータ） (2021-03-02T20:36:04Z)
• GraphAttacker: A General Multi-Task GraphAttack Framework [4.218118583619758]
  グラフニューラルネットワーク(GNN)は多くの実世界のアプリケーションでグラフ解析タスクにうまく活用されている。 攻撃者が生成した敵のサンプルは ほとんど知覚不能な摂動で 優れた攻撃性能を達成しました 本稿では,グラフ解析タスクに応じて構造と攻撃戦略を柔軟に調整可能な,新しい汎用グラフ攻撃フレームワークであるgraphattackerを提案する。
  論文  参考訳（メタデータ） (2021-01-18T03:06:41Z)

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

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