CS Paper Radar

A Sparse Low-Rank Biclique Decomposition for Graphs

Antoine Vialle, Sergei Gerasimov, Aref Einizade, Antonio Ortega, Fragkiskos D. Malliaros, Jhony H. Giraldo

cs.LG ·submitted 2026-11-19 09:42 UTC · v1
top venuecode/data

Abstract

Low-rank plus sparse decompositions, such as robust PCA, typically model the low-rank component as dense and the sparse component as corruption. This viewpoint is poorly suited to graph adjacency matrices, where sparsity is structural and dense low-rank factors destroy the combinatorial and computational properties of the graph. We propose signed biclique decomposition (SBD), a sparse low-rank decomposition for integer-weighted graphs that represents the structured component as a sum of sparse signed binary rank-one factors, together with a sparse signed residual. The resulting representation remains discrete, interpretable, sparse, and compatible with standard linear algebra. We formulate fixed-rank and greedy SBD objectives and derive a gain-based greedy algorithm with theoretical guarantees. Empirically, SBD recovers block structure in noisy graphs, while its factorized representation enables efficient sparse matrix-matrix multiplication (SpMM). On real graphs with strong shared-neighborhood structure, SBD achieves compression factors above $10$ and SpMM speedups up to $6\times$ over cuSPARSE, suggesting a practical alternative to dense low-rank decompositions for graphs. Code is available at https://github.com/IAntoineV/sbd.

Comment
Accepted at NeurIPS 2026. 29 pages, including references and appendices

Closest papers

Nearest neighbours by meaning across the whole index.

Compressed Boolean Matrix Multiplication using Bicliques

cs.DS ·2026-10-23 ·Nicolás Araya, José Zagal, Cecilia Hernández, Gonzalo Navarro
similarity 0.69
Abstract

Boolean matrix multiplication is a fundamental operation in many graph-based applications, including web and social network analysis, information retrieval, and graph query evaluation. However, conventional sparse representations such as CSR}/CSC still incur significant space and time costs on large graphs. In this work, we introduce a method for multiplying Boolean matrices based on a biclique-based compressed representation that decomposes them into dense bipartite subgraphs, thereby capturing large sets of implicit edges. We first improve the iterative biclique extraction algorithm of Hernández and Navarro by introducing percentile-based parameter adaptation that dynamically adjusts its parameters according to the degree distribution, enhancing both extraction efficiency and compression ratio. We then extend the Schoor multiplication algorithm to operate directly on biclique-encoded matrices, thereby enabling a compositional form of multiplication where the output can also be represented as a collection of bicliques. Our experimental results on large real-world web and social graphs show that our approach achieves substantial reductions in space and computation time with respect to CSR/CSC-based representations. For example, using biclique extraction just as a tool to speed up multiplication (but retaining the CSR/CSC format) yields up to 34-fold speedups. Further, using the biclique-based representation for input and output yields up to a 10-fold reduction in space and up to a 290-fold speedup for matrix multiplication. These results demonstrate that our representation based on bicliques is both space- and time-effective to support an algebra of Boolean matrices.

0.52

Strong NP-Hardness of Rank-2 Nonnegative Matrix Factorization

cs.CC math.OC ·2026-10-15 ·Arnaud Vandaele
theory similarity 0.68
Abstract

Nonnegative matrix factorization (NMF) approximates a nonnegative matrix by the product of two nonnegative matrices with a prescribed inner dimension~$r$. The existence of an exact NMF can be decided in polynomial time for every fixed~$r$, and a best rank-$1$ NMF in the Frobenius norm can be obtained from a truncated singular value decomposition. We prove that computing a best rank-$2$ NMF in the Frobenius norm is strongly NP-hard. Our proof uses a polynomial-time reduction from \textsc{Clique} that produces symmetric positive-definite, completely positive matrices with polynomially bounded integer entries. The same reduction also establishes strong NP-hardness of rank-$2$ symmetric NMF.

0.16

On the Binary Rank of Matrices with Constant Real Rank

cs.DM math.CO ·2026-09-24 ·Michal Parnas
theory similarity 0.65
Abstract

