acceptodds
Under review as a conference paper at ICLR 2027

Reconstruct Then Rectify: Information-Conserving Node Interaction Estimation for Graph Unlearning

Abstract

Graph unlearning aims to remove the influence of specified nodes or edges from a trained graph neural network (GNN). We study efficient approximate node unlearning, whose target is to reproduce the behavior of retraining without claiming a certified deletion guarantee. Existing approaches can require partial retraining, full-parameter re-estimation, or accurate influence approximation. We propose Reconstruct Then Rectify (RTR), a post-hoc framework that leaves the base GNN parameters fixed. RTR first learns initial node-interaction estimates through information-conserving reconstruction and then refines them using a range–null-space decomposition under a linear inverse constraint. The refined interactions are subtracted from retained-node embeddings. Under the stated linear-inverse assumptions, the rectification preserves the constraint and does not increase the squared estimation error. Experiments on multiple datasets and four GNN backbones show substantial runtime reductions while maintaining utility close to retraining; we further evaluate poisoned-node removal and resistance to MIA.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph Unlearning, Range--Null-space Decomposition, Interaction Learning

Reviews

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

This paper studies approximate node unlearning in GNNs while keeping the base GNN parameters fixed. The authors propose RTR, which learns node-interaction estimates through information-conserving reconstruction and uses RND to rectify the reconstructed shares during training. The estimated interactions are then subtracted from retained-node embeddings during inference. The method is evaluated across multiple datasets and GNN backbones in terms of efficiency and model ability.

Critical strengths
  1. By formulating node unlearning as embedding modification, the method avoids retraining the entire GNN. Experimental results show substantial reductions in running time while maintaining F1 scores close to those obtained by retraining from scratch. 2.The authors provide an error analysis of the RND rectification step. The ablation study in Figure 6 compares results with RND, providing empirical evidence that this step improves F1 scores.
Critical weaknesses
  1. In Section 4, the authors introduce a nonlinear residual but then leave it out of the theoretical analysis, assuming that the linear inverse constraint holds exactly. THowever, the node interactions are predicted by a network and may contain estimation errors, and the method is also applied to nonlinear GNNs. How does ignoring the nonlinear residual affect this conclusion?
  2. In Section 5, the frozen original GNN produces teacher embeddings on the pruned graph, and these embeddings are used to guide the training of the added module. How much of the performance improvement comes from the reconstruction process, and how much comes from this teacher guidance? 3.Besides the overall results, the paper could also analyze individual nodes. For the same retained node, the authors could compare its predictions before unlearning, after applying RTR, and after retraining from scratch. Showing both cases where RTR works well and cases where it performs less well would help explain the results.
Questions for authors

Please see the weakness,

Reviewer_vwcaOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes Reconstruct Then Rectify (RTR), an approximate graph node unlearning method that modifies node embeddings without updating the pretrained GNN parameters. RTR estimates the interactions between forgotten nodes and retained nodes through hidden-representation reconstruction. It then uses range null-space decomposition to refine these estimates under a linear inverse constraint. Experiments on five datasets and four GNN architectures show substantial runtime improvements and predictive utility close to retraining.

Critical strengths
  1. Efficient unlearning design. RTR freezes the pretrained GNN and modifies its output embeddings through learned node interactions. This avoids updating the original GNN parameters. The reported runtime is substantially lower than retraining across multiple datasets.

  2. Compatibility with different GNN architectures. The method is evaluated on GCN, GAT, SGC, and GIN. It does not require architecture-specific deletion operators. This makes the framework potentially applicable to different message-passing architectures.

  3. Evaluation on large-scale graphs. The experiments include ogbn-arxiv and ogbn-products. The latter contains approximately 2.45 million nodes and 61.9 million edges. RTR maintains competitive predictive utility while reducing unlearning runtime.

  4. A theoretically motivated rectification step. The range–null-space decomposition provides a non-increasing reconstruction-error bound under the stated linear inverse assumptions. The paper also includes an ablation showing that this rectification improves downstream classification performance.

