Hypergraph Unlearning: A Size-Based Hyperedge Selection and Coverage Aggregation Approach

Graph unlearning aims to provably remove some training data from graph neural networks (GNNs) while eliminating their impact on model predictions. Although retraining the GNNs from scratch is a direct and legitimate solution, it entails substantial computational resources. To address this issue, graph unlearning methods have been proposed in the domain of graph data. However, applying existing graph unlearning methods directly to hypergraph data affects model utility. Specifically, the graph unlearning methods severely damage the higher-order structural information of hypergraphs and fail to remove all the information that needs to be unlearned. In this paper, we propose Hyperedge Size-Based Core-Sharing Decomposition, a novel hypergraph unlearning framework tailored to the structural characteristics of hypergraph data. Its contributions include a subgraph partitioning method specific to hypergraphs and an aggregation method based on node coverage. We conduct extensive experiments on seven real-world hypergraph datasets to demonstrate the unlearning efficiency and model utility. Compared to the baseline methods, our approach achieves up to 5% higher accuracy and reduces the average unlearning time by 28%. Furthermore, our node-coverage-based aggregation approach achieves up to 6% higher accuracy.