Biclique compression speeds up large graph boolean matrix multiplication
Compressed Boolean Matrix Multiplication using Bicliques
Data Structures and Algorithms
Summary
Boolean matrix multiplication is a key operation used to analyze networks like social media and the web, but it can be slow and take up a lot of space with traditional methods. The authors improve a way to break down these big connection patterns into smaller dense pieces called bicliques, which helps compress the data. They then show how to multiply matrices directly using this compressed form, making the calculations much faster and using less memory. Their experiments on real web and social graphs show large speedups and space savings compared to common methods.
What this means in practice
- •For web engineers: Process large web graph data faster and with less memory by multiplying boolean matrices using biclique compression.
- •For social network analysts: Accelerate social network graph computations by exploiting compressed biclique representations for boolean matrix operations.
Authors
Nicolás Araya, José Zagal, Cecilia Hernández, Gonzalo Navarro
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.