acceptodds
Under review as a conference paper at ICLR 2027

LENS: Neighborhood-Preserving Partitioning for Exact Graph Unlearning

Abstract

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.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph Neural Networks, Unlearning, Graph partitioning

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_C9HAOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

This paper focuses on the graph partitioning problem in retraining-based graph unlearning. This paper partitions the graph using an edge-preserving algorithm, then trains each sub-model in isolation with a contrastive loss to reduce the label/feature homogeneity problem in each subgraph, and proposes a novel aggregation strategy without training an aggregator. Empirical results show that the proposed method is better than previous baselines, and also show a significant drawback for learning-based aggregation.

Critical strengths
  1. The presentation quality of this paper is quite good. The visual aids and mathematical notations are quite clear and easy to follow. The main idea and motivation for this work are also clear.

  2. The empirical results of this paper are quite promising in comparison with previous retraining-based graph unlearning methods. The insight on challenging the learning-based aggregator is also quite interesting. The efficiency improvements are also noticeable.

  3. The relaxation and rounding mechanisms of this paper are carefully designed to ensure strict balancing constraints. This is a novel point compared with previous works.

Critical weaknesses
  1. This paper only compares retraining-based graph unlearning methods in the main comparison experiment. I am not sure this is a good choice, since we know that all retraining-based graph unlearning methods are still somewhat "approximate" and are not "exact". It would be better if the authors also compare with some approximate unlearning methods that are not based on retraining.

This is the main technical issue for this paper. If the authors could resolve this by comparing with at least 3 representative non-retraining methods, I would like to increase my score.

  1. The novelty of this paper is still a significant issue. Basically, this paper did not propose a new framework for graph unlearning, and only did some incremental improvements in this niche field. The basic framework is from [1], and the insights on optimizing the graph to preserve the edges and deal with label/feature homogeneity in each subgraph are mentioned in [2]. It is true that this paper makes some different technical choices, but the excitement of this paper is better for a journal paper than a conference paper.

  2. It would be better if the authors provided source code to support reproducibility.

  3. For the rounding mechanism, it would be better if the authors showed things more concretely and proved why the rounding problem is an LSAP problem. This is a minor issue but could improve readability.

[1] Chen M, Zhang Z, Wang T, et al. Graph unlearning[C]//Proceedings of the 2022 ACM SIGSAC conference on computer and communications security. 2022: 499-513.

[2] Zhang J. Graph unlearning with efficient partial retraining[C]//Companion Proceedings of the ACM Web Conference 2024. 2024: 1218-1221.

Questions for authors
  1. Can the proposed framework outperform other non-retraining-based graph unlearning methods?

  2. Give a more detailed explanation of the rounding mechanism.

5 comments

W1 and Q1: This paper only compares retraining-based graph unlearning methods in the main comparison experiment [...] It would be better if the authors also compare with some approximate unlearning methods that are not based on retraining.

Response: We are running the baselines and will get back to you with the results and complete response as soon as possible. Update: We've provided the results of the new approximate baselines below.

W2: The novelty of this paper is still a significant issue. Basically, this paper did not propose a new framework for graph unlearning, and only did some incremental improvements in this niche field. The basic framework is from [1], and the insights on optimizing the graph to preserve the edges and deal with label/feature homogeneity in each subgraph are mentioned in [2].

Response: Thank you for sharing your perspective. We believe that LENS advances the field across three major dimensions:

  1. Redesign Across All Three Stages of the SISA Pipeline Almost all existing partition-based graph unlearning methods--including GraphEraser [1] and GraphRevoker [2]--modify only the partitioning and aggregation stages while leaving submodel training unchanged. In contrast, LENS introduces principled innovations across all three stages of the pipeline:

    • GNN-Tailored Partitioning: Rather than optimizing global edge cuts, we formulate a node-level Relative Neighborhood Loss (Lrel\mathcal{L}_{\mathrm{rel}}) specifically aligned with GNN message passing, weighting edge preservation inversely by node degree so low-degree nodes are not isolated.
    • Bridging the Subgraph-to-Full-Graph Training Mismatch: Prior works overlook a critical structural mismatch: submodels are trained on isolated, homophilically clustered shards, yet inference is performed on the complete, unpartitioned graph. LENS is the first to address this gap at the training stage via a degree difference-weighted contrastive loss, preventing representation collapse between low- and high-degree nodes across shards.
    • Training-Free Adaptive Aggregation: Instead of fitting parametric combiners, we design a non-parametric aggregation scheme using entropy filtering and adaptive temperature scaling to calibrate submodel predictions dynamically at inference time.
  2. Principled, Theoretically Supported Optimization vs. Heuristics and Black-Box GNNs Although prior works recognize the high-level intuition of preserving edges, they rely either on ad-hoc heuristics (e.g., balanced label propagation in GraphEraser [1]) or black-box neural networks (e.g., the trainable GNN partitioner in GraphRevoker [2]). LENS replaces both heuristics and heavy black-box partitioners with a principled, theoretically grounded optimization framework. We prove that our Relative Neighborhood Loss is submodular (Theorem 3.1) and derive a balanced convex relaxation via the Lovász extension.

  3. Challenging the Standard Paradigm of Learnable Aggregators (Expanded in Section 4.2) As you kindly noted, "the insight on challenging the learning-based aggregator is also quite interesting." Prior literature [1, 2] has largely treated learnable aggregators as a standard, low-risk design choice. Our work demonstrates that this assumption is flawed. In Section 4.2 of the revised manuscript, we have expanded our analysis to show that learnable aggregators introduce two distinct vulnerabilities:

  • Pre-Unlearning Privacy Leakage: Optimizing a parametric neural aggregator on a small tuning set causes overfitting, significantly elevating Membership Inference Attack (MIA) vulnerability even before any deletion occurs (Please see the table below).

