TLDR: The paper introduces three novel methods (Class-based Label Replacement, Topology-guided Neighbor Mean Posterior Probability, and Class-consistent Neighbor Node Filtering) for “node unlearning” in Graph Neural Networks (GNNs). Node unlearning efficiently removes specific training node information to protect privacy, addressing limitations of existing methods that either restrict GNN structure or don’t fully use graph topology. Experiments on benchmark datasets show these methods effectively remove sensitive nodes, maintain model performance, and are significantly more efficient than retraining from scratch, with Class-consistent Neighbor Node Filtering being particularly effective.
In an era where data privacy is paramount, driven by regulations like the General Data Protection Regulation (GDPR) and the California Consumer Privacy Act (CCPA), the ‘right to be forgotten’ has become a critical concept in machine learning. This right mandates that individuals can request the removal of their personal data from models. While this concept has been explored for traditional data types like text and images, its application to Graph Neural Networks (GNNs) – models that excel at processing interconnected data like social networks and citation graphs – presents unique challenges.
Traditional machine unlearning methods, such as retraining a model from scratch or using techniques like SISA (Sharded, Isolated, Sliced, and Aggregated) and fine-tuning, often fall short when applied to graph data. Retraining from scratch is computationally expensive and time-consuming, especially for large GNNs. SISA, which partitions data into fragments and retrains only relevant sub-models, can compromise the structural integrity of a graph, leading to reduced model utility. Fine-tuning, while more efficient, often fails to adequately consider the intricate relationships between a node to be forgotten and its neighbors within the graph’s topology.
Addressing the GNN Unlearning Challenge
A recent research paper, Graph Unlearning: Efficient Node Removal in Graph Neural Networks, by Faqian Guana,b, Tianqing Zhua, Zhoutian Wangb, Wei Renb and Wanlei Zhoua, introduces three novel methods designed to efficiently remove sensitive training node information from GNN models, specifically focusing on ‘node unlearning’. These methods aim to protect privacy without significantly compromising the model’s overall performance.
The first proposed method is Class-based Label Replacement (CLR). This approach draws inspiration from unlearning techniques used in image and text domains. It works by replacing the target label of the node to be unlearned with the mean posterior probability of its corresponding class in the testing set. While effective, this method does not fully leverage the unique topological features of graph data, potentially leading to suboptimal unlearning outcomes.
To address the topological aspect, the researchers developed Topology-guided Neighbor Mean Posterior Probability (TNMPP). This method identifies the neighboring nodes of the unlearning node and calculates their mean posterior probabilities. This average probability then replaces the target class of the unlearning node. TNMPP effectively incorporates graph topology, but it can be influenced by unrelated neighboring nodes or even other training set nodes, which might hinder complete forgetting.
Building on TNMPP’s strengths while mitigating its weaknesses, the third and most refined method is Class-consistent Neighbor Node Filtering (CNNF). CNNF takes a more selective approach. It first identifies all neighbors of the unlearning node but then filters them, considering only those neighbors that belong to the same class as the unlearning node AND are not part of the training set. If such neighbors exist, their mean posterior probability is used to update the unlearning node’s label. If no such neighbors are found, it falls back to using the mean posterior probability of the class from the testing set, similar to CLR. This filtering mechanism ensures that the unlearning process is more precise and less susceptible to interference from irrelevant or training-related nodes.
Experimental Validation and Superior Performance
The effectiveness of these three methods was rigorously tested on three widely recognized citation network datasets: Cora, Citeseer, and Pubmed. The evaluation focused on three key metrics: Model Utility (how well the model performs after unlearning, measured by accuracy), Unlearning Utility (how effectively the sensitive node’s influence is removed, assessed using membership inference attacks), and Unlearning Efficiency (computational cost, measured by epochs and running time).
The experimental results demonstrated several key findings. In terms of Model Utility, all three proposed methods successfully preserved the model’s performance, significantly outperforming a ‘Naive’ unlearning approach that severely degraded model accuracy. TNMPP often achieved the highest accuracy, while CNNF also maintained strong performance, comparable to retraining from scratch but with far greater efficiency.
For Unlearning Utility, all methods proved effective in removing the influence of unlearned nodes, with membership inference attack accuracy consistently above 85% on Cora and Citeseer, and over 70% on Pubmed. Notably, CNNF showed superior unlearning utility compared to TNMPP, highlighting the benefit of its intelligent neighbor filtering. This indicates that CNNF is better at ensuring the model truly ‘forgets’ the specified data.
Perhaps one of the most compelling results was in Unlearning Efficiency. The proposed methods achieved model convergence in fewer than 70 epochs, a stark contrast to the approximately 500 epochs required by the traditional ‘Retrain’ method. This translates to a significant speed-up, with the new methods completing the unlearning process in less than 1 second, compared to 4-6 seconds for retraining, making them over 7 times more efficient.
Furthermore, the research confirmed the generalizability of these methods across different GNN architectures, including GCN, SGC, and ARMA models. When compared to state-of-the-art unlearning techniques like GraphEraser and GIF, the proposed methods consistently outperformed them in terms of combined model performance and efficiency, sometimes achieving a remarkable 33% improvement in performance.
Also Read:
- Optimizing Large-Scale Graph Neural Network Training with RapidGNN
- CURE: A Framework for Smarter, Fairer Language Models by Unlearning Conceptual Shortcuts
Conclusion
The paper concludes that the three novel node unlearning methods – Class-based Label Replacement, Topology-guided Neighbor Mean Posterior Probability, and Class-consistent Neighbor Node Filtering – offer efficient and effective solutions for removing sensitive training nodes from GNNs. By carefully considering the unique topological features of graph data, especially through the refined filtering in CNNF, these methods enhance privacy protection while maintaining high model utility and significantly improving computational efficiency compared to existing approaches. This work provides valuable insights into the evolving field of machine unlearning for graph-structured data, paving the way for more secure and privacy-preserving GNN applications.
