Pith. sign in

REVIEW 2 major objections 2 minor 8 references

Closed-Form Node Classification with Exact Graph Unlearning

T0 review · 2 major / 2 minor · reviewed 2026-06-29 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Deterministic closed-form ridge solvers, routed by adjusted homophily, match 2-layer GCN accuracy on node classification and support exact unlearning for graph edits.

desk verdict Closed-form routed solvers match 2-layer GNN accuracy and deliver exact unlearning via linear re-solves, but the homophily routing step carries the main risk. read the letter →

arxiv 2605.25662 v1 pith:2LK7APZO submitted 2026-05-25 cs.LG

Aditya Gaur , Charu Sharma This is my paper
classification cs.LG
keywords closed-formsolversexactgraphunlearningnodeclassificationridgeregressionneuralnetworksadjustedhomophilySGCLCF-Net
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper seeks to determine how much node-classification performance from graph neural networks can be recovered by deterministic closed-form solvers instead of gradient descent. It introduces a framework that routes each graph by adjusted homophily to either SGC-style propagation plus ridge regression or a new layer-wise closed-form refinement network called LCF-Net. On 14 benchmarks the closed-form predictors match or beat the best vanilla 2-layer GCN, SAGE and GAT on nine of nine measured datasets and tie tuned deep models within one standard deviation on most small benchmarks. Because the predictors are explicit solutions of linear systems, any modification to labels, features, edges, nodes or subgraphs can be re-solved to produce parameters identical to those obtained by full retraining. This property also yields large speedups for localized updates and allows measurement of privacy leakage from approximate unlearning methods.

What carries the argument

A homophily-routed closed-form framework consisting of SGC-style propagation plus ridge regression for assortative graphs and LCF-Net (layer-wise closed-form feature refinement capped by Gaussian kernel ridge) for heterophilous graphs.

What would settle it

A new graph on which adjusted homophily routes to the wrong solver and the resulting accuracy falls more than one standard deviation below the best vanilla 2-layer GCN.

Watch

Extended reading notes

Core claim

We introduce a routed closed-form framework selected by adjusted homophily. For assortative graphs we use SGC-style propagation followed by ridge regression; for heterophilous graphs we introduce LCF-Net, a layer-wise closed-form graph feature-refinement network whose per-layer ridge solves are capped by a Gaussian kernel-ridge head. Across 14 benchmarks our closed-form predictors match or beat the best vanilla 2-layer GCN/SAGE/GAT on 9 of 9 measured datasets, tie tuned deep recipes within one standard deviation on 9 of 12 small benchmarks, and exceed the OGB-leaderboard plain GCN on both large graphs. Because our predictors are explicit solutions of deterministic linear systems, modified gr

Load-bearing premise

The routing decision based on adjusted homophily correctly separates graphs into assortative and heterophilous regimes where the respective closed-form solvers remain competitive.

Editorial extensions

If this is right

  • Modified graph inputs can be re-solved to obtain retrain-equivalent parameters for any combination of label, feature, edge, node or subgraph changes.
  • K-hop locality of ridge components enables localized updates that give 21-45x speedups over full re-solving on ogbn-arxiv.
  • Exactness of the unlearning procedure is verified across 109 configurations on the evaluated benchmarks.
  • The remaining performance gap on heterophilous graphs closely tracks the gain obtained by moving from 2-layer to deep SAGE, indicating the gap is primarily architectural.
  • Structural-inversion experiments quantify the privacy floor of exact retraining versus approximate graph-unlearning methods.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Systems handling dynamic graphs could perform frequent exact updates without the cost of gradient retraining.
  • The parity with 2-layer models suggests that much of the observed benchmark performance arises from linear feature refinement rather than nonlinear optimization.
  • The exact-unlearning baseline can be used to evaluate leakage in any approximate graph-unlearning technique.
  • Similar closed-form derivations might be attempted for other graph tasks once an appropriate routing signal is identified.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 2 minor

