Decomposing Binary Matrices: Where Linear Algebra Meets Combinatorial Data Mining

The tutorial studies the connection between matrix factorization methods and data mining on binary data (e.g. pattern set mining). On one hand, it shows how many data mining methods can be modeled as discrete matrix factorizations. This change of conceptual framework provides new tools and concepts that help the data miner to generalize the algorithms, develop new algorithms, and analyse the algorithms in new ways. On the other hand, it shows how discretization of matrix factorizations provides new tools and methods for traditional matrix factorization applications.

This tutorial considers the problems of representing a binary matrix as a product of two binary matrices using three different algebras: the normal algebra (where 1+1=2), the modulo-2 algebra (where 1+1=0), and the Boolean algebra (where 1+1=1). In all of these cases, the requirement of binary factor matrices renders most of our normal matrix factorization tools less useful, calling for more combinatorial approaches. The combinatorial nature of the problems further increase when one moves from normal algebra to modulo-2 algebra to Boolean algebra. Nevertheless, all these problems show traces of both linear algebra and combinatorics and solving them requires techniques from both fields. A core idea of this tutorial is to show how ideas and concepts from linear algebra can be translated to combinatorial settings (and vice versa) and how that can be used to solve the factorization problems (and therefore other problems modeled as factorization problems).

The tutorial covers both theory and algorithms for these factorizations. The theory-part concentrates on building the connections (and pointing non-obvious differences) between the discrete and continuous factorizations. Central to this discussion is the concept of matrix rank, and how ranks under different algebras relate to each other. This discussion is also indented to give more intuition on how the different binary factorizations behave. Also the computational complexity of the factorizations is studied at this part, as is the complexity of an important sub-problem: finding the least-error projections. Throughout this discussion the concepts discussed are also related to concepts in pattern mining (e.g. the Boolean rank of a matrix is the minimum number of tiles needed to cover all 1s in the data).

The second part of the tutorial concentrates on algorithms for the problems. More details will be given on few algorithms, but the main concentration is on explaining the ideas and intuitions behind—and similarities and differences between—the algorithms. In addition to the algorithms for the standard problems, the discussion will include methods for selecting the rank and special results with sparse matrices.

Applications of these factorizations are highlighted when appropriate, but the focus of this tutorial is not on applications. It is assumed that the participants generally know applications for discrete data mining methods or matrix factorizations.