- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
This paper introduces and proposes CEDRA to address graph aggregation when a subset of candidate pairwise messages can be computed. CEDRA fixes a candidate set and reference weights before evaluating, predicts all messages from "cheap" features, and corrects this baseline with an AIPW-style estimator. CEDRA improves aggregate-recovery RMSE on synthetic and graph-support benchmarks (Q1, Q2), but in matched node classification (Q3) CEDRA performance is comparable towards baselines.
Critical strengths
S1 The paper offers transparent/honest results, and seemingly does not shy away from presenting poor results. Furthermore, the narrative reinforces that results are only for the first-layer before any non-linearity aggregation.
S2 Separating reference weights from the acquisition probabilities is an understandable and interesting approach.
Critical weaknesses
W1 The paper novelty is limited. Control-variate neighbor sampling already combines a full-neighborhood baseline with a sampled correction (VR-GCN, Chen et al. 2018) yet the paper never discusses them, and the novelty relative to them is unclear.
W2 Paper markets cost-saving and efficiency, but does not report full wall-clock times.
W3 Experiment suites are not convincing enough, only six datasets none of which are large (especially since efficiency is a claim), I would prefer 5 or 10-seed results, and another backbone. CEDRA variants win on 2-3 of 6 datasets and I am not convinced enough. Additionally, the results of Table 3 do not always align with the figures in the appendix (e.g., Tolokers hovers around 68% but in figure 4 Tolokers is a flat 50%).
Questions for authors
Q0 Given the number of frozen protocols and studies, an anonymized code repository would substantially help reviewers assess reproducibility. Could the authors share one during discussion
Q1 Can the authors expand the results of their experiments: more datasets (including large ones like ogbn-arxiv); 5/10-seed runs; and report wall-clock time.
Q1a Can the authors include or compare their results to a control-variate sampler like VR-GCN (Chen, et al. 2018)?
Q2 Why are the predictions from Q3 (Matched Prediction) so far below standard GNNs? e.g., Cora and Roman-empire have balanced accuracies of ~48 and ~51 and are far below the paper's GraphSAGE results in Table 18 (~85, ~72).
Q3 Table 3 reports Tolokers ~68% but Figures 4/5 show ~50% for Tolokers. What is the reason for this discrepancy? Were the sweeps run on a different head than for the experiments in Table 3, and if so do sweep conclusions hold under the balanced head?
3 comments
Author Response: Experimental Consistency, Additional Results, and Methodological Clarifications (2/3)
Q2: Why does the matched Q3 pipeline underperform native-adjacency GraphSAGE?
The comparison changes the graph, available information, and representation-learning pipeline, not merely the aggregation estimator.
Native GraphSAGE uses the original adjacency and node features, whereas Q3 uses a feature-derived candidate graph, restricted feature access, and a frozen pair encoder. Consequently, the absolute accuracy difference cannot isolate the effect of CEDRA's residual correction.
The more informative control is the full-message reference within Q3, which retains the same candidate-message pipeline while removing selective acquisition. Notably, even this 100%-message reference achieves only 51.05%/51.34% balanced accuracy on Minesweeper for SAGE/GIN. Thus, selective acquisition cannot explain the native-GNN gap by itself; the present comparison does not isolate which other pipeline component accounts for it.
More fundamentally, CEDRA addresses selective aggregate estimation rather than unrestricted node-classification optimization. Its contributions are evaluated through three complementary questions:
(i) Q1: Identification and recovery. Can a declared aggregate be recovered when exact messages are selectively observed? CEDRA-HT reduces recovery RMSE by 59.1% relative to evaluated-message averaging and 38.1% relative to matched Navip-style weighting.
(ii) Q2: Risk adaptation. How should residual correction be weighted to control estimation error? CEDRA-RA achieves 0.09107 RMSE, compared with 0.11690 for model-only estimation and 0.14757 for full HT, improving upon model-only estimation in all 144 specified design groups.
(iii) Q3: Downstream transfer. How does selective aggregation affect prediction when the candidate-message interface is held fixed? On Tolokers, CEDRA-HT achieves 68.05%/68.28% balanced accuracy at an expected 30% exact-message evaluation budget, compared with 68.56%/68.24% under full evaluation.
Q3 therefore demonstrates close descriptive performance under reduced exact-message acquisition, rather than statistical equivalence, measured acceleration, or universal superiority over competing selective aggregators. Minesweeper remains less informative for differentiating aggregation methods because the matched pipeline performs near chance even under full-message evaluation.
The central empirical result is improved aggregate recovery and risk control under selective computation. Q3 complements this finding by characterizing its downstream behavior, rather than replacing the direct estimation evidence with an unrestricted classification ranking.
W1 / Q1a: Relation to VR-GCN and control-variate sampling
We appreciate this connection and have expanded the related-work discussion to explicitly address VR-GCN, FastGCN, and LADIES (Section 2; Appendix M.1).
We acknowledge the shared baseline-plus-residual construction; the distinction lies in the estimation objective and the guarantees established for it.
(i) Objective. VR-GCN uses control variates to reduce stochastic GCN training error. CEDRA instead targets a declared receiver-level aggregate whose reference weights are defined independently of exact-message acquisition.
(ii) Baseline construction. VR-GCN uses cached historical activations. CEDRA predicts candidate-pair messages from pre-evaluation information and constructs its baseline across the full candidate support, including unevaluated pairs.
(iii) Identification and risk analysis. CEDRA explicitly separates reference and acquisition laws, characterizes nuisance-model error and residual-dependent selection, and derives a correction coefficient that minimizes MSE along the specified model-to-HT path under its residual assumptions.
FastGCN and LADIES primarily address graph sampling. Our matched HT/IPW comparator holds acquisition fixed to isolate the estimator's contribution and is not presented as a reproduction of those complete sampling algorithms.
Our novelty claim therefore concerns target-explicit selective aggregation, its identification conditions, and risk-adaptive estimation, not the invention of a general control-variate identity.
A direct VR-GCN implementation accounting for historical-cache initialization and refresh would provide an additional systems comparison, rather than an equivalent estimator under the present experimental contract.
Author Response: Experimental Consistency, Additional Results, and Methodological Clarifications (3/3)
W2 / Q1: Backbone coverage, seeds, scalability, and computational cost
We have clarified the existing experimental coverage and expanded the downstream replication.
(i) Backbone coverage. The experiments already include SAGE- and GIN-style backbones, with separate results in Table 3 and matched aggregation comparisons.
(ii) Additional seeds. Six previously unused Tolokers split/seed pairs extend the evaluation to nine reported replicates, retaining both backbones and all nine aggregation arms. The additional results support consistent non-chance performance under the final balanced-head protocol. Other Q3 datasets retain three seeds.
(iii) Recovery robustness. The aggregate-estimation experiments span six public graph supports, two teachers, two candidate laws, two acquisition mechanisms, and three budgets, including 720 frozen evaluation cells. These assess estimator behavior under controlled variations in graph support and acquisition, rather than serving as independent dataset replications or evidence of large-graph throughput.
(iv) Computational accounting. The reported 30% budget measures exact pair-message queries after calibration, not elapsed wall-clock time. We now explicitly distinguish candidate construction, encoder calibration, nuisance fitting, cheap message prediction, exact-message evaluation, and downstream computation (Section 5; Appendix M.4).
The revised manuscript also states the break-even requirement for reduced exact-message evaluations to translate into lower total computational cost. Thus, we distinguish demonstrated query reduction from deployment-level acceleration, which depends on the relative costs of the individual operations. Full-pipeline wall-clock benchmarking and an ogbn-arxiv scalability experiment are not part of the reported evaluation.
Q0: Anonymized reproducibility archive
We have added the anonymized reproducibility repository link at the end of the abstract.
Presentation and experimental organization
We have revised the manuscript to make the progression of the scientific argument explicit:
(i) Q1 establishes aggregate identification and recovery under selective acquisition.
(ii) Q2 derives and evaluates risk-adaptive residual correction.
(iii) Q3 examines downstream prediction under matched acquisition budgets.
The revision distinguishes the final balanced-head results from the original-head sweeps, adds the controlled head-policy factorial experiment, reports six additional Tolokers splits, and separates the historical Fuse/Guard studies from the primary estimator comparisons.
In summary, CEDRA establishes a principled estimation framework for selective exact-message computation, with explicit identification conditions, characterized sources of bias, and risk-adaptive correction. Its aggregate-recovery and risk improvements are directly measured, while the downstream experiments separately assess predictive behavior under constrained acquisition.
We thank the reviewer for the detailed feedback, which has helped us strengthen experimental consistency, clarify the relationship to prior work, and present the contribution at its demonstrated scope. We hope these revisions address the concerns and provide a clearer basis for assessing the work's methodological and empirical significance.
Author Response: Experimental Consistency, Additional Results, and Methodological Clarifications (1/3)
We thank the reviewer for recognizing the target–acquisition distinction and the explicit first-layer scope of our theoretical analysis. We particularly appreciate the observation regarding the discrepancy between Table 3 and the original downstream sweeps. We have addressed this through a controlled head-policy factorial experiment, six additional Tolokers split/seed pairs, and clearer documentation of the experimental protocols. We also expanded the related-work discussion and clarified the computational claims.
W3 / Q3: Why does Table 3 report approximately 68% while the sweeps report approximately 50%?
The results correspond to different prediction-head protocols, and we have now experimentally isolated the source of the discrepancy.
Specifically:
(i) Table 3 uses the final balanced-head protocol: train-balanced cross-entropy, balanced-validation-NLL checkpointing/stopping, and validation-only threshold selection for Tolokers and Minesweeper.
(ii) Figures 2–11 report the original-head additive sweeps. These retain the original prediction policy throughout and should not be interpreted as measurements under the final balanced-head configuration.
(iii) Within each experiment, all aggregation arms share the same prediction-head policy and upstream inputs, preserving the validity of their matched comparisons.
To directly test this explanation, we conducted a controlled head-policy factorial experiment across all nine aggregation arms. Holding checkpointing and threshold selection fixed, changing the training loss to balanced cross-entropy raises CEDRA-HT Tolokers balanced accuracy from 50.00% to 68.01% for SAGE and 50.37% to 68.14% for GIN (Table 4; Appendix N).
These results closely reproduce the 68.05%/68.28% reported in Table 3, providing direct experimental evidence that the head policy explains the apparent discrepancy.
Importantly, we do not attribute this improvement specifically to CEDRA. The ablation isolates head-policy sensitivity, and the original-head sweep trends are not extrapolated to the balanced-head configuration.
We further evaluated six previously unused Tolokers public split/seed pairs (4–9) under the unchanged final protocol, retaining both backbones and all nine aggregation arms. CEDRA-HT achieves 67.52 ± 1.09%/67.53 ± 0.90%, compared with 67.93 ± 0.77%/67.46 ± 1.32% for full-message evaluation (SAGE/GIN).
Together with the original three pairs, this provides nine Tolokers replicates (Section 7.3; Appendix M.2.1, Table 24). The additional splits support reproducible non-chance Tolokers performance without establishing a statistically significant CEDRA-specific advantage.
The combination of protocol clarification, controlled ablation, and independent split replication directly addresses the numerical discrepancy and strengthens the interpretation of Table 3.