acceptodds
Under review as a conference paper at ICLR 2027

Advances in Marginal Inference for Chain-Graph Logical Credal Networks

Abstract

Logical Credal Networks (LCNs) are an expressive probabilistic logic framework that combines propositional formulas with imprecise probability bounds to represent sets of probability distributions. While LCNs support cyclic dependencies and impose few syntactic restrictions, inference remains computationally challenging. Existing exact methods scale exponentially with the number of propositions, and the only available approximate approach is the ARIEL message-passing algorithm. In this paper, we exploit the chain graph structure underlying LCNs and reformulate inference as a credal network problem. Building on this formulation, we propose three approximate inference algorithms based on variable elimination, interval-valued message passing, and coordinate descent for computing posterior probability bounds. We also introduce an exact inference method that leverages a junction tree decomposition of the chain graph to construct and solve a substantially smaller nonlinear program. We establish theoretical properties of the proposed methods and evaluate them on synthetic and realistic LCN instances. The results show substantial speedups over existing approaches while maintaining high-quality probability bounds and enabling exact inference on significantly larger problems.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
probabilistic methods, graphical models, inference, probabilistic logic

Reviews

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

The paper takes advantage of the chain graph structure of Logical Credal Networks (LCNs) to reformulate inference as a credal network problem. Specifically, three approximate inference algorithms are put forth based on variable elimination, interval-valued message passage, and coordinate descent for computing posterior probability bounds. An exact inference method based on junction tree propagation (JTP) can solve substantially smaller nonlinear programs. Some theoretical results are obtained and experimental results are promising.

Critical strengths

As only one approximate inference algorithm (ARIEL) exists for Logical Credal Networks, studying and proposing new exact and approximate inference algorithms is a worthy direction. The paper puts for not one, but multiple methods for LCN inference.

Critical weaknesses

Major Concerns

  1. The paper does not provide a single formal algorithm specification or a proof of any theoretical claim in the main text, making it difficult to assess the novelty, correctness, and technical contributions of the proposed methods.

In S3.4 Credal Variable Elimination, no formal algorithm is provided. Instead, the proposed method is described using two paragraphs on p5.

In S3.5, Interval Belief Propagation, no formal algorithm is provided. Instead, the proposed method is described with one half of p6.

In S3.6, Coordinate Descent with Variable Elimination (CDVE), no formal algorithm is presented. Only one paragraph is used to describe the new approach.

In S4, Credal Junction Tree (CJT) is introduced without a formal algorithm. Instead, one half of a page is used to describe the method on p7.

Some of these appear incremental. For example, CDVE only requires one paragraph to describe. Similarly, CJT reads just like classical JTP. CJTP moralizes and then triangulates, producing a chordal graph. It constructs a junction tree satisfying the running intersection property. It assigns distributions over the cliques.

Likewise, no formal proofs of Theorems 1–6 are provided in the main text.

Experimental Evaluation

On p7, only Random LCNs with a moralized treewidth less than or equal to 3 (at most two parents per atom) are considered. While the text continues by stating that topologies both large and small are constructed, the critical issue is treewidth. Thus, having a "large" network but capping the treewidth at 3 is not interesting. Does this method scale to cases where the treewidth is larger than 3?

In [Darwiche, 2009], it is argued that treewidth can be overcome in some cases when the network involves a lot of determinism. In these cases, a network can be compiled into an arithmetic circuit even when the treewidth is high. How does the proposed method relate to this arithmetic circuit approach?

  1. Weak Writing

The writing is not always precise. For instance, the Abstract simply states that the paper establishes theoretical properties of the proposed methods and shows substantial speedups over existing methods.

The organization could be better. It is strange to have Section S3.1 Credal Networks on p4, yet earlier have Section S2.1 Logical Credal Networks on p2. Perhaps it would be better to first define Credal Networks and then later define Logical Credal Networks.

Proposition 2 just appears. It is never introduced.

Similarly, there is no introduction to Theorem 1, which also just appears. There is no connecting sentence leading from Theorem 1 to Theorem 2. Instead, Theorem 2 just appears in the text after Theorem 1.

