A Bayesian neural network keeps a probability distribution over its weights instead of a single best setting. It reports uncertainty by checking how much plausible weight settings disagree. How wide that distribution should be depends on how much independent evidence the training data carries. On a graph, such as a citation network or a relational database read as rows joined by foreign keys, training examples are not independent. Neighboring nodes share labels, and a single heavily connected "hub" node appears inside the input neighborhood of hundreds of training nodes. The standard training loss for a graph neural network (a model that updates each node's representation by aggregating its neighbors' features) still sums per-node losses as if every node were a fresh, independent observation. So the weight posterior built from that loss counts the same evidence many times. It becomes too narrow, and the model becomes overconfident in exactly the places where the graph is most redundant.
This proposal measures that overcounting directly from the training graph and corrects the weight posterior for it. The tool is the sandwich covariance from composite-likelihood statistics, with cross-node terms limited to pairs whose receptive fields overlap. The correction needs no held-out labels. It is a matrix rather than a single temperature, and it makes a falsifiable prediction: the right amount of posterior widening should grow with label density, autocorrelation, and degree concentration. That gives a concrete, testable reading of whether graph Bayesian deep learning shows a "cold posterior effect", a "warm posterior effect", or both.
Core Claim
The node-classification loss of a message-passing network is a pseudolikelihood: a product of local conditional distributions over overlapping subgraphs. Relational Learning with One Network: An Asymptotic Analysis shows that such estimators remain consistent and asymptotically normal on a single large network, provided degrees are bounded and dependence decays with distance. Their spread, however, is not the inverse curvature that a naive Bayesian or Laplace posterior uses.
Let $\ell_i(W)$ be the loss of labeled node $i$ and $s_i = \nabla_W \ell_i$ its gradient at the trained weights $\hat W$. Let $H = \sum_i \nabla^2_W \ell_i$ be the summed curvature. Let $\mathcal{N}_{2L}(i)$ be the set of labeled nodes within $2L$ hops of $i$; for an $L$-layer network, two receptive fields can overlap only when the nodes are at most $2L$ hops apart. The dependence-aware score covariance is
$$J = \sum_i \sum_{j \in \mathcal{N}_{2L}(i)} \kappa(d_{ij})\, s_i s_j^{\top},$$
where $d_{ij}$ is hop distance and $\kappa$ is a taper that equals 1 at distance 0. The proposal replaces the usual posterior covariance $H^{-1}$ with $H^{-1} J H^{-1}$. A scalar summary of the overcounting is the dependence inflation factor
$$\rho = \operatorname{tr}(H^{-1}J)/p,$$
with $p$ the number of weights being made probabilistic. When nodes are independent and the model is well specified, $J \approx H$ and $\rho \approx 1$. Positive correlation among the scores of nearby training nodes pushes $\rho$ above 1, which means the naive posterior is too narrow by roughly that factor.
The claim is fourfold. First, $\rho$ can be estimated cheaply and is materially above 1 on densely labeled relational benchmarks. Second, it rises with degree concentration and label autocorrelation. Third, applying the matrix correction improves calibration and out-of-distribution detection beyond what a validation-tuned scalar temperature achieves. Fourth, it does so in label-scarce regimes, where no reliable validation set exists to tune that temperature.
Where This Sits in Prior Work
Two papers supply the motivating statistics.
The single-network asymptotic analysis establishes consistency and normality for maximum pseudolikelihood under weak dependence. It also documents an efficiency gap relative to full maximum likelihood. It does not translate this into a covariance for neural network weights, and that translation is what we do. Its weak-dependence and bounded-degree assumptions also constrain us: hubs violate them, and we treat that as something to test rather than assume away.
Learning relational probability trees builds decision trees over aggregated neighbor attributes. It showed that degree disparity and autocorrelation inflate apparent significance, and it fixed this with permutation tests that hold graph topology fixed. We address the same inflation in weight space, analytically rather than by permutation.
Two papers motivate the likelihood-side diagnosis. Bayesian Neural Network Priors Revisited studies why posteriors must often be tempered to $T<1$ to perform well. It attributes this to prior or likelihood misspecification and fixes the prior side with heavy-tailed and correlated priors, at roughly 10,000 GPU hours of sampling. Feature Preserving Shrinkage on Bayesian Neural Networks via the R2D2 Prior designs a shrinkage prior and names graph networks as future work. Both papers act only on the prior. Our argument is that relational data carry a specific, measurable likelihood misspecification, evidence overcounting, which no prior can repair. We include an R2D2 prior arm to check that the two effects are separable.
Three graph uncertainty methods are the competitors. Bayesian Graph Convolutional Neural Networks for Semi-Supervised Classification samples graphs from a community-structure model and applies dropout at test time to approximate weight uncertainty. Graph Posterior Network diffuses per-class density evidence with Personalized PageRank into a Dirichlet distribution over class probabilities, while keeping its weights deterministic. Hierarchical Uncertainty-Aware Graph Neural Network learns attention-based uncertainty at local, community, and global scales and uses PAC-Bayes bounds only as an analysis tool. None of the three asks whether the weight posterior is correctly scaled given that the training nodes are dependent.
Research Program
Estimator. We first build the estimator for the parts of the network where a Laplace approximation is affordable: the last layer, and with a Kronecker-factored curvature approximation, all layers. Per-node gradients come from one backward pass per training node. The double sum in $J$ is computed as $S^{\top} K S$, where $S$ stacks the per-node gradients and $K$ is a sparse, tapered hop-distance matrix over labeled nodes, built from powers of the adjacency matrix up to $2L$. On large graphs we estimate $J$ from a random subsample of anchor nodes $i$ while summing over all of their neighbors $j$. This keeps the cost linear in the number of anchors.
We study three choices of taper: truncation at $2L$, a linear decay, and a decay extended beyond $2L$. The extended version captures label autocorrelation that reaches past the receptive field. Theory says this autocorrelation matters only through the residual scores, and the experiment checks whether that holds.
Ground truth by simulation. Weight-level coverage can only be checked when the true weights are known. We therefore simulate labels from a known teacher on real graph topologies, including the Facebook network used in the asymptotic analysis (7,315 nodes, 46,817 edges) and Erdős–Rényi graphs. The teacher is either an identifiable linearized graph convolution or a templated Markov network. We vary autocorrelation strength, the degree distribution (from bounded to power-law), and the fraction of nodes that are labeled. The quantity of interest is the empirical coverage of 90% credible intervals for the teacher's weights, under the naive posterior and under the corrected one. We also map how far the estimator itself degrades as hubs break the bounded-degree assumption.
Real benchmarks. We then apply the correction to GraphSAGE-style networks on RelBench classification tasks, using the relational deep learning codebase, and on ogbn-arxiv and ogbn-products from the Open Graph Benchmark. For contrast with sparse-label settings we use Cora, CiteSeer, and PubMed through CogDL.
Ablation. Degree-aware loss reweighting, which down-weights nodes by how much their receptive field overlaps with others, is a crude fix that lives entirely in the loss. Running it isolates whether the covariance correction matters beyond reweighting.
Baselines
The naive reference points are a deterministic network with softmax outputs and a standard Laplace posterior at $T=1$ built from the same trained weights. The second is exactly our method with $J$ replaced by $H$, so comparing against it isolates the cross-node terms. That ablation is the key test of the proposal's central ingredient. A second ablation keeps only the diagonal terms $i=j$ of $J$. This is the standard sandwich correction for heteroscedasticity and model misspecification, without any graph dependence.
The strongest practical competitor is the same Laplace posterior with one scalar temperature tuned on the validation set for negative log-likelihood. It shares our compute, weights, and curvature, and it differs only in that it uses validation labels while we do not. It is the alternative most likely to match us.
The other uncertainty competitors are these. Deep ensembles use five members with the same tuning budget per member. Test-time dropout follows the setup of the Bayesian GCN paper. Graph Posterior Network is the strongest single-pass method; on perturbed features and unseen classes it reports over 20% better out-of-distribution detection than baselines, and under 5% accuracy loss when 80% of nodes are perturbed. HU-GNN reports a 20–35% reduction in expected calibration error relative to strong baselines.
Every method uses the same splits and the same backbone where applicable. Hyperparameter search budgets are matched in GPU hours. Accuracy is not the target, but we confirm that no method loses discriminative performance. On relbench-trial the reference points from Grables are 0.7009 AUC for LightGBM, 0.6860 for a pure GNN, and 0.7486 for the LightGBM-plus-GNN-embedding hybrid. On ogbn-products, GraphSAGE reports 78.50% test accuracy against 94.09% training accuracy. No reported calibration or out-of-distribution result was found on Lacuna for RelBench or OGB, so we establish those baselines ourselves.
Beating the strongest baseline means two things. On densely labeled graphs, the method must match the validation-tuned temperature in calibration error and negative log-likelihood. On graphs with few labels or no usable validation set, and in out-of-distribution detection for new entities, it must beat that temperature with non-overlapping seed intervals. It must also beat ensembles and Graph Posterior Network on out-of-distribution AUROC, the area under the curve that measures how well uncertainty separates in-distribution from out-of-distribution nodes, on at least the dense-label benchmarks.
Why not just…?
Why not just tune a posterior temperature on validation data? This is the real threat. On densely labeled graphs with large validation sets, a scalar temperature may recover most of the calibration gain, and we will say so if it does. The proposal still differs in three testable ways. It needs no held-out labels, which matters in the semi-supervised regime: with 5 labels per class on Cora, the setting where the Bayesian GCN paper reports 74.6% accuracy against 70.0% for a plain GCN, a validation set is too small to tune reliably. It widens the posterior along specific directions, those of weights driven by hub-shared features, rather than uniformly. And it predicts the size of the tuned temperature in advance. If the measured $\rho$ tracks the validation-optimal temperature across graphs, the method at minimum explains the phenomenon. If the matrix correction beats the scalar on out-of-distribution detection, it does more than explain it.
Why not just use heavy-tailed or shrinkage priors? Bayesian Neural Network Priors Revisited shows that better priors fix much of the temperature problem in fully connected networks, but that correlated priors make it worse in ResNets. So the prior is not the whole story. Evidence overcounting scales with the number of correlated training nodes, while a prior's influence shrinks as the data grow, so on large graphs no prior can offset it. The experiments test this directly: we cross R2D2 and Gaussian priors with corrected and uncorrected likelihoods and check whether the two effects are additive.
Why not just reweight the loss by degree or neighborhood overlap? Reweighting is cheap and in the spirit of the relational probability tree literature, so we include it as an ablation. It changes the point estimate. It can also only correct the scale of the posterior, not its shape, because cross-node score correlations point in particular directions in weight space. If reweighting matches the full correction on synthetic coverage, the simpler method wins, and we will report that.
Why not just use evidential outputs like Graph Posterior Network, or ensembles? Graph Posterior Network gives single-pass uncertainty but keeps its weights deterministic, and it diffuses evidence under the assumption that neighbors share classes. Ensembles measure disagreement between independently trained models but inherit whatever overconfidence the likelihood creates in each member. Neither ties uncertainty to the effective number of independent observations. On the synthetic graphs, credible-interval coverage under increasing degree concentration will show whether either method stays calibrated while the naive posterior does not.
Decisive Checks
The first decisive check is synthetic. As label density and degree concentration increase, the coverage of 90% credible intervals for the teacher's weights should fall well below 90% under the naive posterior and stay near 90% under the correction. The measured $\rho$ should follow the pattern implied by the asymptotic theory, approaching 1 as dependence vanishes. If coverage does not improve, the core claim is false.
The second check is a cross-benchmark regression. The estimated $\rho$ is plotted against the validation-optimal temperature for each of Cora, CiteSeer, PubMed, ogbn-arxiv, ogbn-products, and the RelBench classification tasks. A strong correlation would show that overcounting explains why graph posteriors need tempering, and in which direction.
The third check tests whether the gain comes from graph dependence specifically. We compare the full correction against the diagonal-only sandwich and against degree reweighting, on calibration and on out-of-distribution detection for entities arriving after RelBench's temporal cutoff. These tests separate a benefit from graph dependence from a generic misspecification fix.
The fourth check covers the regime where the assumptions break. On power-law graphs, where hubs violate bounded degree, we report how the estimator's variance and the resulting coverage degrade.
References
- Relational Learning with One Network: An Asymptotic Analysis
- Learning relational probability trees
- Bayesian Neural Network Priors Revisited
- Feature Preserving Shrinkage on Bayesian Neural Networks Via the R2D2 Prior
- Bayesian Graph Convolutional Neural Networks for Semi-Supervised Classification
- Graph Posterior Network: Bayesian Predictive Uncertainty for Node Classification
- Hierarchical Uncertainty-Aware Graph Neural Network
- RelBench: A Benchmark for Deep Learning on Relational Databases
- Open Graph Benchmark: Datasets for Machine Learning on Graphs
- Grables: Tabular Learning Beyond Independent Rows