Boolean Tensor Factorizations – and Beyond

                                    Pauli Miettinen

                            Max-Planck-Institut, Germany

Abstract. Boolean matrix factorization (BMF) has become a popular method in data
mining, with applications ranging from bioinformatics to lifted inference and multi-label
classification. Tensor factorizations (over the standard algebra) have gained increasing
interest in data analysis community in the recent years, and they have been applied
to network analysis, dynamic networks, and to simplify deep neural networks, among
others. Boolean tensor factorization (BTF) – a natural combination of BMF and tensors
– can be seen as a generalization of BMF, where instead of a single binary relation
(i.e. a matrix), we factorize a higher-arity relation (or a collection of binary relations
over the same entities). In this talk I will cover what will happen when we merge ideas
from standard tensor factorizations with Boolean algebra, discussing the computational
complexity, possible algorithmic ideas, and potential applications. I will also cover some
hybrid approaches that merge continuous and Boolean decompositions.