  Several approaches to graphically representing context-specific relations
among jointly distributed categorical variables have been proposed, along with
structure learning algorithms. While existing optimization-based methods have
limited scalability due to the large number of context-specific models, the
constraint-based methods are more prone to error than even constraint-based DAG
learning algorithms since more relations must be tested. We present a hybrid
algorithm for learning context-specific models that scales to hundreds of
variables while testing no more constraints than standard DAG learning
algorithms. Scalable learning is achieved through a combination of an
order-based MCMC algorithm and sparsity assumptions analogous to those
typically invoked for DAG models. To implement the method, we solve a special
case of an open problem recently posed by Alon and Balogh. The method is shown
to perform well on synthetic data and real world examples, in terms of both
accuracy and scalability.
