acceptodds
Under review as a conference paper at ICLR 2027

Closed-Form Node Classification with Exact Graph Unlearning

Abstract

Graph neural networks for node classification are typically trained by gradient descent over hundreds or thousands of epochs. Recent work shows that carefully tuned classic GCN, GraphSAGE and GAT architectures can rival graph transformers. We ask a complementary question: can closed-form solvers recover this predictive strength and make exact graph unlearning practical? One validation-selected protocol combines multiscale diffusion, nonlinear graph kernels and training-label context with analytical readouts. Across generic and task-aware tracks, **closed-form predictors exceed or come within one point** of the strongest reproduced tuned GNN on all 16 reported benchmarks. The generic protocol achieves this on 14/16, including both OGB graphs; task-aware constructions surpass the remaining two references, setting a new Minesweeper state of the art at 99.95 ROC-AUC with an 11 ms clue-based CPU fit, and reaching 91.60 accuracy on Roman-empire. The generic protocol also exceeds cited retuned GraphGPS and SGFormer means on 14/15 and 12/15 comparisons. We derive exact graph-unlearning procedures that recover the result of retraining the same model from scratch after deleting labels, features, edges, nodes or subgraphs. They reuse unaffected information and recompute only what changes. Across 280 deterministic verification cases, 232 match retrained prediction scores exactly; 43 double-precision label updates differ by less than , and five Questions updates preserve every predicted class against the single-precision reference. Timed in default GPU mode, cached one-label model updates are a **median 93× faster** than tuned-GNN training steps alone across fifteen same-hardware comparisons, with speedups up to approximately 20,000×. Closed-form fitting therefore supports both strong node prediction and exact, verifiable unlearning.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph neural networks, node classification, graph unlearning, closed-form learning, graph representation learning

Reviews

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

The manuscript studies whether closed-form graph predictors can achieve competitive node classification performance while enabling exact graph unlearning. To this end, the proposed framework combines diffusion features, nonlinear graph kernels, and optional label context with analytical ridge (or kernel ridge) readouts. Two task-aware constructions are developed for Minesweeper and Roman-empire. Also, the explicit computational structure enables unlearning through cached analytical downdates when representations remain unchanged and recomputation of affected stages otherwise. Experiments demonstrate the competitive prediction accuracy against tuned GNNs and substantial reductions in cached deletion latency.

Critical strengths
  1. The reviewer thinks that the empirical evaluation addresses a useful question and covers varied graph benchmarks against tuned GNN baselines.

  2. The implementation tracks label-dependent computations and includes numerical checks against retraining on retained data, as well as tests for residual dependence on deleted labels. The evaluation protocol and computational costs are documented in detail.

  3. Same model comparisons demonstrate computational savings. ACR also effectively exploits the supplied Minesweeper clue semantics.

Critical weaknesses
  1. Niu et al. (2023) already develop nonlinear graph covariance kernels with analytical prediction and scalable approximations, while GraphEditor studies exact updates of graph ridge predictors. Proposition 1 and Eq. (5) rely on dependency-aware recomputation and classical block inversion. For these reasons, the reviewer thinks that the contribution rests heavily on the benefits of the proposed integration. However, the internal GCN control is not an official GNNGP reproduction and existing comparisons jointly vary architecture, preprocessing, and selection. Matched predecessor comparisons would better establish the incremental contributions.

  2. The reported speedups over retraining the same model seem to be meaningful. However, generic updates keep the selected configuration fixed, while task-aware updates repeat model selection. Consequently, the reported updates do not account for the cost of rerunning the complete validation selected procedure. This distinction also may affect the interpretation of predictive performance and deletion latency. For example, on Roman-empire, the generic model achieves 84.2% accuracy with a 2.32 second update, while TLCF achieves 91.6% but takes 214-215 seconds including selection. These timings seem to be not comparable since the models and selection procedures differ. It would be nice if there exists a joint comparison of accuracy, setup cost, and deletion latency for each predictor, including the cost of replaying generic model selection.

  3. SGC (Wu et al. 2019) already uses fixed graph propagation followed by logistic regression. Efficient Learning of Linear Graph Neural Networks via Node Subsampling (Shin et al., 2023) studies leverage score subsampling for linear graph regression, and Coresets for Classification- Simplified and Strengthened (Mai et al. 2021) studies Lewis-weight coresets for classifcation losses, including logistic loss. These works motivate comparing ridge and regularized logistic readouts on the same graph representations, with comaprable hyperparameter tuning. Coreset-based logistic training could provide an additioanl scalability comparison. Although the manuscript includes historical SGC+Ridge+C&S controls, these do not compare readouts within the current pipeline. Holding graph representations and their reuse fixed would show how the readout choice affets test performance and fitting time. Also, considering representation construction costs separately would further distinguish improvements due to graph representations from those due to analytical fitting.

Questions for authors
  1. How does the method compare with GNNGP and, where applicable, GraphEditor on the same splits and with comparable tuning budgets? On the same graph representations, how do ridge and logistic readouts compare in test performance and fitting time?

  2. If model selection is repeated after deletion, does the generic model produce the same prediction scores as retraining from scratch on the remaining data? How long does the full update take when both runs use the same precision and execution settings?

  3. Was the final frozen generic method tested on any benchmarks that were not used during development?

