acceptodds
Under review as a conference paper at ICLR 2027

Preserving Learned Propagation Operators for Graph Sparsification

Abstract

Graph sparsification has traditionally focused on preserving the graph Laplacian through spectral approximation. However, many modern GNNs propagate in- formation through model-dependent or learned operators that can differ substan- tially from the input graph Laplacian. Consequently, preserving the input graph alone may be insufficient to preserve the behavior of a trained model. We pro- pose an operator-aware perspective on graph sparsification that instead preserves the learned propagation operator. We instantiate this perspective for Neural Sheaf Diffusion (NSD) through a no-retraining framework for constructing sparse sheaf operators while preserving learned propagation behavior. We provide theoreti- cal analysis connecting operator approximation to stable representations and pre- dictions, and experiments on four benchmark datasets demonstrate consistently higher sparse-model fidelity than conventional reweighting. These results suggest operator-action preservation as an effective post-hoc reweighting principle for no- retraining sparsification of trained NSD models.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph Machine Learning, Geometric Deep Learning

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_TujKOpenReview ↗
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

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.

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.

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

The paper studies post-training sparsification of Neural Sheaf Diffusion (NSD). After training the dense model, it freezes the original model parameters, selects an edge support using sheaf effective resistance, and calibrates nonnegative retained-edge coefficients with Probe-LS. The objective matches the dense operator's action on a probe matrix. Conditional perturbation bounds relate operator-action error to representation and prediction stability. Experiments on four node-classification datasets compare sparse inference with the dense model and separate support selection from reweighting.

Critical strengths

Matching a learned propagation operator is a sensible alternative to preserving only the input graph Laplacian. Separating support selection from coefficient calibration is useful, and the paper appropriately avoids claiming that sheaf-based selection is universally superior. The conditional theory makes the role of operator-action error explicit.

The matched-support evidence for calibration is useful. Probe-LS improves all twelve comparisons in Table 2, with additional Roman-empire curves in the appendix. On Squirrel, retaining 25% of edges gives 56.58% accuracy against 57.26% for the dense model. The operator/logit-drift plots provide further qualitative support for the motivation. These results establish a meaningful advantage over the tested ER weighting rules.

Critical weaknesses

I had trouble determining the probe construction, which is central to the contribution. Sheaf effective-resistance sparsification already appears in Hansen and Ghrist [1]; its use here is an adaptation to learned operators. Select-then-reconstruct ideas also have relevant precedents: Samperio [2] combines spectral edge pruning with nonnegative response fitting, while Kwon et al. [3] calibrate fixed-support masks against dense-layer outputs without retraining the original network. Neither is an equivalent NSD method. Against these precedents, the benefit of the representation-aware metric matters. Section 5 describes final hidden representations on training nodes, whereas Appendix E.2 specifies 16 Rademacher probes. Raw isotropic probes would approximate full-operator Frobenius fitting in expectation, rather than emphasize learned hidden-state directions. Random sketches of hidden representations could reconcile the descriptions. The paper needs to clarify this and isolate the benefit of hidden-state over isotropic probes on the same support.

The results show an improvement over ER reweighting, but leave the quality and robustness of preservation less clear. On Roman-empire, accuracy falls from 85.46% to 50.76% at 25% retention and remains 13.06 percentage points below dense at 65% retention, despite clear gains over the sparse baseline. All reported models are BundleSheaf, and Appendix C describes ten sampling trials conditional on a fixed checkpoint, not ten independent model fits. The unexplained dense-baseline standard deviations make the uncertainty difficult to interpret. Prediction consistency is defined, but I could not find numerical results; similar accuracy does not establish agreement with the dense predictions. Edge reduction is demonstrated, but inference savings and calibration cost are not measured. The paper focuses on fidelity and leaves cheaper calibration to future work. Its practical significance remains difficult to assess.

Questions for authors

Which probe matrix was used: hidden states, raw Rademacher vectors, or sketches of hidden states? Please specify dimensions, training-node masking, and layer usage. Which normalized or unnormalized operator is fitted and used during sparse inference, and are realized restriction maps and normalization held fixed? Please also distinguish the written NNLS optimum from the regularized, capped, 50-step implementation.

Do existing results compare hidden-state and isotropic probes on identical supports with the same optimization budget? I would prioritize this control over a large new benchmark suite. Shapley-based sparsification [4] or FiP-SA/IG [5] could provide context if fairly adapted to NSD; their published GCN/GAT results are not directly comparable. Retraining-based methods are not mandatory baselines for this setting.

What deployment setting motivates the calibration cost, and are any preprocessing, inference-time, or memory measurements available? Please distinguish the demonstrated fidelity benefit from efficiency benefits that remain unmeasured.

[1] Hansen and Ghrist. Toward a Spectral Theory of Cellular Sheaves.

[2] Samperio. Simultaneous Recovery of a Sparse Topology and the Admittance of an Electrical Network.

