Learning a Bayesian network means recovering a directed acyclic graph that states which variables directly influence which. It is computationally hard because the number of candidate graphs grows super-exponentially with the number of variables. The standard workaround is a hybrid learner. A cheap first phase uses statistical tests to decide which pairs of variables could possibly be linked, producing an undirected "skeleton." A slower second phase searches for the best directed graph using only those candidate links. The approach has one well-known weakness: any true link wrongly discarded in phase one can never come back. With continuous data there is an extra complication. Most fast hybrid learners require the data to be chopped into bins first, and binning is exactly the kind of arbitrary choice that silently changes test verdicts. A coarse grid can make two conditionally independent variables look dependent, and it can erase a real dependence entirely.
This proposal treats that arbitrariness as a signal rather than a nuisance. The plan is to run the cheap phase-one filter several times under different reasonable binnings. A link is discarded only if it is discarded under every binning. Links whose verdict flips across binnings are sent to phase two, which is allowed to refine the bin boundaries while it scores those links. The bet is that the true links a single-binning filter wrongly prunes are concentrated among these flip-flopping links. If so, phase two can spend its expensive, discretization-aware effort on a small, well-chosen set of edges. The result would be recall close to that of a slow, recall-oriented skeleton at close to the cost of a fast one.
Core Claim
Our central empirical hypothesis is that disagreement across discretizations predicts phase-one false negatives. More strongly, it predicts them better than simply loosening the filter's threshold until the same number of extra edges is admitted. If the hypothesis holds, a discretization-robust skeleton gives three things at once. It resists the cascading false negatives documented for two-stage pipelines. It keeps the search space bounded by the skeleton's maximum degree, which is what makes hybrids tractable. And it lets joint cutpoint-and-structure scoring, previously limited to a few dozen variables, run on networks with hundreds of variables.
For each unordered pair $(X,Y)$, let $\Lambda_1,\dots,\Lambda_K$ be a family of discretizations that differ in bin count, rule and cutpoint jitter. Examples of rules are equal-frequency, equal-width and Freedman–Diaconis. Let $e_k(X,Y)\in\{0,1\}$ indicate whether the fast per-node filter keeps the edge after symmetrization under $\Lambda_k$. The retention frequency is
$$ s(X,Y) = \frac{1}{K}\sum_{k=1}^{K} e_k(X,Y). $$
An edge with $s=0$ is pruned, one with $s=1$ enters the skeleton as firm, and one with $0<s<1$ enters as uncertain. Only uncertain edges, and the variables they touch, get adaptive cutpoint refinement in phase two.
Where This Sits in Prior Work
Two papers supply the components.
- Feature Selection for Efficient Local-to-global Bayesian Network Structure Learning (F2SL) recasts each node's parent-and-child set as a feature-selection problem. It uses a pairwise mutual-information filter (Fast Correlation-Based Filter, FCBF) with a fixed relevance threshold, and runs up to 58,065 times faster than GGSL. That speed is what makes running the filter $K$ times affordable. F2SL itself, however, assumes the data were discretized in advance and never asks how the binning changes its verdicts.
- Predictive Discretization during Model Selection scores graph structure and bin cutpoints jointly with a leave-one-out predictive criterion. That criterion is invariant to monotone transformations, and on yeast expression data it recovered roughly 65 edges where static binning gave overly sparse graphs. Its alternating greedy search was only run up to 33 variables, and it uses no skeleton restriction. We reuse its score as the phase-two refinement, but apply it only to uncertain edges inside a restricted candidate graph.
Three papers motivate the proposal by documenting the gap.
- Distribution-Free Learning of Bayesian Network Structure in Continuous Domains shows that standard binning rules falsely flagged dependence in all 15 of its non-linear "Lambda" test cases, where the recursive-median test was correct. That test is limited to a single conditioning variable and is slow. We do not try to scale it. We use cheap binning diversity instead of an expensive adaptive test.
- A* Lasso shows that early parent pruning in two-stage pipelines drops true parents irrecoverably. - An Experimental Comparison of Hybrid Algorithms (H2PC) shows that raising phase-one recall lowers final structural error. Both push toward recall.
Our proposal differs from both in which edges get the extra recall. We choose them by a discretization-sensitivity signal, not by a uniformly more permissive test.
The max-min hill-climbing algorithm (MMHC) constrains the design. Its phase one took 19 hours on a 5,000-variable network, while its orientation phase took about 13 days. Any added phase-two work must therefore stay confined to a small edge set, or the approach loses the reason hybrids exist.
Research Program
Phase one. We will build the multi-discretization filter on top of F2SL's FCBF selection.
- The family $\{\Lambda_k\}$ is fixed in advance, with $K$ between 5 and 10. Bin counts range from 2 to about $\sqrt[3]{N}$ per variable, where $N$ is the sample size. Rules are mixed and cutpoints are randomly jittered.
- Equal-frequency members make the family monotone-invariant.
- The relevance threshold is held at F2SL's default of 0.05. This keeps the flip signal separate from threshold tuning.
Phase two. We restrict a tabu hill-climbing search over directed graphs to firm and uncertain edges.
- Firm edges are scored with a standard discrete score (BDeu) under a single median discretization.
- Families containing an uncertain edge are rescored with the Steck–Jaakkola predictive criterion, alternating cutpoint refinement for those variables only.
- Because parent sets are drawn from the candidate neighborhood, per-node work grows with $2^{d}$ for maximum candidate degree $d$, not with $2^{n}$.
- We will report the uncertain-edge fraction on every run. If it exceeds about 20% of candidate edges, phase-two cost would approach full joint search. That outcome would itself be a finding about when binning is unreliable.
Analysis. We will measure how enriched the uncertain set is for true edges relative to pruned edges. We will also measure how that enrichment changes with sample size, link non-linearity, and the conditioning-set sizes the filter implicitly uses.
Baselines
Naive reference: F2SL on one static discretization. We run F2SL-s (FCBF skeleton plus BDeu hill climbing) with equal-frequency binning at a fixed bin count, and separately with Freedman–Diaconis bins. It gets the same data and the same tabu budget as our method. It is the "do nothing" point: what practitioners run today. Beating it means lower structural Hamming distance (SHD, the number of edge additions, deletions or reversals needed to reach the true graph) and higher skeleton recall, at no more than about $K$ times its phase-one runtime.
Strongest recall-oriented hybrid: H2PC under the same static discretizations. H2PC is the most relevant competitor because it attacks the same failure, phase-one false negatives. The file reports only that H2PC beats MMHC in SHD across eight discrete networks while running up to eight times slower at 5,000 samples. It reports no scalar SHD, and no reported result was found on Lacuna for H2PC on continuous, non-linear data. We will therefore run it ourselves with identical data, the same tabu settings and a matched wall-clock cap. Beating it means comparable or lower SHD at lower runtime.
Linear-Gaussian hybrid. MMHC with partial-correlation tests and a Gaussian score avoids binning altogether. We tune it over its significance level with the same number of configurations we give our method. We expect it to win when links are near-linear. That regime is included deliberately.
Full joint discretization-and-structure search. This is the Steck–Jaakkola alternating search run on all variables with no skeleton restriction. It is the accuracy ceiling for our phase two. We run it only where it finishes within budget, roughly up to ALARM's 37 nodes, and use it to quantify how much accuracy the restriction costs.
Key ablation: matched-size permissive skeleton. We lower F2SL's threshold until the skeleton has exactly as many edges as our firm-plus-uncertain set. Phase two is then identical, including predictive rescoring of the added edges. This isolates the claim that which edges are admitted matters, not just how many. If the ablation matches us, the flip signal is worthless.
Why not just…?
Why not just pick a better single discretization, say equal-frequency with more bins? Evidence from Distribution-Free Learning shows three standard rules all failing on non-linear conditional independence. Finer bins also fragment the contingency tables the filter depends on. Still, a well-chosen single rule could be close enough. The static-discretization baseline, swept over bin counts with the best one reported with hindsight, will settle this. If the hindsight-best single binning ties our method, the contribution collapses to "tune the bin count."
Why not just raise recall uniformly, as H2PC does or by lowering FCBF's threshold? This is the most serious threat. H2PC already shows that recall pays off downstream. The matched-size ablation above is designed exactly for this question. Our claim survives only if flip-selected edges contain more true links than an equal number of threshold-admitted edges, and if that advantage carries through to final SHD.
Why not just avoid discretization with linear-Gaussian tests or continuous graph learning? Linear tests misjudge the non-linear links in Margolin et al.'s Lambda networks. A* Lasso is exact but assumes linear Gaussian links and hits memory limits on large graphs. Continuous acyclicity-constrained learning such as NOTEARS was shown by Tearing Apart NOTEARS to follow variable scale: rescaling alone let an attacker force arbitrary graphs with a 1.0 success ratio. Our equal-frequency members are rank-based and immune to such rescaling. We will include a rescaled-data condition to show this directly. Kernel-based continuous independence tests would be a natural further baseline, but no result for them was found on Lacuna, so we treat them as future comparison.
Proposed Experiments
Semi-synthetic benchmarks. These use real network structures with continuous data.
- We take the graphs of ALARM (37 nodes, 46 edges), CHILD, INSURANCE and HAILFINDER (56 nodes, 66 edges), plus tiled ALARM at 500 and 5,000 nodes.
- We generate continuous data with links mixing linear, $2\sin(x)$, $e^{x}$ and $\ln|x|$ forms, following the non-linearities of Margolin et al., plus additive noise.
- Sample sizes follow Gasse et al.: $N \in \{50, 100, 200, 500, 1500, 5000\}$.
- Metrics are SHD, skeleton precision and recall, arrowhead F1 as used by F2SL, held-out predictive log-likelihood, and wall-clock time.
Real data. Real datasets serve as sanity checks rather than leaderboards.
- On the 3-variable Lambda networks and the MEANDER spiral, we check that conditionally independent pairs end up pruned. They should show $s=0$, or be removed in phase two, where static binning keeps them.
- On Boston Housing we check that the NOX–MEDV link is absent.
- On the yeast expression data we compare edge count and pathway edges against the roughly 65-edge network reported by Steck and Jaakkola.
Decisive checks. Three tests could each falsify the idea.
- Enrichment. Among true edges pruned by single-binning F2SL, what fraction fall in our uncertain set? We compare that against the fraction captured by the matched-size threshold ablation. No enrichment means the idea is dead, regardless of other results.
- Downstream SHD. Lower SHD than the matched-size ablation and the static baselines at small-to-moderate $N$, where binning choices matter most.
- Scaling. On tiled ALARM, phase-two cost should grow with the number of uncertain edges, not with $n$. This would extend predictive discretization far beyond its original 33 variables.
References
- Feature Selection for Efficient Local-to-global Bayesian Network Structure Learning
- Predictive Discretization During Model Selection
- Distribution-Free Learning of Bayesian Network Structure in Continuous Domains
- A* Lasso for Learning a Sparse Bayesian Network Structure for Continuous Variables
- An Experimental Comparison of Hybrid Algorithms for Bayesian Network Structure Learning
- The max-min hill-climbing Bayesian network structure learning algorithm
- Tearing Apart NOTEARS: Controlling the Graph Prediction via Variance Manipulation