4 comments
AuthorsOpenReview ↗

Response to DjZq (1/3): contribution and author-implementation GNNGP

Thank you for the precise related-work pointers and request for matched controls experiments. The contribution couples competitive analytical prediction with verifiable maintenance of the full selected predictor. GNNGP's covariance construction and GraphEditor's graph-ridge updates are important foundations; Proposition 1 specifies the retained-data target and Eq. (5) uses classical block inversion. The evidence below measures what the complete prediction procedure adds. Parts 2 and 3 address readouts, reselection cost and additional graphs.

Q1: comparison with the authors' GNNGP implementation

Our generic procedure has higher observed means on 12/13 primary-suite graphs under both the initial and expanded GNNGP searches. With the expanded search, its margins include 5.1 points on Roman-empire, 2.4 on Minesweeper, 2.3 on Squirrel and 2.0 on Tolokers. No task-aware ACR/TLCF score is substituted.

Both procedures use the same source graph, features and masks. We use the authors' kernel and posterior-prediction code. The initial search covers GCN/GCN2/GIN/SAGE, depths 1–4, two bias/ego-coefficient settings and the authors' 101-value nugget grid. The expanded search retains those 32 configurations, adds depths 6/8 for every family, and adds equal ego/neighbour coefficients for SAGE at depths 1, 2, 3, 4, 6 and 8: 54 configurations. Both searches select on validation; our procedure is unchanged.

DatasetGNNGP initialGNNGP expandedOur label-free coreOur full generic procedure
Cora83.9083.9084.0084.50
CiteSeer72.7072.7071.8073.00
PubMed79.1078.4081.4081.40
Photo94.1895.8296.5496.54
Computer92.2993.2093.3894.00
CS95.6795.6796.0796.07
Physics97.2897.3596.8096.68
WikiCS80.5080.8580.8980.89
Ratings52.3354.8856.3156.31
Roman-empire75.0879.1080.9484.20
Minesweeper89.8790.5690.7592.92
Tolokers82.2983.5484.9885.52
Squirrel40.6141.3742.5643.65

Scores are accuracy except Minesweeper/Tolokers (ROC-AUC). Means use three primary masks for WikiCS, Ratings, Roman-empire, Minesweeper and Tolokers; ten for Squirrel; one otherwise. These are higher-mean counts, not significance verdicts: WikiCS differs by only 0.04 points and Physics favors expanded GNNGP by 0.67. The label-free core itself has higher means on 11/13, so the gains do not depend solely on label context.

Both grid columns remain visible; we do not choose between them by test performance. PubMed's expanded winner, for example, improves validation from 80.40 to 80.80 but scores lower on test. This compares complete procedures under stated searches, not equal compute or an isolated depth effect.

For numerical validity, we apply the analytic zero-variance ReLU limit on graphs where zero feature rows otherwise cause 0/0 and exclude GCN2: CiteSeer, WikiCS, Roman-empire and Squirrel. It matches upstream arithmetic on positive-variance inputs in the bitwise self-check and rejects invalid variances. The initial grid uses this rule on affected graphs and raw upstream code otherwise; the expanded grid uses it throughout. All 54 configurations are valid on every split. Raw runs are preserved.

Paired ten-split check

The initial 32-configuration grid was also evaluated on the ten-split prediction-study scheme (zero-variance correction on CiteSeer):

DatasetOur generic procedure − GNNGP [95% paired CI]
Cora+0.35 [−0.54, 1.24]
CiteSeer0.00 [−0.66, 0.66]
PubMed+2.29 [0.69, 3.89]
Photo+1.33 [0.99, 1.68]
Computer+1.24 [0.90, 1.58]
CS+0.26 [0.04, 0.49]
Physics−0.29 [−0.41, −0.17]

Exploratory two-sided paired tests with Holm correction over all seven support positive differences on PubMed, Photo and Computer, and a negative difference on Physics. The intervals are pointwise; these are not paired tests of the expanded grid. Questions was attempted but the dense GNNGP run exhausted the 48 GB GPU; no score is reported. Arxiv/proteins are outside this control.

Beyond linear graph ridge

Submitted Appendix J, Table 12 independently selects within the linear diffusion/ridge restriction and the full label-free pool. The latter gains 1.2/13.3/29.3/16.5/10.6 points on WikiCS/Ratings/Roman-empire/Minesweeper/Tolokers. This is an internal restriction control, not a GraphEditor software reproduction. Part 3 then verifies maintenance of the complete label-dependent and selection-dependent predictor through 400 deletions.

AuthorsOpenReview ↗

Response to DjZq (2/3): matched ridge/logistic readouts

Ridge versus logistic on identical representations

On identical feature maps, dataset-mean scores differ by at most 1.3 points across thirteen graphs; ridge's grid fitting plus prediction is a median 10.4x faster. Ridge is faster on twelve of the thirteen graphs; Physics is the exception. Shared representation construction is reported separately below; the ratio is not an end-to-end claim.

For each split we freeze the submitted label-free representation and vary only the readout. Both primary heads omit the intercept, use the same 15-value regularization grid and select by validation. Logistic uses fp64 L-BFGS with a final-gradient convergence check; all primary candidates converge to the declared tolerance. Kernels are mapped to the same explicit feature matrix for both heads. Because the representation was originally selected with ridge, this is a conditional readout ablation, not an independently retuned logistic pipeline.

