Trail-Weighted Influence Scores for Approximate Outcome Prediction in Bayesian Networks

Sahil Kumar Rajput; Randhir Kumar

cs.LGOct 19, 2026

Trail-Weighted Influence Scores for Approximate Outcome Prediction in Bayesian Networks

Authors: Sahil Kumar Rajput, Randhir Kumar

Abstract

We study trail-weighted pruning of evidence for Bayesian-network prediction. A traversal enumerates the active trails from each evidence node to the outcome, scores each trail by the product of its edge strengths, and drops evidence whose score falls below a threshold. For collider-free networks (chains and forks) over binary variables, we show that the trail score equals the exact correlation between a trail's endpoints, that a chain and a fork with equal edge strengths have identical joint distributions, and that the pruned posterior is within a computable sum of per-trail terms of the exact posterior when each dropped trail lies in its own branch of the outcome node. We prove this bound, check it exhaustively on all small trees, and show that it fails when dropped trails share a branch. In simulations on random trees, thresholding trail scores gives 1.4 to 13 times lower error than random pruning of the same size. We also apply the score, as an unproven heuristic, to seven bnlearn networks with colliders and loops. Keeping the top half of the active evidence by trail score gives lower error than random pruning on all seven, but it is not clearly better than a mutual-information ranking, and scoring costs more than the inference it saves on six of the seven, so we show no speedup. Models trained on trail, graph and information features and tested on networks they never saw do not beat the trail score or mutual information, but trail features carry most of what they use and clearly outperform generic graph features. A bound for general networks is left to future work.

Figures & tables

Figure 1: Mean posterior error (total variation) against threshold

\tau

on 14-node trees (3,000 trials, seed 12345), on a log scale. Factors give random error divided by trail-score error. With

\tau=0

(d-separation only) the error is zero and is not shown.

Regime	Dropped trails	Pairs ( $\tau>0$ )	Violations	Largest error/bound
12-node trees	each alone in its branch	19,681	0	below 1
12-node trees	share a branch	4,319	5	1.085
14-node trees	each alone in its branch	15,606	0	below 1
14-node trees	share a branch	2,394	0	below 1

Table 1: Violations of

|p-q|\leq B(D)

by whether the isolation condition holds.

Network	Nodes	Edges	Evidence per query	Active evidence (mean)	Queries
Asia	8	8	4	4.00	300
Sachs	11	17	4	4.00	300
Child	20	25	8	6.28	300
Insurance	27	52	10	9.20	300
Alarm	37	46	14	7.92	300
Hailfinder	56	66	14	9.37	100

Table 2: Benchmark networks and queries.

Figure 2: Left: mean KL divergence from the exact posterior when keeping 50% of the active evidence, on a log scale. Right: Spearman correlation between each score and the true relevance, with standard errors. Seed 12345; 300 queries per network, 100 for Hailfinder and Andes.

Network	Random	Hop distance	Mutual information	Trail score	Reference
Asia	0.0609	0.0326	0.0093	0.0087	$9.9\times 10^{-4}$
Sachs	0.0988	0.0523	0.0573	0.0557	0.0140
Child	0.0983	0.0226	0.0123	0.0104	0.0085
Insurance	0.0994	0.0273	0.0076	0.0032	0.0025
Alarm	0.1220	0.0164	0.0148	0.0102	0.0119
Hailfinder	0.1363	0.0382	0.0344	0.0303	0.0036

Table 3: Mean KL divergence from the exact posterior when keeping 50% of the active evidence.

Network	Hop distance	Mutual information	Trail score
Asia	0.52	0.73	0.61
Sachs	0.69	0.45	0.37
Child	0.51	0.62	0.63
Insurance	0.45	0.44	0.62
Alarm	0.59	0.47	0.61
Hailfinder	0.51	0.47	0.55

Table 4: Spearman correlation between each score and the true relevance.

Network	Exact	Trail	MI	Half	Edges (once)
Asia	0.66 (0.14)	0.08 (0.07)	0.06 (0.35)	0.58 (0.14)	10
Sachs	0.68 (0.18)	0.34 (0.40)	0.08 (0.40)	0.49 (0.16)	10
Child	1.21 (0.32)	0.93 (1.11)	0.56 (1.24)	0.79 (0.26)	17
Insurance	2.04 (0.51)	24.3 (28.0)	1.61 (3.31)	1.53 (0.66)	69
Alarm	2.12 (0.59)	2.44 (2.40)	2.43 (3.54)	1.63 (0.72)	48
Hailfinder	3.04 (1.11)	6.23 (4.21)	11.1 (8.84)	2.35 (1.42)	84

Table 5: Time in milliseconds, mean (standard deviation over queries). Exact: exact inference with all evidence. Trail: trail scoring. MI: mutual-information scoring. Half: inference with half of the active evidence kept. Edges: edge strengths, computed once per network.

Figure 3: Left: mean KL(

P(Y\mid E)\,\|\,

pruned) keeping 50% of the active evidence, per held-out network (log scale). The leave-one-out reference is not an upper bound. Right: ten largest mean absolute SHAP values of the gradient boosting model.

Network	MI	Trail	Ridge	MLP	RF	GB	Ref
Asia	.00732	.00709	.0175	.0162	.0206	.0210	.00056
Sachs	.0780	.0929	.0674	.0769	.0861	.0689	.0325
Child	.0137	.0154	.0131	.0151	.0216	.0166	.0116
Insurance	.00554	.00317	.00434	.0159	.0125	.00545	.00247
Alarm	.00858	.00499	.00681	.0107	.00752	.00875	.00458
Hailfinder	.00929	.00594	.00462	.00945	.00652	.00636	.00299