[3] Kwon et al. A Fast Post-Training Pruning Framework for Transformers.

[4] Akkas and Azad. Explainable Graph Sparsification with Shapley Values.

[5] Shin and Shin. On the Feasibility of Fidelity- for Graph Pruning.

1 comment

We thank the reviewer for the constructive assessment. We corrected the probe description, clarified the objective and prior work, and expanded the Roman-empire ablation.

1. Probes and operators

The original implementation uses independent Rademacher probes for each selected layer:

\qquad (Z_\ell)_{ij}\in\{-1,+1\}/\sqrt{16}.$$ No node-split mask is applied. For nonlinear models, all learned layers are selected by default and share one edge-coefficient vector. Hidden states are used for separate diagnostics, not calibration. The original training-node hidden-state description was incorrect and has been corrected. We removed claims of task-specific probe directions: isotropic probes instead estimate full-operator Frobenius fitting in expectation. Calibration fits normalized learned sheaf operators, keeping realized restriction maps and dense normalization factors fixed. Normalization is not recomputed from sparse degrees. These operators are used for frozen-model inference. **2. Objective and theory** We minimize mean relative squared operator-action error across selected layers, plus 0.0001 times the mean squared edge coefficient. Shared coefficients are constrained to [0,10]. We use sampling-based initialization and 50 Adam steps with learning rate 0.05, projecting after each update. This approximates a regularized, constrained objective rather than solving the idealized NNLS exactly. The stability bounds assume controlled operator-action error on dense hidden states at each layer. Small sampled-probe error alone does not establish these conditions; the revised interpretation distinguishes them. **3. Probe comparison** A Squirrel experiment across ten folds compares 32-channel hidden-state probes with 16 Rademacher probes. Across five retention ratios, mean accuracy differences are at most 0.17 percentage points, with no consistent winner. Both use 50 optimization steps, but different probe dimensions preclude a strictly matched-budget comparison. We do not claim equivalence or infer prediction agreement from similar accuracy. **4. Preservation and uncertainty** An additional Squirrel accuracy-and-timing evaluation covers folds 0–9. At 35% retention, accuracies are 54.03 ± 2.41% (Graph ER), 55.60 ± 3.02% (Sheaf ER), and 56.99 ± 3.20% (Sheaf ER + Probe-LS). At 55%, they are 55.95 ± 2.49%, 56.93 ± 3.27%, and 57.23 ± 3.32%, respectively. Dense accuracy is 57.26 ± 3.23%. Probe-LS adds 1.39 and 0.30 percentage points over Sheaf ER. These descriptive gains alone establish neither significance nor prediction agreement. These means and standard deviations are across ten folds, not ten independent training-seed replications. We will reconcile the aggregation units and dense-baseline standard deviations for the original experiments. Updated Table 2 includes Roman-empire: at 35% retention, calibration improves accuracy from 46.31% to 57.82% on graph support and from 45.13% to 56.91% on sheaf support. Substantial dense-model gaps remain, and sheaf support is not universally superior. Complete prediction-consistency results remain unavailable. Our empirical scope is BundleSheaf NSD. **5. Prior work and contribution** We now discuss Hansen–Ghrist, Samperio, and Kwon et al., acknowledging precedents for sheaf sparsification and selection followed by reconstruction. Our contribution is joint calibration for frozen learned NSD operators, conditional stability analysis, and evaluation separating support selection from calibration. Sheaf-ER is one compatible support strategy. **6. Cost and deployment** Across the ten Squirrel folds, sparse forward times are approximately 0.044 s at 35% retention and 0.066 s at 55%, similar across methods. Probe-LS optimization adds approximately 11.7–12.8 s offline. Graph ER scoring takes 58.33 ± 10.75 s versus 5.57 ± 0.45 s for Sheaf ER. However, Graph ER uses edgewise multi-RHS CG evaluation, whereas Sheaf ER uses 32-probe random projection. This compares different estimator configurations, not an intrinsic sheaf-sampling speed advantage. We target offline compression where calibrated operators remain applicable and reusable. Calibration does not reduce original training cost and may not pay off for a single inference. Dense forward and peak-memory measurements are unavailable, and total-run timings have unmatched processing scopes. We therefore report calibration overhead without claiming dense-inference acceleration or end-to-end runtime or memory gains.
Reviewer_1TDLOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

Towards the goal of graph sparsification--a post-hoc operation that converts a dense graph with many connections to a sparse graph with only a few--the authors propose a least-square optimization that the Sheaf Laplacian operator instead of the more conventional graph Laplacian operator. The method does not require data training.

Critical strengths
  1. The problem definition and motivation are clearly written; the need for graph sparsification is clear, and the need for operator-preserving sparsification (something other than graph Laplacian--though the graph Laplacian is commonly used as the graph shift operator in GCN / GNN) is also clear. The paper is overall easy to follow.