DatasetRidgeLogisticShared map build (s)Ridge grid fit+predict (s)Logistic grid fit+predict (s)
Cora83.7083.700.100.0120.44
CiteSeer72.8073.400.170.0180.29
PubMed81.4082.300.200.0130.27
Photo96.5495.820.961.663.93
Computer93.3892.153.827.9822.54
CS96.0796.2610.1018.0119.10
Physics96.8096.9933.30113.0177.54
WikiCS80.8980.230.970.0601.48
Ratings56.1455.918.5724.28135.97
Roman-empire80.9481.545.5519.9753.38
Minesweeper90.7591.580.842.0626.68
Tolokers84.9885.093.033.1532.60
Squirrel43.0743.050.190.1052.57

Scores are accuracy except Minesweeper/Tolokers (ROC-AUC). Means use three primary splits for WikiCS, Ratings, Roman-empire, Minesweeper and Tolokers; ten for Squirrel; one otherwise. Shared map build includes kernel-to-feature conversion where needed. Both synchronized head windows include all grid fits and all-node predictions; metric evaluation is outside both. Logistic/ridge head-time ratios range from 0.69x to 37.48x on the same GPU: Physics takes 113.01 s for ridge versus 77.54 s for logistic. Direct KRR in the original pipeline does not require this extra conversion to make the control identical-map.

After the initial Physics feature-map factorization failed, its float32-kernel conversion used diagonal stabilization of 10−610^{-6} times the mean diagonal, versus 10−1010^{-10} for float64 kernels. Both heads use the same stabilized map; its ridge scores differ from the original KRR by at most 5.5×10−45.5\times10^{-4}, with the selected test accuracy unchanged. The other twelve completed records are unchanged.

We also tested an unpenalized intercept for both heads. The qualitative result persists; four logistic penalty fits in that sensitivity analysis did not converge within the evaluation budget and were excluded, with exclusions retained in the record. None affects the no-intercept primary comparison. Arxiv's logistic run exceeded the rebuttal time budget and is excluded from the thirteen-graph summary. We have not run a coreset baseline; this control uses the full training set.

The practical distinction is therefore both computational and operational. Ridge retains performance close to the logistic readout on these maps and also supports the paper's analytical, retrain-equivalent label-deletion update when the representation and configuration are fixed. For the logistic control used here, reproducing the retained-data fit requires iterative re-optimization rather than that analytical update. This is a statement about the evaluated control, not a claim that logistic models cannot be exactly unlearned by other mechanisms.

The paper's full prediction numbers belong to the complete validation-selected procedure, not this restricted ablation. Part 3 evaluates what happens when deletion also changes that selection.

AuthorsOpenReview ↗

Response to DjZq (3/3): reselection cost and frozen evaluation

Q2: the full retained-data predictor, including reselection

Yes. Replaying generic selection reproduces fresh retained-data prediction scores bit for bit in all 400 checks. Across 100 sequential label deletions each on WikiCS, Minesweeper, Photo and Tolokers, selection changes 20, 6, 16 and 10 times. Every candidate validation score, selected configuration and all-node prediction-score array agrees with the independent cold run. Deleted-label poisoning checks that removed values are not consulted. All label-dependent construction and selection is recomputed; only unaffected objects are reused.

A separate acceleration uses shared spectral factors, small-system corrections and direct-solve fallbacks. It preserves all selections; full-output replay at requests 1/10/50/100 has score differences below 7×10−107\times10^{-10} and unchanged classes. This is numerical rather than bitwise agreement. Tolokers uses a disclosed post-hoc integer-AUC rule for floating differences of at most 2.84×10−142.84\times10^{-14} points; the 400 canonical bit-identical checks do not use that relaxation.

Here is the joint comparison for the actual split-0 generic predictors in the isolated-device benchmark. Initial scores belong to these timed predictors, not ACR/TLCF or multi-split averages. Setup includes the full fit, cache and spectral factorization; requests rerun selection.

DatasetInitial test score (%)Setup (s)Median request (s)Fresh full-selection initial fit (s)
WikiCS, accuracy81.4441.92.1240.9
Minesweeper, ROC-AUC92.6577.55.1127.8
Photo, accuracy96.5476.85.2538.8
Tolokers, ROC-AUC84.93176.65.1598.9

Both closed-form paths use the same precision/backend policy; setup is charged and audit replay is outside the timed fast path. Device isolation is monitored throughout; host CPU/RAM are shared. Setup plus 100 Minesweeper requests costs 588.9 s versus 2,734.8 s for fresh closed-form selection: a fully measured 4.64x saving. Checkpoint-interpolated savings against fresh selection are 16.2x on WikiCS, 6.3x on Photo and 14.4x on Tolokers, using three repeated fits at checkpoints 0/1/25/50/75/100.

The fixed-recipe GNN comparison is secondary: Minesweeper costs 1,407.9 s for the full GNN sequence, whereas Photo's GNN is cheaper through 100 requests. We will present fixed-configuration and full-selection costs separately, without pairing TLCF's score with the generic predictor's update time. The 400 full-selection checks concern training-label deletion, not generic structural reselection.

Q3: frozen evaluation on additional graphs

