Boolean matrix factorization meets consecutive ones property

Show full item record



Permalink

http://hdl.handle.net/10138/309983

Citation

Tatti , N & Miettinen , P 2019 , Boolean matrix factorization meets consecutive ones property . in T Berger-Wolf & N Chawla (eds) , Proceedings of the 2019 SIAM International Conference on Data Mining . Society for Industrial and Applied Mathematics , pp. 729-737 , SIAM International Conference on Data Mining (SDM19) , Calgary , Canada , 02/05/2019 . https://doi.org/10.1137/1.9781611975673.82

Title: Boolean matrix factorization meets consecutive ones property
Author: Tatti, Nikolaj; Miettinen, Pauli
Other contributor: University of Helsinki, Department of Computer Science
Berger-Wolf, Tanya
Chawla, Nitesh
Publisher: Society for Industrial and Applied Mathematics
Date: 2019
Language: eng
Number of pages: 9
Belongs to series: Proceedings of the 2019 SIAM International Conference on Data Mining
ISBN: 978-1-61197-567-3
DOI: https://doi.org/10.1137/1.9781611975673.82
URI: http://hdl.handle.net/10138/309983
Abstract: Boolean matrix factorization is a natural and a popular technique for summarizing binary matrices. In this paper, we study a problem of Boolean matrix factorization where we additionally require that the factor matrices have consecutive ones property (OBMF). A major application of this optimization problem comes from graph visualization: standard techniques for visualizing graphs are circular or linear layout, where nodes are ordered in circle or on a line. A common problem with visualizing graphs is clutter due to too many edges. The standard approach to deal with this is to bundle edges together and represent them as ribbon. We also show that we can use OBMF for edge bundling combined with circular or linear layout techniques. We demonstrate that not only this problem is NP-hard but we cannot have a polynomial-time algorithm that yields a multiplicative approximation guarantee (unless P = NP). On the positive side, we develop a greedy algorithm where at each step we look for the best 1-rank factorization. Since even obtaining 1-rank factorization is NP-hard, we propose an iterative algorithm where we fix one side and and find the other, reverse the roles, and repeat. We show that this step can be done in linear time using pq-trees. We also extend the problem to cyclic ones property and symmetric factorizations. Our experiments show that our algorithms find high-quality factorizations and scale well.
Subject: 113 Computer and information sciences
Rights:


Files in this item

Total number of downloads: Loading...

Files Size Format View
1901.05797.pdf 226.8Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record