Summary. The paper proposes a routed closed-form framework for node classification: SGC followed by Ridge regression on assortative graphs (selected via adjusted homophily) and LCF-Net (layer-wise closed-form refinement capped by Gaussian kernel-Ridge) on heterophilous graphs. It claims this matches or exceeds vanilla 2-layer GCN/SAGE/GAT on 9/9 datasets, ties tuned deep models within 1 SD on 9/12 small benchmarks, and beats plain GCN on large OGB graphs, while enabling exact unlearning for label/feature/edge/node/subgraph changes via deterministic linear-system re-solves, with K-hop locality proofs, 109-configuration verification, and large speedups on ogbn-arxiv.

Significance. If the routing is reliable and the closed-form performance holds without circularity, the work is significant for providing deterministic, non-iterative predictors with exact unlearning guarantees and quantifiable privacy floors, which are rare in graph ML and enable efficient localized updates (21-45x over full re-solve) far beyond gradient retraining.

major comments (2)
  1. [Abstract] Abstract and routing description: the central performance claims (matching 2-layer GCN/SAGE/GAT on 9/9 datasets and tying deep recipes on 9/12) are conditioned on correct routing by adjusted homophily, yet the threshold is selected on the same benchmarks used for evaluation; this introduces circularity that makes the regime separation non-generalizable and the competitiveness guarantee conditional on an in-sample choice.
  2. [Unlearning section] Unlearning formalization: while K-hop locality is proven for Ridge components, the manuscript does not explicitly state whether this extends to the Gaussian kernel-Ridge head or the full LCF-Net stack; if not, the exactness claim for heterophilous graphs (and thus the 109-configuration verification) rests on an unproven extension.
minor comments (2)
  1. The abstract reports results across 14 benchmarks and 109 configurations but omits data-split details, error-bar reporting, and whether post-hoc routing decisions were fixed before evaluation; adding these would strengthen verifiability.
  2. Notation for the Gaussian kernel bandwidth and Ridge parameter should be introduced with explicit ranges or selection procedure in the methods to clarify the two free parameters.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed and constructive report. The two major comments identify important points on routing circularity and unlearning formalization. We respond to each below and indicate the revisions we will make.

read point-by-point responses

  1. Referee: [Abstract] Abstract and routing description: the central performance claims (matching 2-layer GCN/SAGE/GAT on 9/9 datasets and tying deep recipes on 9/12) are conditioned on correct routing by adjusted homophily, yet the threshold is selected on the same benchmarks used for evaluation; this introduces circularity that makes the regime separation non-generalizable and the competitiveness guarantee conditional on an in-sample choice.

    Authors: We agree that selecting the adjusted-homophily threshold on the evaluation benchmarks introduces an in-sample element that limits claims of generalizability. Adjusted homophily is a standard, pre-defined metric, and the separation point we used follows common practice in the homophily/heterophily literature, but the choice remains data-dependent. In revision we will (i) state the threshold explicitly as a fixed hyper-parameter chosen from prior literature rather than optimized on the test sets, (ii) add a sensitivity table showing performance under nearby thresholds, and (iii) qualify the abstract claims to note that routing is performed with a literature-derived cutoff. These changes will be reflected in both the abstract and Section 3. revision: partial

  2. Referee: [Unlearning section] Unlearning formalization: while K-hop locality is proven for Ridge components, the manuscript does not explicitly state whether this extends to the Gaussian kernel-Ridge head or the full LCF-Net stack; if not, the exactness claim for heterophilous graphs (and thus the 109-configuration verification) rests on an unproven extension.

    Authors: The referee correctly notes that the manuscript proves K-hop locality only for the linear Ridge components. For LCF-Net the Gaussian kernel-Ridge head operates on the already K-hop-localized node features produced by the preceding closed-form layers; because the kernel matrix is a deterministic function of these features, any change confined to a K-hop neighborhood can be propagated exactly by updating only the affected rows/columns of the kernel matrix and re-solving the small linear system. We will add an explicit lemma and short proof in the revised unlearning section establishing that locality carries through the kernel head, thereby justifying the exactness claim and the 109-configuration verification for heterophilous graphs as well. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; explicit linear-system solutions are independent of routing choice.

full rationale

