CS Paper Radar

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

Sahil Kumar Rajput, Randhir Kumar

cs.LG cs.AI ·submitted 2026-10-19 22:46 UTC · v1
theory

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.

Comment
Research paper on approximate Bayesian-network inference, evidence pruning, theoretical error bounds, and empirical evaluation

Closest papers

Nearest neighbours by meaning across the whole index.

Genetic Algorithms for Tractable Bayesian Network Fusion via Pre-Fusion Edge Pruning

cs.NE cs.LG ·2026-09-03 ·Pablo Torrijos, José A. Gámez, José M. Puerta, Juan A. Aledo
published similarity 0.56
Abstract · 9 pages. Presented at the Genetic and Evolutionary Computation Conference (GECCO 2025)

Bayesian Network (BN) fusion combines multiple input networks into a single structure, balancing dependency preservation with computational tractability. While unrestricted fusion retains all dependencies, it often results in overly complex networks with high treewidth, which affects inference scalability. Limited fusion mitigates this by pruning edges to control treewidth but risks overfitting to input-specific noise and omitting dependencies from the original BNs. This paper introduces a consensus framework that prioritizes shared structures among input networks while enforcing treewidth constraints, ensuring a good consensus. We propose genetic algorithms with advanced initialization, specialized operators, and a tailored fitness function. Additionally, we adapt existing methods to this problem and implement greedy baselines for benchmarking and further optimization. Experiments on synthetic and real-world BNs show the superiority of the proposed genetic algorithms over the adapted methods and greedy baselines.

0.62

CreateScore: Domain-Theory-Informed Bayesian Routing for LLM-Based CV Screening

cs.AI stat.AP ·2026-10-02 ·Rupsa Roy
code/data similarity 0.55
Abstract · 11 pages, 5 figures, 7 tables (Excluding Appendix). CreateScore Planner App GitHub repo link: https://github.com/rupsa-arc1-2441139/createsc…

Large language models (LLMs) can support rubric-based screening of CVs, but applying a high-capability model to every candidate and criterion is costly. We present CreateScore, a domain-theory-informed Bayesian network for criterion-level LLM routing. A hand-specified directed acyclic graph with Dirichlet-multinomial conditional probability tables converts CV evidence into posterior uncertainty; low-uncertainty decisions are resolved by a local 8B model and uncertain ones are escalated to a 120B reference model. The graph is causally motivated, but the system performs standard Bayesian conditioning, not causal inference. The escalation threshold is calibrated on a training fold (target: 70% resolved locally) and then frozen. On 200 synthetic Data Science CVs (139 training and 61 test candidates, five criteria), 77.7% of criterion decisions were resolved locally (237 of 305). Relative to a reference condition in which the 120B model adjudicated every criterion, routed escalation reduced token use by 65.2% and raised exact score agreement from 32.8% (8B alone) to 42.6% (95% CI 31.0-55.1%); at n = 61 the gain was not statistically distinguishable. The uncertainty signal did not, however, identify the decisions on which the 8B model erred: disagreement with the reference was 16.2% among escalated and 19.4% among locally resolved decisions (AUROC 0.47, 95% CI 0.39-0.56), no better than random selection. We also document how an earlier evaluation was invalidated when truncated reasoning-model outputs were silently replaced by local labels, and we recommend safeguards for cascade evaluation. CreateScore is supported as an auditable cost-reduction mechanism, not yet as a targeted error detector, and is not an autonomous hiring system.

0.44

LLM-Augmented Causal Discovery: Probabilistic Fusion of Edge Existence and Orientation

cs.AI ·2026-08-19 ·Neville K. Kitson, Anthony Constantinou
benchmark similarity 0.55
Abstract · Accepted as a poster at Probabilistic Graphical Models (PGM) 2026 Conference

