acceptodds
Under review as a conference paper at ICLR 2027

CEDRA: Doubly Robust Graph Aggregation under Selective Message Evaluation

Abstract

Modern graph learning increasingly operates in regimes where a receiver has many plausible senders, but evaluating every exact pairwise message is expensive. In this setting, the messages that are actually computed might not represent the candidate population that the graph operator is meant to summarize: selective evaluation can turn aggregation into a property of the acquisition rule rather than the declared graph target. We introduce Candidate-Evaluation Doubly Robust Aggregation (CEDRA), a principled aggregation framework that declares the candidate support and reference law before evaluation, predicts each candidate's contribution from pre-evaluation information, and then corrects the candidate-wide baseline using inverse-probability-weighted residuals from the evaluated messages. For the unnormalized first-layer pre-transform aggregate, we give an exact bias decomposition showing that Cedra-HT recovers the declared conditional mean when either the message model or the evaluation model is pointwise correct, under positivity, stable moments, separated nuisance estimation, and mean ignorability. We also derive Cedra-RA, a design-known risk-adaptive path that minimizes mean-squared error under an exchangeable residual model. In controlled recovery studies, Cedra-HT reduces RMSE by 59.1% relative to evaluated-message averaging and by 38.1% relative to matched inverse-propensity aggregation. Across 720 frozen cells on six public graph supports, Cedra-RA lowers RMSE by 22.10% relative to model-only aggregation and wins all 144 prespecified groups. CEDRA turns selective graph computation into a stated estimand, with a doubly robust correction, a risk-adaptive variant, and a matched empirical protocol to measure the gains when exact message evaluation is scarce. Code will be made available upon acceptance.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph neural networks, message passing, doubly robust estimation, inverse-probability weighting, edge-selection shift, candidate-population aggregation, propensity estimation, graph sampling

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_oUewOpenReview ↗
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 qq 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
AuthorsOpenReview ↗

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.

AuthorsOpenReview ↗

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.

AuthorsOpenReview ↗

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.

Reviewer_48sfOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies graph aggregation under selective message evaluation: a receiver ii has a candidate set CiC_i, but only a subset of exact pairwise messages MijM_{ij} is actually computed (Aij=1A_{ij}=1). The authors argue that when evaluation probabilities covary with message means, averaging the evaluated messages changes the population the aggregate represents.

CEDRA (1) declares the candidate support CiC_i and reference weights qijq_{ij} before evaluation, defining the estimand τi(q)=∑jqijmij\tau_i(q)=\sum_j q_{ij} m_{ij}; (2) fits a message model μ^ij\hat\mu_{ij} and an evaluation-probability model π^ij\hat\pi_{ij} from cheap pre-evaluation features; and (3) forms the AIPW-style estimator τ^iHT=∑jqijμ^ij+∑jqijAijπ^ij(Mij−μ^ij)\hat\tau_i^{HT}=\sum_j q_{ij}\hat\mu_{ij}+\sum_j q_{ij}\frac{A_{ij}}{\hat\pi_{ij}}(M_{ij}-\hat\mu_{ij}). Theorem 1 gives an exact conditional-bias decomposition into a product of the two nuisance errors plus a residual–selection covariance term cij/π^ijc_{ij}/\hat\pi_{ij}; under mean ignorability this yields double robustness (Corollary 1). The paper also proposes CEDRA-RA, which shrinks the correction along Bi+λRiB_i+\lambda R_i with λ∗=S0i/(S0i+S1i)\lambda^*=S_{0i}/(S_{0i}+S_{1i}), MSE-optimal under an exchangeable residual model.

Experiments are organized in three tiers: (Q1) target recovery on synthetic data and ten UCI feature tables, where CEDRA-HT reduces RMSE by 59.1% vs. the evaluated-message mean and 38.1% vs. Navip; (Q2) a frozen 720-cell matrix where CEDRA-RA reduces RMSE by 22.1% vs. model-only; (Q3) a matched prediction study on six public graphs, where no aggregation rule is distinguishable (Tolokers 67.8–68.7%, Minesweeper near chance). The appendix also retains earlier end-to-end studies (Optdigits prediction, CEDRA-Fuse, CEDRA-Guard) in which CEDRA does not beat its comparators.

Critical strengths

Clean problem formulation. Separating the reference law qq (who should count) from the acquisition probabilities π\pi (who was actually computed) is a useful conceptual distinction, and Proposition 2 gives a crisp selection-shift identity.

