acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph Neural Networks, Probabilistic Graph Learning, Gaussian Markov Random Fields, Differentiable Inference, Structured Prediction

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_SXZqOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes Variable Elimination Networks for recovering graph states from sparse observations. Shared neural networks parameterize local Gaussian potentials, which are assembled into a positive-definite precision matrix. Observations enter through Gaussian likelihood factors, and differentiable elimination produces conditional means and covariances. The paper establishes basic structural properties and evaluates the method across simulated and measured recovery tasks, with additional analyses of extrapolation, uncertainty, and repeated-query efficiency.

Critical strengths
  1. The architecture provides a coherent formulation of graph-wide conditional recovery, with guaranteed positive definiteness and interchangeable inference backends.

  2. The evaluation is extensive, including five-seed results, physical estimators, component ablations, uncertainty analysis, and detailed latency measurements.

  3. The paper reports its limitations transparently, including weaker results on native DGMRF tasks and restrictions associated with caching, graph structure, and distribution shift.

Critical weaknesses
  1. The methodological advance over existing learned Gaussian models needs sharper differentiation. Exact differentiable inference with learned Gaussian potentials was already explored by [1] in their work on deep Gaussian CRFs. The theoretical propositions here mainly establish standard properties of the construction.

  2. The observation interface is ambiguous. Appendix B states that the source network receives all node channels, apparently including observations that are subsequently inserted as likelihood factors. This complicates the prior/posterior interpretation and the meaning of the “No observation” ablation.

  3. The DGMRF comparison changes several components simultaneously. DGMRF uses a linear mean and Gaussian-likelihood training, whereas VEN uses a nonlinear source network and primarily MSE training. Consequently, the results do not isolate the contribution of the proposed precision parameterization.

[1] Chandra, Siddhartha, and Iasonas Kokkinos. "Fast, exact and multi-scale inference for semantic image segmentation with deep gaussian crfs." European conference on computer vision. Cham: Springer International Publishing, 2016.

Questions for authors
  1. Does the source network receive the observed state values used in the likelihood? Are these values also removed in the “No observation” ablation?

  2. Are there existing comparisons that match the source-network capacity and training objective between VEN and DGMRF? How much of the reported advantage remains under those controls?

  3. Which precision and observation-noise parameters are learned under MSE, and what determines the absolute covariance scale? Appendix E partially addresses calibration, but this aspect of the probabilistic interpretation remains unclear.

2 comments
AuthorsOpenReview ↗

Clarifying VEN's Observation Interface, Controls and Architectural Contribution

Thank you. We clarify the observation interface, controlled comparison, covariance scale and architectural contribution.

  1. Observation interface and "No observation". In the inspected current and archived task implementations, the target-state values used in the likelihood are not inputs to the source. Appendix B's "all node channels" wording is imprecise; we will replace it with explicit task-specific inputs.

GasLib uses boundary-flow measurements/indicators and static attributes in the source; pressure observations enter through the likelihood. SimBench/CINELDI use P/Q pseudo-measurements, their masks and static attributes; voltage/angle PMUs enter separately. LeakDB/AQI use time/calendar context for the prior mean; EEGBCI learns a prior mean. Thus the prior is conditional on available context, before incorporating target-state evidence.

"No observation" removes the target-state likelihood, returning μ0=Q−1b\mu_0=Q^{-1}b (or mm when b=Qmb=Qm). Target observations are already absent from the source; context covariates remain. It therefore measures the contribution of target-state sensors given those covariates. Five passing interface checks on archived models and inspection of data construction/forward paths support this separation. We will clarify the ablation's definition.

  1. Matched source capacity and training objective. We added a GasLib comparison using the authors' DGMRF/FlexLayer precision operator with the same one-hidden-layer SiLU source-MLP architecture, unobserved-node MSE, observation likelihood, data/splits/masks, optimizer, training budget and validation-selection rule. The frozen five-seed test gives NRMSE 0.04828±0.000720.04828\pm0.00072 for VEN versus 0.54057±0.155270.54057\pm0.15527 for DGMRF under this shared protocol; VEN is lower in all five pairs. Stored best-validation checkpoints were evaluated in float64 without retraining or reselection. Across ten checkpoints, precision- and covariance-form posterior means agreed within 2.1×10−102.1\times10^{-10} in the numerical audit. The gap persists after controlling the source-capacity and objective differences raised in the review.

  2. Learned parameters and covariance scale. MSE backpropagates through the conditional mean into the active precision-factor networks, source/prior parameters and observation precision. GasLib/EEGBCI/AQI learn scalar node/edge terms; LeakDB learns edge/boundary terms; SimBench/CINELDI learn 2×22\times2 edge blocks with reference-bus anchoring. Observation precision is τ=ϵ+softplus⁡(ρ)\tau=\epsilon+\operatorname{softplus}(\rho): one shared scalar for scalar tasks, one per state channel for SimBench/CINELDI. Positivity floors and reference constraints are fixed.