We froze the generic procedure before closed-form evaluation on Actor, DBLP, BlogCatalog, LastFM-Asia, Deezer-Europe, GitHub and Flickr. Both methods use the same source graph, features and masks. The GNN reference is selected on validation from 36 configurations across GCN/SAGE/GAT—a bounded search, not an exhaustive search of all Luo et al. settings.

DatasetCommon splitsClosed form − GNN [95% paired CI]
Actor5−3.21 [−4.94, −1.48]
DBLP5+0.39 [−0.09, 0.87]
BlogCatalog5+0.22 [−0.16, 0.59]
LastFM-Asia5+0.62 [−0.07, 1.31]
Deezer-Europe3−0.43 [−1.30, 0.43]
GitHub3+0.18 [−0.24, 0.61]
Flickr1−0.74, descriptive

Intervals are pointwise; hypothesis tests use Holm correction across all seven graphs. DBLP, BlogCatalog, LastFM-Asia and GitHub establish one-point non-inferiority; BlogCatalog/GitHub also establish equivalence. Actor remains a gap and Deezer is inconclusive. Additional initialization seeds preserve these conclusions. Earlier GNN resource pilots were seen, so these graphs are new to closed-form evaluation, not wholly unseen by the researchers. Every graph in the frozen evaluation is reported.

The requested controls show higher observed means than the authors' GNNGP on 12/13 graphs under both searches; on identical maps, ridge is within 1.3 points of logistic at a median 10.4x lower head cost. Together with 400 bit-identical full-reselection checks and setup-inclusive cost measurements, this makes the integrated prediction-and-unlearning contribution concrete. We hope these results answer your questions about value beyond existing closed-form components, and we would be grateful if you would reconsider the score.

Reviewer_DjZqOpenReview ↗

Response to the Authors' Rebuttal

I appreciate the authors' detailed response and additional experiments, which address several of my empirical concerns. However, I remain unconvinced that the proposed framework offers sufficiently clear methodological advance over existing approaches. Therefore, I will keep my original score.

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

This paper makes two contributions. First, it performs node classification via a closed-form approach that constructs graph representations and then solves a system of linear equations, without gradient-based training. Second, leveraging this linear structure, it enables exact retraining after data deletion through matrix updates that complete within milliseconds. This is a very interesting work.

Critical strengths

The combination of closed-form classification and exact forgetting is natural and functionally viable. The mathematical formulation for forgetting is correct, with thorough validation and clearly stated boundaries (no differential privacy guarantees, no cache invalidation, no robustness to online distribution shift). The paper is exceptionally candid: it acknowledges that test results were inspected during development, that some extensions were motivated by initial test outcomes, and the AI statement properly documents LLM assistance in implementation and experiment execution.

Critical weaknesses

The paper adopts “outperforming, or underperforming by no more than 1 point” as its success criterion. However, an asymmetric threshold is applied for positive gains: +0.14 counts as “outperforming”, while −0.04 counts as “on par”. The shaded region in Figure 3 marks a ±1-point range, yet the text uses a zero threshold for positive improvements, creating an inconsistency. Using the symmetric ±1-point criterion shown in Figure 3, the results would yield 2 true wins, 12 ties, and 2 cases only improved by task-specific models, rather than “7 wins”.

The 99.95 accuracy on Minesweeper essentially comes from a puzzle solver. Given exact neighborhood mine counts as clues, ACR directly solves this as a linear system; this is not learned. Comparing it against general-purpose GNNs such as CSNN and GraphTARIF as SOTA is an unfair cross-task comparison.

For the strongest published baselines, both OGB datasets show gaps exceeding 1 point:

  • arxiv: closed-form 72.22 vs strongest published 73.53, gap −1.31
  • proteins: closed-form 85.73 vs strongest published (edge-aware GAT) 87.82, gap −2.09 Coupled with the two issues above and the lack of open-source code, I find it difficult to assess the reported experimental results.
Questions for authors

The weaknesses should be answered.

3 comments
AuthorsOpenReview ↗

Response to utmr (1/2): performance criterion and paired evidence

Thank you for the careful reading of our performance criterion and the published references. Competitive prediction without gradient training has paired statistical support: all seven ten-split comparisons establish one-point non-inferiority, with superiority on CiteSeer and PubMed. We distinguish the descriptive criterion from this stronger evidence here, and address task-aware results and published comparisons in Part 2.

The criterion and the higher-mean count are different statements

The primary descriptive criterion is one-sided: a closed-form score at least as high as the reference minus one point. It applies to every row. Figure 3's caption distinguishes the ±1 band in the parity panel from the at-least-−1 region in the difference panel. “Seven” separately counts higher observed means; it does not establish seven statistically significant wins.

We will use “higher mean” for those entries and distinguish that count from the within-one-point-or-better criterion. Under the symmetric ±1 grouping you suggest, the same generic table has two gains above one point, twelve differences within one point and two losses beyond it. Both descriptions can be computed from the table; the important scientific question is whether competitive prediction without gradient training holds beyond small single-split differences.

Paired evidence answers that question directly

We evaluated ten splits on each of seven previously single-split datasets, with three seeds for each GCN/SAGE/GAT recipe: 630 GNN fits. Within each split, the reference architecture is chosen by mean validation performance and its test score is averaged over seeds. Splits—not individual nodes or pooled initialization runs—are the independent units.