Honest, well-scoped theory. Theorem 1 keeps the covariance term cijc_{ij} explicit rather than burying mean ignorability in the assumptions. Appendix F’s demonstration that the baseline must span all candidates (not just evaluated ones) is pedagogically valuable, and the SN bias analysis in Appendix H is clear.

Critical weaknesses
  1. Limited methodological novelty. Estimator (2) is Robins et al. (1994) AIPW applied per receiver; the proof of Theorem 1 is three lines of conditional-expectation algebra. Proposition 1 assumes independence across candidates, residuals independent of the design, and common variance, so all graph structure is removed and λ∗=p\lambda^*=p is a classical shrinkage result. The claimed “graph-specific contract” is largely a reframing. More importantly, the related-work section omits the closest prior work: VR-GCN (Chen et al., ICML 2018) uses historical embeddings as control variates, giving a baseline-plus-sampled-residual structure nearly isomorphic to CEDRA; FastGCN/LADIES importance sampling is essentially pure HT. The paper needs to position itself against, and compare to, these methods.

  2. Predictive value is unproven, and the Q3 setup appears to be broken. In Table 3 every arm reaches only ~48% BA on Cora, ~51% on Roman-empire, and ~50% on Minesweeper (chance). Yet the authors’ own Tables 18/19 show standard GraphSAGE at 0.82 on Minesweeper and 0.75 on Tolokers. The matched pipeline (even-indexed columns as cheap features, frozen pair encoder, no real adjacency) seems to have destroyed almost all task signal. Comparing aggregation rules in a regime where nothing works cannot support conclusions about aggregation effects. The perfectly flat 50% curves for Minesweeper/Tolokers in Figures 4–11 suggest constant-class predictions.

Questions for authors
  1. Absolute accuracies in Q3 (Cora ~48% BA, Minesweeper ~50%) are far below standard GraphSAGE on the same datasets (Table 18: 0.82). Does this indicate the matched pipeline has lost nearly all task signal? What can aggregation-rule comparisons tell us in this regime?

  2. In Table 7, “outcome correct only” (RMSE 0.045) clearly beats “both correct” (0.127). Does this mean a correct IPW correction increases error in your setting? What is model-only RMSE in the controlled factorial?

  3. Please discuss the relationship to VR-GCN (control-variate aggregation) and FastGCN/LADIES (unbiased importance-sampled estimators), and explain why they are not included as comparators.

  4. Please give a concrete real system in which μ^(Wij)\hat\mu(W_{ij}) can be computed cheaply for all candidates while MijM_{ij} is expensive. If the message model is itself a neural network taking (xi,xj,sij)(x_i,x_j,s_{ij}), where does the cost gap relative to the message function come from?

7 comments
AuthorsOpenReview ↗

Author Response: Novelty, Estimation Guarantees, and Empirical Clarifications (1/2)

We thank the reviewer for recognizing the distinction between reference weights and acquisition probabilities, retaining residual-selection dependence in the bias analysis, and constructing the prediction baseline over the complete candidate support. We strengthened the methodological positioning, expanded related work, and added controlled downstream diagnostics.

W1: Novelty beyond AIPW and variance-reduced graph sampling

CEDRA does not claim to invent AIPW or control variates. Its contribution is to formulate selective graph-message computation as an explicit estimation problem and characterize its identification and risk properties. It comprises three elements:

(i) An acquisition-independent estimand. Candidate support and reference weights define the aggregate of interest before exact-message evaluation. This prevents the computational acquisition policy from implicitly redefining the target.

(ii) Identification under selective observation. Theorem 1 separates nuisance-model misspecification from residual-dependent selection, explaining when conditional target recovery holds and why an evaluated-only prediction baseline can retain selection bias despite accurate message prediction.

(iii) Risk-adaptive correction. CEDRA-RA derives the correction coefficient minimizing realized-aggregate MSE along the specified model-to-HT path under an exchangeable-residual model, guiding the choice between relying on predictions and applying inverse-probability residual correction.

This risk decision has direct empirical consequences. Across 720 frozen evaluation cells, 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 144/144 predefined design groups (Table 2). These are controlled estimation conditions, not independent datasets.

We expanded the comparison with VR-GCN, FastGCN, and LADIES (Section 2; Appendix M.1). VR-GCN uses historical activations to reduce stochastic GCN training error; CEDRA predicts exact candidate-pair messages from pre-evaluation information and analyzes aggregate recovery under selective acquisition. FastGCN and LADIES focus on sampling strategies, whereas our matched HT/IPW comparator holds acquisition fixed to isolate estimation improvements.