With Q≻0Q\succ0 and R≻0R\succ0, these parameters define a normalized conditional Gaussian. Calibration concerns agreement with the data distribution. Mean MSE alone does not identify absolute covariance scale. Writing Q+=Q+S⊤R−1SQ_+=Q+S^\top R^{-1}S, we have μ=Q+−1(b+S⊤R−1y)\mu=Q_+^{-1}(b+S^\top R^{-1}y) and Σ=Q+−1\Sigma=Q_+^{-1}. Whenever common rescaling is permitted, (Q,b,R)↦(cQ,cb,R/c)(Q,b,R)\mapsto(cQ,cb,R/c) for c>0c>0 leaves μ\mu unchanged and maps Σ\Sigma to Σ/c\Sigma/c. Initialization, constraints and regularization can select a numerical scale, but do not establish calibration.

Appendix E already reports uncertainty evaluation. For unobserved validation entries VV, the scale is α=∣V∣−1∑i∈V(zi−μi)2/Σii\alpha=|V|^{-1}\sum_{i\in V}(z_i-\mu_i)^2/\Sigma_{ii}, with Σcal=αΣ\Sigma_{\rm cal}=\alpha\Sigma and unchanged mean (channelwise for SimBench). In the reported marginal-NLL training setting, SimBench raw NLL changes from 0.1390.139 to −0.520-0.520 and 95% coverage from 99.96%99.96\% to 96.54%96.54\%, with NRMSE 0.17855→0.180170.17855\to0.18017 (five-seed means; different training budgets). We will explicitly distinguish exact inference within the learned Gaussian model from empirical uncertainty calibration.

  1. Architectural contribution. VEN defines a neural architecture for graph-wide conditional state updates. Shared node/edge maps learn attribute-dependent interaction blocks and assemble Q(G,a)=blkdiag⁡(Di)+∑eBe⊤WeBeQ(G,a)=\operatorname{blkdiag}(D_i)+\sum_e B_e^\top W_eB_e. Separate paths encode sample context bb and query evidence (S,y,R)(S,y,R); elimination composes these factors into the joint state update. The factor maps share parameters across graph sizes, and a fixed attributed graph permits precision-factor reuse across contexts and queries.

Chandra-Kokkinos [1] predicts A(I),B(I)A(I),B(I) from each image and solves [A(I)+λId]s=B(I)[A(I)+\lambda I_d]s=B(I) for pixel-class scores. VEN specifies different factor generators, parameter sharing and input dependencies for graph-state recovery. Relative to local MPNNs, elimination permits conditioning beyond a fixed hop radius; relative to [1], the distinction is the learned factor architecture and conditional-query computation.

[1] Chandra & Kokkinos. Fast, Exact and Multi-Scale Inference for Semantic Image Segmentation with Deep Gaussian CRFs. ECCV 2016.

Thank you for clarifying which inputs enter the source network. The task-specific explanation resolves my concern about the same target measurement being used twice and makes the “No observation” ablation interpretable. I still view the contribution as an architectural advance over existing Gaussian CRFs, and I would limit the conclusion from the matched comparison to GasLib.

Reviewer_iBe6OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper introduced VEN which learns positive local Gaussian potentials and composes them by exact variable elimination. And Schur, Cholesky, and Woodbury provide equivalent inference backends to prove its well posed and permutation equivariant. And tested the method in 6 different tasks especially in GasLib benchmark.

Critical strengths

1.VEN returns an exact joint Gaussian posterior rather than node embeddings, and sparse measurements enter as likelihood factors with an explicit noise covariance.

2.The experiments use five seeds, external AC and hydraulic residual checks, a conditioning audit and paired bootstrap intervals, and the authors report unfavorable results openly.

Critical weaknesses

1.Most learned baselines are 2–3-layer GCN/GINE, which cannot reach sensors more than a few hops away and are therefore inherently weaker than an explicit global solver on long-range tasks.

