acceptodds
Under review as a conference paper at ICLR 2027

Inducing Triplet Regions for Amortized Kikuchi Learning in Discrete Bayesian Network Models

Abstract

Learning parameters in large discrete Bayesian networks (BNs) from massive incomplete data is challenging due to the high computational cost of repeatedly estimating joint marginals. Standard ELBO-based amortization, such as amortized variational inference (VI), scales well but suffers from restrictive posterior factorization assumptions. To overcome this, we introduce riplet egion Induction-Constrained eural ikuchi Learning (TRNK), a non-ELBO framework grounded in Kikuchi free energy and region graph approximations. TRNK captures higher-order variable interactions for improved accuracy and scalable amortized learning. By leveraging BN structural and factor information, it identifies effective triplet base regions and induces higher-order regions to enhance approximation fidelity and provide orthogonality regularized region interactions. Under these region constraints, TRNK trains an evidence-conditioned deep neural network to produce overlap-consistent region beliefs for each partially observed instance, amortizing inference overhead across the entire dataset. Empirical results show that TRNK significantly outperforms amortized VI and approximate EM baselines in accuracy and efficiency. Furthermore, our region induction algorithm surpasses Bethe and other well-established region-graph alternatives on most benchmarks.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Bayesian networks, variational inference and learning, amortization, belief propagation

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_HzNEOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes TRNK, a method for approximate inference and parameter learning in discrete Bayesian networks with a supplied graph structure. It constructs overlapping triplet and four-variable regions, uses a neural network to predict local probability distributions, and enforces agreement between overlapping regions. The method is evaluated on fixed-parameter inference and learning conditional probability tables from incomplete data.

Critical strengths

1- The paper addresses an important computational problem. Repeated inference over missing variables is a major part of learning Bayesian-network parameters from incomplete data. Sharing an inference network across records is a useful approach to reducing this cost.

2- The consistency construction is a meaningful contribution. Rather than relying only on a penalty to encourage agreement between overlapping regions, the method builds this agreement into its parameterization. Proposition 2 provides a formal result for the specified consistency constraints.

3- The experiments cover several network families and include relevant baselines. The paper reports inference comparisons on eight networks and parameter-learning comparisons on sixteen. The reported results show lower validation prediction error on twelve of sixteen networks and lower probability-table error on fifteen of sixteen. These are promising results, although the evaluation limitations below affect their interpretation.

4- Some comparisons help isolate the proposed components. IJGP-neural uses the same inference solver with a different region construction, and Appendix E.2 compares the previous TRC construction with TRI. These are useful controls rather than comparisons against unrelated methods alone.

Critical weaknesses

1- There is no independent test set for the reported parameter-learning prediction results. Appendix E.1.3 states that hyperparameters are selected using validation data, with no separate test set. The same validation criterion is also used for checkpoint selection and reporting. This may make the reported prediction results optimistic. The comparison against the known generating probability tables remains informative, but it does not replace independent evaluation of predictive performance.

2- The robustness of the numerical results is insufficiently established. The reported experiments use fixed seeds, and the tables do not show variation across repeated training runs or independently generated datasets. The incomplete-data experiments use a missingness probability of 0.3, and Appendix B.1 states that all original variables in the experiments are binary. Results across different missingness levels and non-binary variables would better support the general claims.

3- The efficiency comparison needs more qualification. In the large-data experiment, TRNK uses five A800 GPUs, while VMP runs on a CPU. Region-construction time is excluded, and some VMP results are taken before convergence because the time budget is reached. These comparisons demonstrate performance under the stated implementations, but they do not isolate the computational benefit of the algorithm itself. End-to-end runtime, memory use, and resource-matched comparisons would strengthen the efficiency claims.

4- The connection between the theoretical analysis and the implemented region construction needs clarification. The orthogonality result concerns a specific complete-DAG construction, while the implementation uses a different parent-grouping description. Furthermore, the local approximation result does not establish improved accuracy for the complete learned model. The paper should distinguish properties proved for special constructions from properties supported only by experiments.

5- The learning experiments do not fully isolate the sources of improvement. The TRC–TRI comparison concerns fixed-parameter inference. A corresponding parameter-learning comparison, together with a matched test of the consistency mechanism, would help show whether the gains mainly come from region selection, the neural architecture, or the constraints. This is especially relevant because the neural baselines use different architectures and training settings.

Questions for authors

1- Could the parameter-learning results be evaluated on an independent test set and repeated across several data-generation and optimization seeds?

2- Does Proposition 1 apply to the exact parent-grouping construction used in Algorithm 1 and the experiments? What additional argument is needed for general sparse Bayesian networks?

3- How much of the large-data speed advantage remains when computing resources are matched and region-construction time is included? What is the peak memory requirement?

