LENS: Neighborhood-Preserving Partitioning for Exact Graph Unlearning

Machine unlearning has emerged as a critical research frontier, driven by increasing privacy concerns and regulatory requirements. To circumvent the prohibitive cost of retraining from scratch, several efficient unlearning methods have been proposed. The Sharded, Isolated, Sliced, and Aggregated (SISA) framework is the most prominent for exact unlearning. However, applying partition-based approaches to graph-structured data remains a significant challenge. Naive partitioning disrupts the essential structural dependencies and node neighborhoods upon which Graph Neural Networks (GNNs) rely. In this work, we propose LENS (Local Edge-preserving Node Sharding), a novel partition-based framework for graph unlearning. LENS introduces a partitioning objective that explicitly prioritizes preserving node neighborhoods and maintaining the structural integrity required for effective message passing in GNNs. We provide a theoretically grounded optimization strategy for this objective. We further present a training-free aggregation scheme that combines entropy filtering with adaptive temperature scaling, outperforming more expensive learnable aggregators. Extensive experiments demonstrate that LENS consistently achieves superior performance on downstream tasks across multiple standard GNN backbones and datasets. Finally, we expose a critical limitation in existing partition-based methods that rely on learnable aggregators, challenging the assumption that these aggregators do not require frequent retraining. We show that unlearning high-degree nodes induces shifts in submodels' prediction that degrade learnable aggregators, whereas LENS's training-free aggregation scheme maintains utility and avoids hidden retraining costs.