  We consider the problem of learning the exact skeleton of general discrete
Bayesian networks from potentially corrupted data. Building on distributionally
robust optimization and a regression approach, we propose to optimize the most
adverse risk over a family of distributions within bounded Wasserstein distance
or KL divergence to the empirical distribution. The worst-case risk accounts
for the effect of outliers. The proposed approach applies for general
categorical random variables without assuming faithfulness, an ordinal
relationship or a specific form of conditional distribution. We present
efficient algorithms and show the proposed methods are closely related to the
standard regularized regression approach. Under mild assumptions, we derive
non-asymptotic guarantees for successful structure learning with logarithmic
sample complexities for bounded-degree graphs. Numerical study on synthetic and
real datasets validates the effectiveness of our method. Code is available at
https://github.com/DanielLeee/drslbn.
