CEDRA: Doubly Robust Graph Aggregation under Selective Message Evaluation

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.