Critical weaknesses
  1. The interaction subtraction does not capture multi-hop propagation. Equation (2) only subtracts contributions from forgotten nodes that are directly adjacent to retained nodes. However, deleting a node in a multi-layer GNN also changes the representations of nodes multiple hops away. For example, in a two-layer GCN, deleting node A can affect node C through the path A-B-C. RTR makes no explicit correction to C when A and C are not adjacent. Changes to graph normalization can also alter messages between retained nodes. The local distillation loss may partially mitigate these effects, but it does not establish that the missing interactions are recovered. This is a fundamental limitation of the proposed decomposition. Baselines like GNNDelete considers this in their design.

  2. The task-specific unlearning loss appears ineffective under the stated optimization. Section 5 defines an ascent loss on the forgotten nodes' final embeddings. However, the original GNN is frozen, and Equation (2) only modifies retained-node embeddings. Therefore, the forgotten nodes' embeddings do not appear to depend on the trainable interaction and reconstruction MLPs. Consequently, the gradient of the ascent loss with respect to these MLP parameters appears to be zero. If this interpretation is correct, the loss cannot contribute to unlearning. The paper should clarify the computational graph and explain how this term influences optimization.

  3. The theoretical guarantee does not establish accurate unlearning. Theorem 1 proves that range–null-space projection does not increase the reconstruction error of a source share, assuming that its ideal value satisfies the linear inverse constraint. However, this does not establish that the learned interaction is the true contribution of the forgotten node. The interaction itself is predicted by an unconstrained MLP. Moreover, the paper explicitly drops the nonlinear residual when constructing the inverse constraint. Its accuracy for nonlinear GNNs is not analyzed. The guarantee therefore concerns a conditional reconstruction problem, rather than the distance between RTR and retraining. This distinction is particularly important because inference subtracts the learned interactions directly, without applying RND to them.

  4. The evaluation does not sufficiently establish successful forgetting. The main utility metric is F1-score, but similar F1 scores do not imply that individual predictions or embeddings match retraining. The paper should measure retained-node embedding error, prediction divergence, and agreement with retraining. The privacy evaluation is also limited to a distance-threshold membership inference attack based on embedding changes. In addition, Equation (2) only modifies retained-node embeddings, which makes the construction of pre- and post-unlearning embeddings for forgotten nodes unclear. An AUC near 0.5 against this single attack is insufficient evidence of robust forgetting.

  5. The experiments do not adequately isolate the contributions of the proposed components. The primary ablation removes RND, but the method also introduces reconstruction, interaction subtraction, local distillation, and deletion-ratio reweighting. Their individual contributions are not established. In particular, the local teacher already runs the original GNN on the pruned graph. It is unclear how much of RTR's utility comes from this teacher rather than the proposed interaction estimation. Furthermore, the recent ETR baseline is substantially faster in Table 14. For GCN on CS, ETR takes 0.07 seconds, compared with 1.13 seconds for RTR, while achieving an F1 score of 92.72 versus 91.98. The claimed efficiency advantage is therefore not consistent across the strongest recent baselines.

  6. The computational evaluation contains inconsistencies and lacks a complete cost breakdown. RTR trains two three-layer MLPs, computes a pseudoinverse, and constructs teacher embeddings on the pruned graph. It is unclear whether all these operations are included in the reported unlearning runtime. This matters for repeated deletion requests, where request-specific optimization could dominate the cost. The FLOPs tables also contain numerical inconsistencies. For example, Table 9 reports 6.56e7 base FLOPs for GAT on Cora and 5.02e8 FLOPs for RTR, yet labels the overhead as only 0.06%. Similar inconsistencies occur in Tables 10 and 11. These values should be corrected before the computational claims can be fully assessed.

Questions for authors

Can you clarify the gradient path of the task-specific ascent loss and provide an ablation that separately removes this loss, the local teacher, and reconstruction? It would also be useful to report the complete per-request runtime, including teacher inference and MLP optimization.

Reviewer_e5SGOpenReview ↗
Rating
2(+1)
Confidence
4
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper proposes RTR, a post-hoc method for approximate node unlearning in GNNs. It keeps the trained GNN frozen and uses two small MLPs to estimate and remove the contributions of forgotten nodes from their retained neighbours. It also reconstructs the forgotten nodes' representations using a range-null space decomposition (RND) step.

The paper provides theoretical results for this projection step and evaluates RTR on five datasets with four GNN backbones. The experiments cover F1, runtime, label-noise removal, membership inference, FLOPs and an ablation of RND. The method is fast and easy to deploy. However, I have concerns about the theoretical claims and the experimental evaluation.