The novelty therefore lies not in the familiar baseline-plus-residual algebra, but in the declared estimation target, its recovery conditions, and the risk decision governing residual correction.

W2 / Q1: What does Table 3 establish if native GNNs achieve higher accuracy?

We recognize the concern about absolute classification performance. However, Table 3 evaluates aggregation methods within a matched candidate-message pipeline, whereas native-adjacency GraphSAGE changes the graph structure, feature access, and representation-learning procedure simultaneously.

This distinction matters empirically. Even when 100% of candidate messages are evaluated within Q3, the full-message reference achieves only 51.05%/51.34% balanced accuracy on Minesweeper for SAGE/GIN. Thus, the gap to native GraphSAGE cannot be explained solely by selective acquisition or residual correction. Q3 provides three controlled findings:

(i) Query-budget behavior. On Tolokers, CEDRA-HT obtains 68.05%/68.28% balanced accuracy with an expected 30% exact-message evaluation budget, compared with 68.56%/68.24% under full evaluation. This demonstrates close descriptive predictive performance while evaluating substantially fewer exact messages, without asserting statistical equivalence or runtime acceleration.

(ii) Head-policy sensitivity. A controlled factorial experiment shows that train-balanced cross-entropy raises CEDRA-HT Tolokers performance from 50.00%/50.37% to 68.01%/68.14%, with checkpointing and threshold selection fixed (Table 4; Appendix N). This explains the gap between Table 3 and earlier original-head sweeps without implying a CEDRA-specific gain.

(iii) Replication across previously unused splits. Six additional Tolokers split/seed pairs yield 67.52 ± 1.09%/67.53 ± 0.90% for CEDRA-HT, compared with 67.93 ± 0.77%/67.46 ± 1.32% for full-message evaluation. Together with the original splits, the study now reports nine Tolokers replicates.

Importantly, the primary estimation claims do not depend on Table 3 demonstrating the best classifier. Q1 directly tests aggregate recovery, including 59.1% and 38.1% RMSE reductions against the specified baselines. Q2 independently evaluates risk-adaptive correction. Q3 examines how the resulting estimators behave when embedded in a downstream classifier under matched acquisition.

The findings therefore support complementary conclusions: CEDRA improves aggregate estimation under the studied designs, while downstream predictive gains depend on the surrounding candidate-message pipeline and are not universally established.

AuthorsOpenReview ↗

Author Response: Novelty, Estimation Guarantees, and Empirical Clarifications (2/2)

W2 / Q2: Why can “outcome model correct only” (0.045) outperform “both correct” (0.127)?

The observed ordering is consistent with double robustness because identification guarantees do not imply a particular finite-sample RMSE ordering.

First, an important clarification: both 0.045 and 0.127 correspond to CEDRA-HT with residual correction. The 0.045 result is not a model-only estimate.

Under mean ignorability and a correct message model, the product-bias remainder vanishes even when the propensity model is misspecified. However, the propensity denominators still determine the residual-correction weights, so different propensity estimates can produce different finite-sample variances despite satisfying the relevant identification condition.

This distinguishes three properties:

(i) Conditional identification. Under the theorem's assumptions, correctness of either nuisance component can eliminate the relevant product-bias remainder.

(ii) Finite-sample risk. Correctness of both nuisance functions does not imply lower realized RMSE in every finite-sample configuration, because residual weighting affects variance.

(iii) Realized-aggregate recovery. Conditional target identification should not be confused with design-unbiased estimation of each realized candidate aggregate when acquisition propensities are misspecified.

We have clarified these distinctions in revised Table 8 and Appendix M.3. While differences in residual weighting offer a plausible explanation, the reported summaries do not isolate the exact variance mechanism responsible for the observed ordering. The model-only result in Table 2 belongs to a separate experiment and is not used to infer a factorial-specific comparison.

This distinction also motivates CEDRA-RA: satisfying an identification condition is not sufficient to determine the correction strength that minimizes estimation risk.

Q4: Concrete application with cheap candidate information and expensive exact messages

Document-pair reranking provides a concrete proposed interface for selective message evaluation.

Cached document embeddings can support candidate-wide lightweight message prediction, while exact pair representations may require substantially more expensive cross-encoder evaluations. CEDRA's formulation is applicable when such pre-evaluation information is available before selecting which exact pair messages to compute.

