PDUDT: Provable Decentralized Unlearning under Dynamic Topologies

We thank the Reviewer 6f9d for the time and valuable feedback! We would try our best to address the comments one by one.

1. Response to “Experimental Designs Or Analyses”: Thank you for your constructive feedback. We agree that providing more details on topology evolution and the impact of noise would further strengthen our results. In the experiments, we randomly generate connections among clients and then assign communication weights using the Metropolis-Hastings method. More details are provided in our subsequent response (Response to “Other Weaknesses 1.” ＆ “Questions For Authors 2.”). As for the impact of noise, our Figure 1 demonstrates that increased noise leads to a decline in model accuracy. However, under all noise conditions, the performance of PDUDT and Perturbed Retraining method is always comparable. This indicates that under the same noise conditions, these two approaches can achieve statistical indistinguishability. We hope our response addresses your concerns.

2. Response to “Other Weaknesses 1.” ＆ “Questions For Authors 2.”: Thank you for your constructive feedback. In fact, our experiments are based on dynamic connections. In each round, whether there is a connection between any two clients is randomly generated. Then, in order to ensure that the communication situation can be modeled as a doubly stochastic matrix, we use the Metropolis-Hastings method cited in the paper to generate the communication weights between clients. We have provided this detail of dynamic topology construction in the revised version.

3. Response to “Other Weaknesses 2.” ＆ “Other Comments Or Suggestions 1.”: Thank you for your valuable feedback. We agree that the extensive use of mathematical symbols can be challenging for readers. In our revised version, we have added a comprehensive notation table that summarizes all key variables and parameters, which enhance both readability and accessibility. Thank you again!

4. Response to “Questions For Authors 1.”: Thank you for your insightful question. Network dynamism is explicitly modeled in our theoretical analysis by allowing the communication matrices $\mathcal{W}^t$ (and the corresponding retraining matrices $\tilde{\mathcal{W}}^t$ ) to be time-varying. This reflects the fact that the network topology can change at each round. We introduce spectral gap upper bounds (e.g., $\rho_1$ and $\rho_2$) in our Assumption 4.8, which quantify the connectivity properties of these matrices. These bounds directly influence the convergence rate and error bounds derived in Theorem 4.9 and subsequent results. We hope our answer can clarify your confusion.

5. Response to “Other Comments Or Suggestions 2.＆3.”: We thank the reviewer for these valuable suggestions. In response, we have added a concise overview at the beginning of the appendix that outlines the contents and purpose of each section, making it easier for readers to navigate the supplementary material. Additionally, we carefully proofread the entire paper to correct any minor spelling or grammatical errors, ensuring clarity and a professional presentation. We hope these improvements meet your expectations.

If there are any further confusions/questions, we are happy to clarify and try to address them. Thank you again and your recognition means a lot for our work.

We thank the Reviewer vxha for the valuable feedback! We would try our best to address the comments one by one.

Response to “Claims And Evidence (1)” ＆ “Essential References Not Discussed” ＆ “Questions For Authors (1)”: We have carefully examined these works and provide a detailed comparison below to clarify our unique contributions. (1) vs. HDUS (Ye et al., 2023): HDUS relies on seed model distillation and additional training steps, without theoretical guarantees. PDUDT, by contrast, eliminates influence using saved historical gradients—without retraining—and offers formal guarantees on unlearning and convergence under dynamic topology. (2) vs. AIGC Unlearning (Lin et al., 2024): The AIGC work focuses on privacy-preserving AIGC systems via coded computing, incurring storage and reconstruction overhead. It lacks theoretical unlearning guarantees and is tailored to AIGC tasks. In contrast, PDUDT is application-agnostic, retraining-free, and provides provable client-level unlearning. (3) vs. BlockFUL (Liu et al., 2024): BlockFUL depends on blockchain infrastructure and consensus, which may be impractical in dynamic or asynchronous networks. In contrast, PDUDT is lightweight and naturally supports dynamic peer-to-peer topologies. Therefore, we claim that our work presents the first provable decentralized unlearning algorithm under dynamic topologies. In our current manuscript, although HDUS and BlockFUL have been cited, we agree that adding more detailed discussion will improve the quality. More generally, we also fill in the missing discussion on AIGC Unlearning (Lin et al., 2024).

Response to “Claims And Evidence (2)”: The statistical indistinguishability guarantee in Corollary 4.10 relies on the fact that the difference between the PDUDT output (model corrected by gradient residual estimation) and the output of retraining can be bounded (as shown in Theorem 4.9), and then obfuscated by adding Gaussian noise with a corresponding scale. Specifically, the Gaussian mechanism ensures that, after adding noise drawn from $\mathcal{N}(0,\sigma^2\mathbb{I}_d)$, the two outputs become close in distribution—making them statistically indistinguishable. This approach follows the standard principles of the Gaussian mechanism in differential privacy. In our case, Theorem 4.9 gives an upper bound on this difference, and we use it to determine a noise scale, thereby masking any deviation between the PDUDT output and the retraining output.