The paper's core derivation consists of closed-form Ridge solutions after SGC propagation (assortative case) and layer-wise closed-form refinement plus Gaussian kernel-Ridge head (heterophilous case). These are deterministic linear-system solutions whose parameters are obtained by direct solve rather than iterative fitting or self-referential definition. The routing decision by adjusted homophily is presented as a graph-property selector that partitions regimes; even if its threshold were chosen with reference to the evaluation benchmarks, the performance numbers inside each regime remain explicit solutions rather than quantities forced by construction. No self-citation chain, uniqueness theorem, or ansatz smuggling is invoked as load-bearing support for the central claims. The derivation therefore stands on its own equations without reduction to its inputs.

Assumptions & free parameters 2 free parameters · 2 assumptions · 0 invented entities

The framework rests on the assumption that Ridge regression on propagated features is sufficient for the reported performance parity and that the Gaussian kernel-Ridge head can be solved exactly; no new physical entities are introduced.

free parameters (2)
  • Ridge regularization parameter
    Chosen per dataset or per layer; required for the closed-form solve to be stable.
  • Gaussian kernel bandwidth
    Hyper-parameter of the final head in LCF-Net; fitted or tuned on validation data.
assumptions (2)
  • domain assumption Adjusted homophily metric correctly partitions graphs into regimes where the respective closed-form solver is optimal.
    Invoked to select between SGC+Ridge and LCF-Net; if false the routing decision fails.
  • standard math K-hop locality holds for the Ridge components under the stated graph modifications.
    Used to prove localized updates without full re-solving.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Closed-Form Node Classification with Exact Graph Unlearning." pith.science (2026). https://pith.science/paper/2LK7APZO

@misc{pith2026260525662,
  author       = {Pith},
  title        = {Pith review of: Closed-Form Node Classification with Exact Graph Unlearning},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2LK7APZO}},
  note         = {Machine review of arXiv:2605.25662}
}
abstract

Graph neural networks for node classification are typically trained by gradient descent over hundreds or thousands of epochs. Recent work has shown that, when properly tuned, classic GCN/SAGE/GAT architectures can match graph transformers on many node-classification benchmarks. We ask a complementary question: how much of this performance can be recovered by deterministic closed-form solvers, and what guarantees does this enable? We introduce a routed closed-form framework selected by adjusted homophily. For assortative graphs, we use SGC-style propagation followed by Ridge regression; for heterophilous graphs, we introduce LCF-Net, a layer-wise closed-form graph feature-refinement network whose per-layer Ridge solves are capped by a Gaussian kernel-Ridge head. Across 14 benchmarks, including ogbn-arxiv and ogbn-proteins, our closed-form predictors match or beat the best vanilla 2-layer GCN/SAGE/GAT on 9 of 9 measured datasets, tie tuned deep recipes within one standard deviation on 9 of 12 small benchmarks, and exceed the OGB-leaderboard plain GCN on both large graphs. The remaining heterophilous gap closely tracks the gain from vanilla 2-layer to deep SAGE, suggesting that the residual difference is primarily architectural. Because our predictors are explicit solutions of deterministic linear systems, modified graph inputs can be re-solved to obtain retrain-equivalent parameters. We formalize exact graph-object unlearning for label, feature, edge, node, and subgraph modifications, prove K-hop locality for Ridge components, and verify exactness across 109 configurations. On ogbn-arxiv, localized updates give $21$--$45\times$ speedups over full re-solving and roughly $10^{6}\times$ speedups over gradient retraining. Structural-inversion experiments further quantify the privacy floor of exact retraining and the additional leakage of approximate graph-unlearning methods.

Figures

Figures reproduced from arXiv: 2605.25662 by the authors.