The relevant distinction is the relative cost of cheap prediction and exact evaluation, rather than the model family used for either operation.

For NN candidate pairs, evaluated fraction bb, cheap-prediction cost cμc_\mu, exact-message cost cMc_M, and additional overhead HH, selective evaluation reduces total computation when:

Ncμ+bNcM+H<NcMNc_\mu+bNc_M+H<Nc_M

We now state this break-even condition explicitly (Section 5; Appendix M.4), including calibration costs within the overhead or their amortization. This provides a concrete, testable criterion for computational benefit without interpreting reduced exact-message queries as a measured deployment speedup.

Closing clarification

CEDRA contributes an acquisition-independent estimation target, a characterization of its identification conditions, and a risk-adaptive residual-correction strategy. The theoretical analysis and recovery experiments directly support these contributions, while Q3 separately examines their predictive implications.

We respectfully submit that these constitute meaningful methodological and empirical contributions to selective graph computation, independently of an unsupported claim that the candidate-message pipeline universally outperforms unrestricted native-GNN classifiers. We hope the expanded analysis and experiments address the reviewer's concerns.

AuthorsOpenReview ↗

Follow-up: Additional VR-GCN Comparison and Measured Efficiency Results

Following our initial response, we conducted additional experiments specifically addressing these points.

Direct VR-GCN comparison. We implemented a VR-GCN-style control-variate adaptation under matched selective message evaluation. CEDRA-HT achieves 13.0% lower aggregate RMSE (0.1691 versus 0.1944) at comparable inference latency (114.3 versus 117.0 ms). While this adaptation does not reproduce the complete VR-GCN training algorithm, it provides a direct empirical comparison of the baseline-plus-residual approaches discussed in W1.

Measured computational efficiency. We additionally conducted wall-clock benchmarks across two message-evaluation workloads, three candidate sizes, and four evaluation budgets. At a 30% evaluation budget, CEDRA-HT achieves 2.14-2.59× inference-stage speedups over full-message evaluation, while reducing aggregate RMSE by up to 85.4% relative to model-only estimation. These measurements include exact-message computation, baseline prediction, aggregation, and downstream inference, with timings averaged over five repetitions. The revised Appendix M.4 reports the results and timing breakdown.

We believe these additions strengthen the empirical support for the methodological distinctions outlined in our original response. In particular, the VR-GCN comparison directly addresses the missing baseline identified in W1, while the measured latency results establish computational benefits under the evaluated workloads rather than relying solely on reduced query counts.

We would greatly appreciate the reviewer's assessment of these additional results, particularly whether the direct control-variate comparison addresses the concern raised in W1. We would also welcome any remaining questions or suggestions during the discussion period.

Thank you again for your time and consideration.

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

The paper studies graph aggregation when only a subset of candidate pairwise messages is computed. It proposes CEDRA, which predicts every candidate’s message from cheap features and corrects this baseline with inverse-propensity-weighted residuals on the evaluated messages (an AIPW estimator). Two variants are given: 1) CEDRA-HT: has a double-robust bias decomposition for the first-layer, pre-transform aggregate; 2) CEDRA-RA: a design-known shrinkage of the residual term that minimizes MSE under an exchangeable residual model. Experiments show lower aggregate-recovery RMSE on synthetic data, UCI feature tables, and a 720-cell matrix on six graph supports. Matched node-classification experiments show no consistent predictive gain.

Critical strengths
  1. The problem formulation is clear and reasonable. The paper separates the declared target population (qiq_{i}) from the acquisition rule (πijπ_{ij}), and shows that averaging only the evaluated messages changes the target.

  2. The aggregate-level theory is correct, and the experiments check both double-robust branches plus a controlled violation of mean ignorability.

  3. The paper reports negative results openly, including predictive losses and the far-selection case where CEDRA is worse.