In fact, no formal theorem is ever introduced (Theorems 1-6). They all just appear in the text.

Should Credal Junction Tree (CJT) not instead be called Credal Junction Tree Propagation (CJTP)? The issue is that a junction tree is a type of graph, while junction tree propagation is a class of inference algorithms. The paper introduces CJT, which sounds like a type of graph, yet says it is for probabilistic inference.

Why is the complexity of CJT not given a numbered theorem like IBP and CVE?

The writing in S5 Experiments is choppy and unnatural. I counted 10 colons, not to mention the many semicolons and dashes.

I don't quite follow the significance of the lack of an acyclicity requirement mentioned on p1. In Fig 1, the cyclicity is between a pair of nodes C and D. Maybe it would be better to show a longer cycle. Then in the experimental results reported in Table 1, three of the six networks are classical Bayesian networks where acyclicity holds.

On p2, I find the phrases \psi to \psi and \phi to \phi strange. Maybe it would be clearer to introduce notation to represent formula nodes such as v_{\psi}.

Some citations are lacking or misattributed. For instance, while variable elimination (VE) is attributed to Dechter 2003, it is perhaps better to add (Zhang and Poole, 1996) at the very least. For example, (Zhang and Poole, 1996) is the sole citation for VE in the Koller and Friedman reference. Similarly, the running intersection property (RIP) was also attributed to Dechter 2003, whereas it could have been attributed to a number of references published in the 1980s.

References are listed inconsistently. Compare the first two references and you notice that even papers published in the same journal (IJAR) are shown differently. More generally, journal papers are listed differently (compare IJAR versus JMLR). Conference papers are listed inconsistently. Once again, two IJCAI papers are presented differently.

On a lesser note, calling the new method Interval Belief Propagation (IBP) will cause confusion in the community, since Iterative Belief Propagation (IBP) is already used in the literature [Darwiche, 2009].

Undefined Notation

p2 undefined notation: P
p2 undefined notation: l
p2 undefined notation: u
p2 undefined notation: (X \perp !!! \perp Y | Z)
p2 undefined notation: atoms(s)
p3 undefined notation: C
p3 undefined terminology: projection

Notation Drift

Boldface X is defined as a set of binary variables in S2.1 on p2, redefined as a set of random variables in S2.2 on p3, and changed again as a set of discrete variables with finite domains in S3.1 on p4.

G is a primal graph in S2.1 on p2, redefined as another type of graph in S2.2 on p3, and changed again as a DAG in S3.1 on p4.

pa(X_i) is defined as the parents of a propositional node in S2.1 on p2, then redefined as the parents of a node corresponding to a variable in S2.2 on p3, and then defined as the parents of a node in a DAG in S3.1 on p4.

Typos

  • missing period in Eq. (4)
Questions for authors
  1. How does the proposed method relate to Darwiche's arithmetic circuit approach? In particular, discuss how your approach is better than the arithmetic circuit approach for overcoming high treewidth.
1 comment

No formal algorithms or proofs in the main text. Formal pseudocode is given for every method: Alg. 1 (CJT, App. B), Alg. 2 (CVE, App. F.5), Alg. 3 (IVBP, App. G.2) and Alg. 4 (CDVE, App. H). Full proofs are in Apps. C.2 (CJT), E (compilation), F.8, G.4 and H.2. Within the 10-page limit, the main text gives the key results with proof sketches:

  • the CJT program and Thm. 1, with its two-inclusion proof sketch (§3);
  • Prop. 2 and its proof idea (§4.2);
  • Prop. 3, with the covering and projectivity arguments (§4.3).

App. A.1 adds a dependency map of all results.

