Erase then Rectify: A Training-Free Parameter Editing Approach for Cost-Effective Graph Unlearning

• URL: http://arxiv.org/abs/2409.16684v2
• Date: Thu, 19 Dec 2024 14:18:15 GMT
• Title: Erase then Rectify: A Training-Free Parameter Editing Approach for Cost-Effective Graph Unlearning
• Authors: Zhe-Rui Yang, Jindong Han, Chang-Dong Wang, Hao Liu,
• Abstract summary: Graph unlearning aims to eliminate the influence of nodes, edges, or attributes from a trained Graph Neural Network (GNN) Existing graph unlearning techniques often necessitate additional training on the remaining data, leading to significant computational costs. We propose a two-stage training-free approach, Erase then Rectify (ETR), designed for efficient and scalable graph unlearning.
• Score: 17.85404473268992
• License:
• Abstract: Graph unlearning, which aims to eliminate the influence of specific nodes, edges, or attributes from a trained Graph Neural Network (GNN), is essential in applications where privacy, bias, or data obsolescence is a concern. However, existing graph unlearning techniques often necessitate additional training on the remaining data, leading to significant computational costs, particularly with large-scale graphs. To address these challenges, we propose a two-stage training-free approach, Erase then Rectify (ETR), designed for efficient and scalable graph unlearning while preserving the model utility. Specifically, we first build a theoretical foundation showing that masking parameters critical for unlearned samples enables effective unlearning. Building on this insight, the Erase stage strategically edits model parameters to eliminate the impact of unlearned samples and their propagated influence on intercorrelated nodes. To further ensure the GNN's utility, the Rectify stage devises a gradient approximation method to estimate the model's gradient on the remaining dataset, which is then used to enhance model performance. Overall, ETR achieves graph unlearning without additional training or full training data access, significantly reducing computational overhead and preserving data privacy. Extensive experiments on seven public datasets demonstrate the consistent superiority of ETR in model utility, unlearning efficiency, and unlearning effectiveness, establishing it as a promising solution for real-world graph unlearning challenges.

Related papers

• Toward Scalable Graph Unlearning: A Node Influence Maximization based Approach [27.136177743390945]
  graph unlearning (GU) approaches face significant challenges due to the intricate interactions among web-scale graph elements during the model training. We propose Node Influence Maximization (NIM) through the decoupled influence propagation model and fine-grained influence function in a scalable manner. This approach enables offline execution independent of GU, allowing it to be seamlessly integrated into most GU methods to improve their unlearning performance.
  arXiv  Detail & Related papers  (2025-01-21T02:02:35Z)
• TCGU: Data-centric Graph Unlearning based on Transferable Condensation [36.670771080732486]
  Transferable Condensation Graph Unlearning (TCGU) is a data-centric solution to zero-glance graph unlearning. We show that TCGU can achieve superior performance in terms of model utility, unlearning efficiency, and unlearning efficacy than existing GU methods.
  arXiv  Detail & Related papers  (2024-10-09T02:14:40Z)
• GraphGuard: Detecting and Counteracting Training Data Misuse in Graph Neural Networks [69.97213941893351]
  The emergence of Graph Neural Networks (GNNs) in graph data analysis has raised critical concerns about data misuse during model training. Existing methodologies address either data misuse detection or mitigation, and are primarily designed for local GNN models. This paper introduces a pioneering approach called GraphGuard, to tackle these challenges.
  arXiv  Detail & Related papers  (2023-12-13T02:59:37Z)
• PREM: A Simple Yet Effective Approach for Node-Level Graph Anomaly Detection [65.24854366973794]
  Node-level graph anomaly detection (GAD) plays a critical role in identifying anomalous nodes from graph-structured data in domains such as medicine, social networks, and e-commerce. We introduce a simple method termed PREprocessing and Matching (PREM for short) to improve the efficiency of GAD. Our approach streamlines GAD, reducing time and memory consumption while maintaining powerful anomaly detection capabilities.
  arXiv  Detail & Related papers  (2023-10-18T02:59:57Z)
• GIF: A General Graph Unlearning Strategy via Influence Function [63.52038638220563]
  Graph Influence Function (GIF) is a model-agnostic unlearning method that can efficiently and accurately estimate parameter changes in response to a $epsilon$-mass perturbation in deleted data. We conduct extensive experiments on four representative GNN models and three benchmark datasets to justify GIF's superiority in terms of unlearning efficacy, model utility, and unlearning efficiency.
  arXiv  Detail & Related papers  (2023-04-06T03:02:54Z)
• Efficiently Forgetting What You Have Learned in Graph Representation Learning via Projection [19.57394670843742]
  We study the unlearning problem in linear-GNNs, and then introduce its extension to non-linear structures. Given a set of nodes to unlearn, we propose PROJECTOR that unlearns by projecting the weight parameters of the pre-trained model onto a subspace that is irrelevant to features of the nodes to be forgotten.
  arXiv  Detail & Related papers  (2023-02-17T16:49:10Z)
• 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)
• GraphMI: Extracting Private Graph Data from Graph Neural Networks [59.05178231559796]
  We present textbfGraph textbfModel textbfInversion attack (GraphMI), which aims to extract private graph data of the training graph by inverting GNN. Specifically, we propose a projected gradient module to tackle the discreteness of graph edges while preserving the sparsity and smoothness of graph features. We design a graph auto-encoder module to efficiently exploit graph topology, node attributes, and target model parameters for edge inference.
  arXiv  Detail & Related papers  (2021-06-05T07:07:52Z)
• Robust Optimization as Data Augmentation for Large-scale Graphs [117.2376815614148]
  We propose FLAG (Free Large-scale Adversarial Augmentation on Graphs), which iteratively augments node features with gradient-based adversarial perturbations during training. FLAG is a general-purpose approach for graph data, which universally works in node classification, link prediction, and graph classification tasks.
  arXiv  Detail & Related papers  (2020-10-19T21:51:47Z)

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.