acceptodds
Under review as a conference paper at ICLR 2027

Efficient Partition-Localized Unlearning for Graph Transformers

Abstract

Graph unlearning aims to reduce the influence of designated training nodes from a deployed graph model without retraining from scratch. Most existing approaches are developed for message-passing GNNs, where forgetting is often realized by editing local neighborhoods or fine-tuning on affected neighbors. A Graph Transformer instead relies on shared attention over tokens, so those neighborhood-based deletion recipes do not directly carry over to its computation. We propose PLU-GT, a partition-localized unlearning method for a shared Graph Transformer. The method identifies patches touched by a forget request, remaps forgotten nodes to virtual nodes to block their participation in intra-patch attention, and optimizes a localized objective that combines affected-region supervision, replay, entropy maximization, and cloak regularization. Experiments on four real-world graphs show that PLU-GT provides a favorable utility–efficiency trade-off under a unified unlearning protocol. It remains competitive with full retraining in predictive utility while achieving several-fold speedups, and substantially reduces posterior-based membership leakage under the specified attacker.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph unlearning, graph transformer, efficiency

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_ay6ROpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

PLU-GT handles node-unlearning requests in a partitioned Graph Transformer with shared parameters by locating affected patches, remapping forgotten nodes to virtual nodes, and updating the model with retain supervision, replay, entropy maximization, and cloak regularization. Structural edits are used during optimization, while the main accuracy and membership-inference results are evaluated on the original graph. Experiments on four datasets report faster updates than full retraining, similar accuracy on Cora and Coauthor-CS, and reduced separability under the chosen posterior membership attack.

Critical strengths

1.Remapping forgotten nodes to existing virtual padding positions directly blocks their participation in intra-patch attention during optimization, with a simple design that avoids maintaining a separate model for each partition. 2.In Table 4, PLU-GT trails retraining by only 0.68 and 0.04 percentage points on Cora and Coauthor-CS while reducing runtime from 16.4 and 24.7 seconds to 2.1 and 3.3 seconds, showing a useful efficiency gain on these datasets.

Critical weaknesses

1.Forgetting is assessed mainly through a fixed posterior membership attack, but entropy and cloak directly reshape those posteriors, so near-chance AUC does not distinguish removal of training influence from failure of this particular attacker. 2.Appendix D replaces GraphEraser's separate shard models with local fine-tuning of a shared model and retains only FairGU's FIM-damping stage, removing important components without establishing the strength of the resulting baselines.

Questions for authors

1.Does the near-chance membership result persist when the attacker is retrained for the unlearned model, and how closely do PLU-GT's predictions on forgotten nodes match those of retraining? 2.Under the same initialization, epochs, and loss settings, how do affected-patch and full-retain-set supervision compare in accuracy and runtime, and what fraction of patches is actually affected? 3.With the full loss unchanged, how do accuracy and membership-inference results change when virtual-node remapping is disabled, evaluated separately on the original and edited graphs? 4.Table A.5 describes GraphEraser much like the CE-only ablation, yet their Cora accuracies are 62.86% and 58.02%, so which optimizer or implementation settings account for this difference?

Reviewer_GrThOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The paper proposes PLU-GT, an approximate graph-unlearning method for a shared, partition-based Graph Transformer. Given a set of training nodes to forget, PLU-GT identifies the affected patches, remaps the forgotten nodes to virtual nodes to block their participation in intra-patch attention, and fine-tunes the model using a combination of affected-region training, replay on retained nodes, entropy maximization, and a cloak regularizer on forgotten-node predictions. The authors evaluate the method on four graph datasets against retraining and adapted unlearning baselines, reporting predictive accuracy, unlearning time, and posterior-based membership-inference AUC. Their results suggest that PLU-GT can preserve utility while reducing update time and lowering AUC under the specified attacker.

Critical strengths

Critical Strengths

  1. The paper addresses a practical challenge specific to Graph Transformers. Forgotten nodes can remain visible through patch-level attention even after their labels are removed. PLU-GT’s virtual-node remapping directly targets this pathway, making the problem formulation relevant to partition-based Transformer models.

  2. The evaluation reports both predictive utility and unlearning time across four datasets. The results suggest that PLU-GT can retain competitive accuracy while reducing the cost of updating the model compared with full retraining. This provides useful empirical evidence for the efficiency–utility trade-off, although it does not by itself establish that the method fully removes the forgotten nodes’ influence.

