Fast and Efficient Boolean Matrix Factorization by Geometric Segmentation

Boolean matrix has been used to represent digital information in many fields, including bank transaction, crime records, natural language processing, protein-protein interaction, etc. Boolean matrix factorization (BMF) aims to decompose a boolean matrix via the product of two lowranked boolean matrices, benefiting a number of applications on boolean matrices, e.g., data denoising, clustering, dimension reduction and community detection. Inspired by binary matrix permutation theories and geometric segmentation, in this work, we developed a fast and scalable BMF approach, called MEBF (Median Expansion for Boolean Factorization). MEBF adopted a heuristic approach to locate binary patterns presented as submatrices that are dense in 1s. In each iteration, MEBF permutates the rows and columns such that the permutated matrix is approximately Upper Triangular-Like (UTL) with so-called Simultaneous Consecutive-ones Property (SC1P). The largest submatrix dense in 1 would lie on the upper triangular area of the permutated matrix, and its location was determined based on a geometric segmentation of a triangular. We compared MEBF with state-of-the-art BMF baselines on data scenarios with different density and noise levels. Through comprehensive experiments, MEBF demonstrated superior performances in lower reconstruction error, and higher computational efficiency, as well as more accurate density pattern mining than state-of-the-art methods such as ASSO, PANDA and Message Passing. We also presented the application of MEBF on non-binary data sets, and revealed its further potential in knowledge retrieving and data denoising on general matrix factorization problems.