English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  Boolean Matrix Factorization Meets Consecutive Ones Property

Tatti, N., & Miettinen, P. (2019). Boolean Matrix Factorization Meets Consecutive Ones Property. Retrieved from http://arxiv.org/abs/1901.05797.

Item is

Basic

show hide
Item Permalink: http://hdl.handle.net/21.11116/0000-0004-02F0-A Version Permalink: http://hdl.handle.net/21.11116/0000-0004-02F5-5
Genre: Paper

Files

show Files
hide Files
:
arXiv:1901.05797.pdf (Preprint), 227KB
Name:
arXiv:1901.05797.pdf
Description:
File downloaded from arXiv at 2019-07-10 11:21 To appear in 2019 SIAM International Conference on Data Mining (SDM19). For the associated source code, see https://cs.uef.fi/~pauli/bmf/ordered_bmf/
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-

Locators

show

Creators

show
hide
 Creators:
Tatti, Nikolaj1, Author
Miettinen, Pauli2, Author              
Affiliations:
1External Organizations, ou_persistent22              
2Databases and Information Systems, MPI for Informatics, Max Planck Society, ou_24018              

Content

show
hide
Free keywords: Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Discrete Mathematics, cs.DM,Computer Science, Learning, cs.LG
 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.

Details

show
hide
Language(s):
 Dates: 2019-01-172019
 Publication Status: Published online
 Pages: 13 p.
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: arXiv: 1901.05797
BibTex Citekey: Tatti_arXiv1901.05797
URI: http://arxiv.org/abs/1901.05797
 Degree: -

Event

show

Legal Case

show

Project information

show

Source

show