CS Paper Radar

Compressed Boolean Matrix Multiplication using Bicliques

Nicolás Araya, José Zagal, Cecilia Hernández, Gonzalo Navarro

cs.DS ·submitted 2026-10-23 16:10 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.DS ·2026-10-26 ·Gonzalo Navarro
survey similarity 0.73
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

Scalable GNN-based Knowledge Graph Representation Learning with Efficient Message Passing

cs.LG cs.AI ·2026-09-28 ·Huu Tan Mai, Cuong Xuan Chu, Heiko Paulheim, Daria Stepanova
published similarity 0.63
Abstract · Accepted at the Posters and Demos Track of the International Semantic Web Conference (ISWC) 2026

Graph neural networks (GNNs) excel at representation learning on Knowledge Graphs (KGs), achieving stateof-the-art performance on tasks like link prediction or entity classification. However, their high computational complexity, inherent to their user-defined message passing (MP) algorithm, still prohibits their widespread adoption, especially for large KGs. Current efforts to mitigate the scalability bottlenecks of GNNs on KGs, such as subgraph sampling, are often task- and model-specific, and do not reliably guarantee lossless (if applicable) runtime/space reductions. To address this, we extend Relational Sparse Matrix Multiplication (RSPMM), originally designed to losslessly lower the space complexity of composition-based MP with pointwise composition functions, to support more expressive functions (e.g., 2x2 block-diagonal matrix multiplication, Givens rotation, circular correlation). Our method delivers significant task-independent reductions in runtime and space for current GNNs on KGs and facilitates efficient re-implementations of GNNs that maintain near state-of-the-art performance on challenging KG tasks, for a fraction of computational costs.

0.26

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.63
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

Dynamic Distances Without Matrix Inverse

cs.DS ·2026-10-20 ·Jan van den Brand, Adam Karczmarz, Aryan Patel
top venue similarity 0.59
Abstract · Accepted to SODA 2027

We study the fully dynamic exact distance problem in unweighted directed graphs, where the graph undergoes edge insertions and deletions, and the distance between two query vertices must be reported. Under the combinatorial Boolean matrix multiplication conjecture, any subquadratic-time algorithm for this problem must use algebraic techniques. All prior work uses the polynomial matrix inverse as its algebraic tool, but within subquadratic time, this technique can only maintain distances up to a small-polynomial hop bound. So larger distances must be reassembled from short-range pieces by a combinatorial layer. This hybrid algebraic-combinatorial construction has led to a substantial slowdown for dynamic distances compared to other dynamic graph problems relying on algebraic techniques. We give the first subquadratic-time dynamic distance algorithm built on dynamically maintaining a different algebraic object than the matrix inverse. By maintaining the Frobenius form $A=KCK^{-1}$ of a dynamic generic (i.e., cyclic) matrix $A$, we can query all the powers $A^\ell = K C^\ell K^{-1}$ efficiently. For adjacency matrix~$A$, the smallest $\ell$ with $(A^\ell)_{s,t}\neq 0$ is the $st$-distance in the associated graph. So, unlike dynamic matrix inverse, we get distance information directly without hop truncation, and we no longer need to perform any combinatorial reassembly. This purely algebraic approach to dynamic distances leads to the fastest dynamic distance algorithm with $O(n^{1.58})$ update time. The earlier use of the Frobenius form maintained the dense change of basis $K$ explicitly and required $\tilde O (n^2)$ time per update [KS23]. Our key observation is that this change of basis is highly structured, which lets us maintain it implicitly. This gives the first subquadratic dynamic algorithm for the Frobenius normal form and characteristic polynomial for generic matrices.

0.33

AdaBool: Sparse Boolean Matrix Processing with Adaptive Data Representation

cs.DB cs.DC ·2026-10-15 ·Xiangrui Yang, Yifan Lei, Jiawei Yang, Yekang Zhan, Yuxin Zheng +4 more
top venue similarity 0.58
Abstract · Accepted to ACM SIGMOD 2027 (Proceedings of the ACM on Management of Data). 16 pages, 21 figures, 7 tables