2.The five runs vary initialization, minibatch order and training-time masking, while the data split, generation seed and test masks are fixed . The reported deviations therefore do not capture uncertainty over data splits, the choice of topology, or sensor placement, which appears to be fixed in SimBench and CINELDI.

Questions for authors
  1. Can you use baseline such as deeper GCN and general graph transformer such as Graphormer or GraphGPS during all tasks to have a better comparison?

2.Can you run your benchmark with different data splits to make your result more convince?

2 comments
AuthorsOpenReview ↗

Stronger Baselines and Robustness to Data Splits and Sensor Placement

Thank you for the positive assessment and the suggestions on baseline strength and experimental variability. We added the following comparisons and sensitivity analyses.

  1. Deeper local GNNs and a global-attention baseline. We evaluated task-adapted GraphGPS using PyG GPSConv, with a GINE local branch and global multi-head attention, on GasLib, SimBench and measured AQI. Inputs, observation masks and task losses follow the corresponding protocols. Depth was selected on validation from {2,3,5,8}\{2,3,5,8\} and frozen at 8/3/2, respectively. Five training seeds give the following test mean ±\pm sample SD (VEN versus GraphGPS):
  • GasLib, NRMSE: 0.04654±0.001150.04654\pm0.00115 versus 0.07938±0.006010.07938\pm0.00601.
  • SimBench, NRMSE: 0.1786±0.00070.1786\pm0.0007 versus 0.20676±0.013340.20676\pm0.01334.
  • AQI, PM2.5 RMSE: 22.968±0.10322.968\pm0.103 versus 24.523±1.03424.523\pm1.034.

These results test the gains against a learned baseline with global information access, beyond the receptive-field restriction of shallow local GNNs.

For local baselines, we evaluated GCN and GINE at depths {2,3,5,8}\{2,3,5,8\} on the same three tasks: 24 validation configurations at training seed 7. For GasLib, GCN validation NRMSE at depths 2/3/5/82/3/5/8 is 0.762/0.647/0.376/0.2490.762/0.647/0.376/0.249, respectively; eight layers was selected on validation. Validation selected GasLib GCN-8, SimBench GINE-8 and AQI GINE-3. We then froze these configurations and ran five-seed tests, obtaining 0.49673±0.008380.49673\pm0.00838, 0.42993±0.005260.42993\pm0.00526 and 33.056±4.15333.056\pm4.153, respectively, using the task metrics above. VEN remains lower in each comparison. AQI selects three layers after including deeper candidates in the search. These additions cover three of the six core tasks, spanning gas, power and measured air-quality recovery.

  1. Data splits and observation-placement variability. We agree that the original five-run SD measures training variability conditional on fixed data, splits and test-mask realizations. It does not estimate uncertainty over all these choices. We will make this interpretation explicit.

Fixed test masks across runs do not mean one sensor placement for all snapshots. The audited GasLib and SimBench datasets contain 1,221 distinct observation sets in 1,221 snapshots and 512 in 512, respectively. Inspection of current and archived CINELDI generators also shows per-snapshot PMU resampling. Its 12 settings correspond to four feeders and three PMU densities, rather than twelve fixed sensor layouts.

We additionally evaluated three random splits (seeds 7/42/123) and two new data/measurement realizations (seeds 42/123) on each of GasLib and SimBench. Training seed 7 and the validation-selected architectures were held fixed. Each VEN/GraphGPS pair shares the same data, split and observations.

Across the three random splits, mean ±\pm sample SD NRMSE is:

  • GasLib: 0.04117±0.005750.04117\pm0.00575 for VEN versus 0.04869±0.009780.04869\pm0.00978 for GraphGPS.
  • SimBench: 0.17524±0.005930.17524\pm0.00593 versus 0.19538±0.024090.19538\pm0.02409.

Here SD is across splits, distinct from the training-seed SD above. Across the two new data/measurement realizations, mean NRMSE is 0.04098/0.087570.04098/0.08757 for GasLib and 0.17711/0.202850.17711/0.20285 for SimBench (VEN/GraphGPS).

VEN is lower in 4/5 GasLib pairs and 5/5 SimBench pairs. We retain the exception: GasLib split 123 gives 0.042610.04261 for VEN versus 0.037700.03770 for GraphGPS. Thus the advantage persists on average and in most tested realizations, not uniformly in every split.

