RECORD
Boolean matrix factorization meets consecutive ones property
Data Structures and Algorithms · Submitted 17 Jan 2019
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim Our experiments show that our algorithms find high-quality factorizations and scale well.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
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.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Boolean matrix factorization is a natural and a popular technique for summarizing binary matrices. | background 1.00 | 0.04 | 0.02 | asserted 1.00 |
| s1 | In this paper, we study a problem of Boolean matrix factorization where we additionally require that the factor matrices have consecutive ones property (OBMF). | contribution 0.95 | 0.61 | 0.07 | asserted 0.92 |
| s2 | 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. | background 0.99 | 0.06 | 0.03 | asserted 1.00 |
| s3 | A common problem with visualizing graphs is clutter due to too many edges. | background 1.00 | 0.05 | 0.02 | asserted 1.00 |
| s4 | The standard approach to deal with this is to bundle edges together and represent them as ribbon. | background 0.99 | 0.04 | 0.02 | asserted 1.00 |
| s5 | We also show that we can use OBMF for edge bundling combined with circular or linear layout techniques. | contribution 0.96 | 0.86 | 0.12 | asserted 0.86 |
| s6 | 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). | result 0.90 | 0.88 | 0.36 | asserted 1.00 |
| s7 | On the positive side, we develop a greedy algorithm where at each step we look for the best 1-rank factorization. | method 0.80 | 0.95 | 0.08 | asserted 1.00 |
| s8 | 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. | method 0.98 | 0.92 | 0.05 | asserted 0.98 |
| s9 | We show that this step can be done in linear time using pq-trees. | method 0.77 | 0.93 | 0.06 | asserted 1.00 |
| s10 | We also extend the problem to cyclic ones property and symmetric factorizations. | contribution 1.00 | 0.92 | 0.04 | asserted 1.00 |
| s11 | Our experiments show that our algorithms find high-quality factorizations and scale well. | result 1.00 | 0.96 | 0.23 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original 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.
Human review
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.