DatasetClosed form − GNN [95% paired CI]Holm-corrected conclusion
Cora+0.42 [−0.57, 1.41]Non-inferior
CiteSeer+1.20 [0.49, 1.91]Superior
PubMed+1.33 [0.60, 2.06]Superior
Photo−0.07 [−0.36, 0.21]Equivalent within ±1
Computer+0.14 [−0.04, 0.32]Equivalent within ±1
CS−0.23 [−0.45, −0.01]Equivalent within ±1
Physics−0.30 [−0.46, −0.15]Equivalent within ±1

Intervals are pointwise paired 95% CIs. The superiority, non-inferiority and TOST equivalence tests use pre-specified one-point margins where applicable and Holm correction across all seven datasets in each test family. All seven pass non-inferiority. Equivalence means performance lies within the stated margin, not identical performance: CS and Physics have small negative paired means.

CiteSeer and PubMed were both within the original table's ±1 band; the new paired experiments establish superiority. Conversely, Cora's positive mean does not establish superiority. This is precisely why we separate descriptive differences from inference. The strengthened claim is that analytical fitting remains competitive across all seven paired comparisons, with two supported improvements and not that a +0.14 point estimate alone proves a win.

AuthorsOpenReview ↗

Response to utmr (2/2): task-aware results and published references

ACR: the supplied information, with an explicit task-specific inductive bias

The submission already separates ACR from the generic predictor: §3.4 defines the task-aware track and Table 1 has a separate “Task” column. ACR uses the benchmark's supplied graph, clue features, training labels and evaluation splits—not external clues or test labels. Training mine labels enter its fitted constraints and prior; regularization and handling of censored clues are selected on validation. The reported 99.95 is ROC-AUC, not accuracy.

The distinction is a task-specific inductive bias, not a different prediction task. ACR explicitly interprets the supplied features as clue counts, whereas a general-purpose GNN must learn how to use them. Its scientific value is that near-perfect performance on this benchmark is attainable by a small supervised analytical construction. We will make those assumptions explicit and state the headline as a task-aware benchmark result, not an unqualified SOTA claim. Neither its score nor its solve cost is used as the generic predictor's result.

Local reproductions and stronger published OGB references

The published comparisons you quote are correct. Our descriptive within-one-point result uses the named local reproductions, not the stronger published references:

DatasetGeneric closed formLocal GNN referencePublished GNN reference
ogbn-arxiv72.2272.9373.53, GCN
ogbn-proteins85.7383.7887.82, edge-aware GAT

We will display both reference sets beside the headline and state its scope explicitly: the within-one-point count is relative to local reruns, not the best published GNNs. The generic count is 14/16 reported graphs.

The closed-form predictor also compares strongly with the retuned graph transformers. On proteins, 85.73 exceeds Luo et al.'s retuned GraphGPS, SGFormer and Polynormer means of 77.15, 79.92 and 79.53. Across the submitted comparisons, the generic procedure has higher means than those retuned GraphGPS and SGFormer entries on 14/15 and 12/15 graphs. Together with Part 1's paired results, this supports competitive prediction without gradient training; it does not require claiming to outperform every published architecture.

The clarified criterion and reference protocols make the prediction claim precise: all seven paired comparisons establish non-inferiority, with superiority on CiteSeer and PubMed. With the task-aware result kept separate, we respectfully ask you to reconsider your assessment and score in light of this evidence.

Thank you for your response and the revision of the paper. However, at present, the innovation and clarity of the paper are still insufficient. We are concerned about whether this paper can reach the level of ICLR. I will maintain my original score.

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

The paper asks whether node classifiers fitted in closed form, i.e. regularized linear or kernel solves, can match classic GNNs, and whether this makes exact graph unlearning practical. A generic protocol, selected on validation data, combines multiscale diffusion features, nonlinear graph kernels and context built from training labels, followed by ridge or kernel ridge readouts. Two variants tailored to Minesweeper (ACR) and Roman-empire (TLCF) are reported as a separate track. On 16 benchmarks, these predictors are reported to exceed or come within one point of the best locally reproduced tuned GCN, SAGE or GAT. For unlearning, the paper defines a target equal to retraining on the remaining data, proves that recomputing every affected quantity reaches it, and uses a block inverse update for fixed kernels. Exactness is checked on 280 deletion cases covering labels, features, edges, nodes and subgraphs, and cached label updates are reported to be much faster than training the tuned GNNs.

Critical strengths
  1. Careful and falsifiable verification of exact unlearning. The deletion checks cover five types of edit and compare scores on all nodes against a fresh rebuild. For label recomputations, deleted labels are also overwritten with incorrect values to confirm they are no longer read. This is credible evidence that the updates are equivalent to retraining, which is the paper's main practical claim.
  2. A predictor without gradient training that is competitive with tuned classic GNNs on a broad suite. The generic protocol is competitive with the GNN reference on most datasets, including both OGB graphs. This makes closed form fitting a realistic option where exact deletion matters.