These tests quantify split and data/measurement sensitivity on fixed benchmark topologies; they are not a full crossing of training and data seeds. Random splits also differ from temporal extrapolation. Topology shift is evaluated separately in Appendix H. We will correct Appendix B's SimBench split description to the recorded 332/77/103 samples (approximately 65/15/20), replacing the stated 60/20/20.

Reviewer_iBe6OpenReview ↗

Reply to Authors

Thank you for the additional experiments and for reporting the GasLib exception. The clarification on per-snapshot sensor resampling resolves that part of my second concern.

VEN remains ahead, but the gap depends on baseline strength and split: on GasLib it drops from 89.5% to about 41% against GraphGPS, and to about 15% under random splits, within one standard deviation. Please update the abstract and frame the GasLib advantage as robustness to chronological shift.

For the next version, I think you should extend the depth grid beyond 8 (GasLib validation error is still decreasing), include Ridge and the physical estimators in the split experiments, and cover the remaining three tasks.

I will keep my score.

Reviewer_xDPSOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes Variable Elimination Networks (VEN), a graph neural architecture that learns local Gaussian potentials and performs differentiable Gaussian elimination for graph-wide conditional inference. The method constructs positive-definite precision matrices and incorporates sparse observations through Gaussian likelihood factors. Theoretical analysis establishes well-posedness, permutation equivariance, and inference-backend equivalence. Experiments demonstrate competitive state recovery across several public benchmarks and improved size extrapolation. However, the methodological novelty and generalizability beyond favorable Gaussian inference settings remain insufficiently established.

Critical strengths
  1. The paper provides a principled integration of learned graph potentials and exact Gaussian inference, offering an alternative to conventional local message-passing architectures.

  2. The experiments cover multiple physical and sensor-network tasks, with consistent improvements over the evaluated baselines. The size-extrapolation experiments and computational analyses provide useful evidence of the method's practical potential.

Critical weaknesses
  1. The methodological novelty is limited. Learning Gaussian potentials and performing differentiable inference through Schur complements or Cholesky factorization are closely related to existing GMRF, Gaussian CRF, and differentiable optimization frameworks. Several theoretical properties follow directly from standard matrix identities. The paper does not sufficiently establish a fundamental architectural distinction from these approaches.

  2. The experimental advantages are concentrated in relatively structured, low-fill graph inference settings. Several physical benchmarks rely on simulator-generated targets, while improvements on measured datasets are comparatively modest. Moreover, DGMRF outperforms VEN on its native fixed-mask and larger scalar-field benchmarks. These results limit the evidence for broader superiority and generalization.

  3. The scalability and long-range advantages depend strongly on restrictive conditions. The main architecture assumes reusable, sample-independent precision, and dense covariance caching requires quadratic memory. The theoretical all-pairs sensitivity guarantee applies only to positive scalar couplings and does not ensure meaningful influence over long distances. Performance under dynamically changing interactions and less favorable graph structures remains insufficiently validated.

Questions for authors
  1. What is the fundamental methodological distinction between VEN and existing learned Gaussian CRF/GMRF models with differentiable inference?

  2. How do the authors explain VEN weaker performance than DGMRF on its native and large-scale benchmarks?

  3. Can the authors provide stronger evidence of generalization to changing graph structures and sample-dependent interactions?

  4. How does VEN scale when dense covariance caching is impractical, and does its long-range advantage persist under weak graph coupling?

1 comment
AuthorsOpenReview ↗

Clarifying VEN’s Architectural Contribution and Supporting Evidence

Thank you for recognizing VEN as an alternative to local message passing. We address your four questions.

  1. Architectural contribution. VEN's contribution is an architectural design for graph-wide conditional recovery: shared neural maps learn local interactions, and variable elimination composes their factors into a joint state update. Shared nonlinear node/edge maps produce positive-definite DiD_i and positive-semidefinite WeW_e, assembling Q=blockdiag⁡(Di)+∑eBe⊤WeBeQ=\operatorname{blockdiag}(D_i)+\sum_e B_e^\top W_e B_e. With sample source bb and query (S,y,R)(S,y,R), the output is μ=(Q+S⊤R−1S)−1(b+S⊤R−1y)\mu=(Q+S^\top R^{-1}S)^{-1}(b+S^\top R^{-1}y). One layer can thus condition on distant evidence without stacking one-hop MPNN layers; its numerical cost still depends on the graph.