AUC ROC of MIA (distinguishing between tuning nodes and test nodes) against Partitioning Methods

MethodCoraCiteSeerPubMedBlogCatalog
Revoker0.5885 ± 0.00930.7035 ± 0.00490.5296 ± 0.00180.5942 ± 0.0053
LENS0.526 ± 0.00640.5359 ± 0.00520.4986 ± 0.00250.519 ± 0.0058
  • Post-Unlearning Utility Degradation: When high-degree nodes outside the tuning set are deleted, stale aggregator weights fail to adapt to shifted submodel outputs, causing severe F1 drops unless the aggregator is repeatedly retrained.

Showing that a training-free aggregator eliminates both privacy leakage and post-unlearning staleness--while achieving high utility--provides an important and practical shift for future graph unlearning systems.

Revision: Please refer to Section 4.2 in the revised manuscript for the expanded results on the Pre-Unlearning Privacy Leakage.

[1] Chen M, Zhang Z, Wang T, et al. Graph unlearning[C]//Proceedings of the 2022 ACM SIGSAC conference on computer and communications security. 2022: 499-513.

[2] Zhang J. Graph unlearning with efficient partial retraining[C]//Companion Proceedings of the ACM Web Conference 2024. 2024: 1218-1221.

W3: It would be better if the authors provided source code to support reproducibility.

Response: You can find the link to our source code at the end of the Introduction section or in the Reproducibility Statement.

W4 and Q2: For the rounding mechanism, it would be better if the authors showed things more concretely and proved why the rounding problem is an LSAP problem.

Response: Thank you for this suggestion to improve clarity. We have expanded the rounding discussion in Section 3.2 of the revised manuscript to make the reduction from balanced partitioning to a Linear Sum Assignment Problem (LSAP) concrete and self-contained:

  • Slot-Replication Reduction: Assigning ∣V∣\vert{}\mathcal{V}\vert{} nodes to kk shards with at most m=⌈∣V∣/k⌉m = \lceil \vert{}\mathcal{V}\vert{} / k \rceil nodes per shard is a capacitated many-to-one matching problem. Replicating each shard i∈{1,…,k}i \in \{1, \dots, k\} into mm discrete slots j=(i−1)m+rj = (i - 1)m + r (1≤r≤m1 \le r \le m) creates M=k⋅m≥∣V∣M = k \cdot m \ge \vert{}\mathcal{V}\vert{} slots and converts shard capacity limits into standard one-to-one matching constraints.
  • Explicit LSAP Formulation: With cost Cu,j=−x(u,i)C_{u, j} = -x(u, i), finding the optimal discrete assignment becomes: min⁡P∈{0,1}∣V∣×M∑u∈V∑j=1MCu,jPu,js.t.∑j=1MPu,j=1  (∀u),∑u∈VPu,j≤1  (∀j)\min_{P \in \{0, 1\}^{\vert{}\mathcal{V}\vert{} \times M}} \sum_{u \in \mathcal{V}} \sum_{j=1}^{M} C_{u, j} P_{u, j} \quad \text{s.t.} \quad \sum_{j=1}^{M} P_{u, j} = 1 \; (\forall u), \quad \sum_{u \in \mathcal{V}} P_{u, j} \le 1 \; (\forall j)This is the canonical rectangular LSAP. Minimizing total cost maximizes the total continuous assignment score ∑u,ix(u,i)\sum_{u, i} x(u, i), while the column constraints guarantee that every shard receives at most mm nodes.
  • Shard Recovery: Once the matching PP is obtained, each node uu matched to slot jj (Pu,j=1P_{u, j} = 1) is deterministically mapped back to shard i=⌈j/m⌉i = \lceil j / m \rceil.

Revision: Please see Section 3.2 in the revised manuscript for this updated formulation.

Thanks for the timely response to my questions. I am satisfied, and I have updated the score.

Reviewer_PQUCOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

LENS is a partition-based graph-unlearning framework designed to preserve node neighborhoods while enabling localized retraining. It introduces a relative neighborhood-loss objective for graph partitioning, a balanced optimization procedure based on the Lovász extension, a degree-difference-weighted contrastive loss for training shard-specific GNNs, and a training-free aggregation method using entropy filtering and adaptive temperature scaling. The authors evaluate LENS on four graph datasets with three GNN backbones, reporting node-classification utility and comparing its aggregation method with a learned aggregator under targeted node deletion. The results suggest that LENS can preserve competitive predictive performance across several settings, but the experiments do not directly establish the paper’s claim of exact unlearning.

