Most exact methods for learning a Bayesian network, a directed acyclic graph (DAG) in which each variable is predicted from a small set of "parent" variables, work only on discrete data. Continuous measurements are therefore binned first, using a fixed rule such as equal-frequency cuts or Sturges' rule, and only then passed to an integer-programming solver that returns a provably best-scoring graph. Binning is not harmless. On three-variable networks where $X$ and $Y$ are independent given $Z$, every standard binning rule reported a strong dependence in all 15 test cases (Distribution-Free Learning of Bayesian Network Structure in Continuous Domains). Fixed cutoffs also hide sub-threshold effects and U-shaped relationships (Anaya et al.; Walter et al.). The optimality certificate is therefore a certificate about the wrong data.
The obvious fix is one large mixed-integer program that chooses cut-points and edges together. We argue that this program is mostly unnecessary. The coupling between cuts and graph exists only if each variable must carry one discretization everywhere in the model. If the child stays continuous and each family (a child plus its parents) is allowed its own partition of the parents' values, the joint problem splits into independent per-family problems plus the usual acyclicity problem. The exact graph solver can then be used unchanged. All the hard work moves into two places. The first is computing each family's score, meaning the best penalized fit of a shallow regression tree of the child on those parents, with thresholds searched over continuous values. The second is proving which parent sets can never be optimal, so they are never scored. Continuous-threshold pruning from optimal decision-tree search handles the first. A single per-node "ceiling" bound handles the second. The result is a globally certified DAG for the class of tree-shaped conditional distributions, with no binning step anywhere.
Core Claim
Define the local score of child $v$ with candidate parent set $W$ as
$$s(v,W) = \max_{T \in \mathcal{T}_d(W)} \Big[ \ell(v \mid T) - \tfrac{\log N}{2}\, p(T) \Big],$$
where $\mathcal{T}_d(W)$ is the set of regression trees of depth at most $d$ that split only on variables in $W$ at arbitrary real thresholds, $\ell(v\mid T)$ is the Gaussian log-likelihood of $v$ with a constant or linear model in each leaf, $p(T)$ counts the tree's free parameters, and $N$ is the sample size.
This score is decomposable across families. It is also comparable across parent sets, because the child is always scored as a continuous density. So the standard parent-set formulation of Learning Bayesian Network Structure using LP Relaxations, solved by branch-and-cut as in GOBNILP (Advances in Bayesian Network Learning using Integer Programming), returns the global optimum over DAGs whenever the local scores are exact.
The pruning bound works as follows. Let $L_v$ be the unpenalized likelihood of the best depth-$d$ tree for $v$ over all other variables, computed once per node. Every tree over any superset $W' \supseteq W$ is also a tree over all variables, so
$$s(v,W') \le L_v - \tfrac{\log N}{2}\, p_{\min}(|W'|),$$
where $p_{\min}(m)$ is the fewest parameters any tree needs in order to actually use $m$ distinct parents. Whenever the right-hand side falls below $s(v,W)$, every such superset can be discarded without being scored. The claim to be tested is threefold: exact family-local partitioning recovers nonlinear structure that pre-binning and linear-Gaussian scores miss; the bound removes most candidate parent sets; and the whole pipeline keeps a real optimality gap on networks of about 40 to 60 nodes.
Relation to Prior Work
Three works supply the method. Structure Learning for Bayesian Networks over Labeled DAGs already follows the "search local partitions, then hand the scores to GOBNILP" pattern. It partitions rows of discrete conditional probability tables and reports about 2.5 million local scores in roughly 7 hours on the 37-node Alarm network. We reuse the pattern, but partition continuous parent values instead of discrete table rows, and we add a pruning bound that the LDAG work lacks. ArborEnum prunes whole intervals of continuous split thresholds without binarizing. CLARITree updates linear leaf models with rank-one Cholesky updates during threshold sweeps. Both were built for one prediction target. We run them once per family, as the inner solver for $s(v,W)$.
Other work motivates the proposal or constrains its design. A* Lasso showed that pruning parents before exact search causes errors that cannot be undone, and that heuristics which never overestimate can prune safely. Our ceiling bound follows the second idea while avoiding the first failure. A* Lasso is also restricted to linear-Gaussian scores, which is the gap we target. Inexact Column Generation via Difference-of-Submodular Optimization generates parent sets on demand but gives up exact bounds, and it degrades when penalties are supermodular. Tree penalties behave like discrete ones in this respect, which is why we prune by a certified bound instead of pricing with a heuristic. Guo and Schuurmans is a warning about continuous relaxations: learned orderings were often worse than random, and the method ran 10 to 100 times slower than greedy search. That is why we keep the exact integer program.
The recursive-median test of Distribution-Free Learning of Bayesian Network Structure in Continuous Domains is the closest competitor on nonlinear continuous data. It is constraint-based and was evaluated only up to 14 variables, because it cannot condition on more than one or two continuous variables. A score-based approach avoids that fragmentation by penalizing tree size instead of testing within cells.
Research Program
The first component is the local scorer. We will implement exact depth-2 and depth-3 tree scoring over a parent set, with constant or linear Gaussian leaves. Threshold intervals will be pruned by an active-sample-distance argument adapted from ArborEnum. When leaves are linear, CLARITree-style Cholesky updates will be used. We will prove that the returned value equals $s(v,W)$. Where exact scoring times out, the scorer will return an upper and a lower bound, and the upper bound will enter the integer program as a relaxed objective coefficient. Any optimality gap reported at the end therefore stays honest.
The second component is the pruning bound. We will compute $L_v$ per node and derive $p_{\min}$ in closed form for each leaf model. We will then measure the fraction of parent sets of size up to 4 that are removed. That size is exactly where the precomputation cost of GOBNILP becomes the bottleneck.
The third component is the global solve. GOBNILP will be run on the surviving scores, and we will record the incumbent, the dual bound, and the gap.
The fourth component is an analysis question: when does allowing each family its own cuts, rather than one discretization per variable, change the recovered graph? On graphs of at most 10 nodes we will write the single-discretization mixed-integer program explicitly. It uses binary cut indicators shared across all families in which a variable appears as a parent. Comparing its optimum with ours measures how much the obvious joint formulation actually buys.
Baselines
The naive reference point is equal-frequency binning, and separately Sturges binning, followed by GOBNILP with BIC. This is exactly what practitioners do today. It is run on the same data, with the same maximum in-degree and the same wall-clock limit. The comparison is fair because the graph solver is identical and only the handling of continuous data differs. For reference, GOBNILP 1.3 solved alarm_3_10000 in under 5 minutes, against over 3.5 hours for its predecessor (Advances in Bayesian Network Learning using Integer Programming). Beating this baseline means lower structural Hamming distance (SHD, the number of edge additions, deletions, and reversals needed to reach the true graph) and higher held-out log-likelihood on nonlinear data, with no loss on linear data.
The strongest existing exact competitor is GOBNILP with linear-Gaussian BIC local scores, alongside CG-DCA. CG-DCA reportedly "consistently achieves better BIC scores compared to GOBNILP" on simulated Gaussian networks (Inexact Column Generation); the file gives no numeric value. We will run it on the same data with the same time budget. On linear Gaussian simulations we expect to tie and must not lose by much, since a tree with linear leaves contains the linear model as a special case at depth 0. On nonlinear data we must win on SHD.
A* Lasso is the strongest continuous exact-search method in the file. It reports lower held-out prediction error than L1MB and SBN on 125 S&P 500 stocks and visits sometimes only 10% of the states dynamic programming visits; no numeric error is reported on Lacuna. We run it on the same S&P 500 data and the same splits. Beating it means lower held-out prediction error there.
F2SL-s (Feature Selection for Efficient Local-to-Global BNSL) is the fastest local-to-global method. It is reported up to 58,065 times faster than GGSL and often better on oriented-edge F1. It is run with its default threshold of 0.05 and with a threshold tuned under the same budget we spend on our own tree depth. We expect to be slower. Beating it means better oriented-edge F1 at a stated runtime ratio.
The recursive-median PC variant is run only on networks of at most 14 nodes. For nonlinear continuous DAGs with more than a handful of nodes, no reported SHD result was found on Lacuna for any of these methods. The only hard number is the 15/15 versus 0/15 Lambda result, which we will reproduce as a sanity check.
Four ablations isolate the key ingredients. The first swaps greedy CART trees in as local scores. The second disables the pruning bound and enumerates every parent set up to the in-degree limit. The third replaces family-local cuts with the single-discretization joint mixed-integer program on small graphs. The fourth compares constant with linear leaves.
Why not just…?
Why not just filter candidate parents with FCBF or Lasso and then run the exact solver? A* Lasso documents that this two-stage recipe permanently loses true parents that are collinear with, or only indirectly associated with, the child. Pairwise filters are also blind to parents whose effect appears only jointly with another parent, which is exactly the regime where a tree helps. Our bound prunes only parent sets that provably cannot be optimal. The disabled-bound ablation, compared against FCBF pre-filtering at a matched candidate count, will show whether safe pruning retains true parents that the filter drops.
Why not just use linear-Gaussian scores? They are cheap and exact, but the Lambda and MEANDER results in Distribution-Free Learning show linear tests failing on sinusoidal, exponential, and logarithmic links. On truly linear data this alternative is a real threat. We report linear simulations separately, and if our method loses there by more than noise, we will say so.
Why not just discretize adaptively first, for example by recursive median or supervised binning, and keep GOBNILP? Any single discretization per variable must serve every child that variable parents. When two children depend on a parent through different thresholds, one binning cannot fit both. The single-discretization ablation on small graphs measures this cost directly. If it turns out negligible, the per-family modelling choice is not what drives the gains, and the contribution shrinks to the scorer and the pruning bound.
Why not just use greedy CART trees as local scores? This is the most serious alternative. It is much faster and may recover nearly the same graphs. What it gives up is the certificate: greedy scores are not the maximum in the definition of $s(v,W)$, so the integer program's gap no longer means anything about the stated model class. We will report both the SHD difference and how often the greedy tree's score falls short of the exact one. If greedy trees match on structure, we will recommend them for practice and keep exact scoring only for certification.
Proposed Experiments
The first set uses synthetic nonlinear data. We take the skeletons of Alarm (37 nodes), Insurance, and Hailfinder (56 nodes), and generate continuous data with the link types of the distribution-free study ($2\sin x$, $e^x$, $\ln|x|$), plus threshold effects and U-shaped effects. Each setting uses $N \in \{500, 1000, 10000\}$ with 10 replicates, together with linear-Gaussian controls. Metrics are SHD and oriented-edge F1 on the equivalence class of graphs that fit the data equally well, held-out log-likelihood, wall-clock time, final optimality gap, and the fraction of parent sets pruned.
The second set uses real data: Boston Housing, where we check whether the absent NOX–MEDV edge is recovered, Abalone, and S&P 500 prices, all evaluated by held-out log-likelihood and prediction error.
Four checks decide the outcome. The first is whether the pruning bound removes most parent sets of size 3 to 4 on 37-node graphs. If it does not, the method does not scale past the LDAG-level cost of hours. The second is whether exact tree scores beat both binned GOBNILP and linear-Gaussian GOBNILP on SHD in the nonlinear settings at every sample size, while staying close on linear data. The third is whether the per-family versus single-discretization comparison shows a structural difference on small graphs. The fourth is whether greedy trees close the gap to exact trees. A negative result on the second check would falsify the core claim. A negative result on the fourth would narrow the contribution to certification.
References
- Distribution-Free Learning of Bayesian Network Structure in Continuous Domains
- Characterization of Non-Monotonic Relationships between Tumor Mutational Burden and Clinical Outcomes
- Creatinine clearance versus serum creatinine as a risk factor in cardiac surgery
- Learning Bayesian Network Structure using LP Relaxations
- Advances in Bayesian Network Learning using Integer Programming
- Structure Learning for Bayesian Networks over Labeled DAGs
- ArborEnum: Decision Tree Rashomon Sets over Continuous Features
- CLARITree: Cholesky and Lookahead Accelerations for Regression with Interpretable Piecewise Linear Trees
- A* Lasso for Learning a Sparse Bayesian Network Structure for Continuous Variables
- Inexact Column Generation for Bayesian Network Structure Learning via Difference-of-Submodular Optimization
- Convex Structure Learning for Bayesian Networks: Polynomial Feature Selection and Approximate Ordering
- Feature Selection for Efficient Local-to-global Bayesian Network Structure Learning