FastStep: Scalable Boolean Matrix Decomposition

• Type: Article in International Conference Proceedings Book
• Date: 2016

Authors

araujo, mr (Author) Other; Pedro Ribeiro (Author) FCUP; Faloutsos, C (Author) Other

Conference proceedings International

Title: ADVANCES IN KNOWLEDGE DISCOVERY AND DATA MINING, PAKDD 2016, PT I

Pages: 461-473

20th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD)

Univ Auckland, Auckland, NEW ZEALAND, APR 19-22, 2016

Indexing

ISI Web of Knowledge - 5 Citations

Scopus - 5 Citations

Other information

Authenticus ID: P-00K-BG7

DOI: 10.1007/978-3-319-31753-3_37

Abstract (EN): Matrix Decomposition methods are applied to a wide range of tasks, such as data denoising, dimensionality reduction, co-clustering and community detection. However, in the presence of boolean inputs, common methods either do not scale or do not provide a boolean reconstruction, which results in high reconstruction error and low interpretability of the decomposition. We propose a novel step decomposition of boolean matrices in non-negative factors with boolean reconstruction. By formulating the problem using threshold operators and through suitable relaxation of this problem, we provide a scalable algorithm that can be applied to boolean matrices with millions of non-zero entries. We show that our method achieves significantly lower reconstruction error when compared to standard state of the art algorithms. We also show that the decomposition keeps its interpretability by analyzing communities in a flights dataset (where the matrix is interpreted as a graph in which nodes are airports) and in a movie-ratings dataset with 10 million non-zeros.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 13