We study the problem of determining upper bounds on the maximal binary rank, $b_d$, of a $0,1$ matrix with real rank $d$, for small constant $d$. We prove a general upper bound of $b_d \leq \left\lfloor \sqrt{d2^d + 2d}\right\rfloor -1$. We also develop a general dimension reduction technique of bounding $b_d$ using known upper bounds on $b_{d-1}$ and $b_{d-2}$, as well as prove interesting general structural results on extremal matrices with binary rank $b_d$. This allows us to get improved non-trivial upper bounds on $b_d$ for constant values of $d$, which imply tight bounds on $b_d$ for $3 \leq d \leq 5$. Our results also imply bounds on the equivalent problem of finding the minimum number of bicliques needed to partition the edges of a bipartite graph whose reduced adjacency matrix has real rank at most $d$.

0.12

CAST: Canonical Approximate Schur Tree for Approximate Cholesky on Graphs

cs.LG stat.MLmath.NA ·2026-09-08 ·Meher Chaitanya, Cameron Musco, Aristides Gionis
theory similarity 0.65
Abstract

Graph-data workloads such as diffusion estimation, ranking, semi-supervised learning, and network optimization often solve many Laplacian or symmetric diagonally dominant M-matrix (SDDM) systems with the same coefficient matrix. Approximate Cholesky preconditioners eliminate vertices one at a time and store the resulting sparse approximate factorization, the \emph{factor}, whose construction cost is amortized across these solves. But eliminating a vertex, the \emph{pivot}, creates a dense Schur-complement clique among its $d$ active neighbors. We introduce CAST (Canonical Approximate Schur Tree), which replaces this clique with a weighted random spanning tree sampled directly from it. Every realization is connected and contains exactly d-1 edges, while reweighting each selected edge by the reciprocal of its tree-inclusion probability makes the update unbiased. The distribution is independent of the ordering of the pivot neighbors, and we prove that its leverage-score marginals minimize the largest normalized reweighted-edge contribution among unbiased inverse-marginal one-tree estimators. We also introduce CAST-$ρ$, which replaces each pivot neighbor with $ρ$ copies, each carrying a $1/ρ$ share of that neighbor's incident weight, samples a weighted random spanning tree on the expanded clique, and contracts the copies back to the original neighborhood. The resulting update remains unbiased and connected, can be sampled exactly in $O(ρd)$ time, and satisfies a $1/ρ$ bound on the second moment of the normalized local Schur error. Increasing $ρ$ therefore reduces certified local sampling variability, but may increase construction cost and downstream fill. Empirically, we observe that CAST-1 is the faster default, whereas CAST-2 is preferable when its additional edge contributions remain inexpensive.

0.43

Pattern-Based Matrix Analysis Under Permutations

cs.LG ·2026-11-13 ·Andrei Ermakov
top venue similarity 0.62
Abstract · Accepted at NeurIPS 2026 (The Fortieth Annual Conference on Neural Information Processing Systems)

Low-rank approximation captures one important notion of matrix simplicity: a matrix is simple if it is well described by a low-dimensional linear model. This paper studies a complementary notion. We consider matrices that become structurally simple only after permuting rows and columns, so that their mass concentrates in a prescribed geometric pattern such as a band, block-diagonal, arrowhead, or related form. We introduce a pattern distance that measures how close a matrix is to a given pattern after optimal reordering, giving a common framework for structural problems such as latent ordering, community detection, and bandwidth minimization. The problem is NP-hard in general; we derive an alternating algorithm based on Linear Assignment subproblems. We further introduce a pattern-plus-low-rank decomposition that combines permutation-structured fitting with a low-rank residual, whose permutation step is pattern fitting on the residual; its gains across pattern families persist at a matched parameter budget and are substantially reduced under a density-matched random-mask control. We evaluate the framework on synthetic recovery tasks, real correlation and graph adjacency matrices, and transformer attention heads, showing that a single universal algorithm recovers qualitatively different forms of matrix structure.

0.38

Subzero matrix completion for sparse data analysis: large-scale learning of latent low-rank structure

cs.LG stat.ML ·2026-08-21 ·Lawrence K. Saul, Ningyuan Huang, Dennis Bollweg, Jeff Soules, Diana C. Halikias
similarity 0.62
Abstract

