Swapping hill-climbing for tabu search in Bayesian network learning: PCTABU wins on sparse networks and ties on dense ones
Synopsis
Hybrid Bayesian network learning separates skeleton construction from score-based search, and both the search strategy (hill-climbing or tabu) and the scoring function (BDe, LL or BIC) change the learned structure. PCTABU pairs the PC skeleton with tabu search; against PCHC on eight real benchmark networks it did better on the sparser Alarm, Child and Hailfinder, tied on the other five, and LL scored worst for both algorithms while BDe and BIC performed similarly.
Interpretation
Hybrid Bayesian network learning carries an extra tunable choice: after the skeleton is built, which search strategy picks the final structure among candidate directed acyclic graphs. PCHC previously maximized a scoring function with hill-climbing after skeleton construction, and the choice of search strategy and scoring function was rarely studied systematically. Across eight real benchmark networks, PCTABU beat PCHC on Alarm, Child and Hailfinder and was nearly equivalent on Andes, Hepar2, Insurance, Pigs and Win95pts, with F-score and SHD agreeing.
PCTABU keeps the PC algorithm's skeleton identification and replaces only the second-stage search with tabu search. Tabu search keeps a list of recently visited structures and forbids returning to them, so it keeps exploring even without an immediate score gain and can escape local optima. Categorical data were generated at nine sample sizes from 10,000 to 5,000,000, with tabu list size and no-improvement limit both set to 10, 10 restarts per search, and results averaged over 200 replications.
The scoring function is itself a factor in structural recovery, not a supporting detail of the search strategy. LL measures fit without penalizing parameter count and favors more edges; BIC subtracts a penalty scaled by the logarithm of sample size, and BDe lowers prior probability for denser graphs. In both real and simulated settings, BDe and BIC performed similarly in most cases, while LL was consistently worse for both PCHC and PCTABU.
Perspective
The conclusions rest on eight public real benchmark networks and on simulated networks with 30, 50 and 70 nodes and average neighborhood sizes of 3 and 5, using categorical data at sample sizes from 10,000 to 5,000,000. The authors propose extending the study with more real networks and higher-dimensional simulated data, and leave a direct empirical comparison of PCTABU against MMHC for future work.
PCTABU's advantage appears only on networks with lower average Markov blanket size and average degree, and the two algorithms tied in all six simulated settings; the authors attribute this to simulated random graphs possibly lacking the local-optimum traps that catch hill-climbing, which is an interpretive explanation. PCTABU's expected edge over MMHC rests on PCHC's earlier advantage over MMHC and has not been tested directly.