Critical weaknesses
  1. The problem seems ill-suited for a machine learning conference, as the contribution is basically a convex optimization proecdure that requires no data-training.

  2. The idea of preserving the sheaf Laplacian instead of the more conventional graph Laplacian matrix seems rather trivial. The sheaf Laplacian is a slight generalization of the conventional graph Laplacian matrix (i.e., the graph Laplacian is a special case), and notions like PSDness carry over to the general case naturally. The proposed method is also remarkably similar to effective-resistance sampling (Spielman & Srivastava, 2011), so algorithmic novelty is also limited.

  3. There are no numbers attached to any of the presented equations, which is non-standard.

Questions for authors
  1. What is the non-trivial algorithmic novelty here, beyond a straightforward extension from effective-resistance sampling (Spielman & Srivastava, 2011) that was designed to sparsify a graph to preserve spectrally a graph Laplacian matrix to the more general sheaf Laplacian?

  2. What is the overall complexity of your algorithm? How would the complexity compared to the complexity of a simple extension of the effective-resistance sampling (Spielman & Srivastava, 2011)?

1 comment

We thank the reviewer for recognizing the motivation for preserving the operator used by a trained model. We agree that extending effective-resistance sampling to sheaf Laplacians, or observing that nonnegative combinations of PSD edge operators remain PSD, would not by itself constitute a sufficient contribution. We will clarify the scope of our contribution and the implementation costs.

Contribution beyond sheaf effective-resistance sampling. Our contribution centers on post-selection coefficient calibration for a frozen, trained NSD model. Sheaf-ER is one compatible support-selection strategy. Given a retained support, Probe-LS jointly calibrates its nonnegative edge coefficients across the selected learned layers by matching the dense operators’ actions on random probes. These coefficients are shared across layers and are optimized independently of the inverse-probability weighting rule associated with support sampling. Accordingly, Probe-LS can also be applied to graph-ER supports.

The implemented probes are full-space Rademacher matrices, rather than hidden representations. We will therefore describe the method as randomized learned-operator matching and correct descriptions suggesting hidden-state-dependent calibration. We do not claim a new generic NNLS solver or a new global spectral-approximation guarantee. The contribution is the calibration formulation for frozen NSD inference, its connection to conditional representation and prediction stability, and the empirical separation of support selection from coefficient calibration. Our matched-support ablations show accuracy improvements from Probe-LS on both graph- and sheaf-based supports.

Relevance to machine learning. The setting starts from a model whose parameters and propagation operators have already been learned from data. The original network parameters are frozen, while the retained-edge coefficients are optimized to approximate its learned propagation operators. The absence of network retraining is a constraint of the post-training compression setting. Our empirical question is whether this operator-matching calibration better preserves the trained model’s behavior than sampling-based reweighting.

Computational complexity and comparison with ER sampling. Let NN be the number of nodes, MM the number of unique undirected edges, SS the retained-edge count, KK the selected-layer count, and dd the stalk dimension. Let zz bound the number of nonzeros in each layer’s sheaf Laplacian, with z=O((N+M)d2)z=O((N+M)d^2). Denote the ER projection count by PERP_{\mathrm{ER}}, the CG iteration count by II, the calibration probe count by PP, and the optimization-step count by TT.

The reported Table 1 configuration uses randomized-projection Sheaf-ER with chunked CG solves; it does not form the full pseudoinverse. Its dominant scoring cost is bounded by

O(KI(z+Md)PER),O\left(KI(z+Md)P_{\mathrm{ER}}\right),

rather than a dense-inversion cost of O((Nd)3)O((Nd)^3). The dependence on II remains solver- and conditioning-dependent.

Probe-LS precomputes the dense target responses and retained-edge probe actions. It then reuses the cached edge actions during optimization, rather than forming a dense least-squares design matrix. Including full-node response accumulation and residual evaluation, its cost is

K\left[zP+Sd^2P+T(S+N)dP\right] \right).$$ The cached retained-edge actions require $O(KSdP)$ storage, in addition to operators, probes, and workspaces. The reported Rademacher configuration uses $P=16$ and $T=50$. Thus, beyond operator construction and support sampling, the total cost is the sum of ER scoring and the calibration cost above. The support-ratio search adds $O(Q(M+q))$ under the sampling-cost model, where $Q\le25$ is the search-step limit and $q$ bounds the number of samples per attempt. Compared with a direct sheaf extension of ER sampling using the same score estimator, our method incurs the additional Probe-LS calibration cost and cache storage. We do not claim lower preprocessing complexity than ER sampling. This additional cost is intended to improve frozen-model fidelity; any inference-time benefit must be assessed separately. **Presentation.** We will number the key equations and distinguish the ideal NNLS formulation from the implemented regularized, box-constrained approximation: 50 Adam steps with learning rate $0.05$, regularization $10^{-4}$, and projection onto $[0,10]$.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.