Many data processing tasks revolve around determining whether logical relationships exist between two sets of entities, a pattern that can be naturally modeled as Sparse Boolean Matrix Multiplication (SpBMM). Under Boolean semantics, matrix representations no longer need to store numerical values and instead focus on encoding the positions of non-zero elements, making it highly amenable to data compression for substantially lower memory access overhead. The key challenge, however, is that the most effective compression depends heavily on sparsity distribution: different methods perform best at different sparsity levels, while real-world matrices often contain sharply varying sparsity across regions. Consequently, forcing the entire matrix into any fixed, monolithic representation leaves considerable optimization opportunities untapped. We present AdaBool, a SpBMM framework designed to reconcile this tension through an adaptive data representation. AdaBool partitions matrices into fine-grained element blocks and represents each block with the encoding best matched to its local sparsity. On top of this adaptive encoding, AdaBool introduces a heterogeneous GPU execution model that groups blocks by encoding type and maps them to matching processing paths, enabling efficient execution and scheduling across GPU resources. We implement AdaBool end to end with low-level system optimizations, evaluate it on both production and public workloads, and show that it outperforms representative baselines by over an order of magnitude.

0.71

Subgraph Isomorphism, Integer Linear Programming, and Lattices: A Linear Algebraic Framework

cs.DM cs.DSmath.OC ·2026-10-23 ·Bryant Gipson
similarity 0.56
Abstract · 24 pages, 8 figures

The subgraph isomorphism problem (SGI) asks a deceptively simple question: is a graph B found inside a parent graph A? Famously NP-complete and the subject of volumes of study, attempts to practically solve subgraph problems typically require specialized software or the focused application of problem-specific theoretical knowledge. Here we present a straightforward linear framework that neatly joins SGI to lattice theory and constrained satisfiability and, importantly, yields an easily implemented algorithm that naturally leverages consumer-grade hardware and off-the-shelf libraries to compete with state-of-the-art specialized solvers. We additionally show practical realizations in approachable settings, along with some benchmarks that reduce 6+ hour computations to seconds. Aimed at readability, we develop a series of computable algebraic invariants and demonstrate their application to familiar problems such as the Knight's Tour, with a focus on providing an accessible entry point for researchers in graph theory, abstract algebra, and students in general.

0.34

Approximate Matrix Multiplication through Joint Leverage Score Sampling

eess.SP math.NA ·2026-10-21 ·Neophytos Charalambides, Mert Pilanci, Alfred O. Hero
similarity 0.55
Abstract

In this paper, we investigate approximate matrix multiplication through random sampling. Specifically, we propose using a non-uniform sampling distribution constructed from the leverage scores of the two matrices, and characterize the associated approximation error in terms of the matrix spectral norm; which is well-known to better characterize the downstream error when the matrix product operator is applied to an input vector. We provide the probability error bounds for the proposed algorithm are also given, and discuss connections to data-oblivious approximate matrix multiplication, and graph sparsification algorithms.

0.18

Dual-Number Associative Arrays for One-Pass Provenance and Sensitivity

cs.DS ·2026-11-06 ·Timothy Habashy, Hayden Jananthan, Jeremy Kepner
theory similarity 0.54
Abstract · 5 pages, 1 figure

Associative arrays and GraphBLAS express sparse computations as matrix operations over a chosen semiring, but the result normally contains only the ordinary value. We define a dual-number extension $D_k(S)=S\ltimes S^k$ that carries this value together with $k$ independent auxiliary channels in the same computation. We prove that the construction is a split square-zero extension of any commutative semiring. Over min-plus, the auxiliary value is the weight of the shortest walk constrained to use the corresponding edge, excluding the weight of that edge. This gives an exact shortest-path membership test for that edge, although ties return the union of the edges on all optimal paths. We implement the min-plus construction using sparse \texttt{python-graphblas} operations, with a fixpoint test that checks the value and auxiliary components together. We validate the implementation across 18,692 checks, including 2,825 tied target pairs. On random graphs with 100,000 vertices and 32 seed edges, the dual method is $3.39\times$ faster than the sequential algorithm but $1.50\times$ slower than a min-plus-specific batched method. This difference is largely explained by the dual method requiring $1.55\times$ as many sweeps. Thus, the main contribution is a general algebraic approach with competitive sparse performance, rather than information that specialized min-plus algorithms cannot already compute.

0.27