Critical strengths

Critical Strengths

  1. The partitioning objective accounts for differences in how nodes are affected by cut edges. By measuring neighborhood loss relative to each node’s degree, LENS gives greater attention to preserving the limited neighborhood context of low-degree nodes. This is a relevant design consideration for GNNs, whose predictions depend on local graph structure.

  2. The paper examines how deletion can affect model aggregation. Its targeted-deletion experiment shows that changes in shard predictions can degrade a learned aggregator even when the deleted nodes were not used to train it. This highlights a practical issue in partition-based unlearning and motivates studying aggregation under deletion.

Critical weaknesses

Critical Weaknesses

  1. The exact-unlearning claim is limited to a modified, partition-based training procedure. LENS changes the learner by partitioning the graph and training separate shard models. Retraining only the affected shard may approximate retraining under this specific partitioned procedure, but this does not establish equivalence to retraining the original GNN on the retained graph, or support unlearning for arbitrary training procedures. The paper should clearly define the reference learner and limit its claims accordingly. It should also clarify whether the partition is held fixed after deletion, since the partition itself is constructed from the data.

  2. The contribution appears incremental, and its practical relevance is not established. LENS mainly extends the SISA-style partition-and-retrain framework with a neighborhood-aware partitioning objective, a contrastive loss, and a training-free aggregator. The experiments show classification utility on four datasets, but do not establish that this approach is practical for real-world graphs, where dependencies cross partitions and partitioning and aggregation add costs. The presentation also makes it difficult to distinguish the core contribution from these component-level modifications.

Questions for authors

Questions For Authors

  1. Clarification: What formal guarantee supports the paper’s exact-unlearning claim? Please define the reference training procedure, including how the graph partition is obtained, and provide a proof that retraining only the affected shard produces the same model distribution as rerunning this procedure after deletion. If the method only approximates the reference result, please state and justify an appropriate error bound.

  2. Clarification: Is the guarantee limited to LENS’s partition-based learner, or is it intended to apply to the original GNN training procedure as well? Is the partition recomputed after deletion, or held fixed? Please explain how this choice affects the guarantee.

  3. Evidence affecting the recommendation: Can the authors provide a direct comparison between LENS and full retraining on the retained graph, with the reference procedure clearly specified? This would help establish whether the method approximates the original learner or only its own partition-based training pipeline.

9 comments

W1: Retraining only the affected shard may approximate retraining under this specific partitioned procedure, but this does not establish equivalence to retraining the original GNN on the retained graph, or support unlearning for arbitrary training procedures. The paper should clearly define the reference learner and limit its claims accordingly. It should also clarify whether the partition is held fixed after deletion, since the partition itself is constructed from the data.

Response: Please see our answers to Questions 1 and 2.

W2.1: The contribution appears incremental [...] LENS mainly extends the SISA-style partition-and-retrain framework with a neighborhood-aware partitioning objective, a contrastive loss, and a training-free aggregator.

Response: Thank you for your comment. While LENS retains the SISA partition-and-retrain paradigm to guarantee strict algorithmic unlearning exactness, we respectfully clarify why its contributions represent a principled, end-to-end redesign for graph-structured data:

  1. Coordinated Redesign Across All Three Stages of SISA Almost all prior partition-based graph unlearning methods (such as GraphEraser, GraphRevoker, and GUIDE) modify only partitioning and aggregation while leaving submodel training unchanged. However, partitioning a graph creates coupled structural and distributional challenges across the entire pipeline:
  • Degree-Aware Partitioning (Sections 3.1–3.2): Global edge-cut objectives (previous works) disproportionately sever connections around low-degree nodes. We formulate a node-level Relative Neighborhood Loss (Lrel\mathcal{L}_{\mathrm{rel}}) tailored specifically to GNN message passing, weighting edge preservation inversely by node degree.
  • Resolving the Subgraph-to-Full-Graph Training Mismatch (Section 3.3): Prior works overlook a fundamental domain shift: submodels are trained on isolated, homophilically clustered shards, yet inference runs on the complete, unpartitioned graph. LENS is the first to address this mismatch at the training stage via a degree difference-weighted contrastive loss, preventing representation collapse between low- and high-degree nodes across shards.
  • Training-Free Adaptive Aggregation (Section 3.4): Rather than fitting parametric combiners, we calibrate submodel posteriors dynamically at inference time via entropy filtering and adaptive temperature scaling.
  1. Theoretically Grounded Optimization vs. Heuristics and Black-Box Partitioners Existing methods partition graphs use either ad-hoc heuristics (e.g., balanced label propagation in GraphEraser) or black-box neural networks (e.g., the trainable GNN partitioner in GraphRevoker). In contrast, LENS provides a principled optimization framework with formal guarantees: we prove that Lrel\mathcal{L}_{\mathrm{rel}} is submodular (Theorem 3.1), derive a balanced convex relaxation via the Lovász extension.
  2. Challenging the Learnable Aggregator Paradigm (Expanded in Section 4.2) We appreciate your recognition of our targeted-deletion experiment showing that "changes in shard predictions can degrade a learned aggregator even when the deleted nodes were not used to train it." Prior graph unlearning literature has largely treated learnable aggregators as a low-risk component. In Section 4.2 (and Appendix A.5.3) of the revised manuscript, we expand this analysis to show that parametric aggregators introduce two vulnerabilities:
  • Pre-Unlearning Privacy Leakage: Optimizing a neural aggregator on a small tuning set causes overfitting, significantly increasing Membership Inference Attack (MIA) risk even before any deletion occurs (Please see the table below).