Incrementality; CJT reads like classical junction-tree propagation. CVE, IVBP and CDVE are adaptations, and §4.3 now presents them as such. CJT shares the junction-tree structure with classical JTP but differs in what it computes.

  • Calibration as constraints. An LCN defines a nonconvex set of distributions, so CJT imposes calibration as constraints of one nonconvex program rather than computing it by message passing.
  • Discharging the independence assertions. CJT must discharge the LCN's independence assertions on the tree, which has no JTP counterpart. It uses separator entailment, exact reduction of an assertion to the part still connected, or an ordered tree whose node-wise rows imply every assertion (Prop. 4; App. B.2).
  • Proving exactness. CJT must prove that the result is exact. The reconstruction (Lemma 6) handles zero separator marginals without positivity, and H1–H4 are checked per instance (Thm. 1).
  • Conditional queries. These need a Charnes–Cooper reformulation and certification by a global solver (§3; App. B.3).

Treewidth capped at 3; does the method scale beyond it? The ktree sets have treewidth exactly 3, and the DAG sets ≤3\le 3. CJT's largest clusters have 2–8 atoms (§5). These sets were designed to separate the dependence on nn from the 2n2^n joint, and they show that CJT certifies exact bounds at n=100n=100, where the joint formulation fails beyond n≈6n\approx 6. The dependence on treewidth is the one stated by Thm. 2: O(n 2w+1)O(n\,2^{w+1}) variables. We agree that a treewidth sweep is informative, and we will add one to App. I: kk-trees with k∈{2,…,6}k\in\{2,\dots,6\} at fixed nn, which our generator already produces.

Relation to arithmetic circuits (Darwiche, 2009). Arithmetic circuits (ACs) compile the network polynomial of a precise network and exploit determinism and context-specific independence to evaluate it beyond the treewidth bound. LCN inference is different: it optimizes over a nonconvex set of distributions. An AC can therefore at best represent the objective inside the optimizer, not replace the optimization. The approaches are complementary, and we do not claim CJT is better.

  • CN route. The local coefficients that CDVE computes for a family are exactly the partial derivatives of the network polynomial with respect to that family's parameters. One AC backward pass returns all of them, so an AC is a drop-in replacement for CDVE's variable-elimination step that would exploit determinism.
  • CJT. A sentence with bound 0 or 1 forces cluster-state variables to zero, which presolve can remove. A compiled, determinism-aware encoding of the cluster marginals is a natural extension.

Writing and organization.

  • Section order. Credal networks are now defined first (§2.1), before LCNs (§2.2).
  • Abstract. The abstract now states concrete results (certification rates, scale, conditions) instead of generic claims.
  • Lead-ins. Each result is now introduced: Prop. 1 by the question of whether compilation loses any LCN member; Thm. 1 by its hypotheses and how they are checked; Thm. 2 after the proof sketch.
  • CJT complexity. It is now a numbered theorem (Thm. 2, size), with B.4 giving the details.
  • Experiments. §5 was rewritten.

Acyclicity. LCNs allow a sentence such as P(¬(C⊕D)∣A)P(\neg(C\oplus D)\mid A) to tie CC and DD symmetrically. The structure then has an undirected chain component rather than a DAG edge, and this is not expressible as a Bayesian network over atoms. Our methods treat such components as compound nodes, with exact local sets (§4.1). Larger cyclic dependencies become larger components and are handled identically.

Notation.

  • ℓs,us\ell_s,u_s, atoms(s)\mathrm{atoms}(s) and τs\tau_s are defined with the sentence forms (§2.2).
  • The meaning of (X⊥Y∣Z)(X\perp Y\mid Z) is defined inline (§2.2; Def. 4).
  • Clusters CC and qCq_C are defined in §3.
  • The notation drift is removed:
    • X\mathbf X always denotes the atoms, and the credal-network nodes are V\mathbf V.
    • The graphs are distinguished as GPG_P (primal), GG (chain graph) and DD (component DAG).
    • So are the parent sets: paP\mathrm{pa}_P, paG\mathrm{pa}_G and Pa(v)/pav\mathrm{Pa}(v)/\mathrm{pa}_v.
  • App. A.2 tabulates all symbols.
  • Formula nodes are now written vφv_\varphi, vψv_\psi, as you suggested (§2.2; App. A.3, proof of Lemma 4).
