  Learning causal structure is useful in many areas of artificial intelligence,
including planning, robotics, and explanation. Constraint-based structure
learning algorithms such as PC use conditional independence (CI) tests to infer
causal structure. Traditionally, constraint-based algorithms perform CI tests
with a preference for smaller-sized conditioning sets, partially because the
statistical power of conventional CI tests declines rapidly as the size of the
conditioning set increases. However, many modern conditional independence tests
are model-based, and these tests use well-regularized models that maintain
statistical power even with very large conditioning sets. This suggests an
intriguing new strategy for constraint-based algorithms which may result in a
reduction of the total number of CI tests performed: Test variable pairs with
large conditioning sets first, as a pre-processing step that finds some
conditional independencies quickly, before moving on to the more conventional
strategy that favors small conditioning sets. We propose such a pre-processing
step for the PC algorithm which relies on performing CI tests on a few randomly
selected large conditioning sets. We perform an empirical analysis on directed
acyclic graphs (DAGs) that correspond to real-world systems and both empirical
and theoretical analyses for Erd\H{o}s-Renyi DAGs. Our results show that
Pre-Processing Plus PC (P3PC) performs far fewer CI tests than the original PC
algorithm, between 0.5% to 36%, and often less than 10%, of the CI tests that
the PC algorithm alone performs. The efficiency gains are particularly
significant for the DAGs corresponding to real-world systems.