AUC ROC of MIA (distinguishing between tuning nodes and test nodes) against Partitioning Methods

MethodCoraCiteSeerPubMedBlogCatalog
Revoker0.5885 ± 0.00930.7035 ± 0.00490.5296 ± 0.00180.5942 ± 0.0053
LENS0.526 ± 0.00640.5359 ± 0.00520.4986 ± 0.00250.519 ± 0.0058
  • Post-Unlearning Utility Degradation & Hidden Retraining Costs: Stale aggregator weights fail under shifted shard predictions after high-degree deletions, while continually retraining the aggregator (evaluated via our newly added Revoker Retrained baseline) reintroduces ongoing update overhead.

Showing that a non-parametric, training-free aggregator eliminates both privacy leakage and post-unlearning staleness--while outperforming learnable baselines--establishes an important design principle for future partition-based graph unlearning systems.

Revision: Please refer to Section 4.2 in the revised manuscript for the added results on Pre-Unlearning Privacy Leakage.

W2.2: Its practical relevance is not established [...] The experiments show classification utility on four datasets, but do not establish that this approach is practical for real-world graphs, where dependencies cross partitions and partitioning and aggregation add costs.

Response: Thank you for raising this concern. We would like to clarify that all four benchmarks evaluated in our study are real-world graphs, and we have added explicit runtime measurements in Appendix A.5.1 of the revised manuscript to demonstrate LENS's practical efficiency.

  1. Real-World Benchmarks & Resilience to Cross-Partition Dependencies: Cora, CiteSeer, PubMed, and BlogCatalog are widely used real-world graph benchmarks spanning citation networks and social networks. In particular, BlogCatalog is a dense real-world social network comprising 5,1965{,}196 nodes and 343,486343{,}486 edges. Partitioning such a densely connected graph into k=20k = 20 disjoint shards inevitably severs a large number of edges and introduces substantial cross-partition dependencies. Despite this heavy cross-shard coupling, LENS achieves a Macro F1 of 0.92540.9254 on BlogCatalog with GraphSAGE. This demonstrates that LENS's combination of neighborhood-aware partitioning, degree difference-weighted contrastive regularization, and adaptive inference-time aggregation effectively handles dense, real-world cross-partition dependencies.
  2. Low Computational Cost of Partitioning and Aggregation (Appendix A.5.1)
  • Zero Aggregation Update Cost: Unlike baselines such as GraphRevoker that train and maintain a parametric aggregator, LENS's aggregation scheme is completely training-free. It introduces zero learnable parameters and requires no offline training or post-deletion retraining.
  • Fast, Scalable Partitioning & Retraining: To quantify wall-clock costs, we have added a dedicated efficiency benchmark in Appendix A.5.1 of the revised manuscript comparing partitioning times across all baselines and unlearning retraining times against full retraining from scratch:

Partition Time (seconds)

MethodCoraCiteSeerPubMedBlogCatalog
GraphEraser19.7726.26182.955.17
GraphRevoker197.66214.7634,272.942,043.20
GUIDE5.577.23319.6711.48
LENS7.4310.359.9330.02

Retraining Time (seconds)

BackboneMethodCoraCiteSeerPubMedBlogCatalog
GCNFull Train4.3010.0823.03154.12
GCNLENS0.971.494.374.43
GATFull Train5.0311.2829.04169.69
GATLENS1.221.674.734.70
SAGEFull Train9.4027.4034.71852.04
SAGELENS1.262.414.8215.39

As shown, our method scales well across graphs of different sizes, especially on PubMed (our largest graph by node count), where GraphEraser takes 182.95 s182.95\text{ s} and GUIDE takes 319.67 s319.67\text{ s} in comparison to 9.93 s9.93\text{ s} of LENS. In terms of unlearning speedup: across all 12 backbone–dataset configurations, LENS reduces worst-case unlearning retraining time substantially.

Revision: Please see Appendix A.5.1 in the revised manuscript for the complete runtime tables and analysis.

W2.3: The presentation also makes it difficult to distinguish the core contribution from these component-level modifications.