Critical weaknesses
  1. Limited novelty. The estimator is the standard AIPW/doubly robust estimator applied to a weighted sum over candidates. Theorem 1 is the usual AIPW bias decomposition. Proposition 1 is a simple one-parameter shrinkage MSE calculation. The graph-specific contribution is mostly the framing, and the guarantee covers only the first-layer pre-transform aggregate, not anything the GNN actually outputs.

  2. No predictive benefit. In the matched study (Table 3), CEDRA variants do not beat model-only, evaluated-q, or HT/IPW in any consistent way. Minesweeper is at chance (~50%) for every arm. Absolute numbers are far below standard GNNs on the same datasets: Tolokers is ~68% here vs. ~74.7% for GraphSAGE in Table 18, and Minesweeper is ~50% vs. ~82.2%. On Optdigits, CEDRA is significantly worse than outcome-only, and CEDRA-Fuse/Guard do not beat GraphSAGE. Only 3 seeds are used. Better aggregate RMSE therefore does not translate into better models.

  3. No real selective-evaluation setting. All selection is imposed with known Bernoulli probabilities and synthetic or teacher messages. No application where messages are naturally expensive and selectively computed is evaluated, so the practical motivation is untested.

  4. Hard to read. The paper mixes many sub-studies (Q1–Q3, historical studies, Fuse, Guard, breadth panel). It uses heavy protocol language and leftover method names (DRAPE, AIPW). The main contribution and main evidence are hard to locate.

Questions for authors
  1. Beyond applying AIPW to a candidate-weighted sum, what is technically new compared with existing doubly robust estimators and Navip-style propensity aggregation?

  2. Why are the candidate-graph predictors so much weaker than standard GNNs on the same datasets (e.g., Minesweeper at chance)? Does this make the matched comparison uninformative?

  3. Can you report results with more than 3 seeds for Table 3?

5 comments
AuthorsOpenReview ↗

Author Response: Methodological Contributions and Additional Experimental Evidence (1/3)

We thank the reviewer for recognizing the target–acquisition distinction, the correctness of the aggregate-level theory, and the transparency of our empirical evaluation. We have strengthened the manuscript to clarify CEDRA's methodological novelty, distinguish aggregate estimation from downstream classification, and provide additional experimental evidence.

W1 / Q1: Contribution beyond AIPW and first-layer scope

CEDRA's contribution is not a new AIPW identity, but a distinct estimation problem, its identification analysis, and a principled risk-adaptive solution. Specifically:

(i) Target-explicit aggregation. CEDRA defines the reference aggregate over a fixed candidate support, independently of which exact messages are acquired. This separates what should be estimated from what is computationally observed, preventing selective acquisition from implicitly changing the estimand.

(ii) Identification under selective computation. Theorem 1 characterizes how nuisance-model errors and residual-dependent selection affect aggregate recovery. It establishes conditions for conditional target identification and explains why restricting the prediction baseline to evaluated candidates can preserve selection bias even with an accurate message predictor.

(iii) Acquisition-aware risk adaptation. CEDRA-RA derives a pre-evaluation correction coefficient that minimizes realized-aggregate MSE along the model-to-HT correction path under the stated exchangeable-residual assumptions. This addresses a distinct question from identification: how much residual correction should be applied when correction itself introduces variance?

These distinctions yield measurable improvements. CEDRA-HT reduces aggregate-recovery RMSE by 59.1% relative to evaluated-message averaging and 38.1% relative to matched Navip-style weighting. Across 720 frozen evaluation cells, 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 (Tables 1–2).

We have also expanded the related-work discussion to explicitly address VR-GCN, FastGCN, and LADIES (Section 2; Appendix M.1). We acknowledge their shared control-variate and sampling foundations while clarifying the different objectives. VR-GCN uses historical activations to reduce stochastic GCN training error; CEDRA instead predicts candidate-pair messages from pre-evaluation information and studies recovery of a declared aggregate under selective exact-message acquisition. Our HT/IPW comparator holds acquisition fixed to isolate augmentation and is not presented as a reproduction of these complete samplers.

Finally, we explicitly delimit Theorem 1 to the unnormalized first-layer pre-transform aggregate, without extending its guarantees to arbitrary nonlinear predictions.

AuthorsOpenReview ↗

Author Response: Methodological Contributions and Additional Experimental Evidence (2/3)

W2 / Q2: Scientific significance and interpretation of Table 3

We appreciate the concern regarding downstream classification performance and agree that Table 3 warrants careful interpretation.

Q1 and Q2 directly evaluate these contributions; Q3 examines their downstream predictive implications rather than serving as their defining measure of significance.

Three observations clarify what Table 3 establishes:

(i) Predictive performance under reduced exact-message evaluation. At an expected 30% exact-message evaluation fraction, CEDRA-HT achieves 68.05%/68.28% Tolokers balanced accuracy for SAGE/GIN, compared with 68.56%/68.24% when all candidate messages are evaluated. Thus, substantially fewer exact-message queries yield close descriptive predictive performance. We do not interpret this as statistical equivalence, measured runtime acceleration, or superiority over every selective comparator.