4- How does the method perform when more values are missing or variables have more than two states?

5- Could the authors add parameter-learning controls using TRC regions and the same neural architecture, and explain how the reference marginals for the high-treewidth inference benchmarks were obtained?

10 comments
AuthorsOpenReview ↗

Response to Weakness 1 and Question 1 — Independent testing and repeated experiments

W1 & Q1: Validation is used for tuning, checkpoint selection, and reporting, which may bias predictive results. Evaluate on an independent test set across data-generation and optimization seeds.

Reply to weakness 1 and Q1: Thank you for suggesting an independent test set. We agree and therefore conducted supplementary experiments.

To address this concern, we kept the original fitted models fixed and independently generated 10,000 complete test records for each BN. All methods were evaluated on the same test set for each network. We used validation data to select hyperparameters and checkpoints and reserved the test data for final evaluation. TRNK retained the lowest average Δ\DeltaNLL on the independent test sets. Compared with the best baseline VMP, TRNK's average Δ\DeltaNLL was 42.8% lower on validation and 44.6% lower on the independent test sets (Table R1). The number of networks on which TRNK ranked first increased from 12 to 13.

We then tested whether this advantage would persist with new training samples and optimization seeds. We trained each method twice more, independently sampling the training and validation sets and generating fresh missingness masks for each run. The three runs used optimization seeds 42, 43, and 44, and we evaluated them on the same independent test set for each network. Giving the 16 networks equal weight, TRNK achieved a test Δ\DeltaNLL of 0.12873±0.000770.12873 \pm 0.00077, compared with 0.22953±0.007950.22953 \pm 0.00795 for VMP, in nats per record. The values after ±\pm are sample standard deviations across the three runs. TRNK's average test Δ\DeltaNLL remained 43.9% lower than VMP's, and TRNK ranked first on 13 of the 16 networks by the three-run mean (Fig. 4(a)). The original comparative result thus held across different training samples, missingness masks, and optimization seeds.

Table R1. Validation and independent test Δ\DeltaNLL (nats/case). Three-run results are from Table 4.

EvaluationTRNKVMPReductionBNs where TRNK ranks first
Validation, original fits1.36E-12.38E-142.8%12/16
Independent test, original fits1.29E-12.34E-144.6%13/16
Independent test, three runs1.29E-1 ±\pm 7.74E-42.30E-1 ±\pm 7.95E-343.9%13/16

Revisions are highlighted in blue in the revised manuscript.

AuthorsOpenReview ↗

Response to Weakness 2 and Question 4 — Higher missingness rates and non-binary variables

W2 & Q4: Report variability across repeated runs and independently generated data, and test higher missingness rates and non-binary variables.

Reply to Weakness 2 and Q4: Thank you for suggesting a broader evaluation. We agree and have added two more sets of experiments to test whether the parameter-learning advantage extends to settings with fewer observations or more variable states.

Higher missingness rates. We increased the missingness rate from 30% to 50% and 70% on the same 16 BNs. We ran each method independently three times per setting and evaluated it on independent test data. TRNK achieved the lowest average test Δ\DeltaNLL and CPD KL at both missingness rates (Table R2). Relative to the best baseline for each metric, TRNK reduced test Δ\DeltaNLL and CPD KL by 57.8% and 47.3%, respectively, at 50% missingness. At 70% missingness, the corresponding reductions were 24.1% and 44.5%. TRNK thus retained its average advantage in prediction and CPD recovery even when most values were missing.

Table R2. Parameter learning at 50% and 70% missingness (Fig. 9(a–b, d–e)). Best baselines: IJGP+DAMP-EM for test Δ\DeltaNLL and VMP for CPD KL.

Missingness rateMetricTRNKBest baselineReductionBNs where TRNK ranks first
50%Test Δ\DeltaNLL7.35E-11.74E+057.8%11/16
50%CPD KL1.20E-12.27E-147.3%13/16
70%Test Δ\DeltaNLL3.16E+04.17E+024.1%8/16
70%CPD KL1.78E-13.21E-144.5%10/16

Non-binary variables. We added a dynamic Bayesian network with three-state variables, a Grid network with four-state variables, and a Dense network with a mixture of two-, three-, and four-state variables. We kept the missingness rate at 30%. All five methods ran on three independently sampled training and validation splits with different optimization seeds, for a total of 45 fits. For each network, all methods shared the same independent test set of 10,000 records. TRNK achieved the lowest mean test NLL and CPD KL on all three networks (Table R3). Compared with the best baseline on each network, TRNK reduced mean CPD KL by 45.2%, 44.0%, and 28.6%, respectively. The original CPD recovery advantage thus extended to all three non-binary settings tested. Appendix E.5 describes the experimental setup.

