Tensor Train Decomposition for BN2A Structure Learning

Abstract

BN2A models are bipartite Bayesian networks with binary hidden and observed variables, characterized by Noisy-AND conditional probability tables with leak and penalty parameters. A fundamental challenge in BN2A modeling is identifying the bipartite graph structure, the Q-matrix in cognitive diagnostic models, from observed data alone. Existing tensor-based identification methods face the curse of dimensionality: the joint probability tensor has 2^J entries for J observed variables, and constructive algorithms such as that of Gu (2026) require materializing it explicitly. We bridge BN2A structure learning and tensor network methods by showing that BN2A probability tensors have Tensor Train (TT) rank at most 2^K, where K is the number of hidden variables, reducing storage from O(2^J) to O(J * 4^K), a bound that follows from a known equivalence between BN2A and Restricted Boltzmann Machines. Building on this representation, we show that Gu's rank tests can be performed directly on TT cores via core contractions, without ever materializing the full tensor. Empirical validation on simulated data with J = 15 and K = 3 confirms the rank bound and achieves perfect structure learning; we further characterize the sample-size regime, showing that recovery is robust for n as small as 30% of 2^J. We also report two honest explorations of the boundaries of the approach: greedy mode ordering reduces the TT parameter count of the population tensor by 13% and, once an order-sensitive ambiguity in pure-item detection is resolved, composes fully with Gu's rank tests, although the storage benefit vanishes on noisy empirical tensors; and Gu's Step 2 itself degrades as J grows with K fixed, a limitation of the underlying algorithm rather than of the TT representation.