Critical weaknesses
  1. Limited conceptual contribution on the unlearning side. Proposition 1 holds by construction, and Eq. 5 is the classical block inverse update, as the paper acknowledges. For the generic protocol, exactness holds only for the fixed selected configuration, because validation selection is not replayed. The headline speedup compares the updates with training a different model; measured on the same model, the gain is much smaller for recomputation (App. O.4), and no graph unlearning baseline is reported. Replaying selection for the generic protocol on a few datasets, and reporting the speedups on the same model as the headline, would help address part of this.
  2. The predictive headline is stronger than the evidence. The "within one point" criterion is measured against local reruns. Against the published GCN, SAGE and GAT means of Luo et al. (2024), the generic protocol falls more than one point short on Squirrel and arxiv. Most datasets use a single split, most margins are below one point, and the local GNN references report no variance. App. A.2 states that development was partly informed by test outcomes. The two tailored wins rely on how Minesweeper and Roman-empire are constructed. On Roman-empire, TLCF remains below the retuned Polynormer mean from Luo et al. cited in Table 1, so "surpassing the remaining two references" holds there only against the local rerun. Results over several splits and more cautious claims in the abstract would resolve this.
Questions for authors
  1. Clarification. Can you report unlearning for the generic protocol with validation selection replayed, on at least a few datasets?
  2. Clarification. For the datasets evaluated on a single split, can you give means and standard deviations over several splits (and over seeds for the local GNN references), together with the comparison against the published means of Luo et al.?
  3. Clarification. Which design choices or dataset selections were influenced by test results, and why are Chameleon, ogbn-products and pokec from Luo et al. (2024) not reported?
  4. Suggestion. A comparison with one established graph unlearning method (for example GIF, GNNDelete or SISA/GraphEraser) on two or three datasets would place the trade-off between efficiency and accuracy in context.
6 comments
AuthorsOpenReview ↗

Response to Z9bE (1/3): full reselection and same-procedure cost

Thank you for the detailed questions on reselection, predictive robustness and established unlearning methods. The contribution combines competitive closed-form prediction with verifiable unlearning of the full selected predictor. We address selection and same-procedure cost here, predictive robustness in Part 2, and GIF in Part 3.

Q1: the complete retained-data target

Yes. Replaying the complete validation selection reproduces fresh prediction scores bit for bit in all 400 checks, including 52 changes of the selected model.

After each training-label deletion, we repeat every validation-relevant stage, including label-context construction, regularization and model selection. Only label-independent, mask-independent objects are reused. The independent from-scratch reference repeats the same learning procedure on retained data. We compare all-node prediction scores, every candidate validation score and the selected configuration; deleted-label poisoning checks dependence on removed values.

DatasetSequential deletionsSelected-model changesPrediction-score discrepancy
WikiCS100200
Minesweeper10060
Photo100160
Tolokers100100

Label context remains selected at every request on Minesweeper and Tolokers. Thus the experiment tests the case where deleting a label can change both the representation and the selected model. This full-selection result concerns training-label deletion; it does not silently extend the submitted structural-deletion tests to generic reselection.

Proposition 1 specifies the retained-data target and Eq. (5) uses classical algebra. The contribution is making that target practical for a competitively predictive closed-form system that includes label-dependent representations and selection, and verifying the complete computation—not merely its final regression coefficients.

Cost against fresh closed-form selection

A separate spectral implementation preserves all 400 selections. Full-output replay at requests 1/10/50/100 gives score differences below 7×10−107\times10^{-10} and unchanged classes for the selected predictors. This is numerical, not bitwise, agreement. Tolokers uses a disclosed post-hoc integer-AUC comparison for floating-point differences of at most 2.84×10−142.84\times10^{-14} points; the canonical 400 bit-identical checks above do not use this relaxation.

The following totals charge initial fitting, caches and factorization plus 100 requests. Both closed-form paths use the same precision/backend policy.

DatasetAccelerated total (s)Fresh full-selection total (s)Same-procedure savingFresh-fit baseline
WikiCS254.24,121.016.2xEstimated
Minesweeper588.92,734.84.64xObserved
Photo614.23,866.06.3xEstimated
Tolokers690.99,926.614.4xEstimated

All accelerated totals are measured. Minesweeper also measures the entire fresh-fit sequence; other baseline totals interpolate three repeated fits at checkpoints 0/1/25/50/75/100. The GPU device is isolated throughout; host CPU/RAM are shared. Median accelerated requests are 2.12–5.25 s.

For the distinct fixed-configuration setting, submitted §6.6/Appendix O.4 already reports median same-model savings of 272x for downdates and 6x for cached recomputation (ten and twenty split-model pairs). Those default-GPU windows exclude setup and reselection; the new totals above charge both. We will lead with these same-model comparisons.

Fixed-recipe GNN retraining is a secondary cost/accuracy comparison: it costs 1,407.9 s on the complete Minesweeper sequence, versus 588.9 s for the generic closed-form predictor, but is cheaper on Photo through 100 requests. The same-procedure savings above do not rely on replacing the retraining reference with a different predictor.

AuthorsOpenReview ↗

Response to Z9bE (2/3): paired prediction and evaluation scope

Turning to predictive robustness, all seven ten-split comparisons establish one-point non-inferiority, and CiteSeer/PubMed establish superiority. We separate that evidence from descriptive local/published comparisons and disclose the development history below.

Q2: splits, initialization and reference protocols

