TLDR: INPO (Influence-aware Negative Preference Optimization) is a new framework for graph unlearning that addresses the problem of model utility degradation during the unlearning process. It uses negative preference optimization, an influence-aware message function to amplify the effect of forgotten edges, and a topological entropy loss to preserve local graph structure. This approach significantly improves the quality of forgetting while maintaining the model’s overall usefulness, outperforming previous methods on various real-world datasets and demonstrating strong robustness.
In the rapidly evolving world of artificial intelligence, Graph Neural Networks (GNNs) have become indispensable tools for understanding complex relationships within graph-structured data. From social networks to scientific databases, GNNs help uncover hidden patterns and connections. However, with increasing awareness around data privacy and the ‘Right to be Forgotten,’ the ability to selectively remove specific information from these trained models, a process known as graph unlearning, has become critically important.
Traditional graph unlearning methods often face a significant challenge: while they aim to forget certain data, they frequently cause a drastic decline in the model’s overall usefulness. This happens because these methods, which often rely on a technique called gradient ascent, can make the model diverge too quickly, essentially destabilizing its performance on the data it’s supposed to remember.
Introducing INPO: A Smarter Approach to Graph Unlearning
A new research paper, titled “Graph Unlearning Meets Influence-aware Negative Preference Optimization,” introduces a novel framework called INPO (Influence-aware Negative Preference Optimization) designed to tackle this very problem. The authors, Qiang Chen, Zhongze Wu, Ang He, Xi Lin, Shuo Jiang, Shan You, Chang Xu, Yi Chen, and Xiu Su, propose a method that not only achieves effective unlearning but also significantly improves the robustness of the model’s utility throughout the process. You can read the full paper here.
INPO’s core idea is to slow down the divergence speed during unlearning and make the model more resilient. It draws inspiration from Negative Preference Optimization (NPO), a technique that has shown promise in other AI domains like Large Language Model unlearning due to its inherently slower divergence. Unlike methods that try to maximize forgetting at all costs, NPO focuses on optimizing using only the ‘negative’ examples (the data to be forgotten), striking a better balance between forgetting quality and maintaining overall model utility.
How INPO Works: Key Innovations
The INPO framework incorporates several innovative components:
-
Influence-aware Message Function: The paper theoretically demonstrates that unlearning high-influence edges (connections that have a significant impact on the graph’s structure and the model’s predictions) can reduce the negative impact on the rest of the data. To achieve this, INPO designs a special message function within the GNN that amplifies the influence of the edges targeted for unlearning. This helps to ‘decouple’ the forget set from the retain set, meaning changes to one have less drastic effects on the other. The influence of each edge is estimated quickly using a removal-based method, adding minimal computational overhead.
-
Topological Entropy Loss: To further preserve the model’s utility, INPO introduces a ‘topological entropy loss’ function. This function helps prevent excessive information loss in the local structure of the graph during the unlearning process. By considering the graph’s topology, it ensures that while specific edges are forgotten, the overall local relationships and patterns remain largely intact.
By combining these elements, INPO aims to enlarge the probability difference between the forget set and the retain set, effectively mitigating the tight topological coupling that makes graph unlearning so challenging.
Also Read:
- Evaluating Fairness in Graph Neural Networks on Knowledge Graphs: A New Benchmark
- SE-HTGNN: A Unified Approach to Dynamic Graph Analysis with AI Assistance
Demonstrated Effectiveness
The researchers conducted extensive experiments on five real-world datasets, including Cora, PubMed, and DBLP. The results show that INPO-based models achieve state-of-the-art performance across all metrics related to forgetting quality, such as MI Ratio (a measure of how well the model truly forgets information). Crucially, it does so while successfully maintaining the model’s utility on the data it’s supposed to remember.
For instance, on the DBLP and Cora datasets, INPO significantly improved the MI Ratio by 6.5% and 2.3% respectively, compared to the best existing baselines. The framework also demonstrated strong robustness across different deletion ratios, meaning it performs well even when a larger proportion of edges needs to be forgotten. This indicates that INPO not only forgets effectively but also does so reliably without compromising the model’s core functions.
In conclusion, INPO represents a significant step forward in graph unlearning, offering a robust and effective solution to the complex problem of selectively removing information from graph models while preserving their overall performance. This work paves the way for more privacy-aware and adaptable graph-based AI systems.