Reviewer_c7e5OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper develops an algorithmic connection between LCNs and credal networks using an existing chain-graph factorization. It presents several inference methods, including CVE, IBP, CDVE, and CJT. The connection is conceptually appealing, and CJT is the clearest methodological contribution: under its stated structural conditions, it replaces optimization over the full joint distribution with a clique-marginal formulation containing (O(n2w+1)O(n2^{w+1})) variables, rather than (2n2^n). This can substantially reduce the formulation size on low-treewidth instances, although it does not establish a corresponding bound on global optimization time. The evaluation covers a broad collection of synthetic and realistic benchmarks. Overall, the paper offers a potentially valuable synthesis, but several methods adapt existing credal-network techniques, so its methodological novelty is more concentrated than the number of proposed algorithms might suggest.

Critical strengths
  1. Exploiting chain-graph structure to connect LCNs with existing credal-network algorithms is practically motivated and offers alternatives to optimization over the full joint distribution. CJT is particularly promising: under its stated structural conditions, replacing global joint-probability variables with consistent clique marginals can substantially reduce the formulation size on low treewidth graphs.
  2. The empirical evaluation covers a broad collection of synthetic and realistic benchmarks. The reported results suggest computational benefits from CJT’s compact formulation and an attractive speed–accuracy trade-off for IBP on the synthetic instances, with accuracy measured against the CJT reference. The authors also report less favorable results for the credal-network approximations on non-family-realizable instances, helping readers assess their practical limitations.
Critical weaknesses
  1. The global-optimality verification for CJT reference results needs clarification. CJT exactness depends on its stated structural conditions and on globally solving a potentially nonconvex optimization problem. The authors should state whether every CJT result used as a reference was accompanied by a global-optimality certificate and how uncertified cases were treated.
  2. A more controlled analysis of the strong-extension relaxation would strengthen the empirical conclusions. The paper discusses relaxation error in Section 3.3 and evaluates non-family-realizable instances in Section 5, so this limitation is acknowledged. However, all synthetic benchmarks are family-realizable. On the realistic instances, Table 1 reports IBP upper-bound MAEs relative to CJT of 0.493 on MScaling and 0.263 on PScaling, compared with ARIEL’s 0.000 on both at the displayed precision. The authors also report that IBP and CDVE produce intervals 1.4–7.7 times as wide as the reference intervals. These results demonstrate a speed–accuracy trade-off, but leave the conditions under which the relaxation remains useful insufficiently characterized. Controlled experiments varying the proportion, type, and tightness of non-family-realizable constraints would help. On tractable instances, comparing exact inference over the strong extension with certified LCN bounds would isolate relaxation error, while comparisons with IBP and CDVE would reveal additional approximation error.
  3. Proposition 2 appears to conflate the strong extension with the set of factorizing distributions that generates it. Equation (4) defines (DSED_{\mathrm{SE}}) as a convex hull, but the proof in Appendix C treats an arbitrary element of this hull as a product distribution, overlooking the fact that mixtures need not preserve independence.
Questions for authors
  1. CDVE produces inner bounds relative to the strong extension; these are not automatically valid inner bounds for the original LCN when the two sets differ. Could the authors clarify this interpretation and state whether the cluster mean replacement in CVEcm preserves any rigorous lower or upper bound guarantees?
  2. How do Equations (5)–(7) handle the family-realizable tree (A→BA\to B) with (P(A=1)=0.5P(A=1)=0.5), (P(B=1∣A=1)=0.9)P(B=1\mid A=1)=0.9), and (P(B=1∣A=0)=0.1P(B=1\mid A=0)=0.1)? With evidence (B=1B=1), the factor messages yield ([0.5,0.5]) and ([0.9,0.9]), so Equation (7) appears to return an invalid interval ([0.9,0.5]), rather than the exact ([0.9,0.9]). Is an additional message-combination rule missing?
  3. Equation (4) defines (DSED_{\mathrm{SE}}) as a convex hull, but the proof in Appendix C (Proposition 4) treats an arbitrary member as a factorizing distribution. Since mixtures of independent distributions need not preserve independence, how is the claimed equality (DSE=DLCND_{\mathrm{SE}}=D_{\mathrm{LCN}}) justified?
