Revisiting Edge Perturbation for Graph Neural Network in Graph Data Augmentation and Attack

• URL: http://arxiv.org/abs/2403.07943v1
• Date: Sun, 10 Mar 2024 15:50:04 GMT
• Title: Revisiting Edge Perturbation for Graph Neural Network in Graph Data Augmentation and Attack
• Authors: Xin Liu, Yuxiang Zhang, Meng Wu, Mingyu Yan, Kun He, Wei Yan, Shirui Pan, Xiaochun Ye, Dongrui Fan
• Abstract summary: Edge perturbation is a method to modify graph structures. It can be categorized into two veins based on their effects on the performance of graph neural networks (GNNs) We propose a unified formulation and establish a clear boundary between two categories of edge perturbation methods.
• Score: 58.440711902319855
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Edge perturbation is a basic method to modify graph structures. It can be categorized into two veins based on their effects on the performance of graph neural networks (GNNs), i.e., graph data augmentation and attack. Surprisingly, both veins of edge perturbation methods employ the same operations, yet yield opposite effects on GNNs' accuracy. A distinct boundary between these methods in using edge perturbation has never been clearly defined. Consequently, inappropriate perturbations may lead to undesirable outcomes, necessitating precise adjustments to achieve desired effects. Therefore, questions of ``why edge perturbation has a two-faced effect?'' and ``what makes edge perturbation flexible and effective?'' still remain unanswered. In this paper, we will answer these questions by proposing a unified formulation and establishing a clear boundary between two categories of edge perturbation methods. Specifically, we conduct experiments to elucidate the differences and similarities between these methods and theoretically unify the workflow of these methods by casting it to one optimization problem. Then, we devise Edge Priority Detector (EPD) to generate a novel priority metric, bridging these methods up in the workflow. Experiments show that EPD can make augmentation or attack flexibly and achieve comparable or superior performance to other counterparts with less time overhead.

Related papers

• 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)
• Explainability-Based Adversarial Attack on Graphs Through Edge Perturbation [1.6385815610837167]
  We investigate the impact of test time adversarial attacks through edge perturbations which involve both edge insertions and deletions. A novel explainability-based method is proposed to identify important nodes in the graph and perform edge perturbation between these nodes. Results suggest that introducing edges between nodes of different classes has higher impact as compared to removing edges among nodes within the same class.
  arXiv  Detail & Related papers  (2023-12-28T17:41:30Z)
• Robust Graph Neural Network based on Graph Denoising [10.564653734218755]
  Graph Neural Networks (GNNs) have emerged as a notorious alternative to address learning problems dealing with non-Euclidean datasets. This work proposes a robust implementation of GNNs that explicitly accounts for the presence of perturbations in the observed topology.
  arXiv  Detail & Related papers  (2023-12-11T17:43:57Z)
• Empowering Counterfactual Reasoning over Graph Neural Networks through Inductivity [7.094238868711952]
  Graph neural networks (GNNs) have various practical applications, such as drug discovery, recommendation engines, and chip design. Counterfactual reasoning is used to make minimal changes to the input graph of a GNN in order to alter its prediction.
  arXiv  Detail & Related papers  (2023-06-07T23:40:18Z)
• Refined Edge Usage of Graph Neural Networks for Edge Prediction [51.06557652109059]
  We propose a novel edge prediction paradigm named Edge-aware Message PassIng neuRal nEtworks (EMPIRE) We first introduce an edge splitting technique to specify use of each edge where each edge is solely used as either the topology or the supervision. In order to emphasize the differences between pairs connected by supervision edges and pairs unconnected, we further weight the messages to highlight the relative ones that can reflect the differences.
  arXiv  Detail & Related papers  (2022-12-25T23:19:56Z)
• 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)
• Training Robust Graph Neural Networks with Topology Adaptive Edge Dropping [116.26579152942162]
  Graph neural networks (GNNs) are processing architectures that exploit graph structural information to model representations from network data. Despite their success, GNNs suffer from sub-optimal generalization performance given limited training data. This paper proposes Topology Adaptive Edge Dropping to improve generalization performance and learn robust GNN models.
  arXiv  Detail & Related papers  (2021-06-05T13:20:36Z)
• Unveiling Anomalous Edges and Nominal Connectivity of Attributed Networks [53.56901624204265]
  The present work deals with uncovering anomalous edges in attributed graphs using two distinct formulations with complementary strengths. The first relies on decomposing the graph data matrix into low rank plus sparse components to improve markedly performance. The second broadens the scope of the first by performing robust recovery of the unperturbed graph, which enhances the anomaly identification performance.
  arXiv  Detail & Related papers  (2021-04-17T20:00:40Z)
• Differentiable Causal Discovery from Interventional Data [141.41931444927184]
  We propose a theoretically-grounded method based on neural networks that can leverage interventional data. We show that our approach compares favorably to the state of the art in a variety of settings.
  arXiv  Detail & Related papers  (2020-07-03T15:19:17Z)

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.