Compressed Boolean Matrix Multiplication using Bicliques

Most of those applications involve sparse graphs, which means that their

• Adjacency matrices enable Boolean operations including matrix multiplication, while CSR and CSC store sparse matrices in row- and column-oriented forms.CSR/CSC space is proportional to graph edges, but large sparse graphs still present space and operation costs.Source: Graphs play a fundamental role in… · p. 2, column indices and the starting… · p. 3, On large sparse graphs and matrices,… · p. 3

compression based on bicliques [11], which capture highly connected regions

• Biclique-based compression captures highly connected regions and represents many edges implicitly; the paper extends this representation to matrix-matrix multiplication.The work targets Boolean matrix multiplication on compressed matrices.Source: compression based on bicliques [11],… · p. 4, In this work we improve the… · p. 4

1. We improve our previous biclique extraction [11] by defining an adap-

• Percentile-based parameter adaptation adjusts biclique extraction to the input degree distribution, improving compression ratio and runtime.The approach targets large real-world networks with heterogeneous degree distributions.Source: §1 · p. 4

2. We show that Schoor’s algorithm [6] adapts naturally to biclique-based

• The paper extends Schoor’s algorithm to receive and produce matrices represented as bicliques.This supports multiplication directly over the compressed representation.Source: §2 · p. 4, In this work we improve the… · p. 4

3. We provide an extensive experimental evaluation on large real-world

• Up to 10-fold less space and 290-fold faster multiplication were reported against the CSR/CSC baseline when bicliques represented inputs and outputs.The biclique representation also compressed multiplication outputs particularly well.Source: §3 · p. 5
• Up to 34-fold faster multiplication was reported when biclique extraction accelerated multiplication while matrices remained in CSR/CSC format.The comparison was against Arroyuelo et al.’s CSR/CSC baseline multiplication.Source: §3 · p. 5

been improved by exploiting locality, similarity, and node ordering in large

• Compressed graph methods exploit locality, similarity, clustering, or biclique patterns, and prior work also applied compressed representations to matrix operations.The cited work includes matrix-vector and matrix-matrix multiplication methods.Source: Efficient Boolean matrix… · p. 5, been improved by exploiting locality,… · pp. 5–6, Compressed graph representations also… · p. 6

algorithms, over a CSR/CSC-like representation. The algorithm uses 5C +

• Schoor’s algorithm intersects nonempty columns of X with nonempty rows of Y, with each shared index contributing a biclique to the Boolean product.Its average time is O(CxCy/N), assuming uniformly distributed nonzero entries.Source: algorithms, over a CSR/CSC-like… · p. 7

Recently, Arroyuelo et al. [7] implemented Schoor’s algorithm in a more

• Arroyuelo et al. implemented Schoor’s algorithm using CSR and CSC, with average time O(CxCy log(N)/N).The implementation stores both orientations to support multiplication.Source: Recently, Arroyuelo et al. [7]… · p. 7, §3.2 · p. 7

3.2. A Compact Implementation

• The compact multiplication takes X in CSC and Y in CSR, identifies shared column-row indices, and records each resulting Cartesian product’s pointers and sizes.It computes the product in two main steps.Source: §3.2 · p. 8
• Two min-heaps handle duplicate cells while Cartesian products are merged by row and then by column to produce Z in CSR format.Products are grouped by their smallest row; columns are emitted in increasing order.Source: §3.2 · p. 8

CSR formats, respectively, which are used to compute the multiplication

• Figure 1 illustrates the algorithm stages, including intersections that yield Cartesian products and the heap-based construction of the output.The walkthrough shows products processed in ascending row order before the result is built in CSR.Source: Figure 1 · p. 9, §3.2 · p. 9, CSR formats, respectively, which are… · p. 9

A representation based on bicliques (i.e., complete bipartite subgraphs)

• A biclique represents all edges in the Cartesian product of its vertex subsets, while the residual contains edges not covered by any biclique.The graph representation is the biclique collection together with that residual.Source: A representation based on bicliques… · p. 11

The representation based on bicliques uses |Si| + |Ci| words to represent

• The representation stores each biclique using its two vertex subsets and stores residual edges explicitly, with a bitmap marking component starts.Its stated space is the sum of biclique subset sizes and twice the residual-edge count, plus a sublinear bitmap term.Source: The representation based on bicliques… · p. 11

The main challenge to use this representation is how to extract suitable

• Finding bicliques that minimize representation space is NP-hard, so the extraction method uses heuristics to find large bicliques.The described process uses MinHashing, clustering, edge-frequency ordering, and a prefix tree.Source: The main challenge to use this… · p. 11, edge frequency each cluster adjacency… · p. 12