4 comments

W1. Are all CJT reference endpoints certified, and how are uncertified ones treated? Yes; only certified endpoints are used (§5 "Reference and metrics"; App. I.2). An endpoint enters the reference only if two conditions hold:

  • SCIP proves it optimal, or its primal–dual gap is ≤10−4\le 10^{-4};
  • the structural conditions H1–H4 of Thm. 1 hold.

Uncertified endpoints are excluded from scoring, and CJT reports them by their dual bound, which is sound and outer. Certification rates are 100% on the tree/polytree/ktree sets, 98.6% / 81.6% on small / large DAGs, and 95.6–99.7% on the almost-realizable sets (§5).

W2. A controlled analysis of the strong-extension relaxation. We ran it, following your suggestion (§5 "Almost-realizable LCNs"; Fig. 3c; App. I.6).

  • Design.
    • Family-realizable tree/dag bases (n∈{10,20}n\in\{10,20\}) receive m∈{0,1,2,4,8}m\in\{0,1,2,4,8\} non-realizable sentences.
    • There are three kinds: non-root marginals (nr1), mixture conditionals (nr2) and cross-family sentences (nr3).
    • Tightness varies with δ∈{0.05,0.1,0.3}\delta\in\{0.05,0.1,0.3\}.
    • A 60-instance ablation varies one kind at a time.
  • Isolating relaxation error. CVE is exact for DSE\mathcal D_{SE}, so the error of CVE against the certified LCN bounds is the relaxation error. The difference between IVBP/CDVE and CVE is the algorithmic error.
  • Findings.
    • CVE, CVE$_\varepsilon$ and CDVE agree to within 2×10−32\times10^{-3}, and IVBP agrees with them on trees. So the remaining error is the relaxation itself.
    • The relaxation is outer (99.9% of atoms).
    • It grows with mm: the mean error is 0.03–0.04 at m=1m=1 and 0.14 at m=8m=8, and intervals become 1.3–2.3× wider.
    • It halves at n=20n=20.
    • Non-root marginals are by far the most damaging kind (MAE 0.15, width ratio 3.9 at m=4m=4, against 0.03–0.05 for the other kinds).
    • ARIEL stays within 0.013 MAE but has no guarantee.

W3 / Q3. Old Prop. 2 / Prop. 4 conflate DSE\mathcal D_{SE} with the factorizing set. Correct, and fixed. We now distinguish the product set PSE\mathcal P_{SE} from its hull DSE\mathcal D_{SE} (§2.1, Eqs. 1–2). The claimed equality is now PSE=DLCN\mathcal P_{SE}=\mathcal D_{LCN} (Prop. 2; proof in App. E.3); no member of the hull is treated as a product. The inclusion is DLCN⊆PSE⊆DSE\mathcal D_{LCN}\subseteq\mathcal P_{SE}\subseteq\mathcal D_{SE} (Prop. 1; App. E.2). Bounds transfer to the hull because a linear-fractional objective attains its extrema at extreme points, which lie in PSE\mathcal P_{SE} (Lemma 3). App. E.4 shows the hypotheses of Prop. 2 are necessary.

Q1. CDVE's inner bounds and CVE$_{cm}$. CDVE is inner for DSE\mathcal D_{SE} (every visited point is a member with P(e)>0P(e)>0). It is inner for DLCN\mathcal D_{LCN} only when the two sets have the same bounds, e.g. under Prop. 2. Otherwise its relation to the LCN interval is not determined; this is now stated in Prop. 3 and Table 1 (§4.3). CVE${cm}/CVE/CVE{cp}$ carried no rigorous guarantee and were removed. The guaranteed approximation is now the FPTAS CVE$_\varepsilon$ of Mauá et al. (2012). It returns inner bounds within a factor 1+ε1+\varepsilon of CVE's (Prop. 7; covering proof, Lemma 12).