Critical strengths
  1. The paper addresses an important problem and proposes a practical approach to reduce the computational cost of graph unlearning. The method avoids retraining the base GNN and achieves substantial runtime savings.

  2. The paper evaluates the method across five datasets and four GNN backbones. It also studies label-noise removal, membership inference, computational cost, and the effect of RND through ablation experiments.

Critical weaknesses
  1. According to the GDPR law, right to be forgotten, (https://gdpr-info.eu/art-17-gdpr/) which has been the prime reason for boom of unlearning works, one should remove "any links to, or copy or replication of, those personal data".

RTR keeps the trained GNN parameters fixed and subtracts estimated interactions from retained-node embeddings at inference. This changes the model's outputs without changing the parameters that were learned from the forgotten data. The paper therefore demonstrates inference-time correction, but does not establish that the forgotten nodes' influence has been removed from the trained model.

Hence keeping the original GNN frozen does not achieve unlearning.

  1. The theory does not cover the method that is actually deployed, and the proof of Lemma 1 is circular.

(a) The proof in Sec. 4 writes HsRND=HH†Hs+(H−HH†H)s=Hs=cHs^{RND} = HH^\dagger Hs + (H - HH^\dagger H)s = Hs = c. This assumes that the preliminary share already satisfies the constraint. If so, H†c=H†HsH^\dagger c = H^\dagger Hs and sRND=ss^{RND} = s. RND would do nothing. The correct computation is HsRND=HH†cHs^{RND} = HH^\dagger c. This equals cc only if c∈range(H)c \in \mathrm{range}(H), for example, when HH has full row rank. The lemma may hold under this assumption, but the paper does not state it or prove the lemma correctly.

(b) Theorem 1 is the non-expansiveness of the orthogonal projector I−H†HI - H^\dagger H. This is a standard result. The same range-null space decomposition is used in DDNM (Wang, Yu, Zhang, ICLR 2023) and null-space networks (Schwab, Antholzer, Haltmeier, Inverse Problems 2019). Neither paper is cited. Also, s∗s^* can be any vector that satisfies c=Hs∗c = Hs^*. The paper does not show how this vector relates to the model obtained by retraining without UU. So the bound does not say anything about unlearning quality.

(c) More importantly, Sec. 4 says that RND is applied only to the reconstructed shares during training, while inference subtracts the unrectified cj→ic_{j\to i} (Eq. 2). Theorem 1 therefore bounds the error of ss, which is not used at inference. It does not bound the error of h~i\tilde h_i, which is the output that matters. Fig. 6 is the only evidence that RND helps the deployed output. It covers two small datasets at 30% deletion, with a gap of about 1–2 F1 points and no variance reported.

So the claims that RND “provides a tighter bound with smaller L2 rectification error” (Introduction) and that the estimate “has an absolutely lower error” (Conclusion) are not supported by the theory or experiments. I am not saying these claims are false. The paper does not show that they hold for the output that matters. This drives my rating because the theory is presented as the main technical contribution.

  1. Comparison with important baselines is missing: D2DGN (TNNLS 2025) [1]. Sinha, Y., Mandal, M., and Kankanhalli, M. “Distill to Delete: Unlearning in Graph Networks With Knowledge Distillation.” IEEE Transactions on Neural Networks and Learning Systems, 2025. DOI: 10.1109/TNNLS.2025.3607995. 21
Questions for authors
  1. The method keeps the base GNN parameters fixed. How does this approach achieve the stated unlearning objective, given that the original parameters remain unchanged?

  2. For Lemma 1, do you assume HH has full row rank, so that HH†=IHH^\dagger = I? If not, how is c∈range(H)c \in \mathrm{range}(H) ensured? Since inference subtracts the unrectified cc (Eq. 2), can you give any bound or measurement of the error of h~i\tilde h_i itself, for example ∥h~i−hiretrain∥\|\tilde h_i - h_i^{retrain}\| with and without RND, with variance and on more datasets than Fig. 6? Also, ss targets the fused average H∗H^*, while H=WkH = W_k maps only the last hidden layer. How are the dimensions and semantics reconciled?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.