edge frequency each cluster adjacency list to improve the discovery of large

• The extractor’s initial parameters are arbitrary and ignore input-graph information, making tuning cumbersome and affecting biclique quality and runtime.Parameters include minimum degree, target biclique size, a productivity threshold, and maximum iterations.Source: edge frequency each cluster adjacency… · p. 12

Boolean matrix multiplication can benefit significantly from the biclique

• The product expands into four terms: residual-by-residual, residual-by-bicliques, bicliques-by-residual, and bicliques-by-bicliques.The input matrix is defined as the biclique matrix plus its residual.Source: Boolean matrix multiplication can… · p. 12

We will carry out the first multiplication using the algorithm of Arroyuelo

• The residual-by-residual term uses Arroyuelo et al.’s algorithm, while the other three terms require new multiplication algorithms.The paper describes algorithms for multiplying a general matrix by bicliques and two biclique sets.Source: We will carry out the first… · p. 13

To perform this multiplication, we compute the product between matrix

• For residual-by-biclique multiplication, intersect CSC(Rx) column indices with each biclique’s row set, then combine the retrieved rows with its column set to form output bicliques.The resulting bicliques sharing the same column set are collapsed into one biclique.Source: calculate the intersections between… · p. 13, §1 · pp. 13–14, Figure 2 · p. 13

1. For each biclique byi, we identify the intersections between the columns

• For biclique-by-residual multiplication, intersect each biclique’s column set with row indices in CSR(Ry), then form output bicliques analogously.The paper identifies this as analogous to the preceding matrix-by-biclique operation.Source: Figure 3 · p. 14

4. Finally, the new bicliques undergo a deduplication stage on the sequence

• Deduplication removes repeated rows from the sequence of newly generated bicliques.The supplied passage gives only this brief description of the deduplication stage.Source: §4 · p. 14

5.2. Biclique-to-Matrix Multiplication (Bx × Ry)

• For each input biclique, intersect Cxi with the rowId array of CSR(Ry).This is the stated setup for the biclique-to-matrix operation.Source: §5.2 · p. 14, §1 · p. 15

2. For each intersecting element rowId[k] ∈Cxi, we retrieve the column

• For each matching rowId[k], retrieve the corresponding CSR(Ry) column values using colIdx and rowPtr.The retrieved values come from colIdx[rowPtr[k]..rowPtr[k +1]−1].Source: §2 · p. 15

3. The output biclique is (Sxi, C). To form C, we concatenate in a se-

• Concatenate the qualifying column values to form C, producing the output biclique (Sxi, C).Source: §3 · p. 15

5.3. Biclique-to-Biclique Multiplication

• The marks(By) table lists elements of each Syi in sorted order with the Cyj sets connected to each element.The table is the lookup structure used by the multiplication.Source: §5.3 · p. 15
• For each biclique bxi, search its Cxi elements in marks(By).Source: §5.3 · p. 15
• A matching element supplies associated Cyj sets, indicating output bicliques (Sxi, Cyj).Source: §5.3 · p. 16

• Combine the Cyj values obtained from marks(By) into C for the generated biclique.Source: §3 · p. 16

5.4. Matrix Input and Output Representation

• The multiplication output consists of residual CSR for Rx × Ry and bicliques for Rx × By, Bx × Ry, and Bx × By.The resulting matrix Z can be represented in the same compressed format.Source: §5.4 · pp. 16–17
• Keeping results as bicliques plus a residual matrix makes the representation compositional, so multiplication outputs can be operated on directly.The passage also identifies transposition and sums as operations that can be incorporated in this format.Source: §5.4 · p. 17

Recompression can be incorporated to the matrix algebra as an operation

• Recompression can improve biclique representation quality by extracting bicliques again from Z after converting it to CSR.The passage gives bicliques with |Si| = 1 or |Ci| = 1 as examples that are better integrated into Rz.Source: §5.4 · p. 17, by extracting bicliques again from Z.… · p. 17, Recompression can be incorporated to… · p. 18
• In the speedup scenario, inputs and outputs remain CSR while bicliques are extracted before multiplication and the output is converted back afterward.Source: Recompression can be incorporated to… · p. 18

5.5. Recovering the Matrix from the Bicliques

• To recover CSR, concatenate and deduplicate the Czi components associated with each row, then merge with the residual Rx × Ry component.The described process also merges bicliques from Bx × Ry and Rx × By.Source: §5.5 · p. 18, we produce the CSR representation as… · p. 19

The original biclique extraction technique, described in Section 4, uses