Graph DGMRF [1] uses Q=G⊤GQ=G^\top G, where GG is a product of Gℓ=αℓDγℓ+βℓDγℓ−1AG_\ell=\alpha_\ell D^{\gamma_\ell}+\beta_\ell D^{\gamma_\ell-1}A with layerwise scalar parameters (DD: degree matrix). VEN learns heterogeneous block interactions from local attributes through shared neural maps. This changes the factor generators, parameter sharing and precision structure: VEN's original QQ is edge-local, whereas DGMRF's LL transforms can introduce up-to-2L2L-hop couplings. Both support global conditional inference.

Deep Gaussian CRF [2] predicts quadratic and linear terms from each image; [3] combines learned denoising potentials with unrolled inference. In VEN, graph attributes generate QQ, sample context generates bb, and query evidence enters through (S,y,R)(S,y,R). On a fixed attributed graph, changing context or observations leaves the precision factors reusable. Obtaining this layer from those networks requires changing factor-generation modules and their input dependencies. This specifies the architectural distinction beyond the shared Gaussian inference step.

Section 5.2 tests a consequence: training on 16-node chains and testing at 256 gives five-seed NRMSE 0.00662±0.000770.00662\pm0.00077 for VEN versus 0.06817±0.001530.06817\pm0.00153 for GCN-3. This is a controlled, fixed-interaction size-transfer test.

  1. DGMRF comparison and empirical scope. The native DGMRF benchmarks complement our main graph-recovery evaluation. DGMRF performs better on Mix32, California and Wind; we retain these results. The additional GasLib comparison examines performance under a shared conditional-recovery protocol.

The GasLib comparison uses the authors' DGMRF/FlexLayer precision operator, with the same source MLP, unobserved-node MSE, observation likelihood, data/splits/masks, optimizer, training budget and validation-selection rule. Evaluating the frozen checkpoints in float64 gives five-seed test NRMSE 0.04828±0.000720.04828\pm0.00072 for VEN versus 0.54057±0.155270.54057\pm0.15527 for DGMRF under this shared protocol; VEN is lower in all five pairs.

On measured AQI, five-seed PM2.5\mathrm{PM}_{2.5} RMSE is 22.968±0.10322.968\pm0.103 for VEN versus 24.523±1.03424.523\pm1.034 for validation-selected, task-adapted PyG GraphGPS. Together, these results demonstrate value across simulated and measured recovery tasks.

  1. Changing topology and sample-dependent interactions. The main model reuses Q(G,a)Q(G,a). Appendix H already evaluates sample-conditioned factors yielding Q(x,G,a)Q(x,G,a) on WCCI/Grid2Op. Unseen-topology NRMSE decreases from 0.5617±0.05000.5617\pm0.0500 to 0.4776±0.01960.4776\pm0.0196 (15.0%); cross-season NRMSE decreases from 0.4936±0.00790.4936\pm0.0079 to 0.4789±0.00890.4789\pm0.0089 (3.0%). All are five-seed results. Mean training time rises from 999 to 2,111 s. This demonstrates an evaluated extension to changing interactions, with an accuracy-reuse tradeoff. We will distinguish this extension and the two distribution shifts more clearly.

  2. Scaling and useful long-range influence. Dense covariance caching is optional. Appendix F uses sparse factorization and posterior-mean computation on Wind: 126,652 nodes, 379,933 edges, 0.6435±0.02340.6435\pm0.0234 s, with 0.94 GB peak RSS in the seed-7 audit. This computes the mean without forming a dense covariance. Sparse cost depends on fill-in; Appendix K's chain/grid measurements document this dependence. Wind establishes a large-graph operating point, rather than efficiency on arbitrary high-fill graphs.

The positive-scalar theorem guarantees nonzero influence, not a distance-independent magnitude. In our 243-setting sweep, effective chain ranges at normalized influence 10−310^{-3} vary from 3 to 138 hops. Separately, for SimBench nodes at least 13 hops from sensors, five-run mean NRMSE is 0.2320 for VEN versus 0.7068 for the best evaluated three-layer GNN. These results quantify both weak-coupling attenuation and useful distant conditioning in the evaluated regime.

[1] Oskarsson et al., Scalable Deep Gaussian Markov Random Fields for General Graphs, ICML 2022. [2] Chandra & Kokkinos, Fast, Exact and Multi-Scale Inference for Semantic Image Segmentation with Deep Gaussian CRFs, ECCV 2016. [3] Vemulapalli et al., Deep Gaussian Conditional Random Field Network, CVPR 2016.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.