Graph Protection under Multiple Simultaneous Attacks: A Heuristic Approach

• URL: http://arxiv.org/abs/2403.17108v1
• Date: Mon, 25 Mar 2024 18:46:13 GMT
• Title: Graph Protection under Multiple Simultaneous Attacks: A Heuristic Approach
• Authors: Marko Djukanovic, Stefan Kapunac, Aleksandar Kartelj, Dragan Matic,
• Abstract summary: 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. We propose a variable neighborhood search algorithm in which the feasibility of the solution is checked by introducing the concept of quasi-feasibility.
• Score: 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.

Related papers

• Minimum Topology Attacks for Graph Neural Networks [70.17791814425148]
  Graph Neural Networks (GNNs) have received significant attention for their robustness to adversarial topology attacks. We propose a new type of topology attack, named minimum-budget topology attack, aiming to adaptively find the minimum perturbation sufficient for a successful attack on each node.
  arXiv  Detail & Related papers  (2024-03-05T07:29:12Z)
• Self-Guided Robust Graph Structure Refinement [37.235898707554284]
  We propose a self-guided graph structure refinement (GSR) framework to defend GNNs against adversarial attacks. In this paper, we demonstrate the effectiveness of SG-GSR under various scenarios including non-targeted attacks, targeted attacks, feature attacks, e-commerce fraud, and noisy node labels.
  arXiv  Detail & Related papers  (2024-02-19T05:00:07Z)
• Graph Agent Network: Empowering Nodes with Inference Capabilities for Adversarial Resilience [50.460555688927826]
  We propose the Graph Agent Network (GAgN) to address the vulnerabilities of graph neural networks (GNNs) GAgN is a graph-structured agent network in which each node is designed as an 1-hop-view agent. Agents' limited view prevents malicious messages from propagating globally in GAgN, thereby resisting global-optimization-based secondary attacks.
  arXiv  Detail & Related papers  (2023-06-12T07:27:31Z)
• LGTBIDS: Layer-wise Graph Theory Based Intrusion Detection System in Beyond 5G [9.63617966257402]
  Intrusion detection signifies a central approach to ensuring the security of the communication network. A Layerwise Graph Theory-Based Intrusion Detection System (LGTBIDS) algorithm is designed to detect the attacked node. Results validate the better performance, low time computations, and low complexity.
  arXiv  Detail & Related papers  (2022-10-06T05:32:03Z)
• GUARD: Graph Universal Adversarial Defense [54.81496179947696]
  We present a simple yet effective method, named Graph Universal Adversarial Defense (GUARD) GUARD protects each individual node from attacks with a universal defensive patch, which is generated once and can be applied to any node in a graph. GUARD significantly improves robustness for several established GCNs against multiple adversarial attacks and outperforms state-of-the-art defense methods by large margins.
  arXiv  Detail & Related papers  (2022-04-20T22:18:12Z)
• Sparse and Imperceptible Adversarial Attack via a Homotopy Algorithm [93.80082636284922]
  Sparse adversarial attacks can fool deep networks (DNNs) by only perturbing a few pixels. Recent efforts combine it with another l_infty perturbation on magnitudes. We propose a homotopy algorithm to tackle the sparsity and neural perturbation framework.
  arXiv  Detail & Related papers  (2021-06-10T20:11:36Z)
• Online Adversarial Attacks [57.448101834579624]
  We formalize the online adversarial attack problem, emphasizing two key elements found in real-world use-cases. We first rigorously analyze a deterministic variant of the online threat model. We then propose algoname, a simple yet practical algorithm yielding a provably better competitive ratio for $k=2$ over the current best single threshold algorithm.
  arXiv  Detail & Related papers  (2021-03-02T20:36:04Z)
• GraphAttacker: A General Multi-Task GraphAttack Framework [4.218118583619758]
  Graph Neural Networks (GNNs) have been successfully exploited in graph analysis tasks in many real-world applications. adversarial samples generated by attackers, which achieved great attack performance with almost imperceptible perturbations. We propose GraphAttacker, a novel generic graph attack framework that can flexibly adjust the structures and the attack strategies according to the graph analysis tasks.
  arXiv  Detail & Related papers  (2021-01-18T03:06:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.