Bayesian network structure learning (BNSL) from observational data struggles with orientation identifiability, while large language models (LLMs) offer broad but often unreliable causal knowledge. We propose combining these complementary sources through a novel representation, termed Probabilistic Dependency Graphs (PDGs). In a PDG, each edge is associated with a distribution over directed, undirected, and absent states, enabling fusion via weighted averaging. We evaluate this approach on 26 benchmark networks, combining ensembles of three BNSL algorithms (FGES, Tabu, PC) with three LLMs (Gemini, Claude, GPT) across multiple prompts and random seeds. A simple 50/50 fusion improves F1 over the better of either source alone in 22 of 26 networks, with a statistically significant mean improvement of $0.056$ $(p<0.001)$. Analysis reveals that the two sources play complementary roles: BNSL contributes a high-recall edge skeleton (80\% vs 60\% for LLM), while LLM contributes accurate edge orientation (96\% vs 77\% for BNSL). Our results show that representing both sources as probabilistic uncertainty over edge existence and orientation is a practical and effective way to improve causal graph accuracy.

0.36

Structural Fusion of Bayesian Networks with Limited Treewidth Using Genetic Algorithms

cs.NE cs.LG ·2026-09-09 ·Pablo Torrijos, José A. Gámez, José M. Puerta
published similarity 0.54
Abstract · 8 pages. Presented at the 2024 IEEE Congress on Evolutionary Computation (CEC 2024)

This paper introduces an evolutionary computation approach for consensus in structural Bayesian Network (BN) fusion under the constraint of limited treewidth. The consensus BN aims to reconcile multiple input BNs into a single one that retains key structural features present in the original networks. Treewidth, a graph-based parameter associated with computationally tractable inference, is utilized to restrict the complexity of the resulting network. A genetic algorithm is proposed to look for a BN that codifies as much information about the unrestricted fusion as possible while ensuring the treewidth restriction. Experimental evaluation demonstrates the genetic algorithm's ability to obtain consensus BNs with limited treewidth, providing a valuable tool for aggregating information from diverse sources while returning a computationally actionable model.

0.51

Exact Bayesian Tracking of Dynamic Network Topologies

eess.SP ·2026-09-10 ·Victor M. Tenorio, Elvin Isufi, Geert Leus, Antonio G. Marques
similarity 0.54
Abstract · Under review

Tracking the temporal evolution of network topologies is a fundamental challenge in social networks, epidemiology, and sensor systems, among others. This paper develops an exact Bayesian tracker for unweighted, directed graphs using nodal signal observations. This framework yields the full posterior probability distribution over network states at each time step, naturally enabling uncertainty quantification, prediction, and principled decision-making. We model the network dynamics as a Markov process on the Boolean hypercube, where edges transition independently according to a flip probability. For efficient computation, we cast the prediction step as a dyadic convolution, and leverage the Fast Walsh-Hadamard Transform to reduce the computational cost from $\mathcal{O} (4^k)$ to $\mathcal{O} (k 2^k)$, where $k$ is the maximum node degree. When the network transition probabilities are unknown, we develop an Expectation-Maximization framework to learn them from the observed signals. Comprehensive experiments on synthetic and six real-world datasets validate the proposed method and demonstrate its superior tracking accuracy, faster recovery from topological changes, and meaningful uncertainty estimates compared to state-of-the-art and classical baselines.

0.29

Canopy: Exploiting Piecewise Smooth Tree Priors for Multi-Fidelity Bandits

cs.LG cs.AI ·2026-09-24 ·Michael Jerge, Suman Jana
theory similarity 0.54
Abstract

Many LLM inference problems, including model routing, prefix-cache management, prompt trimming, and test-time search, can be viewed as optimization over a tree. This structure arises naturally from autoregressive generation: every prefix defines a node, and its continuations form a subtree below it. Internal nodes of the tree provide cheap but biased estimates of a region's value, while leaf evaluations are expensive but accurate. Hierarchical bandit methods can exploit this structure, but typically require a specific smoothness schedule to be specified in advance, even though real objectives are often only piecewise smooth and their optima may lie near sharp boundaries. We introduce CANOPY, a multi-fidelity tree bandit that learns where the smoothness prior is valid rather than assuming it globally. CANOPY uses cheap random-path probes to construct an online certificate of local aggregation bias, then directs expensive leaf evaluations toward cells where the certificate detects a smoothness violation. We prove fixed-budget and regret guarantees whose additional cost is additive in the number of discontinuities, recovering the smooth-tree rate when no violations are present and approaching structure-blind search as violations become dense. Across routing, top-$k$ identification, test-time search, caching, and prompt trimming, CANOPY consistently improves matched-budget performance, including $2.9\times$ higher top-10 recall on a 1000-model pool, $1.6\times$ more SWE-bench Verified issues resolved than best-of-$N$, and $3.6\times$ lower median time-to-first-token with prefix caching.

