- 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
-
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.
-
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.
-
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
- 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.
-
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.
-
It would be better if the authors provided source code to support reproducibility.
-
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
-
Can the proposed framework outperform other non-retraining-based graph unlearning methods?
-
Give a more detailed explanation of the rounding mechanism.
5 comments
Part 2
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 nodes to shards with at most nodes per shard is a capacitated many-to-one matching problem. Replicating each shard into discrete slots () creates slots and converts shard capacity limits into standard one-to-one matching constraints.
- Explicit LSAP Formulation: With cost , finding the optimal discrete assignment becomes: This is the canonical rectangular LSAP. Minimizing total cost maximizes the total continuous assignment score , while the column constraints guarantee that every shard receives at most nodes.
- Shard Recovery: Once the matching is obtained, each node matched to slot () is deterministically mapped back to shard .
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.
Part 1
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.
Response: Thank you for sharing your perspective. We believe that LENS advances the field across three major dimensions:
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:
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.
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:
AUC ROC of MIA (distinguishing between tuning nodes and test nodes) against Partitioning Methods
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.