- Rating
- 2(−1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
he paper audits whether inference-time graph sparsification preserves a frozen GNN pipeline's predictions and reference explanations. A node passes when the class prediction is unchanged and normalized L1 drift, top-k overlap, and reference top-k mass retention meet prespecified tolerances. The framework reports overall, structural-stratum, and worst-stratum preservation, with exact finite-population lower confidence bounds obtained by hypergeometric inversion. A 280-run main matrix covers five datasets, thirteen sparsifier implementations and four explainers plus identity controls. Appendices examine reference fidelity, co-training, a GraphSAGE slice, tolerance sensitivity, seed variation, and an ogbn-arxiv pilot.
Critical strengths
- The deployment question is concrete and distinct from ordinary predictive accuracy. Reproducing a documented explanation is a legitimate reference-relative requirement, and the paper explicitly avoids claiming that the full-graph explanation is ground truth.
- The audit outcome, finite-population estimand, and statistical assumptions are clearly specified. Conditioning on fixed pipelines/outcomes makes uniform sampling without replacement hypergeometric; graph dependence between node outcomes does not invalidate this design-based argument. Bonferroni addresses simultaneous structural-group claims without assuming independent groups.
- The main evidence shows a substantial empirical gap: non-identity pipelines have mean prediction preservation .904 versus joint preservation .438, with considerable dataset/sparsifier heterogeneity. The audit is useful even though these metrics need not agree by construction; the measured size and structural distribution are the contribution.
- The supplementary controls materially strengthen the paper. Appendix E finds the gap among references passing sufficiency/necessity checks; Appendix F repeats a node-matched slice with GraphSAGE; Appendix D distinguishes co-trained matched-model and cross-model comparisons; Appendix G evaluates all 125 tolerance settings; Appendix H reports seed variability. These should be credited rather than requested as absent.
- The all-strata example responsibly separates lack of certification from actual poor preservation: a census follow-up can resolve uncertainty in a weakly sampled group. The scalable pilot and audit-time reporting help connect the framework to practical use.
Critical weaknesses
-
Several named sparsifiers are adapted proxies, limiting method/family-level conclusions (Appendix I). The “Spectral” implementation uses resistance-based deterministic top-k ranking rather than stochastic reweighted spectral sampling, and “t-spanner” is a sampled shortest-path-tree ranker without a guaranteed stretch property. Learned methods are mostly frozen off-design preprocessors. These are disclosed, but the main text and result labels should distinguish the evaluated adaptations from the original methods and their guarantees. The NeuralSparse companion is useful but cannot validate every learned/proxy implementation. The audit framework survives this issue; conclusions about canonical sparsifier families require narrower wording.
-
Drift should be decomposed into unavoidable pruned mass and changes on retained edges (Secs. 3, 5.2). In original edge coordinates, pruned edges contribute their full reference mass to L1 drift regardless of how retained-edge scores behave. This is relevant to preservation, not an error in the definition, but it can mechanically explain part of the failures. Reporting removed reference mass and retained-edge score movement separately would show what the additional audit reveals beyond pruning important edges. Degree associations may likewise reflect neighborhood size, support, or attribution concentration rather than a new structural causal effect.
-
Failure-mode “signatures” depend on priorities and tolerances (Sec. 5.2, Appendix G). A single dominant label is assigned in the order prediction, drift, overlap, mass. Consequently, 71% drift and near-zero mass erosion are priority-conditioned shares, not independent violation frequencies. Appendix G shows at least one mode ordering changes as tolerance changes. Include the marginal/co-occurring violation rates or state the priority explicitly beside every family-level interpretation.
-
Stochastic-explainer robustness and operating-point breadth remain limited. Fixed seeds define a valid reproducible pipeline and make identity tests meaningful, but Appendix H varies backbone and audit-node seeds, not independent explainer randomness. A cross-seed identity comparison would contextualize whether ordinary explainer instability is of similar magnitude; it is a robustness study rather than a prerequisite for the fixed-seed guarantee. The main pruning ratio is .5 and also sets k_i, so sparsity and top-k evaluation budget are coupled. The 125-setting tolerance sweep does not vary that retention ratio.
-
Reference preservation and deployment quality should remain separate throughout . A failed preservation audit can represent either a faithful changed explanation or degraded explanation quality. Appendix E appropriately studies reference fidelity but does not fully assess the sparsified explanation's fidelity to its own deployed model. The paper should present the audit as measuring change under a chosen behavioral contract rather than treating every failure as harmful explanation degradation. The exact confidence machinery is standard; the strongest novelty is its integration with a broad, interpretable empirical audit.
Questions for authors
- Can the main tables explicitly rename the resistance-ranking and sampled-tree adaptations and summarize how each differs from the original method? What actual retained edge ratios and weight conventions were achieved?
- From existing explanation vectors, how much L1 drift is contributed by reference mass on pruned edges versus retained-edge changes, and how does that decomposition vary by degree?
- Please report independent failure-indicator frequencies or their overlaps, alongside the priority-ordered shares. Are family signatures robust to changing that order?
- Are independent-explainer-seed identity results or retention-ratio sweeps already available? If not, please delimit the fixed-seed, rho=.5 claim rather than treating the tolerance sweep as a substitute.
- Is the targeted all-strata follow-up intended as descriptive evidence for selected pipelines, with confidence claims only within each fixed pipeline, rather than simultaneous post-selection inference across all 260? Please clarify the stated scope.
5 comments
Dear Reviewer,
We are still preparing the response and will submit it as soon as it is ready. Thanks!
W1/Q1,W3/Q3
Thank you for your suggestions and comments.
W1
We will distinguish the evaluated adaptations from the original methods in the main text and result labels.
For learned/proxy methods, we will state more clearly that the main experiments apply fixed edge scores to a separately trained full-graph GNN. Conclusions about individual methods and families will be limited to the implementations and deployment settings evaluated. We will clarify that the NeuralSparse companion experiment evaluates joint training only for NeuralSparse; it does not validate the other learned/proxy implementations or support family-wide conclusions.
Q1
We agree that the method names should make these adaptations clear. We will revise the names throughout the paper as follows:
- "Spectral" becomes "Resistance-ranked pruning." It keeps edges with the highest approximate effective-resistance scores instead of sampling and reweighting edges as in the original spectral method. The original spectral guarantee therefore does not apply.
- "-spanner" becomes "Sampled-tree pruning." It counts how often each edge appears in shortest-path trees rooted at sampled nodes and keeps the edges with the highest counts. It does not enforce the original method's stretch bound.
Weight conventions. Both adaptations assign weight 1 to retained edges. Resistance scores determine edge selection only; no inverse-probability reweighting is applied.
Across four explainers, preservation rates changed by at most 1.5 percentage points on Chameleon and 2 percentage points on Squirrel.
Actual retention. At the nominal budget , both methods retain the following numbers of edges.
| Dataset | Retained / original entries | Entry retention | Resistance-ranked: node pairs | Sampled-tree: node pairs |
|---|---|---|---|---|
| Cora | 5,278 / 10,556 | 50.0% | 50.0% | 50.4547% |
| CiteSeer | 4,552 / 9,104 | 50.0% | 50.0% | 50.2636% |
| PubMed | 44,324 / 88,648 | 50.0% | 50.0% | 50.0857% |
| Chameleon | 18,050 / 36,101 | 49.9986% | 54.1615% | 52.5453% |
| Squirrel | 108,536 / 217,073 | 49.9998% | 52.6511% | 51.3952% |
W3 / Q3
We examine twelve evaluated implementations: Random, degree-distribution pruning, DSpar, Resistance-ranked pruning, Sampled-tree pruning, GraphPRI, NeuralSparse, SparseGAT, SGS-GNN, SGCN, GraphUltra, and MoG. These span five datasets and four explainers (240 configurations), using the resistance-ranked results for Chameleon and Squirrel. We retain and and average percentages equally across configurations, as in the original failure-share table.
We measured how often each condition fails and how often multiple conditions fail on the same node. We also recomputed the assigned failure shares under all 24 priority orders to test whether the family differences persist. Changing the labeling order does not change joint pass/fail outcomes or preservation rates. For the 240 configurations specified above, the table compares individual failure frequencies with the shares assigned under the original priority:
| Violated condition | Among all audited nodes (%) | Among failing nodes (%) | Assigned share under the original priority (%) |
|---|---|---|---|
| Prediction preservation | 9.34 | 20.38 | 20.38 |
| Explanation drift | 49.62 | 90.93 | 71.78 |
| Top- overlap | 43.59 | 65.77 | 7.83 |
| Retained mass | 45.49 | 82.78 | 0.010 |
The original priority is prediction flip, drift, top- rearrangement, then mass erosion. On average, 89.06% of failing nodes violate multiple conditions; 80.83% violate both drift and retained mass. Mass erosion is therefore common, but rarely receives the assigned label because another condition fails earlier in the order. We will correct the statement that mass erosion itself is rare and include individual and overlapping frequencies alongside the assigned shares.
Across all 24 priority orders, drift's assigned share ranges from 4.13% to 90.93%, and mass erosion's from 0.010% to 82.78%. Two aggregate contrasts retain their direction across all orders: the evaluated learned/proxy implementations have more prediction-flip labels, and the structural implementations have more top- rearrangement labels. However, the differences range from 0.024 to 6.93 percentage points and from 1.44 to 5.10 points, respectively, and do not hold uniformly within every dataset or explainer. We will describe these as aggregate differences at the stated tolerances, rather than universal family signatures, and state the labeling order beside the corresponding interpretations.
follow-up and reconsideration
My concern that the evaluated spectral and t-spanner methods do not implement the original algorithms or preserve their guarantees remains unaddressed. This makes the conclusions about sparsifier families less convincing, so I am revising my rating from 3 to 2.