Table R3. Three-run means for parameter learning with non-binary variables (Table 10).

BNCPD KL (TRNK)CPD KL (baseline)KL reductionTest NLL (TRNK)Test NLL (baseline)
HMM 4×34\times31.07E-11.96E-145.2%7.23E+07.40E+0
Grid 4×44\times44.37E-27.79E-244.0%1.22E+11.23E+1
Dense101.58E-12.22E-128.6%6.13E+06.27E+0

Revisions are highlighted in blue in the revised manuscript.

AuthorsOpenReview ↗

Response to Weakness 3 and Question 3 — Efficiency on large datasets

W3 & Q3: Account for GPU/CPU differences, omitted region-construction time, and VMP runs stopped before convergence. Report end-to-end runtime, peak memory, and results with matched resources.

Reply to Weakness 3 and Q3: Thank you for the feedback concerning the fairness of the comparison between VMP and TRNK. And for the missed end-to-end runtime, memory use, etc. We agree and therefore have added additional experiments.

For matched computing resources, we compared amortized VI (MF-VAE) on the same GPU platform and found that TRNK offers both accuracy and efficiency advantages. VMP, on the other hand, is not a GPU-native method, so it must run on a CPU with limited scalability; thus, the comparison is cross-platform. In contrast, TRNK is designed to fully use the advantages of GPU parallelization. Therefore, running TRNK on CPUs is somewhat compromised. The difference between the two algorithms' mechanisms is:

TRNK's amortized inference is designed to parallelize computation across samples. TRNK shares a single inference network across samples, allowing it to distribute the computation of region beliefs for a batch across multiple GPUs. The BayesPy VMP implementation used in our experiments updates each sample's variational state iteratively and runs on CPU. For these implementations, CPU is the common hardware platform. A single-core comparison measures update costs under a shared CPU budget. TRNK's multi-GPU implementation exercises the parallelism for which its large-sample training was designed. So, the original comparison measures practical training efficiency with each implementation running on its supported hardware.

To quantify the benefit of GPU parallelism, we held the code, data, and global batch size fixed on Grid5 with 200,000 samples and scaled TRNK from one to five A800 GPUs. The median time per training epoch decreased from 1.031 s to 0.227 s, a 4.54×4.54\times speedup, with virtually identical validation NLL. This shows that TRNK is a GPU-native method.

As shown in Table 6(C), on Grid5 with one million samples, the first two updates on the same CPU core took 42.79 s for VMP and 1764.76 s for TRNK. These CPU timings reflect the cost of the first two updates. Under the same single-core CPU budget, TRNK was slower than VMP over the first two updates. However, this setup limits TRNK’s ability to use parallelism across samples, which drives its efficiency on GPUs.

Including region construction preserves the original runtime comparison under the reported hardware configurations. Region construction accounts for only 0.10–0.74% of TRNK's total runtime across the nine settings. In the six HMM and Grid settings where VMP converged, TRNK was faster in five and achieved lower CPD KL in all six (Tables 6(A) and 1). On Grid5 with one million samples, TRNK took 372.90 s, compared with 522.63 s for VMP, and achieved approximately 91% lower CPD KL. For the three Promedas tests, the reported VMP checkpoints were taken at the two-hour time limit, before convergence. This is because we found the VMP iterations updated too slowly to converge within the time budget for these tests.

Table R4. Grid5 replay time and peak memory (Table 6(B)).

Grid5 measurementTRNKVMP
200k, end-to-end replay (s)116.4277.41
200k, peak host PSS (GiB)9.400.62
200k, peak combined GPU memory (GiB)30.37N/A
1M, peak host PSS (GiB)17.70∗17.70^{*}1.92
1M, peak combined GPU memory (GiB)68.90∗68.90^{*}N/A

The 200k replay (Table R4) ran through the stopping criterion. The combined GPU memory peak is the maximum simultaneous sum across the five GPUs. ∗^{*}The 1M TRNK memory peaks were measured over three training epochs.

Revisions are highlighted in blue in the revised manuscript.

Reviewer_YYadOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
1
Soundness
3(+1)
Read review
Paper summary

The authors propose a method to learn the relationships between variables in a bayesian network when presented with missing data. The graph is assumed to be known, the problem is to learn the conditional probability distribution between the variables. The method they propose consists of breaking the graph down into overlapping ‘regions’ and then 1. doing inference over the unobserved binary variables as part of a region, then 2. learning the conditional probability distributions. Steps 1 and 2 is repeated in an alternating expectation-maximisation-type algorithm until convergence. They propose new ways to define appropriate regions for the graph, then use the Kikuchi free energy objective for the gradient updates for the posterior of unobserved variables. In order to learn the conditional probability distributions between all of the nodes in the graph, the marginals on each variable must satisfy some constraints such that all of the overlapping regions have consistent marginals when considered together. They propose a method to learn these conditional probability distributions with constraints using attention mechanisms. The primary goal of the method is to provide an efficient approach to learn these conditional probability distributions, whilst also improving performance, which they show in the experiment section on a number of datasets.