Response to “Theoretical Claims”: We fully understand your concern about the accuracy of the difference between the retrained and the unlearned models, as it affects the subsequent noise scale. But in fact, we cannot get the exact value because $\tilde{\theta}_i^{t_1}$ is a retrained model. Therefore, we need to approximately seek the upper bound of it through the model iteration rule. Our Theorem 4.9 provides a conservative upper bound on the difference between the retrained and the unlearned models, which ensures that the noise scale $\sigma$ selected suffices to achieve the desired level of statistical indistinguishability. While the bound might not be tight in some scenarios, this conservativeness is intentional and aligns with the standard approach in differential privacy, where upper bounds are used to ensure worst-case guarantees. We also highlight that the Gaussian mechanism is chosen due to its robustness under such uncertainty—it provides meaningful guarantees as long as the upper bound is valid.

Response to “Experimental Designs Or Analyses” ＆ “Questions For Authors (2)”: Due to limited computational resources and funding constraints, we are currently unable to simulate scenarios involving hundreds of clients. However, to show the scalability, we conducted experiments with 20 clients on a NLP task. Specifically, we evaluated PDUDT using the Yahoo! Answers dataset with the Bert-tiny model. The results can be found at: https://anonymous.4open.science/r/Unlearning-47E3, confirming that PDUDT has good scalability to larger networks and NLP task.

Response to “Other Strengths And Weaknesses”: We would like to clarify that Corollary 4.10 in our paper also applies to the early stopping variant PDUDT (ES). The key difference between them lies in their cumulative weighted gradient residual approximation ($\frac{1}{n-1}\sum\limits_{i=1}^{n-1}\sum\limits_{t=0}^{t_1-1}p_i^t \delta_i^t$ for PDUDT and $\frac{1}{n-1}\sum\limits_{i=1}^{n-1}\sum\limits_{t=0}^{t_{1,i}-1}p_i^{'t} \delta_i^t$ for PDUDT (ES)). Despite it, they both can be bounded by the same upper bound in Theorem 4.9. This is formally justified in Appendix A (Lemma A.2) and further supported by the derivations in Appendix C. We note that the current manuscript did not explicitly state that Corollary 4.10 also holds for PDUDT (ES). We have clarified this in the revised version.

If you have further confusions, we are happy to clarify them. Thank you again for your support.

We thank the Reviewer rNoR for the time and valuable feedback! We would try our best to address the comments one by one.

1. Response to “Claims And Evidence”＆ “Questions For Authors”: Thank you for your insightful feedback. As we discussed in Related Work, approximate unlearning has demonstrated sufficient effectiveness in many practical scenarios and has thus motivated further work by many researchers, such as Liu et al. (2021) and Ye et al. (2024). Therefore, in this work, we primarily employ the weighted gradient residual approximation to adjust the local model, further achieving approximate unlearning in the decentralized paradigm. Corollary 4.10 shows the unlearning performance that our algorithm can achieve, which is statistically indistinguishable from perturbed retraining. In addition to the theoretical guarantee, we experimentally verify its statistical indistinguishability and further analyze the utility and efficiency of PDUDT. We hope our answer can clarify your confusion.

2. Response to “Theoretical Claims”: Thank you for your valuable feedback. We note that Assumption 4.7 is a standard and widely adopted assumption in decentralized learning frameworks. Furthermore, many methods have been proposed to construct a doubly stochastic communication matrix, such as the Metropolis-Hastings method. However, under extremely harsh communication conditions, the use of Assumption 4.7 has certain limitations, since it may be challenging to guarantee the doubly stochastic nature of the communication matrix. We have included a discussion on this limitation in the revised version. Thank you once again for your insightful comments.

3. Response to “Experimental Designs Or Analyses”: Thank you for your insightful feedback. We hope that the following explanation of MIA design can clarify your confusion: Membership Inference Attack (MIA) is employed to determine whether the data samples of a client slated for forgetting were part of the training process. A higher MIA success rate indicates that the global model still retains considerable information about this client's training data, signifying an inadequate unlearning effect. In contrast, a success rate of 50%—equivalent to random guessing—implies that the model no longer carries exploitable traces of the client's data, thereby demonstrating effective client removal. Thank you again for your valuable comments, we have added this explanation in the revised version.

If there are any further confusions/questions, we are happy to clarify and try to address them. Thank you again and your recognition means a lot for our work.