Figure 1
Figure 1. Method overview. Routing on hadj at τ=0.2 selects Pipeline A (assortative; SGC+Ridge+C&S) or Pipeline B (heterophilous; multi-scale + LCF-Net+ Gaussian KRR). Theorem 1: exact unlearning refresh in O(|NL(S)|D2 ) for Ridge components, byte-identical to retrain. et al., 2024), GraphAny (Zhao et al., 2025)). Luo et al. (2024) show tuned classic GCN/SAGE/GAT match or beat specialized heterophily models and graph transfor… view at source ↗
Figure 2
Figure 2. LCF-Net layer structure. Each iteration aggregates with [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Three-tier accuracy comparison on the SAGE family across 9 datasets (other architectures behave similarly; [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: TICR-Multi whitening ablation on ogbn-arxiv. No whitening reaches [PITH_FULL_IMAGE:figures/full_fig_p010_4.png]
Figure 5
Figure 5. Figure 5: K-hop locality scaling on ogbn-arxiv (n=169 k), Pipeline A only. Top: wall-clock for unlearning vs. forget-set size. K-hop downdate ∼2 ms across the entire forget-set range; full re-solve 40–66 ms; gradient retrain-from-scratch (Luo GCN) ∼1.8×106 ms. The flat scaling o…

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

8 extracted references · 4 canonical work pages

  1. [1]

    Node-wise filtering in graph neural networks: A mixture of experts approach.CoRR, abs/2406.03464,

    arXiv:2406.03464. Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. InAdvances in Neural Information Processing Systems (NeurIPS),

    work page arXiv

  2. [2]

    Jianan Zhao, Zhaocheng Zhu, Mikhail Galkin, Hesham Mostafa, Michael Bronstein, and Jian Tang

    arXiv:2506.00808. Jianan Zhao, Zhaocheng Zhu, Mikhail Galkin, Hesham Mostafa, Michael Bronstein, and Jian Tang. Fully-inductive node classification on arbitrary graphs. InInternational Conference on Learning Representations (ICLR),

    work page arXiv

  3. [3]

    2024 reproductions We reproduce all 33 recipes of Luo et al

    A Luo et al. 2024 reproductions We reproduce all 33 recipes of Luo et al. (2024) (11 datasets× GCN/SAGE/GAT) using theirmedium_graph/main.py code, their exact hyperparameters from run_gnn.sh, and their seed ( =

    2024

  4. [4]

    Luo et al

    on the same splits. Luo et al. (2024) does not publish a Tolokers recipe; we adopt a standard heterophilous configuration (hidden= 128, 4 layers, Batch- Norm, residuals, 2000 epochs) uniformly across GCN/SAGE/GAT, matching the depth/width of their published Tolokers-adjacent recipes (Minesweeper, Amazon-Ratings, Roman-empire). Every reproduction is within...

    2024

  5. [5]

    no error bars

    achieves locality on shard-cached propagation but requires a propagation cache and approximate retraining within shards. Our K-hop locality result is byte-identical and requires no cache: it is a direct consequence of the closed-form solver structure. Floating-point non-associativity caveat.Both proofs rely on the assumption that the linear system solve i...

    2024

  6. [6]

    Wall-clock per experiment: reproductions of Luo et al

    on Ada HPC RTX 2080 Ti (11 GB). Wall-clock per experiment: reproductions of Luo et al. (2024) range from ∼2 min (small-Coauthor-Physics-2L-SAGE) to ∼65 min (9L/2500-epoch Roman-empire deep SAGE). Pipeline A closed-form runs: <30 seconds per dataset per hyperparameter sweep. Pipeline B LCF-Net runs: ∼2.5 minutes per split including the full grid and final ...

    work page arXiv

  7. [7]

    recipe).SGC + Ridge: Pipeline A minus C&S, isolating the marginal C&S contribution

    as a standalone baseline with two bases: (a)Lin + C&S(Ridge on raw X, pure training-free), (b)MLP + C&S(2-layer MLP base, gradient-trained, original Huang et al. recipe).SGC + Ridge: Pipeline A minus C&S, isolating the marginal C&S contribution. ∆: ours − best C&S. Pipeline A wins on 6/7; the only loss is Coauthor-Physics ( −0.69 pp vs. MLP+C&S, which is ...

    work page arXiv 2024

  8. [8]

    All” column at 5% unlearn. “–

    ♮WikiCS approximate from Mernyei and Cangea (2020). Minesweeper/Amazon-Ratings/Roman-empire are our own vanilla-2L runs on the splits of Luo et al. (2024). Closed-formboldedwhere it beats the best vanilla 2L architecture. O Full TrendAttack 12-configuration breakdown Complete results referenced from §5.6: 3 datasets × 2 unlearn ratios × 2 attack variants,...

    2020

Pith tools

Reviewed June 29, 2026 · model on record in the stance chip above.