We evaluated ten splits on each of seven previously single-split datasets, with three seeds for each GCN/SAGE/GAT recipe: 630 GNN fits. The architecture is selected by mean validation performance within each split, then test performance is averaged over seeds. Below, ± is SD across splits; 95% CIs are pointwise paired intervals over splits, not individual nodes or pooled seeds.

DatasetClosed formGNN referencePaired difference [95% CI]
Cora82.20±1.4881.78±1.09+0.42 [−0.57, 1.41]
CiteSeer70.27±2.0269.07±1.76+1.20 [0.49, 1.91]
PubMed79.40±2.4378.07±1.96+1.33 [0.60, 2.06]
Photo95.82±0.6895.89±0.62−0.07 [−0.36, 0.21]
Computer92.36±0.6392.22±0.54+0.14 [−0.04, 0.32]
CS95.51±0.4095.74±0.44−0.23 [−0.45, −0.01]
Physics96.76±0.2197.06±0.20−0.30 [−0.46, −0.15]

Mean within-split GNN seed SDs are 0.80/0.49/0.77/0.24/0.17/0.10/0.07 points in table order. With pre-specified margins and Holm correction across seven datasets, all seven pass non-inferiority; CiteSeer/PubMed pass superiority; Photo/Computer/CS/Physics pass equivalence within ±1 point by TOST. Equivalence within that margin does not mean identical performance.

For the requested published comparison, these are the submitted generic means against the best starred GCN/SAGE/GAT entries in Luo et al., v2, Tables 2–4, with edge-aware proteins GAT from Table 11. They retain the source protocols; this is not a paired test or an exhaustive maximum over every appendix variant.

DatasetSubmitted genericPublished GNN mean±SD
Cora84.5085.10±0.67
CiteSeer73.0073.14±0.67
PubMed81.4081.12±0.52
Photo96.5496.78±0.23
Computer94.0094.09±0.37
CS96.0796.38±0.11
Physics96.6897.46±0.10
WikiCS80.8981.07±0.54
Ratings56.3155.54±0.51
Roman-empire84.2091.27±0.20
Minesweeper92.9297.86±0.24
Tolokers85.52Not in these tables
Questions78.3679.02±0.60
Squirrel43.6545.01±1.63
ogbn-arxiv72.2273.53±0.12
ogbn-proteins85.7387.82±0.16

Against these published starred references, the generic protocol is within one point or better on 10/15 graphs; Tolokers is not reported there. The separately reported task-aware constructions exceed the corresponding GNN means on Roman-empire (TLCF: 91.60 vs 91.27) and Minesweeper (ACR: 99.95 vs 97.86).

The submission uses released-code reruns on the same masks, with validation-selected GNN checkpoints, for a protocol-matched comparison. Their best local Final means are 83.56/72.44/80.54 on Cora/CiteSeer/PubMed, versus the published 85.10/73.14/81.12 (submitted Table 14).

We will show local and published references side by side and name the comparator in the abstract: TLCF exceeds the corresponding tuned-GNN mean, while its 91.60 remains below Polynormer's 92.66.

Q3: development history and omitted graphs

The initial kernel grid used validation exploration on Ratings, Tolokers, WikiCS and PubMed; scale/context extensions were partly motivated by initial arxiv/proteins test outcomes. Validation-only final selection does not make development test-unseen.

A separate evaluation froze the procedure before closed-form evaluation on seven additional graphs. Against a validation-selected 36-configuration GCN/SAGE/GAT search, differences are DBLP +0.39, BlogCatalog +0.22, LastFM-Asia +0.62, GitHub +0.18, Deezer −0.43, Actor −3.21 and Flickr −0.74 points. The first four establish non-inferiority; BlogCatalog/GitHub also establish equivalence. Deezer is inconclusive, Actor remains a gap, and Flickr is single-split/descriptive. Earlier GNN resource pilots were seen; every graph in the frozen evaluation is reported.

Chameleon was evaluated and omitted after its results were known: 43.96±4.53 over ten splits versus local GCN 46.74. We will report the row and exclusion history; including it gives 14/17 under the generic descriptive criterion. Products and pokec were not evaluated under the completed current protocol. The paired seven-dataset evidence above remains the basis for the statistical claim.

AuthorsOpenReview ↗

Response to Z9bE (3/3): established unlearning comparison (GIF)

Q4: an established unlearning method on the same requests

We have completed a GIF comparison on Cora, CiteSeer and PubMed using the same 21 edge, node, feature and subgraph deletion requests as our structural suite. The distinction is competitive prediction with recovery of the retained-data fit, not simply the cheapest update: our stored deterministic closed-form checks have zero score discrepancy against their own fresh retrains on all 21 requests. GIF is inexpensive, but does not recover its retrained GCN predictor across these requests.

We port the authors' influence update to the current environment and report two models: their 16-unit GCN architecture with five seeds, and the tuned GCN recipes with three seeds. The port uses full-batch transductive training and training labels only. The primary influence vector is the full training-objective gradient difference, with the repository's fixed-hop rule also evaluated. The primary setting is the README's 100 iterations and scale 500. These are disclosed port results, not a claim to reproduce the original package unchanged.

For each request, the target is a same-seed GCN trained from scratch on the physically edited graph with retained train/validation/test masks. Agreement uses all retained nodes; accuracy uses retained test nodes. Configurations are fixed in this comparison; full generic reselection is addressed in Part 1.

