Covariance-complement uncertainty head
Implementation & benchmark of arXiv:2607.28706 — Accelerated Random-Sweep Gibbs Sampling for Gaussian Graphical Models via Dual Normal Factor Graphs
Source paper: Accelerated Random-Sweep Gibbs Sampling for Gaussian Graphical Models via Dual Normal Factor Graphs arXiv:2607.28706 ⓘ · analyzed Aug 31, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Represent uncertainty of a graph-structured neural feature field through dual covariance rather than explicitly storing a dense primal covariance. Recover calibrated primal marginal variances from dual statistics using the paper's covariance-complement identity.
Formulas
Mathematical statement
Let X be the primal graph field and tilde_X = B tilde_Y the dual auxiliary field, where B is the oriented incidence matrix. Proposition 2 states that D_s to the power minus one-half times Cov(X) times D_s to the power minus one-half, plus D_s to the power one-half times Cov(tilde_X) times D_s to the power one-half, equals I. For diagonal D_s = diag(d_s,1, ..., d_s,n), the i-th diagonal entry gives Var(X_i) = d_s,i - d_s,i squared times Var(tilde_X_i). In the homogeneous case d_s,i = s squared, this is Var(X_i) = s squared - s to the fourth power times Var(tilde_X_i). The identity follows from Woodbury applied to Q inverse = (D_s inverse + B D_sigma inverse B transpose) inverse. The resulting parameterization stores only per-node, per-channel dual variances and computes primal marginal variances elementwise, avoiding a dense n by n covariance.
Implementation notes
Integrate this into the uncertainty head of a graph neural network or graph VAE. Let the GNN output a mean feature tensor mu with shape n by d and dual log-variance parameters a with shape n by d, instead of a dense n by n covariance. Set d_s,i = softplus(b_i) + epsilon and parameterize the dual variance as v_tilde,i = d_s,i inverse times (1 - sigmoid(c_i)); this guarantees that v_tilde,i is positive and less than d_s,i inverse, and therefore gives positive primal variance v_i = d_s,i - d_s,i squared times v_tilde,i. Use v_i in the Gaussian negative log-likelihood, uncertainty-weighted reconstruction loss, or heteroscedastic node-regression head. If dual samples are available, estimate v_tilde,i online with an exponential moving average of (tilde_x_i - mean_tilde_x_i) squared; otherwise use the neural prediction. Add a consistency loss L_cc = (1 divided by n d) times the sum over i and c of (v_i + d_s,i squared times v_tilde,i - d_s,i) squared, with a small coefficient such as 1e-3. Never form a dense covariance matrix. On small graphs, compute exact diagonal entries of Q inverse by Cholesky solves and compare them with the predicted diagonal. Begin with synthetic cycle and grid graphs, node regression targets, and a two-layer GCN. Compare a diagonal Gaussian head, a dense exact Gaussian head, and this dual-complement head. Success means memory scaling of O(n d) rather than O(n squared d), lower negative log-likelihood than the diagonal baseline, and improved calibration measured by negative log-likelihood and expected calibration error.
Verification
This idea has not been verified yet.
Verification happens in two stages: Stage 1 — a mechanism check on a toy system confirms the claimed mathematical phenomenon reproduces; Stage 2 — a benchmark implements the idea on a real (small) neural network task and compares it against a tuned baseline over 8 paired seeds with a permutation test.
Artifacts
Artifacts unavailable.