We investigate when a sparse nonnegative matrix can be recovered from a real-valued matrix of much lower rank by zeroing out its negative elements. The potential for such decompositions suggests a mathematical connection between sparsity and rank; we analyze a number of sparse matrices with this latent low-rank structure and use them to illustrate the geometric origins of this connection. Previous algorithms have discovered these decompositions via an alternating minimization over the factors of a low-rank matrix, but to do so, they have also needed to compute and store another matrix, neither sparse nor low-rank, that is the size of their product. We develop a stochastic, alternating least-squares algorithm that operates on smaller blocks of this dense matrix and scales as a result to much larger problems. We also show how to further accelerate this algorithm with sparse optimizations and customized CUDA kernels. As one example, we use the algorithm to analyze the sparse matrix of synaptic weights for the recently published $\textit{Drosphilia}$ connectome. The nonzero elements of this matrix, with 139,255 rows and columns, record the number of synapses between cells in the nervous system of a female fruit fly. Despite a slowly decaying spectrum of singular values, this matrix exhibits a latent low-rank structure that is predictive of cell categories across multiple levels of specificity.

0.38

Compact Representations of Geometric Bipartite Graphs via Weighted Biclique Covers

cs.DS cs.DB ·2026-08-21 ·Aryan Esmailpour, Khoi Le, Stavros Sintos
top venuehot direction similarity 0.62
Abstract

Bipartite graphs are a fundamental representation for relational data arising in recommendation systems, social networks, and communication graphs. A key challenge in these settings is to store and transmit large bipartite graphs compactly while preserving exact structural and path information. We study biclique-based representations of bipartite graphs $\boldsymbol{G}=(\boldsymbol{V},\boldsymbol{U},\boldsymbol{E})$, where the edge set is encoded using a collection of complete bipartite subgraphs. We focus on the Weighted Biclique Covering problem, which minimizes the total number of vertices used across all bicliques, and introduce a generalized variant that additionally penalizes the number of bicliques, capturing practical overheads in storage, transmission, and model complexity. While the weighted biclique covering problem is known to be $\mathsf{NP}$-Complete, we show that the generalized variant is also $\mathsf{NP}$-Complete. Despite this hardness, many real-world bipartite graphs admit low-dimensional geometric embeddings or can be well approximated by them. Leveraging this observation, we develop the first approximation algorithms with provable guarantees for the (generalized) weighted biclique covering problem on geometric bipartite graphs. Specifically, for $δ$-disk bipartite graphs in low-dimensional $\ell_\infty^d$ spaces, we design a polynomial-time algorithm that achieves an $O(\log |\boldsymbol{U}| \cdot \log^d |\boldsymbol{V}|)$-approximation, combining ideas from greedy set cover, geometric range searching, and densest subgraph optimization. We also show how our algorithms extend to $\ell_α^d$ metrics for any $α\geq 1$. Finally, we evaluate our algorithms on real-world bipartite datasets and show that they efficiently compute significantly smaller biclique-based representations than natural baselines, while scaling to large graphs.

0.62

Computation-Friendly Compression of Matrices: Speeding up Linear and Boolean Algebra

cs.DS ·2026-10-26 ·Gonzalo Navarro
survey similarity 0.61
Abstract

Large sparse matrices---adjacency matrices of web and social graphs, feature matrices of machine-learning pipelines, the relations of graph databases---are routinely compressed to save space. Classical compressors, however, force the matrix to be decompressed before it can be used, so the space savings often yield a computational overhead. A recent line of work studies \emph{computation-friendly} compression: formats that are not only small, but let us carry out matrix--vector products, and in some cases matrix--matrix products, sums and closures, directly on the compressed representation {\em in time proportional to that compressed size}. This survey organizes that literature around the kind of redundancy each format exploits: spatial clustering of the nonzeros ($k^2$-trees and their variants), similarity between rows (Boldi--Vigna-style referencing and set-difference compression), repeated substrings (grammar compression), and dense bipartite substructures (bicliques). For each family we describe the representation, the algorithms, the theoretical guarantees and the empirical performance. Further, we show that the last three families are instances of a single general scheme, which we call a {\em sparse straight-line factorization} of the matrix, whose forward and backward substitutions evaluate right and left products in time proportional to the size of the representation, and that the product of two such factorizations is again one, which gives matrix--matrix products with a compressed output. We also relate the model to linear circuits, give simple recompression steps, and study the size of the smallest factorization: worst-case bounds, separations from each family, and parallelism. We close with a cross-family comparison and a list of open problems.

0.42