Variable Elimination Networks: Learning Gaussian Potentials for Graph-Wide Conditional Inference

In many networked systems, measurements are available at only a subset of nodes, while the states of different nodes remain interdependent across the graph. Therefore, accurate recovery of the unobserved states requires sparse local evidence to be integrated with dependencies that may span long graph distances. Message-passing neural networks access distant nodes through repeated local updates, tying long-range conditioning to propagation depth. We introduce the Variable Elimination Network (VEN), a graph neural architecture that learns local Gaussian potentials and composes them through exact differentiable Gaussian elimination. Shared node and edge maps construct a positive-definite precision Qθ (G, a), while a sample-dependent source map constructs bθ (x, G); optional measurements enter as Gaussian likelihood factors, and Schur, Cholesky, or Woodbury backends return the joint posterior mean and covariance. We establish positive definiteness and permutation equivariance, prove all-pairs source sensitivity for connected scalar systems with positive couplings, and show equivalence of the three inference back- ends. Across six public water, power, gas, EEG, and air-quality state-recovery tasks, five-seed experiments show that VEN improves over the strongest evaluated baseline on every task. On the GasLib benchmark, VEN reduces NRMSE by approximately 12.1% relative to a pressure-conditioned hydraulic MAP estimator, by 85.6% relative to ridge, and by at least 89.5% relative to the learned graph baselines. Controlled size extrapolation and component ablations associate the gains with graph-wide conditioning, observations, and learned coupling. Cached inference supports repeated sparse conditional queries at throughput comparable to shallow GNNs in the evaluated moderate-size systems. Additional large sparse- field, citation-graph, and task-matched DGMRF comparisons delineate the regime in which reusable, low-fill Gaussian graph systems are effective. Code is available at https://anonymous.4open.science/r/VEN.