When Is a Graph a Covariance? Bayesian Residual Propagation under Covariance Uncertainty
Abstract
Observing a prediction error at one node can help correct predictions elsewhere, but the benefit depends on the residual dependence between nodes. A graph suggests where that dependence might occur, yet does not establish its sign or strength. We develop a Bayesian model of residual covariance to determine how revealed errors should update a fixed feature-based predictor. For a fixed set of revealed nodes, we derive an exact identity for the change in expected squared error under linear residual propagation. The identity characterizes the optimal linear update and expresses the excess error of any other update as an exact quadratic. Under covariance uncertainty, the Bayes-optimal fixed linear update uses the posterior mean covariance. We average over four positive-semidefinite covariance families representing no dependence, positive dependence, negative dependence, and dependence whose sign can alternate with graph distance. Across eight graph benchmarks, four show posterior support within the distance-profile family for negative covariance between neighbors and alternating signs with distance. Among the evaluated methods, ours achieves the smallest worst-case recall gap to the best method on each graph. The method improves squared error over residual propagation on five of eight graphs, but performs substantially worse on one dense heterophilous graph. In these experiments, selecting the highest-posterior family performs similarly to model averaging.
Related
- Longitudinal Brain Aging in Covariance Space: Temporally Calibrated Bayesian Inference for Adaptive Covariance Operators
- Low-Latency LDPC Decoding Based on Consensus and Return Residual Belief Propagation
- No-Harm Physics-Informed Inverse Learning with Residual-Calibrated Uncertainty
- Machine learning-based thermoelectric materials screening with physical consistency and uncertainty propagation
- UAMP: Consistent video object segmentation with uncertainty-aware memory propagation
BibTeX
@misc{richardson2026when,
title = {{When Is a Graph a Covariance? Bayesian Residual Propagation under Covariance Uncertainty}},
author = {Robert Richardson},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.04989},
eprint = {2610.04989},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.04989},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - When Is a Graph a Covariance? Bayesian Residual Propagation under Covariance Uncertainty
AU - Robert Richardson
PY - 2026
DA - 2026/10/04
PB - arXiv
DO - 10.48550/arxiv.2610.04989
UR - https://arxiv.org/abs/2610.04989
AB - Observing a prediction error at one node can help correct predictions elsewhere, but the benefit depends on the residual dependence between nodes. A graph suggests where that dependence might occur, yet does not establish its sign or strength. We develop a Bayesian model of residual covariance to determine how revealed errors should update a fixed feature-based predictor. For a fixed set of revealed nodes, we derive an exact identity for the change in expected squared error under linear residual propagation. The identity characterizes the optimal linear update and expresses the excess error of any other update as an exact quadratic. Under covariance uncertainty, the Bayes-optimal fixed linear update uses the posterior mean covariance. We average over four positive-semidefinite covariance families representing no dependence, positive dependence, negative dependence, and dependence whose sign can alternate with graph distance. Across eight graph benchmarks, four show posterior support within the distance-profile family for negative covariance between neighbors and alternating signs with distance. Among the evaluated methods, ours achieves the smallest worst-case recall gap to the best method on each graph. The method improves squared error over residual propagation on five of eight graphs, but performs substantially worse on one dense heterophilous graph. In these experiments, selecting the highest-posterior family performs similarly to model averaging.
ER -