Table 6: Mean KL at 50% kept for models trained on the other six networks. Mean is the equal-weight average over networks. Ref: leave-one-out reference.

Features	Mean KL, 50% kept	Spearman
All 37	0.0181	0.55
Trail + query	0.0192	0.53
Graph + query	0.0340	0.36
Information + query	0.0187	0.47
Graph + information + query	0.0200	0.46
Trail + graph + query	0.0189	0.52

Table 7: Gradient boosting on feature subsets, leave-one-network-out.

Feature	Meaning	SHAP	Higher value
t_best_rho_nocoll	Best product score, active trails without collider	0.55	raises
t_best_rho	Best product score over active trails	0.25	raises
i_H_e	Entropy of the evidence node	0.23	raises
t_sum_rho	Sum of product scores over active trails	0.21	raises
t_n_blockers	Other evidence nodes on trails to $Y$	0.16	lowers
i_mi	Mutual information with $Y$	0.15	raises

Table 8: Ten largest mean absolute SHAP values.

Bayesian Networks

Bayesian networks represent joint probability distributions as graphs of variables and conditional dependencies, enabling inference under uncertainty.

See all 47 papers

Oct 9, 2026

How Well Do Prior-Data Fitted Networks Amortize Bayesian Inference?

Prior-data fitted networks (PFNs) are trained to approximate the Bayesian posterior predictive distribution (PPD) of a synthetic prior, yet results about the approximation quality are surprisingly thin. Taking an empirical risk minimization perspective, we decompose the deployment error of PFNs into prior, context, and amortization error, and measure the latter against a reference PPD under a realistic prior. Results show that PFNs generally recover the targeted PPD very well. Nevertheless, we find that parts of the residual amortization error persist, especially in rare settings under the prior pretraining distribution, even when scaling the model size, which manifests in disagreement between independently pretrained PFNs and leaves uncertainty about the predictor at inference time. As a remedy, we study multiple types of Bayesian model averages and find that these can consistently reduce this uncertainty and improve predictions up to full-size TabICLv2 models.

Manuel Hülskamp, Julius Kobialka, Emanuel Sommer +2

LMU Munich and Munich Center for Machine Learning

Bayesian Model Averaging Prior-Data Fitted Networks Amortized Inference Bayesian Inference

Ask PDF

May 8, 2026

Direct Bethe Free Energy Minimization for Bayesian Neural Networks

Bayesian neural networks are typically trained against the evidence lower bound (ELBO), whose Jensen gap closes only when the variational posterior is exact. We instead train by local consistency: gradient descent on the Bethe free energy, driving the belief at every factor toward agreement with its neighbours rather than placing a loss on the output. The resulting objective scores each observation by its own predictive density: a strictly proper rule whose optimum is the true conditional, for any likelihood with a tractable predictive convolution. Instantiated with a Gaussian last layer over a deterministic backbone, exact inference appears as one known corner: the neural-linear marginal likelihood. That corner is evidence-optimal; the shared-cavity, free-routed interior is predictive-optimal, improving NLL and calibration over it. This instance, SCROLL (Shared-Cavity fRee-rOuting Last-Layer), is a single-pass Bayesian neural network: batchable, any-likelihood, and implicitly empirical-Bayes-prior precision, observation noise, covariance, and backbone fit in one gradient pass. Prior work enters the interior only through the ELBO and its Jensen gap, even in this conjugate setting. At a single training run and forward pass per architecture-where the validation-tuned conventional references cross-validate

λ

and ensembles pay

5

50\times

at inference-a fixed SCROLL variant is best-or-tied on NLL and calibration on 7/8 UCI regression benchmarks, and best on 4/5 across three large tabular datasets (up to 515k examples) and two frozen text/vision embeddings.

Pavel Prochazka

Cisco Inc.

Bayesian Neural Networks Variational Inference

Ask PDF

Oct 12, 2026

Neural Bayesian Networks for Modular and Scalable Decision-Making Under Uncertainty

Bayesian Networks (BNs) are established tools for letting agents reason under uncertainty in sequential decision-making. They split a joint distribution into local conditional mechanisms arranged on a directed acyclic graph, which makes them modular, interpretable, and ready to perform probabilistic inference. Their classical formulation, however, has limitations in both expressiveness and scale: each conditional is usually stored as a table or a linear-Gaussian form, and inference evaluates the graph one node and one query at a time. In this paper we introduce Neural Bayesian Networks (NBNs), in which each conditional is a differentiable, tensor-valued mechanism, while the graph and its factorization are unchanged. NBNs retain the modularity and local mechanisms of BNs, can represent any learnable conditional distribution, and run natively on GPUs. We also release NBN, a PyTorch-based library for learning and inference in NBNs, together with a public benchmark. Our evaluation shows gains in both expressiveness and scale: NBNs fit distributions that classical BN libraries struggle to represent, and on large networks and large batches of queries they run two orders of magnitude faster thanks to GPU parallelization. NBN is available at https://github.com/Giovannibriglia/NeuralBayesianNetworks.

Giovanni Briglia, Marco Lippi, Stefano Mariani +1

University of Modena and Reggio Emilia, Reggio Emilia, Italy · University of Florence, Florence, Italy

Bayesian Networks Efficient Neural Network Inference

Ask PDF

Abstract

Bayesian Networks

Explore similar work

How Well Do Prior-Data Fitted Networks Amortize Bayesian Inference?

Direct Bethe Free Energy Minimization for Bayesian Neural Networks

Neural Bayesian Networks for Modular and Scalable Decision-Making Under Uncertainty