- Rating
- 2
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper proposes a post-hoc graph sparsification method designed to preserve the dense operator of a trained Neural Sheaf Diffusion (NSD) model. Standard approaches sample edges by graph effective resistance (ER). This method instead samples edges by sheaf effective resistance and reweights the edges using a least squares optimization, so that the model’s intermediate and final outputs are preserved. Inference can then be approximated using the sparse sheaf operator. The authors compare their method against graph ER sparsification and random reweighting.
Critical strengths
-
The paper is well presented and easy to follow, with clear notation.
-
It addresses a relevant gap: existing sparsification methods are model-agnostic.
-
The theoretical analysis yields provable approximation guarantees.
Critical weaknesses
- Unclear use case. Post-hoc sparsification reduces inference cost, but the resource-intensive step for these models is typically training, not inference. The practical motivation is therefore not convincing.
- Limited empirical evaluation. Only one model is benchmarked. Random reweighting can hardly be considered a meaningful baseline, which leaves graph ER as the only real comparison.
- Skewed comparison. The ablation shows that most of the gain comes from the parameter-specific edge reweighting rather than from sheaf-based sampling itself. A method with access to the learned parameters will naturally outperform a parameter-agnostic baseline. Since the proposed method is the only one in the evaluation with access to model parameters, the comparison does not isolate the contribution of the sheaf sparsification.
Questions for authors
- What is the intended use case of the method, given that it reduces inference cost but not training cost?
- Why was graph ER the only substantive baseline? Were other sparsification methods considered?
- The method requires a trained model, whereas graph ER needs no access to model weights. Graph ER can therefore be applied before training and reduce training cost, but it cannot adapt to the learned parameters. Given these different settings, do the authors consider the comparison fair? How would the method compare against a baseline that also has access to the trained parameters?
2 comments
This answer does not satisfactorily respond to any of my questions/weaknesses.
Unclear use case. The use case the authors describe is that inference time can be reduced due to sparsification and argue that this is the main metric in an application where the up front cost of training a model can be considered fixed. With the ever-quickening pace of model development, I must disagree with this point. Further, the authors do not compare with the dense inference time.
Limited empirical evaluation. The authors present a new datasets, not a new competing model.
Skewed comparison. With the new experiments, the authors actually give evidence for my point. On all datasets but squirrel, the by far greatest factor is the edge reweighting, not the sparse sampling. This is to be expected, as the weights are chosen such that they model output is preserved.
I maintain my score, albeit I am slightly more inclined toward clear rejection after the author response.
We thank the reviewer for recognizing the motivation, clarity, and theoretical analysis. We agree that the intended use case and the distinction between support selection and coefficient calibration need clearer presentation.
1. Intended use case and measured costs
We study post-training compression of an existing NSD model, with the original network parameters frozen. The intended setting is deployment where preserving the trained model is important and retraining is undesirable or unavailable. Calibration is offline preprocessing whose cost could be amortized when the calibrated operators remain applicable and are reused.
This setting does not reduce original training cost. For a single inference on a static transductive graph, preprocessing may outweigh any inference savings.
We added Squirrel timing measurements across ten folds. Sparse forward times are approximately 0.044 s at 35% retention and 0.066 s at 55%, with similar times across methods. Probe-LS optimization adds approximately 11.7–12.8 s offline. These measurements quantify calibration overhead but do not establish acceleration over dense inference, for which matched timing measurements are unavailable.
Graph ER scoring takes 58.33 ± 10.75 s and Sheaf ER scoring 5.57 ± 0.45 s. However, the former uses edgewise multi-RHS CG evaluation, whereas the latter uses 32-probe random projection. This timing difference reflects different estimator configurations and should not be interpreted as an intrinsic advantage of sheaf-based sampling. We do not claim an end-to-end runtime or memory advantage.
2. Baselines and empirical scope
We agree that random reweighting is a sanity check rather than a competitive baseline. The evaluation also includes Graph ER + Probe-LS and Sheaf ER + ER reweighting in the ablations. These comparisons separate support selection from coefficient calibration.
The additional ten-fold Squirrel evaluation reports accuracies of 54.03 ± 2.41% for Graph ER, 55.60 ± 3.02% for Sheaf ER, and 56.99 ± 3.20% for Sheaf ER + Probe-LS at 35% retention. At 55%, the corresponding values are 55.95 ± 2.49%, 56.93 ± 3.27%, and 57.23 ± 3.32%. Dense accuracy is 57.26 ± 3.23%. These are descriptive accuracy results, not evidence of statistical significance or prediction agreement.
Our empirical evidence remains restricted to BundleSheaf NSD across four datasets. We have clarified this scope and do not claim superiority over other model-aware sparsification methods or generality across GNN architectures.
3. Fairness of access to learned parameters
We agree that Table 1 changes both support selection and reweighting. It compares complete pipelines and cannot, by itself, isolate the contribution of sheaf-based sampling.
The ablations address this distinction in two ways. First, Graph ER + Probe-LS and Sheaf ER + Probe-LS both use learned-operator calibration, allowing support selection to be examined with calibration fixed. Second, Sheaf ER + ER reweighting and Sheaf ER + Probe-LS share the same learned-operator-dependent support. This tests calibration against a baseline that already uses trained-model information.
The expanded Table 2 includes Roman-empire. At 35% retention, Probe-LS improves accuracy from 46.31% to 57.82% on graph support and from 45.13% to 56.91% on sheaf support. Graph support remains stronger after calibration in this setting. We therefore interpret the results as evidence for post-selection calibration on either support, rather than universal superiority of sheaf-based selection.
Our central contribution is joint calibration of retained-edge coefficients across frozen learned NSD operators, its conditional stability analysis, and the empirical separation of selection from calibration. Sheaf-ER is one compatible support-selection strategy.
Finally, applying Graph ER before training addresses a different objective: reducing training cost while allowing adaptation to the sparse graph. Our frozen-model experiments evaluate post-hoc preservation and do not compare the total training-and-deployment costs of these settings. We have clarified this distinction in the manuscript.