Critical strengths

The method seems to be more efficient than other existing methods and also comes with increased accuracy of finding the conditional independence relationships/inference over the posteriors of hidden variables. The method proposes a principled way to find regions for this problem, something that was lacking from the field.

Critical weaknesses

The main weakness for this paper is in the experiments section. Firstly, there are no error bars, as a result, statements such as "our method does better in x out of y datasets" I dont think is sufficiently supported, especially since in some of the plots, the proposed method seems to be very close to baseline methods. Im unsure which of the algorithms entail some stochasticity and which do not, but since the proposed algorithm would lead to some stochastic outcomes, it would make sense to repeat the experiments at least on all of the methods tested that would lead to variability in results. Coupling this with non-overlapping datasets in figures 2 and 3 (see questions for authors), I dont think that the experiments provide sufficient evidence for this method, this is the main reason for my low rating.

As a minor point which is subjective, as someone who is unfamiliar with region graphs and kikuchi free energy objective, I found the paper hard to understand. I believe in part this was due to the fact that it was difficult to discern what was novel and what was not. It would be helpful to a reader such as myself if this was crystal clear in the writing. For example, for equation 1 since there is no derivation, I assume this is a simple plug and play of the kikuchi free energy objective, however, there is not a reference for this objective directly after the equation nor at any point before in the paper, which stops me from investigating this further myself.

Questions for authors
  • Is there any explanation about what makes TRNK performance similar to baselines for HMM datasets for the singleton inference results? Similarily for the CPD learning on the Dense datasets, why does TRNK underperform?
  • Why are Dense and Promedas datasets which are present in figure 3 omitted from figure 2?
  • What is the relationship between the performance of algorithms in terms of singleton inference and in terms of conditional dependence relations? If say for one method, singleton inference was shown not to be as effective as other methods, could the method still outperform other methods on finding the conditional probability distributions? In other words, is TRNK obtaining better estimates of the CPDs purely as a result of better estimates of the posteriors of the hidden variables or is there something else going on here? The results in figure 2 for TRNK HMM 3x3 makes me wonder this, since even though TRNK is not the best-performing method for singleton inference for this dataset, it seems to be doing as well or better than other methods in estimating CPDs in figure 3.
10 comments
AuthorsOpenReview ↗

Response to Weaknesses 1 and 2 and Question 2 — Repeated experiments, benchmark coverage, and clarity

W1 & Q2: Repeat stochastic experiments and show error bars to assess close baseline comparisons. Why are Dense and Promedas omitted from the inference figure?

Reply to Weakness 1 and Q2: Thank you for pointing out that the evaluation is insufficient to assess the proposed method. We agree and have therefore added extensive evaluations to better present and clarify our method's significant improvement compared with competing methods.

In our revised version, we evaluated each stochastic inference method with five random seeds and revised Fig. 3(a–b) with error bars to show the minimum and maximum across runs. LBP and DAMP-BP are deterministic under the fixed settings and were each evaluated once. Fig. 4(a–c) reports the mean and sample standard deviation across three parameter-learning runs. We also added Dense, Promedas, and Pigs to Fig. 3 so that the inference and parameter-learning experiments now cover the same 16 Bayesian networks, enabling a direct comparison across tasks.

The error panels use logarithmic axes, which compress differences in the raw errors. Giving each of the 16 networks equal weight, the best inference baseline, IJGP-MP, has mean and maximum node KL values 2.28 and 4.92 times those of TRNK, respectively (Table R1). For parameter learning, the best baseline, VMP, has test Δ\DeltaNLL and CPD KL values 1.78 and 1.45 times those of TRNK, respectively. We've added these numerical values explicitly in the revised version.

Table R1. Inference and parameter learning on 16 BNs. Averages weight BNs equally. Counts refer to TRNK and include inference ties at the 10−610^{-6} display threshold. Data are from Tables 3–4.

MetricTRNKBest baselineReductionLowest or tied
Mean node KL1.12E-32.55E-3 (IJGP-MP)56.2%15/16
Maximum node KL4.61E-32.27E-2 (IJGP-MP)79.7%15/16
Test Δ\DeltaNLL1.29E-12.30E-1 (VMP)43.9%13/16
CPD KL1.05E-11.53E-1 (VMP)31.2%16/16

W2: Clarify the paper’s novel contributions and cite the source of the Kikuchi objective in Eq. (1).