Q2. Old Eqs. (5)–(7) give the invalid interval [0.9, 0.5] on a tree with evidence. You found a real bug. The interval-combination rule of old Eq. (7) was replaced.

  • Why the bug cannot recur. Messages are now sets of normalized vectors, stored as hull vertices. The belief is the hull of the normalized elementwise products of the incoming vertices, so its lower and upper bounds are a minimum and a maximum over one set, and an inverted interval cannot arise (App. G.1–G.2).
  • Your example. We ran the corrected code on this tree: P(A)=0.5P(A)=0.5, P(B∣A)=0.9P(B\mid A)=0.9, P(B∣¬A)=0.1P(B\mid\neg A)=0.1, with evidence B=1B=1. The prior message [0.5,0.5][0.5,0.5] and the λ-message [0.9,0.9][0.9,0.9] combine into the single belief vertex 0.5⋅0.9/(0.5⋅0.9+0.5⋅0.1)=0.90.5\cdot0.9/(0.5\cdot0.9+0.5\cdot0.1)=0.9. IVBP returns the exact [0.9,0.9][0.9,0.9], identical to CVE.
  • Exactness. Thm. 7 proves exactness on polytrees with evidence. App. G.3 is a worked example.

Formulation size vs. solving time. Agreed. §3 now states after Thm. 2 that the bound concerns the formulation, not the solving time: global optimization of the nonconvex program is not polynomial in its size, but the program is exponential in ww rather than nn.

Thank you for the detailed response and substantial revisions. The revised proof, IVBP update, and SCIP certification protocol address several of my concerns. The revised manuscript seems to provide no updated results for MScaling and PScaling, leaving the speed–accuracy tradeoff relative to ARIEL on these benchmarks unverified.

AuthorsOpenReview ↗

Realistic LCNs

Thank you for the feedback. We reran the realistic LCNs and report the 14 that the certified reference (CJT with SCIP) covers (§5 "Realistic LCNs"; App. I.8; Tables 20–21). They behave like the almost-realizable sets already included in the revised version of the paper.

Thank you for adding the updated results. They clarify the tradeoff with ARIEL, though certification coverage remains limited and the compiled intervals are substantially wider on application instances.

Reviewer_A2ATOpenReview ↗
Rating
2(+1)
Confidence
4
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies marginal inference in Logical Credal Networks (LCNs), an expressive probabilistic logic framework that combines propositional formulas with imprecise probability bounds to represent sets of probability distributions. The authors exploit the chain graph structure underlying LCNs and reformulate inference as a credal network problem. They also introduce Credal Junction Tree (CJT), an exact inference method that leverages a junction tree decomposition to construct and solve a substantially smaller nonlinear program.

Critical strengths

The main contribution of this paper is to establish an algorithmic connection between chain-graph Logical Credal Networks (LCNs) and credal networks. In particular, the authors introduce Credal Junction Tree (CJT), an exact inference method that exploits the chain graph structure by moralizing and triangulating the graph and constructing a junction tree. This allows the original optimization problem over the full joint probability distribution to be reformulated as a substantially smaller nonlinear program over local clique marginals. The authors further prove that CJT computes exact lower and upper probability bounds for the original LCN under certain conditions, including that every probabilistic constraint can be assigned to a clique and all relevant conditional independence assertions are properly accounted for.

Critical weaknesses

The paper has several limitations that I think deserve further discussion. First, the proposed framework relies heavily on the underlying network structure, as the analysis mainly focuses on chain-graph LCNs, and some of the exactness guarantees require additional assumptions such as family-realizability. For more general LCNs, the strong extension can be substantially larger than the original feasible distribution set, potentially leading to loose probability bounds. The advantages of the approximate methods are not entirely consistent across different settings. Although IBP performs very well on synthetic benchmarks, these instances are specifically constructed to satisfy family-realizability, while on more realistic instances, the existing ARIEL method often produces more accurate bounds. This raises questions about how well the proposed approximations generalize to less structured problems. While CJT significantly reduces the number of variables in the nonlinear program, the resulting optimization problem remains nonconvex. The experiments mainly rely on IPOPT, which does not guarantee global optimality, so it is unclear whether the reported CJT results can always be regarded as certified exact solutions. And the methodological novelty seems somewhat limited, since the chain-graph factorization is based on previous work, and CVE, interval message passing, and coordinate descent are closely related to existing credal network inference techniques. Much of the contribution lies in adapting these methods to LCNs, with CJT being the main new algorithmic development.