Response: Thank you for pointing this out. We clarify both the conceptual hierarchy of our design and the empirical separation of each component below:

  1. Conceptual Distinction: Core Contribution vs. Supporting Components
  • Core Methodological Contribution (Sections 3.1–3.2): LENS's primary contribution is Neighborhood-aware Partitioning. Unlike prior partition-based graph unlearning methods that rely on heuristic or global edge-cut objectives, we formulate a node-level Relative Neighborhood Loss (Lrel\mathcal{L}_{rel}) that accounts for heterogeneous degree sensitivity in GNN message passing. We prove that this objective is submodular (Theorem 3.1) and derive a balanced convex relaxation via the Lovász extension.
  • Supporting Components (Sections 3.3–3.4): Our training and aggregation modules are designed to resolve downstream challenges introduced by neighborhood-preserving partitioning:
    • Degree Difference-Weighted Contrastive Loss (Section 3.3) counteracts homophilic over-clustering within neighborhood-preserving shards and prevents low- vs. high-degree representation collapse when transitioning from isolated shard training to full-graph inference.
    • Training-Free Adaptive Aggregation (Section 3.4) mitigates submodel overconfidence on fragmented shards via entropy filtering and adaptive temperature scaling (Section 4.2).
  1. Empirical Separation (Appendix A.6) To empirically distinguish the effect of our core partitioning method from component-level modifications, we added a dedicated Component Ablation Study in Appendix A.6 of the revised manuscript. We isolate the individual contributions of LENS's partitioning and aggregation modules using the GraphSAGE backbone with k=20k = 20 shards and our degree difference-weighted contrastive loss.
  • Varying Partitioning Methods: We hold LENS's adaptive aggregation and contrastive training fixed while varying the partitioning algorithm used by GraphEraser, GraphRevoker, GUIDE, and LENS.

Impact of Varying Partition Methods on Macro F1

PartitionCoraCiteSeerPubMedBlogCatalog
GraphEraser0.7815 ± 0.01130.6587 ± 0.01950.8515 ± 0.00220.9283 ± 0.0125
GraphRevoker0.6894 ± 0.09630.6475 ± 0.01890.8464 ± 0.00410.9166 ± 0.0107
GUIDE0.7500 ± 0.06210.6612 ± 0.02280.8459 ± 0.00230.8923 ± 0.0142
LENS0.8281 ± 0.00450.678 ± 0.01460.8504 ± 0.00180.9226 ± 0.0158
∑Δ\sum\DeltaF1+0.2634+0.0666+0.0074+0.0306
  • Varying Aggregation Methods: We hold LENS's neighborhood-aware partitioning and contrastive training fixed while varying the aggregation scheme from four frameworks (note that GUIDE uses simple posterior averaging).

Impact of Varying Aggregation Methods on Macro F1

AggregationCoraCiteSeerPubMedBlogCatalog
GraphEraser0.7542 ± 0.04090.6415 ± 0.02460.8455 ± 0.00330.9083 ± 0.0082
GraphRevoker0.7746 ± 0.02350.6702 ± 0.01780.8357 ± 0.00750.9118 ± 0.0121
GUIDE0.8050 ± 0.01020.6548 ± 0.0140.8494 ± 0.00290.9219 ± 0.0143
LENS0.8281 ± 0.00450.6780 ± 0.01460.8504 ± 0.00180.9226 ± 0.0158
∑Δ\sum\DeltaF1+0.1505+0.0675+0.0206+0.0258

As shown by the cumulative relative gains ∑ΔF1=∑m(F1LENS−F1m)\sum\Delta F1 = \sum_{m} (F1_{LENS} - F1_{m}), isolating our core Neighborhood-aware Partitioning yields substantial improvements on its own (up to +0.2634+0.2634 cumulative Macro F1 on Cora), while our training-free aggregation provides complementary gains across all benchmarks (e.g., +0.0206+0.0206 on PubMed).

Revision: We added a dedicated Component Ablation Study in Appendix A.6 of the revised manuscript.

Reviewer_wBHMOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper presents LENS, a framework for removing node data from graph models while reducing retraining costs and preserving predictive performance. It follows the idea of partitioning a graph into subgraphs, training a separate GNN on each, and combining their predictions. When a deletion request arrives, the relevant nodes are removed and only the affected submodels are retrained. I see the main idea as improving three parts of this process: partitioning, training, and aggregation. During partitioning, the authors consider not only how many edges are cut, but also what fraction of its neighbors each node loses, while keeping shard sizes similar. During training, they introduce a degree difference-weighted contrastive loss to help address representation changes between training on subgraphs and inference on the complete graph. At inference, each submodel makes predictions on the complete graph. Uncertain predictions are filtered out, and the remaining predictions are adjusted for confidence and averaged. One advantage of this stage is that it requires no additional aggregator training. Experiments compare LENS with existing partitioning methods across four datasets and three GNN backbones. LENS achieves the highest Macro F1 among the compared unlearning methods in eight of the twelve settings. This suggests that the complete approach preserves predictive performance well under most of the tested conditions.

