Computing WSBM binary marginals with Tensor-Train decomposition

Abstract

The Weighted Stochastic Block Model is a statistical model for unsupervised clustering of individuals based on a dissimilarity matrix. The computation of the binary conditional marginals of group memberships by exact enumeration is out of reach. We use the fact that the joint conditional distribution, given the dissimilarities, is factored into binary factors and we describe how to obtain a Tensor-Train (TT) decomposition from the SVD of each factor. It leads to variable separation involving products of matrices and we show how to exploit it for the computation of binary conditional marginals. This exact calculation faces severe numerical challenges. The dimensions of the matrices involved in the products increase exponentially with the number of factors. We bypass this difficulty by using the TT-matrix format. The TT-rank of the products themselves grows exponentially. We use a numerical approximation called rounding by Oseledets to control this. We compare the behavior of the TT approach with the Mean-Field approximation and the Gibbs Sampler for various dissimilarity structures and up to forty variables. We recommend the TT approach due to its accuracy and reasonable computing time.

The authors' abstract, as published at the source. ESAIM Probability and Statistics, 2026 · DOI ↗