DatasetGIF accuracyFresh tuned GCN accuracyStored closed-form accuracyGIF agreement with retrain (%)
Cora60.03*83.9184.4661.55–95.96*
CiteSeer72.1672.3072.9890.66–100
PubMed80.3879.8981.3089.93–100

Accuracy columns average the seven requests and, for GCN/GIF, three seeds. Agreement ranges span request means. *The primary setting produces non-finite outputs in 6 of Cora's 21 request–seed cases; these count as errors rather than being discarded. A deliberately favorable oracle, selecting the best agreement from the evaluated settings using the retrained target, raises Cora's range to 93.37–97.12%. Across all three tuned models, this oracle improves agreement over unchanged weights on the edited graph by at most 0.54 points. Similar aggregate agreement does not imply identical individual predictions.

We also repeat each fresh retrain with the same seed: agreement ranges are 98.36–100% on Cora, 98.78–100% on CiteSeer, and 100% on PubMed, exposing the default-GPU execution floor.

The 16-unit GCN control additionally covers Photo and CS: 35 requests across five graphs, with five seeds per request. Same-seed repeat agreement is 99.95–100%; primary GIF agreement spans 81.21–100%. Even the oracle improves agreement over unchanged weights by at most 0.13 points. Its post-edit accuracies are:

DatasetGIF (16-unit GCN)Fresh 16-unit GCNStored closed form
Cora81.3281.1884.46
CiteSeer67.1166.9572.98
PubMed77.4477.2381.30
Photo90.8990.9996.47
CS92.7392.7496.05

These five-graph figures concern the small model only; the tuned-model table above remains scoped to Cora/CiteSeer/PubMed. All 35 corresponding deterministic closed-form checks have zero score discrepancy against their own fresh retrains.

GIF is fast: dataset medians are 0.04–0.18 s versus 0.08–0.20 s for small-GCN retraining, and 0.18–0.35 s versus 1.32–2.44 s for the three tuned-GCN controls. Synchronized GIF times include preparation, gradients, the influence update and prediction; retraining includes final prediction. Closed-form accuracies and exactness above come from the stored same-request suite; we make no matched CF/GIF speed claim from its historical timings.

This complements Part 1's full-selection experiment. Approximate influence updates can be cheaper, but the closed-form approach combines competitive post-edit accuracy with a directly checkable retained-data target. We will report all settings, port details, repeat floors and non-finite cases alongside the comparison.

Your questions on practical exactness and predictive reliability are addressed by 400 bit-identical reselection checks, a measured 4.64x saving over fresh selection, seven paired non-inferiority results, and the same-request GIF comparison. We hope this evidence resolves the main concerns behind your assessment, and would be grateful if you would reconsider your score.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Central contribution and evidence addressing the reviews

Thank you for the careful reviews and the concrete requests for further evidence. The central result is competitive graph prediction without gradient training, coupled with exact maintenance of the complete validation-selected predictor. The following results directly test both sides of that contribution.

Anonymized code is provided in the supplementary material: the protocol engine, frozen configurations, validators/tests, deletion checks and rebuttal controls.

  1. Competitiveness beyond single-split margins. The generic procedure is within one point or better of the matched local tuned-GNN reference on 14/16 reported benchmarks. Across ten splits on seven suite datasets and 630 GCN/SAGE/GAT fits, all seven comparisons establish one-point non-inferiority after Holm correction; CiteSeer and PubMed establish superiority. Against the cited retuned graph-transformer references, the generic procedure also has higher observed means than GraphGPS on 14/15 graphs and SGFormer on 12/15.

  2. Measured gains beyond graph-GP predecessors and iterative readouts. Using the authors' GNNGP code on matched inputs and masks, our generic procedure has higher observed means on 12/13 graphs under both the initial and expanded searches. A separate ten-split initial-grid control supports gains on PubMed, Photo and Computer under exploratory Holm-corrected paired tests. Across thirteen graphs with identical feature maps per split, ridge and logistic dataset means differ by at most 1.3 performance points, while ridge's grid fitting and prediction is a median 10.4x faster, excluding shared construction.

  3. Exact unlearning includes context and model selection. Recomputing every affected stage reproduces fresh full-selection prediction scores bit for bit in 400 sequential training-label deletions, including 52 changes of the selected model. Deleted-label poisoning and comparisons of every candidate validation score verify the complete computation. On 21 matched structural requests across three graphs, our deterministic closed-form checks have zero score discrepancy against their own fresh retrains; our port of the established influence-based method GIF does not consistently reproduce its own retrained GCN.

  4. Savings with selection and setup included. A separately validated numerical acceleration costs 588.9 s for setup and 100 Minesweeper requests, versus 2,734.8 s for fresh closed-form selection: a fully measured 4.64x reduction against the same learning procedure. Checkpoint-interpolated estimates give same-procedure savings of 6.3x on Photo, 14.4x on Tolokers and 16.2x on WikiCS.

Together, these results connect competitive prediction, verifiable retraining equivalence and practical maintenance cost. The representations, label context and selection decisions that deliver the predictive result are included in the retained-data target itself. The reviewer-specific responses provide the complete per-graph comparisons, protocols and scope of each result.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.