- 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
-
The reviewer thinks that the empirical evaluation addresses a useful question and covers varied graph benchmarks against tuned GNN baselines.
-
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.
-
Same model comparisons demonstrate computational savings. ACR also effectively exploits the supplied Minesweeper clue semantics.
Critical weaknesses
-
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.
-
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.
-
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
-
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?
-
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?
-
Was the final frozen generic method tested on any benchmarks that were not used during development?
4 comments
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.
| Dataset | Ridge | Logistic | Shared map build (s) | Ridge grid fit+predict (s) | Logistic grid fit+predict (s) |
|---|---|---|---|---|---|
| Cora | 83.70 | 83.70 | 0.10 | 0.012 | 0.44 |
| CiteSeer | 72.80 | 73.40 | 0.17 | 0.018 | 0.29 |
| PubMed | 81.40 | 82.30 | 0.20 | 0.013 | 0.27 |
| Photo | 96.54 | 95.82 | 0.96 | 1.66 | 3.93 |
| Computer | 93.38 | 92.15 | 3.82 | 7.98 | 22.54 |
| CS | 96.07 | 96.26 | 10.10 | 18.01 | 19.10 |
| Physics | 96.80 | 96.99 | 33.30 | 113.01 | 77.54 |
| WikiCS | 80.89 | 80.23 | 0.97 | 0.060 | 1.48 |
| Ratings | 56.14 | 55.91 | 8.57 | 24.28 | 135.97 |
| Roman-empire | 80.94 | 81.54 | 5.55 | 19.97 | 53.38 |
| Minesweeper | 90.75 | 91.58 | 0.84 | 2.06 | 26.68 |
| Tolokers | 84.98 | 85.09 | 3.03 | 3.15 | 32.60 |
| Squirrel | 43.07 | 43.05 | 0.19 | 0.105 | 2.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 times the mean diagonal, versus for float64 kernels. Both heads use the same stabilized map; its ridge scores differ from the original KRR by at most , 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.
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 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 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.
| Dataset | Initial test score (%) | Setup (s) | Median request (s) | Fresh full-selection initial fit (s) |
|---|---|---|---|---|
| WikiCS, accuracy | 81.44 | 41.9 | 2.12 | 40.9 |
| Minesweeper, ROC-AUC | 92.65 | 77.5 | 5.11 | 27.8 |
| Photo, accuracy | 96.54 | 76.8 | 5.25 | 38.8 |
| Tolokers, ROC-AUC | 84.93 | 176.6 | 5.15 | 98.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.
| Dataset | Common splits | Closed form − GNN [95% paired CI] |
|---|---|---|
| Actor | 5 | −3.21 [−4.94, −1.48] |
| DBLP | 5 | +0.39 [−0.09, 0.87] |
| BlogCatalog | 5 | +0.22 [−0.16, 0.59] |
| LastFM-Asia | 5 | +0.62 [−0.07, 1.31] |
| Deezer-Europe | 3 | −0.43 [−1.30, 0.43] |
| GitHub | 3 | +0.18 [−0.24, 0.61] |
| Flickr | 1 | −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.
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.
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.
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):
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.