Critical strengths
  1. I find the motivation for the partitioning objective clear. Losing two neighbors can have very different effects on a node with three neighbors and one with a hundred. Measuring the fraction of lost neighbors captures this distinction and gives more consideration to nodes with few neighbors.
  2. I think the authors have developed the method in reasonable detail. Beyond defining the partitioning objective, they consider shard balance, provide a submodularity proof, and describe the optimization and discrete assignment procedures.
  3. The aggregation scheme is another useful part of the design. It selects submodel outputs for each node and adjusts their confidence without additional training. This allows aggregation to respond to the current predictions without maintaining learned aggregation parameters. Section 4.2 gives a concrete example of why this can help. After submodels are updated, the fixed MLP aggregator loses substantial performance, while LENS remains relatively stable.
  4. The overall experimental results are encouraging. Among the compared unlearning methods, LENS ranks first in eight of the twelve combinations of datasets and backbones, and second in three others. The authors also report means and standard deviations over seven random seeds. These results suggest that the benefits of the complete method are not limited to one dataset or one GNN architecture.
Critical weaknesses
  1. I am still unsure how much each design contributes, and the ablation study seems incomplete. LENS changes partitioning, training, and aggregation, but Section 4.3 only varies the number of shards. This shows sensitivity to shard count rather than the contribution of each component. Section 4.2 compares aggregation schemes, but the effect of the main partitioning objective remains unclear. Could the authors compare partitioning objectives while keeping training and aggregation fixed? Separate tests of the degree difference-weighted contrastive loss, entropy filtering, and adaptive temperature scaling would also help establish where the performance gains come from.
  2. I could not find a comparison of actual running times. The paper emphasizes reducing retraining costs and avoiding aggregator updates. However, LENS also adds partitioning optimization and a training regularizer. How much time do these steps take compared with existing partitioning methods? How long does an unlearning update take? Reporting partitioning, training, and update times, with full retraining as a reference, would help me assess the relationship between performance and computational cost.
  3. I find the observation in Section 4.2 worth discussing, but I think the conclusion could be more cautious. The experiment uses GAT, compares one MLP aggregator with LENS, and specifically removes nodes with high degrees. This shows a possible failure under the tested conditions. It does not yet establish that learnable aggregators generally require frequent retraining. I would like to see a retrained MLP aggregator included as a comparison.
  4. I would appreciate an explanation of the GAT result on BlogCatalog in Table 1. LENS obtains a Macro F1 of 0.5504, compared with 0.6590 for GraphRevoker. What causes this gap? The overall ranking is good, but I think this exception also deserves discussion when claiming consistency across settings. Some winning margins in Table 1 are also small. For example, on PubMed with GCN, LENS exceeds the strongest baseline by only 0.0004.
  5. I also have a question about Figure 1. It presents the three components reasonably clearly, but I still find it difficult to follow the actual unlearning process. When a deletion request arrives, which node is removed? Which submodel is retrained? How are the other submodels retained and used in aggregation? I would appreciate a clearer illustration of this process to help me follow the framework as a whole.
Questions for authors

see weaknesses

5 comments

W1: I am still unsure how much each design contributes, and the ablation study seems incomplete. LENS changes partitioning, training, and aggregation, but Section 4.3 only varies the number of shards. This shows sensitivity to shard count rather than the contribution of each component [...] Could the authors compare partitioning objectives while keeping training and aggregation fixed? Separate tests of the degree difference-weighted contrastive loss, entropy filtering, and adaptive temperature scaling would also help establish where the performance gains come from.

Response: Thank you for this constructive suggestion. In Appendix A.6 of the revised manuscript, we isolate the individual contributions of LENS's partitioning and aggregation modules using the GraphSAGE backbone with k=20k = 20 shards and our degree difference-weighted contrastive loss across 7 random seeds:

  1. Varying Partitioning Methods: We hold LENS's adaptive aggregation and contrastive training fixed while varying the partitioning algorithm used by GraphEraser, GraphRevoker, GUIDE, and LENS.

Impact of Varying Partition Methods on Macro F1

PartitionCoraCiteSeerPubMedBlogCatalog
GraphEraser0.7815 ± 0.01130.6587 ± 0.01950.8515 ± 0.00220.9283 ± 0.0125
GraphRevoker0.6894 ± 0.09630.6475 ± 0.01890.8464 ± 0.00410.9166 ± 0.0107
GUIDE0.7500 ± 0.06210.6612 ± 0.02280.8459 ± 0.00230.8923 ± 0.0142
LENS0.8281 ± 0.00450.678 ± 0.01460.8504 ± 0.00180.9226 ± 0.0158
∑Δ\sum\DeltaF1+0.2634+0.0666+0.0074+0.0306
  1. Varying Aggregation Methods: We hold LENS's neighborhood-aware partitioning and contrastive training fixed while varying the aggregation scheme from four frameworks (note that GUIDE uses simple posterior averaging).

Impact of Varying Aggregation Methods on Macro F1