Reply to Weakness 2: We appreciate this feedback and agree with this point. Eq. (1) gives the standard region-graph Kikuchi free-energy objective. The revised manuscript cites Yedidia et al. (2005) where we introduce it. Our contributions are the Triplet Region Induction (TRI) algorithm, a neural parameterization that enforces marginal consistency across overlapping regions, and their integration into amortized learning of conditional probability distributions (CPDs) from incomplete data (Section 1).

Revisions are highlighted in blue in the revised manuscript.

AuthorsOpenReview ↗

Response to Questions 1 and 3 — Singleton inference and CPD learning

Q1: Why is TRNK close to baselines on HMM singleton inference and weaker on Dense parameter learning?

Reply to Q1: Thank you for pointing out the results that need further validation and explanations. We agree and therefore performed additional tests.

In the original single run on HMM 3×33\times3, IJGP-MP achieved a lower mean node KL than TRNK. Across five inference runs on this BN, TRNK had lower mean and maximum node KL than IJGP-MP (Table R2). TRNK achieves the lowest mean and maximum node KL on all three HMMs (Fig. 3(a–b)).

Table R2. Fixed-CPD inference on HMM 3×33\times3. Single-run results are from the original submission; five-run means and sample standard deviations are from Table 3.

RunsMethodMean node KLMaximum node KL
1IJGP-MP3.57E-53.14E-4
1TRNK2.69E-41.41E-3
5TRNK2.68E-4 ±\pm 1.37E-61.42E-3 ±\pm 9.81E-6
5Best baseline3.23E-4 ±\pm 1.07E-52.87E-3 ±\pm 7.97E-5
5IJGP-MP3.43E-3 ±\pm 3.09E-31.79E-2 ±\pm 1.60E-2

We agree that MF-VAE achieves lower test ΔNLL\Delta\mathrm{NLL} on Dense 10, Dense11 and Dense12 (Fig. 4(a)). On those networks, TRNK achieves lower CPD KL. The metrics weight parent configurations differently. Test ΔNLL\Delta\mathrm{NLL} evaluates the joint likelihood of the complete test records, so configurations that occur more often contribute more to the score. CPD KL gives every parent configuration equal weight within each node, including configurations absent from the test set (Appendix C.2.4). A model can therefore fit the test records better while having a larger average error across CPD rows. CPD KL is more directly aligned with our goal of recovering the generating CPDs from incomplete data, as described at the beginning of our paper (Section 1).

On Dense 10, Dense11 and Dense12, MF-VAE fits the test records better, and TRNK recovers the generating CPDs more accurately on average. This helps explain why the rankings differ. TRNK achieves the lowest CPD KL on all three Dense networks, reducing it by 5.2%, 20.1%, and 20.2% relative to the best baseline on each network, respectively (Table 4).


Q3: How does singleton inference accuracy relate to CPD recovery, especially on HMM 3×3?

Reply to Q3: We appreciate the valuable feedback and agree with the point. We therefore added more tests to validate our findings.

We generally expect the two to improve together because more accurate posterior estimates can provide more reliable expected counts for CPD updates. Those counts depend on the joint posterior of a child and its parents given the observations (Eqs. (12)–(13)). Singleton KL measures the marginal distribution of each variable separately. A method with higher singleton KL can therefore still recover more accurate CPDs if it estimates the joint posteriors needed for the updates more accurately. In reverse, a more accurate estimate of the joint should yield more accurate singleton KL.

In the newly added experiments on the HMM 3×33\times3 example, TRNK achieves the lowest mean and maximum node KL, averaged across five inference runs, and the lowest CPD KL, averaged across three parameter-learning runs (1.55E-3 vs. 2.07E-3 for the best baseline) (Tables 3–4). We have updated the result in the revised paper.


References

Yedidia, J. S., Freeman, W. T., and Weiss, Y. (2005). Constructing free-energy approximations and generalized belief propagation algorithms. IEEE Transactions on Information Theory.

Revisions are highlighted in blue in the revised manuscript.

AuthorsOpenReview ↗

Opportunity for Further Discussion

Dear Reviewer YYad,

Many thanks again for taking the time to review our work. We have carefully addressed your concerns regarding experimental reliability, performance variations across datasets, and the relationship between singleton inference and CPD learning. We would greatly appreciate your feedback on whether our responses have adequately addressed your concerns.

We would be happy to clarify any remaining questions.

Sincerely,
The Authors

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

This paper proposes so called Triplet Region Induction-Constrained Neural Kikuchi Learning (TRNK) algorithms for parameter learning in discrete Bayesian networks (more precisely a DAG) with incomplete observations. First, a triplet region induction procedure constructs higher-order regions by merging selected interaction triplets with primary regions derived from the Bayesian network. Second, a neural network roduces region beliefs, with shared Helmert contrast coefficients enforcing consistency across overlapping regions. Additional corrections are carried out to ensure nonnegativity and compatibility with deterministic constraints. The resulting beliefs are used to optimize an evidence-clamped Kikuchi free-energy objective . The theoretical results establish a counting-number property termed “orthogonality,” a local KL improvement from merging regions, and feasibility guarantees for the belief construction.