(ii) The native-GNN gap cannot be attributed to selective acquisition alone. Native GraphSAGE uses different adjacency, feature access, and representation training. Importantly, even the 100%-message reference within the matched Q3 pipeline achieves only 51.05%/51.34% balanced accuracy on Minesweeper. Consequently, the gap to native GraphSAGE cannot be attributed specifically to CEDRA's residual correction; the responsible component of the broader candidate-message pipeline is not isolated by this comparison.

(iii) The apparent head-policy discrepancy is experimentally explained. Table 3 employs the final balanced-head protocol, whereas the original sweeps use a different head policy. Holding checkpointing and threshold selection fixed, train-balanced cross-entropy raises CEDRA-HT Tolokers balanced accuracy from 50.00%/50.37% to 68.01%/68.14% for SAGE/GIN (Table 4; Appendix N). This resolves the numerical discrepancy without attributing the improvement specifically to CEDRA.

The key distinction is between estimating a declared aggregate accurately and optimizing an unrestricted classifier. Higher classification accuracy does not establish correct recovery of an aggregate under selective acquisition; similarly, an accurate aggregate estimator does not guarantee that a fixed downstream representation will outperform an unrestricted model.

CEDRA's scientific contribution is therefore supported by its identification analysis and directly measured recovery and risk improvements. Table 3 provides complementary evidence about how selective aggregation behaves in a matched downstream pipeline. We do not claim universal classification superiority.

The ICLR reviewer guidelines explicitly recognize that scientific significance does not necessarily require state-of-the-art results, but can arise from new, relevant theoretical or empirical knowledge. Consistent with this criterion, our objective was to establish (i) when a declared graph aggregate is identifiable under selective exact-message evaluation, (ii) how nuisance errors and acquisition affect its recovery, and (iii) how residual correction can be adapted to minimize estimation risk.

AuthorsOpenReview ↗

Author Response: Methodological Contributions and Additional Experimental Evidence (3/3)

W2 / Q3: Additional seeds

To strengthen the downstream evidence, we evaluated six previously unused Tolokers public split/seed pairs (4–9) using the unchanged final protocol, both backbones, and all nine aggregation arms.

CEDRA-HT achieves 67.52 ± 1.09% (SAGE) and 67.53 ± 0.90% (GIN) balanced accuracy, compared with 67.93 ± 0.77%/67.46 ± 1.32% under full-message evaluation.

Together with the original three split/seed pairs, this provides nine reported Tolokers replicates (Section 7.3; Appendix M.2.1, Table 24). The additional splits support the reproducibility of non-chance Tolokers performance and its close relationship to full-message evaluation. They do not establish a statistically significant CEDRA-specific classification advantage. Other Q3 datasets retain three seeds.

W3–W4: Acquisition assumptions, computational scope, and presentation

Controlled acquisition is an identification experiment, not a surrogate for deployed throughput. By exposing the otherwise unevaluated reference aggregate, it permits direct measurement of recovery error, both robustness branches, and violations of residual-selection assumptions.

Importantly, the 38.1% improvement over matched Navip-style weighting uses cross-fitted nuisance models rather than oracle nuisance probabilities. Thus, the evaluation tests aggregate recovery with learned nuisance functions, despite its experimentally controlled acquisition policy.

We have also clarified computational accounting (Section 5; Appendix M.4), separating candidate construction, encoder calibration, nuisance fitting, cheap prediction, exact-message evaluation, and downstream computation. The reported budget measures exact-message queries; end-to-end acceleration depends on satisfying the stated break-even condition and is not claimed as an observed result.

Finally, we reorganized the experimental narrative around Q1: identification and recovery; Q2: risk-adaptive correction; and Q3: downstream transfer. The revision also distinguishes the balanced-head results from the original-head sweeps and clarifies the role of historical Fuse/Guard experiments.

In summary, CEDRA establishes a target-explicit estimation framework with characterized identification conditions and a risk-adaptive correction strategy for selective graph-message computation. The theoretical analysis and recovery experiments directly support this contribution, while downstream prediction provides a complementary assessment of its implications.

We respectfully submit that this combination of new estimation knowledge, theoretical characterization, and controlled empirical validation establishes the scientific value of the work independently of unrestricted node-classification rankings.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.