Countering adversarial perturbations in graphs using error correcting codes

• URL: http://arxiv.org/abs/2406.14245v2
• Date: Wed, 11 Sep 2024 12:51:33 GMT
• Title: Countering adversarial perturbations in graphs using error correcting codes
• Authors: Saif Eddin Jabari,
• Abstract summary: adversarial perturbations occur during the transmission of the graph between a sender and a receiver. This study explores a repetition coding scheme with sender-assigned noise and majority voting on the receiver's end to rectify the graph's structure.
• Score: 7.553245365626645
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of a graph subjected to adversarial perturbations, such as those arising from cyber-attacks, where edges are covertly added or removed. The adversarial perturbations occur during the transmission of the graph between a sender and a receiver. To counteract potential perturbations, this study explores a repetition coding scheme with sender-assigned noise and majority voting on the receiver's end to rectify the graph's structure. The approach operates without prior knowledge of the attack's characteristics. We analytically derive a bound on the number of repetitions needed to satisfy probabilistic constraints on the quality of the reconstructed graph. The method can accurately and effectively decode Erd\H{o}s-R\'{e}nyi graphs that were subjected to non-random edge removal, namely, those connected to vertices with the highest eigenvector centrality, in addition to random addition and removal of edges by the attacker. The method is also effective against attacks on large scale-free graphs generated using the Barab\'{a}si-Albert model but require a larger number of repetitions than needed to correct Erd\H{o}s-R\'{e}nyi graphs.

Related papers

• Asymmetric Graph Error Control with Low Complexity in Causal Bandits [21.812120023339876]
  The objective is to select an optimal sequence of interventions on nodes in a causal graph. By exploiting the causal relationships between the nodes whose signals contribute to the reward, interventions are optimized.
  arXiv  Detail & Related papers  (2024-08-20T23:37:08Z)
• ADEdgeDrop: Adversarial Edge Dropping for Robust Graph Neural Networks [53.41164429486268]
  Graph Neural Networks (GNNs) have exhibited the powerful ability to gather graph-structured information from neighborhood nodes. The performance of GNNs is limited by poor generalization and fragile robustness caused by noisy and redundant graph data. We propose a novel adversarial edge-dropping method (ADEdgeDrop) that leverages an adversarial edge predictor guiding the removal of edges.
  arXiv  Detail & Related papers  (2024-03-14T08:31:39Z)
• Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
  This paper proposes a novel Deep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE) for attributed graph data. The proposed method surpasses state-of-the-art baseline algorithms by a significant margin on different downstream tasks across popular datasets.
  arXiv  Detail & Related papers  (2024-01-12T17:57:07Z)
• Addressing Heterophily in Node Classification with Graph Echo State Networks [11.52174067809364]
  We address the challenges of heterophilic graphs with Graph Echo State Network (GESN) for node classification. GESN is a reservoir computing model for graphs, where node embeddings are computed by an untrained message-passing function. Our experiments show that reservoir models are able to achieve better or comparable accuracy with respect to most fully trained deep models.
  arXiv  Detail & Related papers  (2023-05-14T19:42:31Z)
• EDoG: Adversarial Edge Detection For Graph Neural Networks [17.969573886307906]
  Graph Neural Networks (GNNs) have been widely applied to different tasks such as bioinformatics, drug design, and social networks. Recent studies have shown that GNNs are vulnerable to adversarial attacks which aim to mislead the node or subgraph classification prediction by adding subtle perturbations. We propose a general adversarial edge detection pipeline EDoG without requiring knowledge of the attack strategies based on graph generation.
  arXiv  Detail & Related papers  (2022-12-27T20:42:36Z)
• Resisting Graph Adversarial Attack via Cooperative Homophilous Augmentation [60.50994154879244]
  Recent studies show that Graph Neural Networks are vulnerable and easily fooled by small perturbations. In this work, we focus on the emerging but critical attack, namely, Graph Injection Attack. We propose a general defense framework CHAGNN against GIA through cooperative homophilous augmentation of graph data and model.
  arXiv  Detail & Related papers  (2022-11-15T11:44:31Z)
• Joint Network Topology Inference via a Shared Graphon Model [24.077455621015552]
  We consider the problem of estimating the topology of multiple networks from nodal observations. We adopt a graphon as our random graph model, which is a nonparametric model from which graphs of potentially different sizes can be drawn.
  arXiv  Detail & Related papers  (2022-09-17T02:38:58Z)
• Model Inversion Attacks against Graph Neural Networks [65.35955643325038]
  We study model inversion attacks against Graph Neural Networks (GNNs) In this paper, we present GraphMI to infer the private training graph data. Our experimental results show that such defenses are not sufficiently effective and call for more advanced defenses against privacy attacks.
  arXiv  Detail & Related papers  (2022-09-16T09:13:43Z)
• Are Gradients on Graph Structure Reliable in Gray-box Attacks? [56.346504691615934]
  Previous gray-box attackers employ gradients from the surrogate model to locate the vulnerable edges to perturb the graph structure. In this paper, we discuss and analyze the errors caused by the unreliability of the structural gradients. We propose a novel attack model with methods to reduce the errors inside the structural gradients.
  arXiv  Detail & Related papers  (2022-08-07T06:43:32Z)
• SoftEdge: Regularizing Graph Classification with Random Soft Edges [18.165965620873745]
  Graph data augmentation plays a vital role in regularizing Graph Neural Networks (GNNs) Simple edge and node manipulations can create graphs with an identical structure or indistinguishable structures to message passing GNNs but of conflict labels. We propose SoftEdge, which assigns random weights to a portion of the edges of a given graph to construct dynamic neighborhoods over the graph.
  arXiv  Detail & Related papers  (2022-04-21T20:12:36Z)
• A Robust and Generalized Framework for Adversarial Graph Embedding [73.37228022428663]
  We propose a robust framework for adversarial graph embedding, named AGE. AGE generates the fake neighbor nodes as the enhanced negative samples from the implicit distribution. Based on this framework, we propose three models to handle three types of graph data.
  arXiv  Detail & Related papers  (2021-05-22T07:05:48Z)

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.