Critical strengths

The paper addresses an important computational problem. Repeated posterior inference is a major bottleneck when learning a dag from incomplete data.

The consistency-preserving parameterization seems interesting.

The region construction algorithms seem to exploit model structure. Rather than choosing clusters arbitrarily, TRI uses the Bayesian-network structure to identify and merge relevant regions. The local KL identity in Equation (4) gives an interpretable justification for retaining additional interactions.

Critical weaknesses

the theoretical results seems somewhat narrow. It does not establish that optimizing the full loopy Kikuchi objective yields better approximate posteriors or more accurate learned parameters. also the theory does not imply statistical consistency.

I must mention this paper is very hard to read due to the technical nature of the approach. I think the author should do a careful job to outline and convey the ideas to general audience. Started with throwing a bunches of jargon too early without motivating the methods too well.

Questions for authors

Does Proposition 1 apply directly to the parent-grouping factorization and sparse networks used in the experiments? can you characterize when TRI improves the optimized Kikuchi approximation? Are there examples where merging regions worsens the final inference result?

can you elsbraote on e proposed “orthogonality” property, what benefits come with it?

4 comments
AuthorsOpenReview ↗

Response to Weakness 1 — Scope of the theoretical results

W1: The local theory does not establish improved posteriors or learned CPDs from optimizing the full loopy Kikuchi objective, or statistical consistency.

Reply to Weakness 1: Thank you for pointing out the need to clarify the scope of our theory. We agree that our established theoretical results justify the TRI merge locally and establish overlap consistency of the resulting beliefs. However, we have shown the accuracy improvement in the following ways.

Comparison with Bethe. If the Kikuchi clusters and separators form a junction tree covering all factors, globally minimizing the Kikuchi free energy recovers the exact posterior marginals, whereas the Bethe optimum on the original loopy factor graph can have nonzero marginal error. This special case explains how larger regions can improve inference when they capture dependencies around a loop.

Local approximation and region structure. Eq. (4) shows that, when both local reconstructions use the true region marginals, merging TRC triplets into TRI quadruplets reduces forward KL by exactly the sum of two conditional mutual information terms. Both local reconstructions are junction trees. The gain comes from retaining additional conditional dependencies (larger regions). At the level of the full graph, TRI reduces the number of independent cycles in the five-variable example in Fig. 2(a–b) from 10 under TRC to 4. Proposition 1 characterizes the counting numbers of the newly induced interactions for the specified complete-DAG construction, and Proposition 2 guarantees agreement on region overlaps throughout optimization. With fixed CPDs, TRI lowers mean singleton KL relative to TRC on 8 of 12 networks (Table 7). TRNK also achieves lower mean singleton KL than Bethe-neural on all 16 networks (Table 3).

Statistical consistency. TRNK achieves the lowest mean CPD KL on all 16 networks and the lowest mean independent-test ΔNLL\Delta\mathrm{NLL} on 13 of 16 among the evaluated methods (Table 4). These are finite-sample results. The CPD updates use approximate posterior family counts (Eqs. (12)–(13)), whose systematic errors may persist as the sample size grows. Establishing statistical consistency would require showing that the population learning criterion identifies the generating CPDs and that the estimator converges to them. We will clarify these limitations in the revision (Appendix B.5).

Revisions are highlighted in blue in the revised manuscript.

AuthorsOpenReview ↗

Response to Questions 1 and 2 — TRI region merging and orthogonality

Q1: Does Proposition 1 apply to sparse and parent-grouped BNs? When does TRI improve the optimized approximation, and when can it worsen inference?