• A 90th-percentile degree threshold initializes minAdjNodes, filtering out small adjacency lists to favor detection of large bicliques.The initial degree-distribution traversal identifies highly connected nodes for the filter.Source: The original biclique extraction… · p. 19, Algorithm 1 presents the pseudocode… · p. 20

The algorithm then proceeds with the iterative extraction phase, following

• When an iteration yields fewer bicliques than 80% of the historical average, minAdjNodes decreases by 20% so later rounds explore lower-degree nodes.The algorithm compares each iteration’s extraction count with the historical average adjusted by a tolerance threshold.Source: The algorithm then proceeds with the… · p. 21
• Segmenting the search reduces extraction cost by processing fewer elements per iteration, while selected nodes tend to share similar degrees.The resulting bicliques are described as having enhanced structural coherence.Source: The algorithm then proceeds with the… · p. 22

7. Experimental Evaluation

• The evaluation compared sequential implementations on public graph datasets and measured extraction, compression, and multiplication against the Baseline and k2-tree.The implementation extended Arroyuelo et al.’s C++ code; the Baseline stores CSR/CSC, and the comparison also included k2-tree.Source: §7 · pp. 22–23, All results were obtained by using… · p. 23

We first compare the space compression and running time performance

• Adaptive extraction usually took 45% of non-adaptive runtime and produced representations using 70%–75% of its space; one case took 162% of the time and 103% of the space.In that slower case, non-adaptive extraction achieved only 2% compression, versus 41% for adaptive extraction.Source: We first compare the space compression… · p. 23, the adaptive version. The resulting… · p. 24, Table 2 · p. 24

the adaptive version. The resulting compressed representation usually takes

• Adaptive extraction achieved higher cumulative compression per second in all cases, and parameter-adaptation iterations improved compression without significantly worsening runtime in most datasets.The plotted comparison tracks cumulative compression ratio over successive iterations.Source: the adaptive version. The resulting… · p. 24, Figure 8 · p. 25

supported directly, however, our biclique compression substantially reduces

• WebGraph and RePair32 outperformed biclique compression in space, but bicliques used 13%–36% of the Baseline’s space across datasets.Storing only the Baseline’s CSR part would use 26%–72% of the Baseline’s space.Source: As observed, Webgraph achieves the… · p. 25, shows the bpe (bits per edge) for the… · p. 25, supported directly, however, our… · p. 26

This section studies the usage scenario where the matrices are still stored

• For multiplication, our approach achieved speedups between 1.75 and 34.3 on larger datasets, while the Baseline was typically much faster on smaller datasets.The hardest multiplications took minutes to hours.Source: This section studies the usage… · pp. 27–28

Table 5 shows that our approach with recompression provides a great

• With recompression, the output used 9%–19% of the Baseline’s space, while the method was competitive on larger matrices but up to 8 times slower on smaller ones.On larger matrices, it was 30%–60% slower in most cases and 16 times faster in one; output recompression considerably slowed multiplication.Source: Table 5 · p. 28, Table 5 shows that our approach with… · pp. 29–30

Table 7 shows the space and execution time comparing the multiplication

• 10%–26% of the Baseline’s space and up to 289-fold faster multiplication were achieved without recompressing outputs; space degraded by 7%–40%.The method was slower than the Baseline in one case, by 44%.Source: Table 7 · p. 30, Table 7 shows the space and execution… · p. 31

Our final experiment aims to measure how the degradation in the quality

• When squaring matrices twice, intermediate recompression made the whole process almost twice as fast as skipping it; the approach also beat the Baseline in time by up to 13.6 times.The two approaches were faster than the Baseline and k2-tree by up to 13.6 and 586 times, respectively; squaring increased edge counts by an order of magnitude each time.Source: Table 6 · p. 29, Our final experiment aims to measure… · pp. 31–32, Table 8 · p. 32

In order to obtain large bicliques efficiently, we improved our previous

• The percentile-guided extractor adapts parameters to the input graph’s degree distribution, improving compression efficiency and extraction time over the previous implementation.Source: In order to obtain large bicliques… · p. 33
• The extended Schoor algorithm decomposes multiplication into four components and produces bicliques, keeping computation in the compressed domain.The components are matrix–matrix, matrix–biclique, biclique–matrix, and biclique–biclique multiplication.Source: In order to obtain large bicliques… · p. 33

Experimental results on web and social graphs demonstrated that our

• On web and social graphs, the method achieved up to 290 times faster multiplication while using up to 10 times less space than CSR/CSC; multiplication outputs compressed especially well.Source: Experimental results on web and social… · p. 33
• Future work includes parallel and GPU implementations, graph-query integration, and extending the model to weighted and dynamic graphs.Source: Experimental results on web and social… · pp. 33–34