Toward Scalable Graph Unlearning: A Node Influence Maximization based Approach

• URL: http://arxiv.org/abs/2501.11823v1
• Date: Tue, 21 Jan 2025 02:02:35 GMT
• Title: Toward Scalable Graph Unlearning: A Node Influence Maximization based Approach
• Authors: Xunkai Li, Bowen Fan, Zhengyu Wu, Zhiyu Li, Rong-Hua Li, Guoren Wang,
• Abstract summary: 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.
• Score: 27.136177743390945
• License:
• Abstract: Machine unlearning, as a pivotal technology for enhancing model robustness and data privacy, has garnered significant attention in prevalent web mining applications, especially in thriving graph-based scenarios. However, most existing graph unlearning (GU) approaches face significant challenges due to the intricate interactions among web-scale graph elements during the model training: (1) The gradient-driven node entanglement hinders the complete knowledge removal in response to unlearning requests; (2) The billion-level graph elements in the web scenarios present inevitable scalability issues. To break the above limitations, we open up a new perspective by drawing a connection between GU and conventional social influence maximization. To this end, we propose Node Influence Maximization (NIM) through the decoupled influence propagation model and fine-grained influence function in a scalable manner, which is crafted to be a plug-and-play strategy to identify potential nodes affected by unlearning entities. This approach enables offline execution independent of GU, allowing it to be seamlessly integrated into most GU methods to improve their unlearning performance. Based on this, we introduce Scalable Graph Unlearning (SGU) as a new fine-tuned framework, which balances the forgetting and reasoning capability of the unlearned model by entity-specific optimizations. Extensive experiments on 14 datasets, including large-scale ogbn-papers100M, have demonstrated the effectiveness of our approach. Specifically, NIM enhances the forgetting capability of most GU methods, while SGU achieves comprehensive SOTA performance and maintains scalability.

Related papers

• Erase then Rectify: A Training-Free Parameter Editing Approach for Cost-Effective Graph Unlearning [17.85404473268992]
  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.
  arXiv  Detail & Related papers  (2024-09-25T07:20:59Z)
• Malicious Internet Entity Detection Using Local Graph Inference [0.4893345190925178]
  Detection of malicious behavior in a large network is a challenging problem for machine learning in computer security. Current cybersec-tailored approaches are still limited in expressivity, and methods successful in other domains do not scale well for large volumes of data. This work proposes a new perspective for learning from graph data that is modeling network entity interactions as a large heterogeneous graph.
  arXiv  Detail & Related papers  (2024-08-06T16:35:25Z)
• Dynamic Graph Unlearning: A General and Efficient Post-Processing Method via Gradient Transformation [24.20087360102464]
  We study the dynamic graph unlearning for the first time and propose an effective, efficient, general, and post-processing method to implement DGNN unlearning. Our method has the potential to handle future unlearning requests with significant performance gains.
  arXiv  Detail & Related papers  (2024-05-23T10:26:18Z)
• 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)
• Efficient Dynamic Graph Representation Learning at Scale [66.62859857734104]
  We propose Efficient Dynamic Graph lEarning (EDGE), which selectively expresses certain temporal dependency via training loss to improve the parallelism in computations. We show that EDGE can scale to dynamic graphs with millions of nodes and hundreds of millions of temporal events and achieve new state-of-the-art (SOTA) performance.
  arXiv  Detail & Related papers  (2021-12-14T22:24:53Z)
• 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)
• Model-Agnostic Graph Regularization for Few-Shot Learning [60.64531995451357]
  We present a comprehensive study on graph embedded few-shot learning. We introduce a graph regularization approach that allows a deeper understanding of the impact of incorporating graph information between labels. Our approach improves the performance of strong base learners by up to 2% on Mini-ImageNet and 6.7% on ImageNet-FS.
  arXiv  Detail & Related papers  (2021-02-14T05:28:13Z)
• Graph Contrastive Learning with Adaptive Augmentation [23.37786673825192]
  We propose a novel graph contrastive representation learning method with adaptive augmentation. Specifically, we design augmentation schemes based on node centrality measures to highlight important connective structures. Our proposed method consistently outperforms existing state-of-the-art baselines and even surpasses some supervised counterparts.
  arXiv  Detail & Related papers  (2020-10-27T15:12:21Z)
• 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)
• Tensor Graph Convolutional Networks for Multi-relational and Robust Learning [74.05478502080658]
  This paper introduces a tensor-graph convolutional network (TGCN) for scalable semi-supervised learning (SSL) from data associated with a collection of graphs, that are represented by a tensor. The proposed architecture achieves markedly improved performance relative to standard GCNs, copes with state-of-the-art adversarial attacks, and leads to remarkable SSL performance over protein-to-protein interaction networks.
  arXiv  Detail & Related papers  (2020-03-15T02:33:21Z)

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.