AggregationCoraCiteSeerPubMedBlogCatalog
GraphEraser0.7542 ± 0.04090.6415 ± 0.02460.8455 ± 0.00330.9083 ± 0.0082
GraphRevoker0.7746 ± 0.02350.6702 ± 0.01780.8357 ± 0.00750.9118 ± 0.0121
GUIDE0.8050 ± 0.01020.6548 ± 0.0140.8494 ± 0.00290.9219 ± 0.0143
LENS0.8281 ± 0.00450.6780 ± 0.01460.8504 ± 0.00180.9226 ± 0.0158
∑Δ\sum\DeltaF1+0.1505+0.0675+0.0206+0.0258

Key Takeaways:

  • Consistent Component Gains: Across both ablations, LENS's module ranks first or second on every dataset and yields positive cumulative relative gains: ∑ΔF1=∑m(F1LENS−F1m)\sum \Delta F1 = \sum_{m} (F1_{LENS} - \text{F1}_{m}) across all four benchmarks, confirming that both components actively contribute to downstream predictive utility.
  • Complementary Contributions Across Datasets: Neither component dominates universally. Neighborhood-aware partitioning drives larger gains on Cora (+0.2634+0.2634 vs. +0.1505+0.1505) while adaptive aggregation contributes more on PubMed (+0.0206+0.0206 vs. +0.0074+0.0074), and both contribute roughly equally on CiteSeer and BlogCatalog.

Revision: To avoid any confusion about the scope of our main-text analysis, we have renamed Section 4.3 to Shard Granularity Analysis and added a dedicated Component Ablation Study in Appendix A.6 of the revised manuscript.

W2: How much time do these steps take compared with existing partitioning methods? How long does an unlearning update take? Reporting partitioning, training, and update times, with full retraining as a reference, would help me assess the relationship between performance and computational cost.

Response: Thank you for this helpful suggestion. We have added a dedicated Efficiency of LENS section (A.5.1) in the Appendix (and referenced it in Section 4.1) reporting both offline graph partitioning times across all partitioning baselines and online unlearning update/retraining times compared to full retraining from scratch.

  1. Offline Graph Partitioning Time (Comparison with Partition-based Baselines) Because all SISA-based frameworks retrain only the subgraph(s) affected by a deletion request, the primary computational distinction among partition-based methods lies in offline preprocessing--most notably graph partitioning. Scalability Advantage: Our Lovász-extension optimization of the Relative Neighborhood Loss scales consistently well across graph sizes, finishing in 9.93 s9.93\text{ s} on PubMed (our largest graph by node count), where GraphEraser (182.95 s182.95\text{ s}) and GUIDE (319.67 s319.67\text{ s}) slow down substantially.

Partition Time (seconds, k=20k = 20 shards)

MethodCoraCiteSeerPubMedBlogCatalog
GraphEraser19.7726.26182.955.17
GraphRevoker197.66214.7634,272.942,043.20
GUIDE5.577.23319.6711.48
LENS7.4310.359.9330.02
  1. Unlearning Update Time (vs. Full Retraining)

Because LENS uses a training-free aggregation scheme with zero learnable parameters, an unlearning update requires no aggregator retraining. The total unlearning update time equals the retraining time of the affected shard submodel(s). Furthermore, the LENS training times below already include our degree difference-weighted contrastive loss regularizer while the Full Train baseline uses a regular loss function. To reflect worst-case single-node deletion latency, we report LENS's retraining time on the subgraph of the most nodes. Across all 12 backbone--dataset settings, LENS achieves significantly faster retraining than full retraining from scratch.

Retraining Time (seconds)

BackboneMethodCoraCiteSeerPubMedBlogCatalog
GCNFull Train4.3010.0823.03154.12
GCNLENS0.971.494.374.43
GATFull Train5.0311.2829.04169.69
GATLENS1.221.674.734.70
SAGEFull Train9.4027.4034.71852.04
SAGELENS1.262.414.8215.39

Revision: Please see the Efficiency of LENS subsection (A.5.1) in the Appendix of the revised manuscript for full details.

W3: I would like to see a retrained MLP aggregator included as a comparison.

Response: As requested, we have added the Retrained Aggregator baseline (Revoker Retrained) across all four datasets (compared to three datasets before):

Macro F1 Degradation of Different Aggregation Methods

MethodCoraCiteSeerPubMedBlogCatalog
Revoker Stale0.3315 ± 0.04780.221 ± 0.06310.3933 ± 0.09380.4888 ± 0.0514
Revoker Retrained0.0494 ± 0.02220.0019 ± 0.03930.005 ± 0.003-0.002 ± 0.019
LENS0.0066 ± 0.04930.0143 ± 0.00770.0032 ± 0.0022-0.0346 ± 0.0356

Isolating Parameter Staleness: When the neural aggregator is explicitly retrained after submodel updates (Revoker Retrained), Macro F1 degradation is significantly reduced. This confirms that the neural aggregator has sufficient capacity to model the updated submodel outputs, and that the severe drop in Revoker Stale stems directly from stale aggregator weights failing to adapt to post-unlearning distribution shifts.