0.17

Efficiently Estimating Cycle Statistics on Graphs via Spanning Trees

cs.SI stat.CO ·2026-11-05 ·Josef Hoppe, Michael T. Schaub
code/data similarity 0.53
Abstract · 15 pages, 8 figures, plus appendix

Simple cycles encode feedback and alternative routes in networks and are important for routing problems, the convergence of dynamical processes on networks, message passing and belief propagation, or even static network characterizations such as structural balance in signed networks. Being able to assess and sample from the cycle structure of a graph is thus of interest in many analysis contexts. However, due to the combinatorial growth of the cycle space with graph size, the computational cost for such sampling is high. Therefore, we here introduce a sampling framework that enables us to sample from the cycle structure without enumerating all cycles. Specifically, the method draws uniform spanning trees and collects the fundamental cycles created by their non-tree edges, such that each tree provides an informative subset of simple cycles. Because cycles are included with unequal probabilities and are dependent within each subset, we formulate an inclusion-probability-based Horvitz-Thompson estimator, which we average over random subsets, a procedure we call Monte Carlo Horvitz-Thompson. For this, we sample multiple Horvitz-Thompson estimators and introduce a method to further subsample the individual estimators for increased computational performance. For sampling cycles, the estimator is unbiased if exact cycle inclusion probabilities are known. To extend the method to larger networks, we derive an efficient mean-field approximation for the inclusion probabilities and characterize the graph regimes in which it remains accurate. Experiments on synthetic and real-world networks demonstrate the computational scaling and statistical performance of the framework. We then illustrate the utility of Monte Carlo Horvitz-Thompson estimation by estimating cycle counts and cycle-level frustration statistics in signed spin systems. An implementation is available in the py-raccoon package.

0.68

Revealing Pathway Interactions in Network Computations with Complete Path Contribution

cs.LG q-bio.NC ·2026-11-19 ·Shenghua Liu, Youssef Faragalla, Surya Ganguli, Stephen A. Baccus
benchmark similarity 0.52
Abstract · 40 pages, 24 figures

Networks pass signals through many layers of interconnected units, so explaining what they compute means tracing how information travels from input to output and how pathways interact. Most existing approaches analyze only pairwise interactions between components such as units, layers or attention heads. Even when these measurements are combined post hoc into a circuit, they do not capture higher-order interactions along full causal chains (paths) from input to output, and so cannot address how exponentially many paths interact to construct network computation. This leaves a large set of mechanistic questions unanswerable, for example whether inhibitory pathways veto excitatory ones, and how the two combine to yield network decisions. To address this gap, we introduce Complete Path Contribution, a method to decompose the network output into mathematically complete contributions of individual paths to study path-level interactions directly and at scale. Partial summation then induces definitions of contributions for any circuit at any granularity level, with completeness guaranteed at every level. We further present an efficient algorithm that identifies the $k$ strongest paths without examining all of them, with runtime empirically linear in $k$ rather than exponential in depth. By applying Path Contribution to benchmark image classification networks, we quantify excitatory-inhibitory interactions and show how they collectively construct network decisions at a level of detail previously unmeasurable. Furthermore, in an interpretable model of the mouse retina, it reveals how dynamic receptive fields emerge from excitatory-inhibitory interaction motifs among pathways between different cell types in response to time-varying natural stimuli. Overall, Path Contribution reveals how a network's causal pathways interact at scale to transform input to output.

0.22