Questions for authors

My main concern is the correctness of several theoretical claims. In particular, the dominance pruning rule used in CVE does not appear to preserve the extrema of normalized posterior probabilities, which calls the exactness guarantee in Theorem 2 into question. Similarly, the proposed IBP updates differ substantially from standard belief propagation, and the proof of Theorem 4 does not establish why these updates should be exact on singly connected structures. I am also concerned about the equality between the original LCN distribution set and the strong extension, since the latter is defined as a convex hull and may contain distributions that violate the original conditional independence constraints. Finally, while the CJT reconstruction argument appears more plausible under its stated assumptions, the paper does not clearly establish how often these assumptions hold in practice, and the descriptions of the optimization solver and global optimality guarantees are inconsistent across the main text and appendix. These issues directly affect the validity of the theoretical guarantees and the reliability of the experimental comparisons. I believe they require substantial clarification and, potentially, corrections to the stated results.

2 comments

Q1. CVE's dominance pruning does not preserve the extrema of normalized posteriors (old Thm. 2). You are right, and the rule was replaced. CVE now reduces every query-free potential to the pairs whose normalized functions are vertices of the convex hull of the set (§4.3; Alg. 2, App. F.5). The query ratio q/(p+q)q/(p+q) is linear-fractional in each function, so its extrema are attained at vertices (Lemma 3). Pareto pruning is applied only at the final step, where it is exact. A covering lemma (Lemma 12) shows that every reduction keeps, for every way the rest of the elimination can weight a pair, a pair at least as good for each bound. This gives exactness for DSE\mathcal D_{SE} with or without evidence (Thm. 5; proof in App. F.8). Empirically, CVE matches every certified endpoint on all 480 family-realizable instances (MAE <10−5<10^{-5}; §5).

Q2. The IBP updates are non-standard, and the exactness proof (old Thm. 4) is missing. IVBP was rebuilt and renamed (IBP already denotes Iterative BP). It now runs sum-product on the credal network's factor graph. Each message is the set of hull vertices of its normalized message vectors; for binary nodes this is the factor-graph form of 2U (§4.3; updates in App. G.2, Alg. 3).

Q3. DSE\mathcal D_{SE} is a convex hull and may violate the LCN's independences. Agreed; the submission conflated the two sets. We now separate them:

  • the product set PSE\mathcal P_{SE} (Eq. 1), whose members do factorize;
  • its hull DSE\mathcal D_{SE} (Eq. 2), which may contain mixtures (§2.1).

The set-level results concern PSE\mathcal P_{SE}:

  • DLCN⊆PSE\mathcal D_{LCN}\subseteq\mathcal P_{SE} for factorizing LCNs (Prop. 1);
  • PSE=DLCN\mathcal P_{SE}=\mathcal D_{LCN} under explicit hypotheses (Prop. 2): consistency, local feasibility, factorization, the product-Markov property, and full family-realizability.

The bounds transfer to DSE\mathcal D_{SE} because both sets have the same lower and upper probabilities, for marginals and conditionals (Lemma 3). App. E.4 gives counterexamples showing that each hypothesis is needed.

Q4. How often do CJT's assumptions hold, and are the solver descriptions inconsistent? H1–H4 are checked for each instance rather than assumed (§3; App. B.2–B.3):

  • H1 by a connectivity test;
  • H2 and H4 by host search;
  • H3 by construction, unless an assertion has to be relaxed, in which case the result is flagged.

They held on all 740 instances, through the ordered construction (Prop. 4), with no relaxed assertion (§5). The solver description is now the same in the main text and the appendix:

  • Every endpoint is solved by SCIP. It is reported as certified if it is proven optimal or its primal–dual gap is ≤10−4\le 10^{-4}. Otherwise its dual bound is reported, which is a sound outer bound (§3; App. B.3).
  • ipopt appears only as a separately labelled variant (CJT$_{\text{ipopt}}$). It is shown to fall into local optima on DAGs (§5).