Reply to Q1. Proposition 1 establishes orthogonality for the BF construction over a complete DAG. This ensures applicability for sparse BNs. Since every sparse BN can be converted to its corresponding complete DAG and then used to obtain the associated BF model, TRC regions obtained directly from the BF model conveniently satisfy the defined orthogonality (newly induced inner regions' counting number = -1).

However, mapping a sparse BN to its complete DAG and then to the BF model introduces redundant intermediate variables that are solely copies of the original variables. Orthogonality is satisfied under these distinct intermediate variables, even though they are copies of the same original variable. These copies need not be preserved and can be safely replaced by their original variable in a region after all orthogonality regions have been identified. It can be shown that the replacement will not alter the joint distributions over the same set of variables (Appendix B.5). Therefore, there could be cases that counting number changes from -1 to -2 after the variable replacement.

The grouped BF is a variant of BF used solely to ensure the maximum factor weight does not exceed that of the original BN, which is necessary for a fair comparison with competing algorithms in the experimental section. The grouped BF model is a sparse BN which also complies with the above region orthogonality analysis. In Fig. 7(a–c), we show, with a concrete example, that the grouped BF can be mapped to its complete DAG and the associated BF construction, which identify regions that satisfy the orthogonality.

Across the 16 parameter-learning graphs, 1,016 of the 1,018 retained newly induced interactions have a count of −1. The two exceptions are moral-edge pairs in Dense12 and Barley, which have a count of −2. If we restore distinct intermediate variables, all counts return to -1 (Appendix B.5, counting numbers).

TRI improvement of KFE approximation. TRI improves the local approximation when merging two triplets captures a dependence that remains after conditioning on the variables they share. For the overlap pattern in Appendix B.3, Eq. (4) shows that the stronger this additional dependence is, the larger the reduction in local KL.

For the optimized Kikuchi approximation, one sufficient condition is that the merged regions form a junction tree covering all model factors. In that case, globally minimizing the Kikuchi objective with the original factors and standard consistency constraints gives the exact marginals (Yedidia et al., 2005). On loopy graphs, we assess the accuracy of the optimized marginals empirically.

In the TRC–TRI comparison (Table 7), at least one singleton KL metric increased slightly on each of the three Grid models, Pigs, and Dense10, but the differences are minor. The gain of TRI merge can depend on the factors information of the CPDs. Both methods had mean singleton KL below 2×10−62\times10^{-6} on the Grid models and Pigs. TRI lowered both mean and maximum singleton KL on seven of the twelve models, including all three HMMs.


Q2: What benefits does orthogonality provide?

Reply to Q2. Benefits of Orthogonality. Thank you for asking us to clarify this property. In Definition 1, orthogonality means that each newly induced inner region has a CVM counting number of −1-1. These are regions that contain a moral-edge pair and meet the primary-triplet criteria. The property concerns how region overlaps are weighted in the Kikuchi entropy.

For example, in Fig. 1(d), the two merged regions Q1Q_1 and Q2Q_2 share the triplet UU. Their entropy terms both include the entropy of UU, so the local Kikuchi expression

H(bQ1)+H(bQ2)−H(bU)H(b_{Q_1}) + H(b_{Q_2}) - H(b_U)

subtracts the shared entropy once. If three outer regions intersect pairwise exactly at UU, the CVM recursion instead gives cU=1−3=−2c_U = 1 - 3 = -2, so the entropy of UU is subtracted twice. Orthogonality therefore provides a structural criterion for selecting regions that retain higher-order dependencies while requiring only one entropy correction at each newly induced overlap.

From an approximation-quality perspective, adding too many interactions will not yield sensible approximations because the induced interactions are all local, which does not ensure that repeated enforcement contributes to accuracy gains. So the orthogonality ensures only one interaction region contributes to the target local belief improvement. This motivates retaining one of two competing interaction triplets for the same moral edge, as discussed in Appendix B.5, TRC candidate selection and in Lin et al. (2020, Appendix A.3).

Revisions are highlighted in blue in the revised manuscript.

AuthorsOpenReview ↗

Response to Weakness 2 — Clarity and motivation

W2: Introduce the learning problem and motivate the method before presenting technical concepts.

Reply to Weakness 2: Thank you for this constructive feedback. We agree that the introduction presents several technical concepts before clearly defining the underlying learning problem. In our revision, we restructure the motivation in a more natural sequence in Section 1.

Learning the parameters of a discrete Bayesian network from large, incomplete datasets requires estimating joint posterior probabilities across many partially observed records. While amortized variational inference (VI) makes this process efficient by sharing a single inference network across all records, standard mean-field VI uses a fully factorized posterior that cannot capture the dependencies needed to accurately estimate joint counts during parameter updates.

A structured VI posterior can retain these dependencies. There is added cost from obtaining the joint marginals needed for both the expected counts and the ELBO. Even in a tree-structured posterior, a node and its parents may be connected through other missing variables. Computing their joint marginal can require summing over those variables, and evaluating the ELBO gradient can require differentiating through that calculation (Bouchard-Côté and Jordan, 2009). Therefore, for structured VI posteriors, computing the joint marginals needed for parameter updates can substantially increase the per-record inference cost, even with amortisation. Sampling is another option, but sampling-based training can yield noisy gradients for the inference network in discrete models (Mnih and Gregor, 2014).

To address these limitations, we introduce a flexible, non-ELBO framework that provides controllable accuracy for parameter learning and requires no sampling, along with an amortized variant for GPU acceleration. Unlike existing non-ELBO methods that rely on the Bethe objective, we use the Kikuchi objective, which captures higher-order dependencies to improve accuracy while preserving computational efficiency through restricted cluster sizes. Also, current soft penalty-regularized model-specific methods cannot ensure belief consistency for the Bethe/Kikuchi objectives. These components naturally motivate region construction, consistent region beliefs, and amortized learning, respectively.


References

Yedidia, J. S., Freeman, W. T., and Weiss, Y. (2005). Constructing free-energy approximations and generalized belief propagation algorithms. IEEE Transactions on Information Theory.

Lin, P., Neil, M., and Fenton, N. (2020). Improved high dimensional discrete Bayesian network inference using triplet region construction. Journal of Artificial Intelligence Research.

Bouchard-Côté, A., and Jordan, M. (2009). Optimization of structured mean field objectives. UAI.

Mnih, A., and Gregor, K. (2014). Neural variational inference and learning in belief networks. ICML.

Revisions are highlighted in blue in the revised manuscript.

AuthorsOpenReview ↗

Opportunity for Further Discussion

Dear Reviewer 5wt6,

Many thanks again for taking the time to review our work. We have carefully addressed your concerns regarding the orthogonality property, its benefits, and the conditions under which TRI improves the Kikuchi approximation. We would greatly appreciate your feedback on whether our responses have adequately addressed your concerns.

We would be happy to clarify any remaining questions.

Sincerely,
The Authors

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of revisions

We thank all three reviewers for their careful reading and constructive feedback. Their concerns are mainly focused on the presentation, the applicability of the Orthogonality property, local accuracy improvement, and the need for more validation of the efficacy of our proposed methods. We have carefully addressed all concerns in our revised version. The main changes can be summarized below.

  • Motivation, novelty and presentation (5wt6, YYad). In Section 1, we emphasize that commonly used VI-based methods provide only a limited, fixed factorization upfront and are insufficient for generalizing dependence modeling (Rezende & Mohamed, 2015) (Bouchard-Côté & Jordan, 2009) (Mnih & Gregor, 2014). We clarify TRNK's novelty in flexibly capturing dependencies where they matter for CPD learning and providing controllable complexity. Along with an improved neural architecture, it predicts beliefs that agree on overlapping marginals and processes records in GPU batches, making the approach scalable to large datasets. We reviewed all equations and verified that derivations from prior work are properly cited. We moved the two-level region graph from the Appendix to the main text for better presentation consistency in Fig. 2 (b–c).

  • Orthogonality and local accuracy (5wt6, HzNE). Appendix B.5 clarifies which construction Proposition 1 covers and how a sparse BN can be equivalently represented by that construction while preserving its joint distribution on the original variables (Fig. 7(a–c)). So connections between Algorithm 1 and Proposition 1 are retained. We report the CVM counting numbers there and explain how the local KL result establishes improved accuracy (Appendix B.3).

  • Repeated experiments and independent testing (YYad, HzNE). Inference and parameter learning now cover the same 16 BNs. Fig. 3(a–b) shows error bars for five-seed inference, and Fig. 4(a–c) shows error bars for three-run CPD learning (Tables 3–5). The learning runs use different data and optimization seeds, and all methods share an independent test set of 10,000 complete records per BN (Appendix E.1.3, Data). TRNK has the lowest mean CPD KL on all 16 BNs (Fig. 4(b)) and the lowest mean test ΔNLL on 13 of 16 (Fig. 4(a)). Table R1 in our response to YYad (W1 and Q2) summarizes the results across all 16 BNs, and Table R1 in our response to HzNE (W1 and Q1) compares validation and independent-test results. We also updated Table 1 with three-run means and sample standard deviations for all nine large-sample settings.

  • Region and consistency ablations (5wt6, HzNE). We expanded the TRC–TRI inference comparison (Table 7) and added a paired CPD-learning comparison with a shared neural architecture (Table 8). In a separate matched comparison, enforcing marginal consistency lowered mean CPD KL on all 9 BNs tested (Table 9). Tables R5–R6 in our response to HzNE (W5 and Q5) summarize the paired parameter-learning ablations.

  • Higher missingness and non-binary variables (HzNE). TRNK achieves the lowest average test ΔNLL and CPD KL at both 50% and 70% missingness (Fig. 9(a–b, d–e)), and the lowest mean test NLL and CPD KL on each of the three non-binary BNs (Table 10).

  • Large-sample efficiency (HzNE). We added runtimes including region construction, peak host and GPU memory measurements, and hardware controls (Table 6(A–C)). Region construction accounts for 0.10–0.74% of TRNK's total runtime. On Grid5 with 200k records, using five A800s instead of one reduced median epoch time from 1.031 s to 0.227 s.

Revisions are highlighted in blue in the revised manuscript.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.