Avoiding Hidden Retraining Overhead: While retraining the neural aggregator recovers utility, relying on this fix reintroduces aggregator retraining costs even when deleted nodes lie outside the tuning set. In contrast, LENS matches or outperforms Revoker Retrained with zero aggregator parameters or updates by dynamically calibrating predictions via entropy filtering and adaptive temperature scaling.

Revision: Please see Appendix A.5.3 in the revised manuscript for the updated discussion and this full table.

W4: I would appreciate an explanation of the GAT result on BlogCatalog in Table 1. Some winning margins in Table 1 are also small. For example, on PubMed with GCN, LENS exceeds the strongest baseline by only 0.0004.

Response: Thank you for this careful reading of Table 1. We agree that both the BlogCatalog–GAT exception and the narrow margins on PubMed warrant explicit discussion.

  1. Explaining the BlogCatalog-GAT Gap (0.55040.5504 vs. 0.65900.6590) To determine whether the performance gap on BlogCatalog with GAT stems from LENS's partitioning or its training-free aggregation, we conducted a controlled cross-ablation on BlogCatalog (GAT backbone) swapping the partitioners and aggregators between LENS and GraphRevoker:
  • Revoker Partitioner + LENS Training-Free Aggregator: 0.4077±0.11500.4077 \pm 0.1150 (vs. 0.55040.5504 with LENS Partitioner)
  • LENS Partitioner + Revoker Neural Aggregator: 0.6469±0.01960.6469 \pm 0.0196 (vs. 0.65900.6590 with Revoker Partitioner)

These results show that LENS's neighborhood-aware partitioning is not the bottleneck. Instead, GraphRevoker's advantage in this specific setting comes from its parametric neural aggregator, which learns cross-shard correction weights to compensate for noisy GAT submodels. However, as we demonstrate in our expanded Section 4.2, relying on a learnable neural aggregator introduces considerable privacy and post-unlearning reliability risks:

  • Pre-Unlearning Privacy Leakage (MIA Risk): Fitting a neural aggregator on a small tuning set causes overfitting to those nodes, exposing them to Membership Inference Attacks even before any unlearning occurs (under the same GAT setup):

AUC ROC of MIA (distinguishing between tuning nodes and test nodes) against Partitioning Methods

MethodCoraCiteSeerPubMedBlogCatalog
Revoker0.5885 ± 0.00930.7035 ± 0.00490.5296 ± 0.00180.5942 ± 0.0053
LENS0.526 ± 0.00640.5359 ± 0.00520.4986 ± 0.00250.519 ± 0.0058
  • Post-Unlearning Utility Collapse: When high-degree nodes outside the tuning set are deleted, GraphRevoker's stale neural aggregator loses 0.4888±0.05140.4888 \pm 0.0514 Macro F1 on BlogCatalog (Appendix A.5.3) unless repeatedly retrained, whereas LENS remains stable without parameter updates.

Thus, LENS trades off the extra parametric fitting capacity of a neural aggregator to guarantee zero aggregation-level privacy leakage and post-deletion stability.

  1. Why Winning Margins on PubMed Are Narrow On PubMed, LENS already performs very close to the upper bound of unpartitioned full training (Full Train), leaving very little headroom for larger improvement. By contrast, on benchmarks and backbones where partitioning creates greater structural disruption and wider headroom below the full-training upper bound, LENS achieves larger improvements over the strongest baseline (e.g., +0.0149+0.0149 Macro F1 on BlogCatalog with SAGE).

W5: When a deletion request arrives, which node is removed? Which submodel is retrained? How are the other submodels retained and used in aggregation? I would appreciate a clearer illustration of this process.

Response: Thank you for your questions. While Figure 1 illustrates LENS's initial partitioning, isolated training, and inference pipeline, we agree that an explicit visual walkthrough of the online deletion workflow makes the framework much easier to follow. To address this, we have added Figure 2 to the revised manuscript, which illustrates each step of the unlearning procedure:

  • Which node is removed? When a deletion request arrives for a revoked training node, that node--together with its feature vector and all of its incident edges (highlighted in red in Figure 2)--is removed from the specific subgraph to which it belongs (e.g., the second shard).
  • Which submodel is retrained? Because the graph is partitioned into mutually disjoint shards, only the submodel (GNN 2 in the figure) assigned to the affected shard was exposed to the revoked node during training. We discard this contaminated model (marked with a red cross) and retrain a replacement submodel from scratch on the pruned subgraph.
  • How are the remaining submodels retained and aggregated? All submodels trained on unaffected subgraphs (GNN 1 and GNN 3 in the figure) never observed the deleted node or its incident edges. They are therefore retained without modification (indicated by green checkmarks). During inference, the outputs from the untouched submodels (GNN 1, GNN 3) and the retrained submodel (GNN′ 2\text{GNN}'\ 2) are passed directly to our training-free adaptive aggregator, which filters high-entropy predictions, applies adaptive temperature scaling, and averages the calibrated probabilities without requiring any aggregator parameter updates.

Revision: Please refer to Figure 2 in the revised manuscript for this updated illustration.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.