Critical weaknesses

Critical Weaknesses

  1. The paper does not establish a principled connection between its optimization objective and actual unlearning. PLU-GT combines losses on retained nodes with entropy and cloak regularizers on forgotten-node predictions, but provides no theoretical guarantee or analysis showing that optimizing this objective removes the forgotten nodes’ influence or approximates retraining on the retain set. The reported results under a fixed membership-inference attacker do not resolve this gap, so it remains unclear whether the method achieves unlearning or mainly changes the forgotten nodes’ output predictions.

  2. The motivation for the cloak reference distribution is unclear. The method constructs qq by averaging logits from sampled retained nodes and minimizes KL(q∥pv)\mathrm{KL}(q\|p_v) for each forgotten node. The paper does not explain why this particular distribution represents the appropriate post-unlearning prediction, or show that matching forgotten-node predictions to it reduces their influence on the model. Without such justification or supporting analysis, the cloak term appears heuristic.

  3. The contribution appears incremental, and the empirical comparisons do not fully establish its advantage. PLU-GT applies partition-localized, SISA-style ideas to a Graph Transformer, but the paper does not clearly distinguish its conceptual contribution from this adaptation. Moreover, some baselines are substantially modified for the shared Transformer setting, making it difficult to determine whether the reported gains reflect PLU-GT’s design or differences in the adaptations. The presentation also needs clearer motivation for the method’s components and their connection to the claimed unlearning goal.

Questions for authors

Questions For Authors

  1. Clarification: What is the formal unlearning objective that PLU-GT is intended to approximate? Can the authors provide a theoretical argument or analysis connecting their training objective to reduced influence of the forget set or to retraining on the retain set?

  2. Clarification: Why is the cloak reference distribution qq, computed by averaging logits from sampled retained nodes, an appropriate target for forgotten-node predictions? What evidence shows that matching pvp_v to this qq reduces forgotten-node influence, rather than merely changing the outputs used by the membership-inference attack?

  3. Evidence affecting the recommendation: Can the authors compare PLU-GT with faithful implementations of the relevant partition-based and unlearning baselines, and isolate the gains from virtual-node remapping, replay, entropy maximization, and the cloak term under a matched protocol?

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

The paper proposes PLU-GT, a partition-localized method for node unlearning in Graph Transformers. It identifies patches affected by forgotten nodes, remaps those nodes to virtual tokens to prevent their participation in intra-patch attention, and updates the model using affected-region supervision, replay, and forget-side regularization. Experiments on four graph datasets compare predictive accuracy, membership-inference exposure, and unlearning efficiency with adapted baselines and retraining.

Critical strengths
  1. The paper addresses a relevant gap between graph unlearning for message-passing GNNs and partition-based Graph Transformers. The localized editing mechanism is reasonably motivated by the underlying attention structure, making the proposed approach technically coherent.
  2. The experiments consider utility, membership-inference behavior, and computation cost rather than accuracy alone. This is useful because an unlearning method must retain performance while reducing the influence of forgotten data.
Critical weaknesses
  1. The main evaluation is conducted on the original graph, although structural edits are applied during unlearning optimization (Section 4.2 and Appendix B). This protocol is described, but it remains unclear how closely the reported results reflect a deployment scenario in which the requested node deletion also changes the inference graph. This limits the practical interpretation of the unlearning claim.
  2. The privacy evidence is based mainly on a posterior-based membership-inference attack (Table 3). Performance against this particular attacker does not by itself establish that forgotten-node information is robustly removed. This slightly weakens the evidence supporting the effectiveness of forgetting.
Questions for authors
  1. Could the authors clarify which deployment setting motivates evaluating the updated model on the original graph, and how conclusions change under the edited-graph evaluation reported in Appendix B?
  2. Do the authors have evidence from an alternative membership-inference attack or a comparable forgetting diagnostic that supports the same conclusion?

Comments on the paper

1 comment

Dear Reviewers,

The authors have now responded to the questions and concerns raised by everyone. Could I kindly ask you to review the authors' responses, take a look at the comments from the other reviewers, and actively participate in the discussion?

Thank you all very much for your valuable time and contributions!

Best regards,

The AC

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.