Binary Expansion Group Intersection Network

Conditional independence is fundamental to modern statistics and machine learning, yet beyond special parametric families it rarely admits an exact covariance-based characterization. We introduce the binary expansion group intersection network (BEGIN), a distribution-free graphical framework for representing conditional independence in multivariate binary data and bit-encoded multinomial variables. We show that for arbitrary binary random vectors, conditional independence is equivalent to a zero cross block of a generalized Schur complement. Its entries are probability-weighted sums of conditional covariances, with signs determined by conditioning interactions. The representation encompasses Ising models, higher-order binary models, and categorical graphical models, including distributions with structural zeros. We characterize the rank of the interaction covariance and establish Markov properties and conditions for concatenating BEGIN graphs. We test conditional independence using the maximum absolute value of the estimated entries in the BEGIN cross block, and we show that this test attains the optimal sample order under sparse interaction alternatives. Simulations show the power gain under sparsity and the computational efficiency of the interaction scan. An analysis of categorical Mushroom records shows how the maximizing binary interactions explain detected conditional associations.