W1. The experiments rely on IPOPT, so CJT is not certified. The reference is now CJT solved by SCIP, and only certified endpoints are scored (§5; App. I.2). SCIP certifies all 17,700 endpoints on the tree, polytree and ktree sets, 98.6% / 81.6% of the endpoints on small / large DAGs, and 95.6–99.7% on the almost-realizable sets. The exact 2n2^n method certifies all endpoints only up to n≈6n\approx 6 (App. I.3).

W2. Reliance on chain-graph structure and family-realizability, and the generalization of the approximations. CJT's exactness does not require family-realizability: it needs only H1–H4, which are checked per instance. Family-realizability matters only for the compiled route. Rather than restricting the benchmarks to family-realizable LCNs, we now measure what happens outside that class (§5; Fig. 3c; App. I.6):

  • Adding mm non-realizable sentences makes the compiled bounds looser, but they stay outer: CVE contains the reference on 99.9% of atoms.
  • The mean endpoint error grows from 0 at m=0m=0 to 0.14 at m=8m=8.
  • CJT stays exact throughout.

The compiled methods are therefore positioned as fast and exact on family-realizable LCNs, and sound but loose elsewhere. CJT is the general exact method.

W3. Limited novelty. We agree that CVE, IVBP and CDVE adapt existing techniques, and §4.3 now presents them that way. The main contributions are:

  • CJT (§3), with mechanically checked exactness conditions (Thm. 1);
  • the characterization of when compilation is exact (Prop. 2, the exact local sets for compound children in §4.1, and the counterexamples in App. E.4);
  • corrected guarantees for the adapted algorithms under evidence and compound nodes (Table 1, Prop. 3).

Thank you for your rebuttal. Based on your response, I have decided to increase my score.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response to all reviewers

We thank the reviewers for their careful reading. The concerns about soundness were justified: several statements in the submission were wrong or not proven. We corrected them and reran every experiment. Changes are in blue in the revised PDF. The appendix was rewritten throughout, and sections with no counterpart in the submission are tagged (new).

Summary of the main changes

  1. Restructuring. Credal networks now come before LCNs (§2.1). CJT, the main contribution, is now §3. The credal-network route is §4. CVE, IVBP and CDVE are presented explicitly as adaptations of existing algorithms: §4.3 summarizes them, with Table 1 and Prop. 3. Their full descriptions, pseudocode and proofs are in Apps. F–H.
  2. Corrected theory.
    • The strong extension. We now distinguish the product set PSE\mathcal P_{SE} from its convex hull DSE\mathcal D_{SE}. Prop. 1 states DLCN⊆PSE⊆DSE\mathcal D_{LCN}\subseteq\mathcal P_{SE}\subseteq\mathcal D_{SE}, and Prop. 2 states PSE=DLCN\mathcal P_{SE}=\mathcal D_{LCN}. Both sets have the same bounds (Lemma 3).
    • CVE pruning. CVE now uses exact convex-hull pruning instead of dominance pruning (Thm. 5).
    • IVBP. IVBP was rebuilt as a credal sum-product algorithm, with a full exactness proof on polytrees (Thm. 7).
    • CJT. CJT's hypotheses H1–H4 are now checked mechanically for every instance (Thm. 1).
  3. Corrected experiments (§5, App. I).
    • Reference. The reference is now CJT solved by the global solver SCIP. An endpoint is scored only if SCIP certifies it and H1–H4 hold.
    • Benchmarks. The experiments cover 740 instances. 480 are family-realizable LCNs with up to 100 atoms. The other 260 are almost-realizable LCNs, built by adding a controlled number of non-realizable sentences.
    • Removed variants. CVE${cm}/CVE/CVE{cp}$ were removed.
    • Realistic instances. The submission's realistic-instance numbers came from the code before these corrections. We removed them, and the rerun will be added to App. I.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.