{"id":"109426a8-fbf5-4af5-abfa-aecd5ba80e54","arxiv_id":"2505.11089","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A DCA-based column generation heuristic learns high-scoring Bayesian networks from Gaussian data, outperforming GOBNILP on BIC score within time limits.","lead":"This paper speeds up score-based Bayesian network structure learning by solving column generation's pricing subproblem with difference-of-submodular optimization (DCA). A reader interested in causal discovery or large-scale integer programming heuristics will find a practical method that beats an exact solver on dense Gaussian problems within a time budget.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"DCA subgradient formulas in §3.2 omit the N/2 (Gaussian) and N (discrete) factors present in Propositions 1–2, so as written the algorithm is not minimizing the stated DS pricing objective and Eq. (4) does not apply.","rationale":"The reader's verdict was CONDITIONAL and I agree that the paper needs revision, but the most load-bearing problem is not merely that DCA is a local method. The manuscript's own algorithm description is internally inconsistent with its DS reformulation: the subgradient formulas in §3.2 drop the sample-size factors that appear in Propositions 1 and 2. Since the DCA update depends on the subgradient y_t, using a scaled-down vector is not equivalent to solving the stated DC program; the convergence property (4) is lost. This matters because the paper's contribution is precisely 'apply DCA to the DS pricing problem'. If the printed formulas are implemented, the method is some other heuristic and the theoretical grounding of the experiments is absent. If they are a typo and the code uses correct factors, the paper needs to state that and release code; either way, the current text is not verifiable. The concrete test I propose (comparing printed versus true subgradient, then running both variants) settles which world we are in. The DS reformulation itself in Propositions 1–2 appears mathematically sound, so the paper is not hopeless; the verdict remains CONDITIONAL, but the conditions should include correcting these formulas and releasing the implementation.","tokens_in":21167,"tokens_out":14246,"duration_ms":145968,"concrete_test":"On a small Gaussian dataset (e.g., n=6, N=20), pick a random x_t in [0,1]^{n−1}, sort it, and compute (a) the printed y_t from §3.2 and (b) the true subgradient (N/2)(logdet(Σ_{S_k}) − logdet(Σ_{S_{k−1}})). Verify whether (a) = (b)/(N/2). Then run Algorithm 1 with both y choices on the same pricing instance and record z_L(x_t) across iterations. With the printed y_t the sequence need not be non-increasing; with the corrected y_t, Eq. (4) should hold. Also record whether each variant finds columns with negative reduced cost. This distinguishes a typographical omission from a working algorithm and settles whether the DCA/DS claim is supported as written.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim requires that DCA solve the DS pricing problem of Propositions 1–2. Section 3.2 states subgradients of f_L at x_t. For the Gaussian case f(J) = (N/2) logdet(Σ_{J,J}) (Prop. 1), so the derivative along the sorted order is (N/2)(logdet(Σ_{S_k}) − logdet(Σ_{S_{k−1}})). The paper instead gives y_t = logdet(Σ_{S_k}) − logdet(Σ_{S_{k−1}}), omitting N/2. For the discrete case f(J) = N·H(J) − Λ(a_i−1)∏_{j∈J} a_j (Prop. 2), the entropy marginal should appear with factor N, but the paper prints it without N. With these y_t, Algorithm 1 Line 5 minimizes g_L(x) − ⟨y_t, x⟩, which is not the DCA subproblem for z_L = g_L − f_L; y_t is not a subgradient of f_L, so the monotone-decrease guarantee (4) is not valid for the stated objective. Because no code is released, the reported CG-DCA results cannot be checked against the analyzed algorithm; the empirical advantage may come from a different objective or update. This is a concrete correctness gap in the core method, distinct from (and prior to) any concern about DCA local optimality.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes an inexact column generation (CG) method for Bayesian network structure learning (BNSL). For l0-penalized Gaussian and multinomial likelihood scores, it rewrites the CG pricing problem as a difference of submodular (DS) functions (Propositions 1 and 2) and applies the Difference of Convex Algorithm (DCA) to generate columns with negative reduced costs. The resulting CG-DCA is compared against GOBNILP, CG-MINLP, hill climbing, stable-PC, and MMHC on simulated Gaussian data (n=15,20,25; average in-degree 0.5-2) and on three small discrete benchmarks. The authors report better BIC scores than GOBNILP on Gaussian instances within a 3-hour time limit, and structural accuracy competitive with constraint-based and hybrid baselines; they also report that DCA is ineffective for discrete scores.","tokens_in":21426,"tokens_out":8931,"duration_ms":87566,"significance":"The DS reformulation of the pricing problem is a clean and checkable contribution: it replaces an MINLP pricing subproblem with submodular optimization, for which efficient local methods such as DCA exist, and the algebraic derivations in Propositions 1-2 are transparent and use standard submodularity arguments. If the implementation matched the stated objective, the approach would be a useful heuristic for Gaussian BNSL and a step toward more scalable exact branch-price-and-cut. However, the paper does not release code, the DCA subgradient formulas in Section 3.2 contain a scaling error relative to the stated DS decomposition, and the empirical claims are weakened by the absence of error bars and by the 3-hour time limits that often terminate GOBNILP without proof of optimality. The discrete results are explicitly acknowledged by the authors to degrade, so the demonstrated practical contribution is essentially limited to Gaussian scores.","major_comments":[{"comment":"The displayed subgradient formulas for f_L omit the multiplicative constants present in Propositions 1 and 2. In the continuous case, Proposition 1 defines f(J) = (N/2) log det(Σ_{J,J}); hence a subgradient of f_L at x^t along the sorted order has k-th component (N/2)(log det(Σ_{S_k}) − log det(Σ_{S_{k−1}})), but the paper prints log det(Σ_{S_k}) − log det(Σ_{S_{k−1}}) with no factor N/2. In the discrete case, Proposition 2 defines f(J) = N·H(J) − Λ(a_i−1)∏_{j∈J} a_j; the printed subgradient omits N on the entropy differences. Consequently, the vector y^t used in Algorithm 1 Line 5 is not a subgradient of the stated f_L, the subproblem solved is not the DCA linearization of z_L = g_L − f_L, and the monotone non-increase guarantee (4)—which the paper relies on for the convergence of the pricing heuristic—does not follow for the objective of Propositions 1-2. Because no code is released, the reported CG-DCA results cannot be checked to determine whether the experiments used the correct factors or the printed unscaled formulas. This must be corrected and the experiments either re-run with the correct subgradients or explicitly documented as using a differently scaled objective.","section":"§3.2"},{"comment":"The headline claim that CG-DCA 'consistently outperforms GOBNILP in terms of average scores' is a comparison under a 3-hour time limit, not a claim about optimality. Several GOBNILP rows report runtimes at or near 10800 seconds (e.g., the (25,5000,2.0) and (25,20000,2.0) rows show max times of 10801.63s and 10801.71s), so for those instances GOBNILP was terminated without proving optimality and the reported BIC gaps are upper bounds on the achievable gaps. The abstract and Section 5.2 should qualify the claim as 'within the time budget.' In addition, Table 1 reports (min, max) and average over ten instances without standard deviations or any measures of variability; with only ten replications and gaps as small as 0.00–0.03 in several rows, the phrase 'consistently outperforms' is not statistically supported. Please add per-cell variation (e.g., standard errors), report how many instances hit the time limit for each solver, and adjust the wording accordingly.","section":"Table 1 / Abstract"},{"comment":"The paper's own Section 5.3 states that for the discrete BIC score the 'highly supermodular penalization term ... makes DCA less effective,' and Table 3 shows CG-DCA with SHD 35–37 on ALARM versus GOBNILP's 7 and precision 0.46 versus 0.87. The conclusion acknowledges limited scalability for discrete data. Given this, the abstract's phrase 'for the general class of ℓ0-penalized likelihood scores' overstates the demonstrated scope: the DS reformulation in Propositions 1-2 is general, but the proposed algorithm is shown to be effective only for Gaussian scores, while the discrete experiments serve as a negative result for the DCA approach. The abstract and introduction should temper the general-claim language, or the discrete results should be framed explicitly as a limitation rather than as evidence of viability.","section":"§5.3, §6"}],"minor_comments":[{"comment":"The quantity z_i(J;λ*) in (3) is the negative of the standard reduced cost for a maximization LP: the standard reduced cost of x_{i←J} would be score_i(J) − λ*_i − ∑_{C} λ*_C. Please state this sign convention explicitly to avoid confusion when comparing with the column generation literature.","section":"Equation (3)"},{"comment":"Algorithm 1 returns a vector x^t, while Algorithm 2 Line 10 uses a parent set 'pa'; the paper does not specify how the binary parent set is recovered from the possibly fractional DCA iterate. Please add a sentence describing the rounding or extreme-point recovery procedure used in the implementation.","section":"Algorithm 1 / Algorithm 2"},{"comment":"The hybrid initialization switches from random to warm-start once the candidate set contains 50 parent sets, but Appendix D.1 only compares the three strategies at this fixed threshold and provides no sensitivity analysis. Please report results for a range of threshold values or justify the chosen value.","section":"§4.1"},{"comment":"The word 'inaccurrate' in the sentence about MINLP numerical issues should be spelled 'inaccurate'.","section":"§5.1"}],"recommendation":"major_revision","confidential_remarks":"The missing N/2 and N factors in the Section 3.2 subgradient formulas are likely typographical errors, but because no code is released, the experimental verification must be done by the authors. I would also ask the editor to encourage the authors to make the code available, as the correctness of the pricing implementation cannot otherwise be checked. The empirical section would benefit from standard deviations and a clear statement of how many runs hit the time limit; the current min/max/average format makes the tables hard to read and the 'consistently outperforms' claim too strong."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing to know: Propositions 1 and 2 are correct, and the DS reformulation is genuinely new for BNSL pricing. But Section 3.2's subgradient formulas omit the N/2 (Gaussian) and N (discrete) factors from the f functions defined in the propositions. As written, Algorithm 1 is not computing subgradients of that f, so the DCA monotonicity guarantee in Eq. (4) does not apply to the stated pricing objective. The empirical results might still be fine—the authors could have implemented the right scaling—but without code release we cannot verify.\n\nThe strength is the DS decomposition itself. Writing the Gaussian reduced cost as a difference of submodular functions via logdet is standard but hasn't been applied to BNSL pricing before; the discrete case is analogous. The authors are honest that DCA struggles with the discrete supermodular penalty term, and they flag it in Section 5.3. On Gaussian data, the speedups over GOBNILP and the better BIC scores within the 3-hour budget are credible, though the comparison is time-limited because GOBNILP often hits the cap. The structural metrics are averages over 10 instances without variance, so the precision/recall/SHD claims are weaker than the BIC ones.\n\nBeyond the scaling issue, the soft spots are the missing code and error bars, and an abstract that says 'higher quality' without noting the Gaussian-only success and the time limit. The hybrid initialization threshold and other heuristics are reasonable but would also require code to reproduce.\n\nBottom line: this deserves a serious referee. The DS reformulation is a contribution, and the Gaussian evidence is suggestive. But the paper needs to fix the subgradient formulas—either by adding the constants or by clarifying that the algorithm solves a scaled or approximate objective—and release code so the gap between theory and implementation can be closed. I would send it to review with a request for major revision.","headline":"The DS reformulation of the BNSL pricing problem is sound, but the DCA subgradient formulas in Section 3.2 are missing the N/2 and N scaling factors, so the algorithm as written does not minimize the stated objective.","tokens_in":22016,"tokens_out":3122,"would_cite":false,"duration_ms":31092,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C27","90C11","90C25"],"pacs":[],"model":"deepseek-v4-flash","headline":"Column generation for Bayesian networks can be made practical by solving its pricing problem as a difference of submodular functions with DCA.","keywords":["Bayesian network structure learning","column generation","difference-of-submodular optimization","DCA","l0-penalized likelihood","integer programming","restricted master heuristic","Lovász extension"],"falsifier":"Take one Gaussian instance where CG-DCA terminates quickly (say n = 25, d = 2, N = 5000) and rerun the identical row-and-column generation with DCA pricing replaced by an exact pricing oracle that enumerates all parent sets up to size 4; if the oracle finds a negative reduced cost after CG-DCA has stopped, or the final restricted master IP has a strictly higher BIC score, then the claim that DCA pricing is sufficient for high-quality Gaussian BNSL fails on that instance.","tokens_in":20906,"feed_emoji":"🧠","tokens_out":9567,"duration_ms":85966,"temperature":0.7,"pith_summary":"The paper claims that the pricing step of column generation for score-based Bayesian network structure learning, usually the computational bottleneck, can be rewritten exactly as optimizing a difference of two submodular set functions for ℓ0-penalized Gaussian and multinomial likelihood scores. Because submodular functions have convex Lovász extensions, the difference can be attacked with the Difference of Convex Algorithm, which runs fast and yields candidate parent sets with negative reduced cost. The authors combine this inexact pricing with row and column generation and a restricted master IP heuristic into CG-DCA. On continuous Gaussian data, CG-DCA finds higher BIC scores than the exact IP solver GOBNILP, especially as graph density grows, and matches constraint-based and hybrid baselines in recovery quality. If right, the value is a substantially cheaper pricing step for an NP-hard search problem, making score-based structure learning viable on larger and denser instances.","feed_headline":"Cheaper pricing finds better Gaussian Bayesian networks","feed_subtitle":"Rewriting column generation's pricing step as a difference of submodular functions lets DCA beat the exact IP baseline.","key_machinery":"The load-bearing object is the Lovász extension of a submodular set function: a convex function on the unit cube that agrees with the set function at 0/1 points. This extension turns the difference-of-submodular pricing objective $\\min_J [g(J)-f(J)]$ into a difference-of-convex program $\\min_x g^L(x)-f^L(x)$, which DCA solves by linearizing $f^L$ at the current point and minimizing the resulting convex approximation. Because a subgradient of the Lovász extension of $f$ can be evaluated through function evaluations of $f$, each DCA iteration is cheap; for Gaussian scores the paper computes all needed subgradients from a single Cholesky factorization of the permuted covariance matrix, which is what makes the pricing loop fast enough to drive column generation.","core_discovery":"The central claim is that, for ℓ0-penalized likelihood scores, the reduced cost of a candidate parent set $J$ for node $i$ in the column-generation pricing problem, $z_i(J;\\lambda^*)=-\\mathrm{score}_i(J)+\\lambda^*_i+\\sum_{C\\in\\hat{C}: i\\in C, J\\cap C\\ne \\emptyset}\\lambda^*_C$, can be written exactly as $g(J)-f(J)$ with both $g$ and $f$ submodular. For Gaussian data the proof uses the Schur-complement identity $\\hat\\sigma^2_{i\\leftarrow J}=\\det(\\hat\\Sigma_{J\\cup\\{i\\},J\\cup\\{i\\}})/\\det(\\hat\\Sigma_{J,J})$ together with the fact that $\\log\\det$ of a principal submatrix is submodular; for multinomial data it uses entropy submodularity and treats the parameter-count penalty $-\\Lambda(a_i-1)\\prod_{j\\in J}a_j$ as part of the subtracted supermodular term. Since the Lovász extension converts each submodular function into a convex function, minimizing $g-f$ becomes a difference-of-convex program, and the Difference of Convex Algorithm (DCA) produces a non-increasing sequence of objective values and, at integer points, recovers the original set-function value. The paper's experiments show that this inexact pricing is fast and accurate enough on Gaussian data that the overall CG-DCA method beats the exact GOBNILP solver in BIC score within a 3-hour budget and matches constraint-based and hybrid methods in graph recovery quality.","pith_inferences":["A direct extension the paper leaves implicit is to embed DCA pricing inside exact branch-and-price: because column generation only needs exact pricing near termination, a DCA-generated negative-reduced-cost column could be accepted as a warm candidate and certified later by an exact oracle, potentially retaining the speedup while restoring optimality guarantees.","The same $g-f$ decomposition should transfer to other ℓ0-penalized scores whose log-likelihood term is submodular in the parent set, such as some exponential-family or nonparametric scores; the two propositions in the paper are templates, not just special cases.","The reported precision/recall pattern—high recall, moderate precision, denser recovered graphs on Gaussian data—suggests that inexact pricing biases column generation toward adding many parent sets; a testable prediction is that the number of negative-reduced-cost columns added per iteration is larger under DCA pricing than under exact pricing.","The switch from random to warm-start initialization after about 50 candidate parent sets is an algorithmic choice that likely carries much of the empirical speedup; varying that threshold and measuring BIC and runtime would isolate how much of the gain comes from the DS reformulation versus the initialization schedule."],"forward_implications":["On simulated Gaussian data with n = 15, 20, and 25, CG-DCA achieves BIC scores at or near the true-graph score and smaller average BIC gaps than GOBNILP, with the advantage growing as the average in-degree increases.","Pricing with DCA is orders of magnitude faster than the MINLP pricing baseline: it recovers the Gaussian.test ground truth in 1.2 seconds versus 19.2 seconds, and per-node pricing drops from about 35.1 seconds to 0.3 seconds on an n = 20, d = 1 instance.","Collecting intermediate DCA solutions as candidate columns and using warm-started restricted master IPs yields valid DAGs, so the approach works as a primal heuristic with acyclicity enforced through lazy cluster constraints.","On discrete data the supermodular penalty term $(a_i-1)\\prod_{j\\in J}a_j$ in the multinomial score makes DCA less effective, and GOBNILP outperforms CG-DCA on the LUCAS, INSURANCE, and ALARM benchmarks."],"supporting_citations":[{"why":"Supplies the column-generation formulation and the MINLP pricing baseline that DCA pricing is designed to replace.","marker":"[18]"},{"why":"The exact IP solver that CG-DCA is compared against on BIC score and runtime.","marker":"[17]"},{"why":"Provides the DCA algorithm for difference-of-submodular minimization used as the pricing engine.","marker":"[22]"},{"why":"Establishes that arbitrary set functions admit difference-of-submodular decompositions and motivates approximate DS minimization.","marker":"[30]"},{"why":"Proves that the log-determinant of a principal submatrix is submodular in the index set, used in Proposition 1.","marker":"[34]"},{"why":"Establishes that entropy is submodular, used in Proposition 2 for the multinomial score.","marker":"[24]"},{"why":"Provides the cluster-constraint IP formulation whose dual values enter the pricing objective.","marker":"[31]"},{"why":"Provides the restricted master heuristic that turns generated columns into a DAG solution.","marker":"[32]"},{"why":"Justifies using approximate pricing solutions in column generation rather than solving every pricing problem exactly.","marker":"[37]"}],"fun_headline_variants":["Submodular pricing beats exact IP in Bayesian net search","DCA inexact pricing finds higher-quality Bayesian networks","Submodular difference pricing cuts cost, boosts BNSL quality","Inexact pricing via DC programming finds better Gaussian nets","Submodular reformulation of pricing makes BNSL column-gen viable"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is empirical: DCA's local solutions to the difference-of-submodular pricing problem must have negative reduced costs often enough for the restricted master heuristic to find good DAGs, since DCA only guarantees that its objective sequence does not increase and gives no global optimality certificate.","fun_headline_variants_meta":{"raw":{"variants":["Submodular pricing beats exact IP in Bayesian net search","DCA inexact pricing finds higher-quality Bayesian networks","Submodular difference pricing cuts cost, boosts BNSL quality","Inexact pricing via DC programming finds better Gaussian nets","Submodular reformulation of pricing makes BNSL column-gen viable"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000713,"raw_usage":{"total_tokens":3268,"prompt_tokens":1066,"completion_tokens":2202,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":682,"completion_tokens_details":{"reasoning_tokens":2117}},"tokens_in":682,"tokens_out":2202,"duration_ms":14228,"temperature":1.0,"reasoning_tokens":2117,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T20:58:20.995361+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take one Gaussian instance where CG-DCA terminates quickly (say n = 25, d = 2, N = 5000) and rerun the identical row-and-column generation with DCA pricing replaced by an exact pricing oracle that enumerates all parent sets up to size 4; if the oracle finds a negative reduced cost after CG-DCA has stopped, or the final restricted master IP has a strictly higher BIC score, then the claim that DCA pricing is sufficient for high-quality Gaussian BNSL fails on that instance.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the column-generation formulation and the MINLP pricing baseline that DCA pricing is designed to replace."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The exact IP solver that CG-DCA is compared against on BIC score and runtime."},{"cited_title":"El Halabi, G","cited_arxiv_id":null,"evidence_quote":"Provides the DCA algorithm for difference-of-submodular minimization used as the pricing engine."},{"cited_title":"Iyer and J","cited_arxiv_id":null,"evidence_quote":"Establishes that arbitrary set functions admit difference-of-submodular decompositions and motivates approximate DS minimization."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Proves that the log-determinant of a principal submatrix is submodular in the index set, used in Proposition 1."},{"cited_title":"Fujishige","cited_arxiv_id":null,"evidence_quote":"Establishes that entropy is submodular, used in Proposition 2 for the multinomial score."},{"cited_title":"Jaakkola, D","cited_arxiv_id":null,"evidence_quote":"Provides the cluster-constraint IP formulation whose dual values enter the pricing objective."},{"cited_title":"Joncour, S","cited_arxiv_id":null,"evidence_quote":"Provides the restricted master heuristic that turns generated columns into a DAG solution."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Justifies using approximate pricing solutions in column generation rather than solving every pricing problem exactly."}],"review_version":1}