WorksComputer Science
A Sparse Low-Rank Biclique Decomposition for Graphs
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 and SpMM speedups up to over cuSPARSE, suggesting a practical alternative to dense low-rank decompositions for graphs. Code is available at https://github.com/IAntoineV/sbd.
Introduction
Low-rank decomposition is a fundamental tool for uncovering latent structure in high-dimensional data. In sparse plus low-rank (SLR) models [30] (see Table 4 for abbreviations), a data matrix is decomposed as , where is a low-rank matrix that captures global or latent structure, and is a sparse matrix capturing localized deviations, outliers, or corruptions. We refer to as the residual (or remainder) of the decomposition. A prominent example of SLR is robust principal component analysis (RPCA) [8], which recovers these two components through a convex optimisation problem. RPCA and related SLR methods have been successful in many applications, including medical imaging [7, 9], asset pricing [3], background subtraction, and corruption removal [8].
| Abbreviation | Description |
| SLR | Sparse plus Low-Rank (matrix decomposition model) |
| SLRS | Sparse plus Low-Rank-and-Sparse (our graph-adapted model) |
| RPCA | Robust Principal Component Analysis |
| SPCA | Sparse Principal Component Analysis |
| SBD | Signed Biclique Decomposition (proposed framework) |
| SpMM | Sparse Matrix-Matrix Multiplication () |
| CF | Compression Factor () |
| CR | Memory Compression Ratio () |
| AO | Alternating Optimization |
| ILP | Integer Linear Programming (exact combinatorial solver) |
| CSR | Compressed Sparse Row format |
| SBM | Stochastic Block Model |
Table 4. Summary of abbreviations and acronyms used in this paper.
In this paper, we ask what an SLR-like decomposition should look like for sparse graph adjacency matrices. Since sparsity is intrinsic to graph structure, both components should remain sparse: the structured term should capture shared connectivity patterns through graph-supported objects, such as clique-, biclique-, or shared-neighborhood blocks, while the residual should store sparse signed corrections. Classical SLR methods such as RPCA are poorly matched to this goal: their low-rank component is typically dense and incoherent, and sparsity is treated as corruption [8]. Applied to graphs, this can introduce dense fill-in, destroy the adjacency sparsity pattern, and produce representations that are inefficient to store (see Appendix § 10.3.§ 4).
A relevant alternative is sparse PCA (SPCA) [35, 19, 29], which enforces sparsity on the low-rank factors rather than directly on the reconstructed matrix or residual. However, the resulting singular vectors are generally not binary or indicator-like, and thus the induced low-rank approximation is poorly aligned with the discrete structure of graphs. As a consequence, the residual component typically remains comparably dense, offering limited improvement in sparsity over the original adjacency matrix (see Appendix § 10.3.§ 4).
These limitations suggest a different sparse-low-rank principle for graphs: the structured component should be both low-rank and sparse, while the residual should remain sparse. This leads to a sparse plus low-rank-and-sparse (SLRS) formulation, in which is represented by a small number of sparse graph-supported low-rank components and stores the remaining signed corrections. Figure 1 illustrates this goal: a sparse graph adjacency matrix is decomposed into a sparse low-rank block component and a sparse signed residual. This is the formulation pursued in this work.
Figure 1. A sparse graph adjacency matrix is decomposed into a sparse low-rank block component and a sparse signed residual . Green entries denote added edges, while red entries denote missing edges relative to the recovered block structure.
In this paper, we propose sparse low-rank decompositions for integer-weighted graphs from a combinatorial perspective. We establish a connection between RPCA-style decompositions and sparse decompositions of graphs by introducing a signed biclique decomposition (SBD) framework. SBD represents a graph using a residual and a small number of sparse, signed, binary components, which can be interpreted as discrete shared-neighborhood or biclique-like patterns. This result provides a theoretical foundation for fast and scalable SLRS models on graphs and shows that low-rank graph structure can be approximated by discrete combinatorial objects rather than dense real-valued factors. Building on this connection, we propose a simple greedy algorithm that extracts such components efficiently and scales to large graphs.
SBD is motivated by the need for graph representations that are simultaneously sparse, interpretable, and computationally efficient. Sparser representations are desirable in graph settings as they preserve locality and reduce redundancy in the underlying structure. Empirically, we show that this formulation matches the reconstruction behavior of RPCA-style methods on small graphs while remaining scalable to large-scale settings. Moreover, the resulting decomposition enables significant computational gains, in particular, by accelerating sparse matrix–matrix multiplication (SpMM).
Our main contributions are:
We formulate graph sparse low-rank decomposition as a signed biclique decomposition of an integer-weighted adjacency matrix. Each component is a sparse signed binary rank-one matrix, so the resulting low-rank term remains combinatorial and sparse rather than dense.
We derive a greedy objective for signed bicliques. We prove that positive-gain steps decrease the residual norm and give conditions for alternating optimisation to find them. We bound the remainder using the stopping rule.
We introduce scalable SBD implementations for medium and large graphs. Because the decomposition is expressed in standard linear algebra, it can be used directly to accelerate SpMM.
We evaluate the method on graph denoising and SpMM benchmarks, where the sparse signed-biclique representation yields speedups over standard sparse kernels on graphs with strong shared-neighborhood structure.
Related Work
Several lines of work are closely related to our sparse low-rank decomposition framework.
Sparse low-rank decompositions for graphs and matrices. The most closely related works study matrices that are simultaneously sparse and low-rank. Savalle et al. [31] consider the estimation of matrices that satisfy both constraints, motivating sparse low-rank structure beyond the classical RPCA setting. Closer to our setting, Kanada et al. [20] propose a low-rank sparse decomposition of graph adjacency matrices for extracting clean clusters. These works share our motivation that graph structure should not be represented by a dense low-rank matrix. Like RPCA, these methods use singular-value thresholding for regularized nuclear-norm minimization, which is difficult to scale to large graphs and does not provide the discrete signed-biclique representation considered here.
Binary and Boolean matrix decompositions. A related line of work decomposes binary matrices under algebraic structures, such as the Boolean semiring or arithmetic over [26, 10, 5, 17]. These models suit compression and pattern discovery, but they use notions of rank that differ from standard linear algebra: Boolean addition satisfies , while arithmetic over satisfies . Consequently, they do not directly support linear operations such as multiplying an adjacency matrix by a dense feature matrix. Binary matrix factorization methods use ordinary arithmetic [22, 34, 33, 4], this typically restricts the model to unsigned bicliques, making it closer to edge partitioning than to a signed low-rank-plus-residual decomposition. Other methods, like Miller et al. [27], learn binary latent features on nodes to predict edge probabilities of the graph.
Cut, biclique, and spectral graph decompositions. Cut and biclique decompositions have also been studied in graph approximation and regularity theory. The Frieze–Kannan weak regularity lemma [11, 12] approximates a weighted adjacency matrix by a sum of weighted cut matrices, equivalently biclique-like blocks, with a residual controlled in cut norm. This provides an important connection between matrix approximation and graph structure. However, regularity-based decompositions are not designed to preserve sparsity.
There is also a classical connection between biclique decompositions and spectral graph structure. For example, the minimum number of bicliques required to partition the edges of a graph is lower bounded by , where and denote the numbers of positive and negative eigenvalues of the adjacency matrix [16, 15]. This shows that the biclique structure is closely tied to the spectrum of the graph. Related work by Ames and Vavasis [2] studies recovery of planted cliques and bicliques via nuclear norm minimization, further connecting combinatorial graph patterns with low-rank structure. These results motivate the use of biclique-like components.
Graph compression and summarization. Graph compression and summarization methods aim to represent graphs using compact structures, often through lossless or near-lossless encodings [24, 6]. While these methods are effective for reducing storage or identifying dense patterns, they are not designed to provide low-rank plus sparse decompositions compatible with linear algebraic operations. Those are much more aligned with binary matrix decomposition.
Accelerating SpMM on graphs. Several optimized GPU kernels have been proposed to accelerate SpMM on graphs, including Sputnik [13], dgSparse, and GE-SpMM [18]. More recently, compressed binary matrices (CBM) [1] proposed compressing graph adjacency operators using ordered neighborhood differences and cumulative sums to accelerate SpMM.
Overall, prior work either provides sparse low-rank formulations without a scalable discrete signed representation, binary decompositions under nonstandard algebraic operations, or graph compression methods that are not designed as linear low-rank-plus-residual models. Our contribution is to combine these desiderata: we decompose an integer-valued adjacency matrix in standard linear space into sparse signed biclique components and a sparse signed residual. The signed components allow cancellations between overlapping structures, while the binary supports preserve a combinatorial graph interpretation and enable efficient storage and computation.
Preliminaries
Notation. We write vectors and matrices in boldface. For an integer , let . For a matrix , denotes the Frobenius norm, the nuclear norm, and the entrywise norm. We denote by the rank of |\mathbf{M}|_{0}$ its number of nonzero entries. Given a set , we write for its indicator vector and its cardinality. For an optimisation problem over a vector , we denote an optimal solution by . Throughout the paper, for a given integer-weighted directed graph, denotes the number of nodes, denotes set of edges and denotes an integer-weighted adjacency matrix. We write decompositions of the form
where is the structured component and is the residual. We use the notation for the low-rank component in order to avoid confusion with the graph Laplacian.
Sparse plus low-rank decompositions. Sparse plus low-rank decompositions model an observed matrix in the form (1), where the two components satisfy and .
The low-rank component is intended to capture global or latent structure, whereas the sparse component captures localized deviations, corruptions, or outliers. Classical convex relaxations replace the rank by the nuclear norm and the number of nonzeros by the entrywise norm.
Robust principal component analysis. RPCA is a canonical sparse plus low-rank model. Given an observed matrix , RPCA seeks a decomposition (1) by solving the convex optimisation problem
where controls the low-rank–sparsity tradeoff [8]. Under suitable incoherence and sparsity assumptions, RPCA can exactly recover low-rank matrices with sparse corruptions. However, these assumptions are poorly matched to sparse graph adjacency matrices (see Appendix § 10.3.§ 4). This motivates decompositions in which the structured component is not only low-rank but also sparse.
Sparse principal component analysis. SPCA modifies PCA by imposing sparsity on the principal directions. A typical rank- formulation estimates sparse vectors through
Different variants use different normalizations, deflation schemes, and sparsity penalties [19, 35]. Although SPCA promotes sparse low-rank factors, it is not directly adapted to adjacency matrices since the factors are real-valued rather than discrete vertex indicators, and factor sparsity does not ensure that the residual remains sparse. Thus, SPCA does not, by itself, provide the sparse, combinatorial, and storage-efficient graph decomposition required here.
Signed Biclique Decomposition
We introduce SBD, a discrete low-rank model that represents an integer-weighted directed adjacency matrix as a sum of signed biclique blocks plus a sparse residual.
Model
Let be a directed integer-weighted adjacency matrix. For each component , let denote source and target node sets, and let denote its sign. We write , , where are binary indicator vectors. A signed biclique is the rank-one integer matrix . Given components, SBD writes
Since each biclique is rank one, . The decomposition has two goals. First, the biclique component should capture the dominant structure of , leaving a small residual , i.e., . Second, the representation should be compact. We encode each component by its supports and its sign, giving a storage cost of . The residual is stored sparsely. This motivates the cost , and the corresponding compression factor
Thus, larger values of CF correspond to more compact representations of the input graph and directly reduce the number of arithmetic operations required for sparse matrix computations.
Fixed-rank SBD objective
For a fixed number of components , we search for an SBD as the following discrete regularized optimisation problem.
Fixed-rank signed biclique approximation. Given and , solve
The first term controls reconstruction error:
The second term controls the length of the biclique component. Indeed, since and are binary, and . Thus, trades off reconstruction accuracy against biclique size. Small values of favor aggressive reconstruction, while larger values favor smaller and denser components (see Appendix § 10.3.§ 2). The Frobenius loss in (6) also promotes sparse residuals. Since and all signed bicliques are integer-valued, the residual is integer-valued. Therefore, , and minimizing the squared residual hence upper-bounds the number of residual entries that must be stored explicitly.
Greedy SBD objective
The problem in (6) is a combinatorial optimisation problem over coupled bicliques. We therefore use a greedy approximation that iteratively extracts one signed biclique at a time, in the spirit of matching pursuit [25], but with data-dependent combinatorial atoms. Let . At iteration , the next component is chosen by solving the rank-one problem
The residual is then updated as . An exact solver stops when no nonempty biclique improves the objective. Our finite seed search (§ 4.5) stops when its search budget is exhausted or no returned candidate has positive gain. This provides guarantees on the properties of the remainder obtained using either the exact solver or our heuristic methodology (Theorem 1).
Guarantees
The following result establishes the theoretical guarantees of greedy minimizing in (7). Full proof is deferred to Appendix § 10.§ 1.
Definition 1. We call gain the following function:
Note that minimizing (7) is equivalent to maximizing .
Theorem 1. Let . Start with . At each accepted step update , where . Then:
Residual decrease. Each step satisfies
There are at most steps. If , also .
Constraints at stopping. Suppose that stopping certifies for every candidate in a set , evaluated on the final residual. For each ,
where . If both signs were checked for the same supports, this also bounds .
Compression bound. Define . and is non increasing. For ,
Also, is non increasing for . It shows that our update increases a surrogate lower bound on CF at each step.
Corollary 1. If the stopping certificate includes every singleton support with both signs, then for all . Thus for , and its entries have magnitude at most one for .
A sequential search that checks positive gain on the exact current residual before acceptance satisfies the descent assumptions of Theorem 1. This includes both SBDGreedy and SBDFast. Neither method needs an exact rank-one solver for this descent guarantee.
The stopping constraints apply only to candidates checked on the final residual. A global rank-one oracle checks all candidates and implies Corollary 1. A finite seed search does not provide that global certificate. Appendix § 10.2 gives additional theoretical guarantees. Appendix § 10.3.§ 3 compares our search with a rank-one solver on small graphs.
Algorithms
SBDGreedy uses alternating optimisation (AO) to maximise (8). For a fixed sign and row support, columns contribute independently. With a density floor , the update is
The row update is symmetric. The density floor limits holes in the selected block. Appendix § 10.2.§ 2 derives the updates and local candidate sets. SBDGreedy checks the full gain before each sequential extraction, so Theorem 1 applies. Its stopping certificate covers only the candidates checked.
SBDFast searches seed batches in parallel and applies proposals sequentially. Before each acceptance, it recomputes the gain on the current exact residual, including updates from earlier proposals in the batch. The search first proposes positive blocks, then searches both signs. See Appendix § 10.4.§ 1 for more details.
Accelerating SpMM with SBD
Standard truncated SVD (-SVD) accelerates dense matrix multiplication by replacing a full matrix with dense low-rank factors, but this is poorly suited to graph SpMM: the dense singular vectors destroy the sparsity structure that makes SpMM efficient. In contrast, SBD accelerates SpMM while preserving sparsity and remaining lossless. After decomposition steps, defining , , , we obtain
This factorization yields a sparser representation of the propagation operator, thereby reducing the number of multiplications in SpMM. Computationally, it replaces a single SpMM by two sequential sparse multiplications involving thinner factors. As a result, the method reduces arithmetic and communication costs at the expense of decreased parallelism. In practice, the decomposition can be implemented efficiently in CUDA, where the reduced message volume helps amortize kernel-launch overhead.
Algorithm 1: SBDGreedy: signed biclique extraction
Require: , , , seed budget per sign, AO cap , extraction cap
repeat
For each sign , take up to rows ranked by
for all signed seeds in parallel do
Form local candidate sets around ; set ,
Alternate for at most iterations
Stop AO if both supports are unchanged or either is empty
end for
Select the nonempty candidate with largest full gain
if no candidate has positive gain then
stop
end if
until at most blocks have been extracted
Experiments
We evaluate SBD along three axes. First, we test whether the signed biclique model can recover sparse low-rank graph structure in a controlled denoising setting. Second, we compare the scalability of SBD against existing sparse low-rank matrix decomposition methods on real graphs (see Appendix § 10.4.§ 6). Third, we evaluate whether the learned representation yields practical speedups for SpMM, the core linear-algebraic primitive in many graph representation learning methods like graph neural networks [21].
Experimental setup
Graph denoising. We follow the benchmark of Kanada et al. [20]. The clean graph has ten cliques of 20 nodes (). We add inter-community edges with probability . We threshold at 0.5 and measure against the clean graph, excluding the diagonal. We compare SBDGreedy with RPCA [8], sparse SVD, Kanada et al. [20], and Savalle et al. [31], solved by ADMM. Each method uses 30 Optuna trials on five tuning graphs per noise level. Evaluation uses ten separate graphs. Appendix § 10.4.§ 2 gives all ranges and fixed settings.
Decomposition scalability. We measure decomposition time on real graphs with fixed settings. SBDGreedy and SBDFast run on CPU using eight threads, while the continuous baselines run on an RTX 3090 GPU. These settings do not match reconstruction quality. For compression, we select the SBDFast decomposition with the highest CF from 30 Optuna trials per graph.
SpMM acceleration. We reuse the selected decomposition across feature widths and GPUs. We compare with cuSPARSE, Sputnik [13], dgSPARSE, GE-SpMM [18], and CBM [1]. SBD_base uses our kernel without bicliques ( and ). All kernels are measured on RTX 3090, A40, and L40S, with ten warm-up and 50 timed launches; we report median latency. We use float32 features with columns. Multiplication uses , retaining the exact remainder. Appendix § 10.4.§ 3 describes the kernel and Appendix § 10.4.§ 2 gives the timing protocol.
Denoising sparse low-rank graph structure
Table 1 reports denoising performance across corruption levels. SBD exactly recovers the clean graph on the evaluation seeds in the low-noise regimes and remains competitive as the inter-community noise increases. At , SBD substantially improves over the noisy baseline and Savalle et al., and remains close to the best-performing methods. At the highest noise level, SBD and Kanada et al. both score 0.992, while SBD outperforms RPCA and sparse SVD. These results indicate that SBD captures the intended sparse block structure while using discrete biclique factors rather than dense or continuous low-rank components.
| Method | 0.05 | 0.15 | 0.25 | 0.35 |
| Noisy input | 0.808 | 0.585 | 0.457 | 0.375 |
| Savalle | 1.000 | 0.989 | 0.869 | 0.744 |
| RPCA | 1.000 | 1.000 | 0.999 | 0.707 |
| Sparse SVD | 1.000 | 0.999 | 0.970 | 0.749 |
| Kanada | 1.000 | 1.000 | 1.000 | 0.992 |
| SBDGreedy (ours) | 1.000 | 1.000 | 0.999 | 0.992 |
Table 1. SBM denoising F1 (), , , . Means over ten evaluation graphs.
Scalability of the decomposition
Table 2 compares decomposition runtimes under a 60 second budget. Kanada et al. and Savalle reach the time limit on Cora, CiteSeer and ca-HepPh, and run out of memory on ca-AstroPh. Savalle uses the same symmetry-based ADMM solver as in denoising. RPCA succeeds on Cora and CiteSeer, while its dense intermediate matrices scale as in memory. Sparse SVD is computationally efficient, but its continuous factors are not binary indicators and therefore do not provide the signed biclique representation needed for our SpMM kernel; see Appendix § 10.3.§ 4. In contrast, SBDFast completes all five graphs on CPU, from 0.022 seconds on Cora to 12.3 seconds on COLLAB, and SBDGreedy remains practical on the smaller instances. Continuous baselines are not evaluated on COLLAB because its dense input exceeds the memory limit.
Representation quality
tbl:3 reports the size of the SBDFast representation on larger real graphs. We distinguish between the compression factor CF, which counts support memberships, signs and residual entries, and the memory compression ratio CR, which compares representation bytes with CSR. CBM uses a graph compression format based on ordered neighborhood differences. SBD optimizes a different objective: it factorizes shared neighborhoods into signed biclique components while preserving compatibility with ordinary linear algebra. Thus, the relevant question is not only whether SBD compresses the
| Method | Cora | CiteSeer | ca-HepPh | ca-AstroPh | COLLAB | |
| SBDGreedy | 5.99 | 5.59 | OOT | OOT | OOT | |
| SBDFast | 0.022 | 0.026 | 0.35 | 0.60 | 12.3 | |
| Kanada | OOT | OOT | OOT | OOM | OOM | |
| RPCA | 4.36 | 7.10 | OOT | OOT | OOM | |
| Sparse SVD | 6.30 | 2.08 | 55.0 | OOT | OOM | |
| Savalle | OOT | OOT | OOT | OOM | OOM | |
| Dataset | CF | |||||
| Cora | 2,708 | 10,556 | 181 | 1.05 | 0.99 | 1.06 |
| PubMed | 19,717 | 88,648 | 1,651 | 1.08 | 1.04 | 1.05 |
| ca-HepPh | 12,008 | 237,010 | 2,437 | 3.23 | 3.43 | 2.75 |
| ca-AstroPh | 18,772 | 396,160 | 10,519 | 2.15 | 2.70 | 1.73 |
| coPapersDBLP | 540,486 | 30,491,458 | 86,855 | 8.57 | 10.3 | 5.98 |
| coPapersCiteseer | 434,102 | 32,073,440 | 84,862 | 11.3 | 14.4 | 9.91 |
| COLLAB | 372,474 | 24,572,158 | 53,646 | 10.9 | 12.2 | 11.0 |
Table 2. Runtime in seconds under a 60-second compute limit. OOT: time limit; OOM: allocation failure or dense input exceeding the 24 GiB budget. SBD uses eight CPU threads; continuous baselines use RTX 3090.
graph, but whether the resulting operator representation accelerates SpMM. Appendix § 10.4.2.4 gives both storage models.
The results show two regimes. On graphs with limited shared-neighborhood structure, such as Cora and PubMed, SBD is close to break-even in CF and does not provide substantial memory compression. Their byte ratios are 0.99 and 1.04. On graphs with stronger shared-neighborhood structure, such as coPapersDBLP, coPapersCiteseer and COLLAB, SBD obtains compression factors of 8.57, 11.3 and 10.9. Under the stated byte models, CBM compresses slightly better on Cora and PubMed, while SBD compresses better on the other five graphs.
SpMM acceleration
Figure 2 reports SpMM speedups relative to cuSPARSE. Averaged across the three GPUs, SBD is faster than cuSPARSE on every tested graph at each feature width, with the largest gains on high-CF datasets. On COLLAB, SBD reaches speedup at and remains above at and . On coPapersCiteseer, SBD obtains speedup at and above at larger feature dimensions. These results show that the signed biclique representation can reduce repeated computation while preserving the exact SpMM operator.
Figure 2. SpMM speedup over cuSPARSE, averaged over within each GPU and then over RTX 3090, A40 and L40S. Error bars show variation across GPU averages. SBD_base uses no bicliques. Per-width results are in Appendix C.5.
Figure 2 includes CBM alongside the GPU SpMM kernels. Compared with CBM, SBD is faster on every dataset and feature dimension in the GPU averages of Table 8. CBM benefits from compression on the largest community graphs, but is slower than cuSPARSE on the smaller graphs. SBD is also faster than Sputnik, dgSPARSE and GE-SpMM on the three largest graphs. However, Sputnik is faster on Cora, PubMed and ca-HepPh at every tested width.
| Dataset | Sputnik | dgSPARSE | GE-SpMM | SBD_base | CBM | SBD | |
| Cora | 32 | ||||||
| Cora | 128 | ||||||
| Cora | 256 | ||||||
| PubMed | 32 | ||||||
| PubMed | 128 | ||||||
| PubMed | 256 | ||||||
| ca-HepPh | 32 | ||||||
| ca-HepPh | 128 | ||||||
| ca-HepPh | 256 | ||||||
| ca-AstroPh | 32 | ||||||
| ca-AstroPh | 128 | ||||||
| ca-AstroPh | 256 | ||||||
| coPapersDBLP | 32 | ||||||
| coPapersDBLP | 128 | ||||||
| coPapersDBLP | 256 | ||||||
| coPapersCiteseer | 32 | ||||||
| coPapersCiteseer | 128 | ||||||
| coPapersCiteseer | 256 | ||||||
| COLLAB | 32 | ||||||
| COLLAB | 128 | ||||||
| COLLAB | 256 |
Table 8. Mean sample standard deviation of speedups over cuSPARSE across RTX 3090, A40, and L40S. SBD_base uses no bicliques. All six kernels, including CBM, were measured on each GPU.
SBD_base uses the same kernel without bicliques. Comparing it with SBD isolates the effect of the decomposition. On COLLAB at , it gives speedup compared with SBD’s , whereas it is faster than SBD on PubMed. The two-pass biclique computation amortizes column aggregation across rows sharing the same target set, but its overhead outweighs these benefits on weakly compressible graphs. Additional kernel-level details are provided in Appendix § 10.4.§ 3.
When does SBD help?
The largest speedups in Figure 2 occur on the graphs with the highest compression factors in Table 3. The observed speedup is smaller than CF on these graphs because SBD replaces a single CSR SpMM by a two-pass computation involving the biclique factors and the residual. CF counts entries rather than GPU costs, so it does not predict latency directly. Graphs such as Cora and PubMed provide little compression, and the additional two-pass overhead can dominate the benefit of the blocks.
Figure 3 studies the effect of using only the top bicliques, ordered by decreasing area. Increasing moves more of the graph from the sparse residual into the structured two-pass path, but the benefit depends on the feature dimension. At , speedup continues to improve over a large range of : COLLAB reaches its best sampled speed using about 56% of the available bicliques, and coPapersCiteseer behaves similarly. At and , these graphs reach their best sampled speed earlier. On COLLAB, the corresponding fractions are about 3.2% and 0.6%.
Figure 3. SpMM speedup over PyTorch sparse multiplication vs. number of bicliques used on L40S, for . Bicliques are added in decreasing area order and the exact residual is rebuilt for each prefix.
This is not a universal cutoff: ca-AstroPh reaches its best sampled speed at the full decomposition for all three widths. Thus, the decomposition is most beneficial when the graph contains many reusable shared-neighborhood blocks, and using all blocks need not give the fastest multiplication. Appendix § 10.3.§ 6 discusses the feature-width dependence. Both experiments use PyTorch sparse CSR multiplication with CUDA cuSPARSE backend as the reference.
Limitations
Our approach relies on structural redundancy in the graph for effective representation. Graphs with few shared-neighborhood structures require more biclique components and reduce compression efficiency. Signed binary factors may be less effective for weighted graphs (varying edge weights can require more components). Finally, our decomposition does not always lead to faster SpMM, as the overhead may outweigh its benefits on graphs with limited redundancy.
Conclusion
We introduced signed biclique decomposition (SBD), a sparse plus low-rank-and-sparse decomposition for integer-weighted graphs. Unlike classical low-rank methods such as RPCA, SBD represents the structured component as a sum of sparse signed binary rank-one factors, preserving the discrete, combinatorial, and computational properties of the graph. We formulated fixed-rank and greedy SBD objectives with theoretical guarantees. Empirically, SBD recovers latent block structure in noisy graphs competitively with RPCA-based methods, while remaining scalable to large graphs. On graphs with strong shared-neighborhood structure, SBD achieves compression factors above 10 and SpMM speedups up to over cuSPARSE, demonstrating that sparse combinatorial decompositions can serve as a practical and interpretable alternative to dense low-rank representations for graph data.
Appendix
Acknowledgment
The authors declare no competing interests. The authors acknowledge the French National Research Agency (ANR) for the JCJC project DeSNAP ANR-24-CE23-1895-01. This work is also supported by Hi! PARIS, ANR/France 2030 program ANR-23-IACL-0005, ANR-23-CMAS-0033, and ANR-23-RHUS-0002 (Innov4-ePiK).
Appendix
Table of Abbreviations
To assist the reader, Table 4 provides a summary of the main abbreviations and acronyms used throughout this paper.
Proofs
Proof of Theorem 1
Proof of Theorem 1. (1) Residual decrease and finite termination. Write and . Expanding the squared norm gives
Substituting the gain gives (9). Each accepted step strictly decreases the squared norm. This norm is a nonnegative integer, so there are at most steps. For , nonempty supports give . Summing the decreases over accepted steps yields
Hence . The bound also holds for .
(2) Constraints at stopping. Let . A nonempty candidate satisfies
Dividing by gives (10). Checking both signs on the same supports bounds . The bound covers only candidates checked on this final residual.
(3) Compression factor. Every nonzero integer has squared magnitude at least one. Thus
For , the representation cost satisfies
Since , dividing by these costs gives (11). Equation (9) also gives . Hence
For positive integer , an accepted gain is an integer with . The right-hand side is nonpositive, so the lower bound on does not decrease.
Proof of Corollary 1. The certificate checks both signs on every singleton. Choose the sign of a nonzero , where . Its gain satisfies
Since the residual is integer-valued, . Zero entries also satisfy this bound. It is zero for and one for .
Theoretical analysis
Additional Analysis on SBD Objective
Expansion of the greedy SBD objective. Expanding the Frobenius norm in (7) and using the fact that for binary vectors, the minimization reduces to the following (dropping the constant ):
Recall that we define the block density of a matrix on as:
Substitution of the residual. Substituting into (14) and using (15) yields:
Since and for binary vectors, the cross term satisfies:
Factoring out from (16), the objective reduces to:
where:
Interpretation of . The three terms in (19) have distinct roles:
Density reward : rewards bicliques that are aligned with the block structure of . For nonnegative , this term favours when the block density is positive. For signed input, it favours the sign of .
Signed overlap penalty : acts as an implicit memory mechanism. Same-sign overlap raises , discouraging the algorithm from covering the same region twice with the same sign. Opposite-sign overlap lowers , encouraging self-correction via an opposite-sign biclique on a previously covered region.
Size penalty : tends to zero as both supports grow and equals for a singleton, penalising small bicliques more strongly. The parameter directly controls this bias.
We denote overlap-corrected density as .
implies:
Since the right-hand side is strictly positive, and
Acceptance requires the absolute residual density to exceed . Here is the current residual density. This has three consequences: (i) the threshold is at least ; for , it approaches from above for large blocks and grows for small ones, so small blocks must be denser to be accepted; (ii) larger raises the threshold; in particular, when residual entries are bounded by in magnitude (e.g. binary before any overlap), block can be extracted, even when fully dense, only if ; (iii) same-sign past overlap reduces , requiring higher raw density to justify revisiting an already-covered region.
Derivation of the AO closed-form update
Separability of the gain at fixed . Fix the sign and the source set . Recall that the gain reads
where . decomposes as
Each contributes independently: including in improves the gain if and only if
The optimal at fixed therefore consists exactly of all columns whose average connection to exceeds . Denoting this set by
we have
Symmetrically, for fixed , the corresponding update satisfies
Thus, starting from an initial seed, alternating these two updates yields an alternating-optimization procedure whose gain is non-decreasing at each step.
Minimum-density floor (binary matrices). For a current residual and sign , entries with are holes: subtracting from sets them to , adding nonzero residual entries at those positions. The hole count equals exactly , so controlling directly limits holes.
We impose a per-node density floor: include only if . Combined with (24), this gives
Setting recovers the pure half-step. Averaging gives for a nonempty AO output. For a binary current residual and positive sign, this bounds holes by .
Neighbourhood initialisation. Seeds are ranked separately by positive and negative residual. We take up to seeds per sign and orientation (row or column), giving at most starts per extraction. Algorithm 1 shows the row-seed case.
For sign , we expand the neighbourhood along entries with . A row seed first reaches columns, then rows, then columns again; a column seed uses the transposed initialisation. We search both seed types. AO updates rows first for a row seed, and columns first for a column seed. Before AO, we trim the candidate sets using alternating row and column updates. If either set is empty, the initial window is kept. Trimming reduces search cost but can exclude positive-gain blocks. AO uses residual weights within the retained sets. Acceptance checks the full gain.
Positive-gain certificates
The following conditions identify seeds that can yield positive-gain. Let be the current nonempty column set and let . For each row , define
The row update keeps whenever
Proposition 1 (Shared-neighborhood certificate). Assume that there is a nonempty set such that
with
and
Then the next row update has positive gain. Later updates preserve positive gain if they maximise the gain with the other support fixed. An active density floor need not preserve this property.
Proof. Every row in passes the update threshold. At fixed , the gain can be written as
Let be the row support returned by the update. Since every selected row has positive contribution,
Each later exact coordinate update maximizes the gain with the other support fixed. Hence the gain cannot decrease.
For the initialization and ,
For a binary residual, this is the number of neighbors shared by and the seed . A second certificate uses the clustering coefficient.
Proposition 2 (Clustering certificate). Let be the adjacency matrix of a simple undirected binary graph. Let have degree and clustering coefficient . Then the block
has positive gain for if and only if
Proof. Let be the number of edges between the neighbors of . Then
For ,
Thus if and only if
The two certificates have different roles. The shared-neighborhood condition applies to the AO update. The clustering condition shows that the neighborhood block has positive gain, but it does not guarantee that AO finds this block.
Exact-recovery guarantees
Fix , a sign , and scoped domains . Let be a positive-gain fixed point of the actual updates, including the density floor and tie rule. Let be the nonempty initial column set and define
Proposition 3 (Recovery of a fixed point). Assume
One row update followed by one column update recovers .
Proof. The separation condition makes the first row update select exactly . Since the target is a fixed point, the next column update returns .
If the target also maximises gain over the scoped domain, the recovered block is optimal there. This does not imply optimality outside that domain. Global optimality alone does not ensure a fixed point of updates with an active density floor or a different tie rule. For a binary residual and , counts shared neighbours. Recovery requires the threshold to separate target rows from all other candidates after scoping.
Bounds from empty updates
If a column update from nonempty returns no column in , then
This follows by reversing the update inequality and dividing by . An empty row update gives the symmetric bound. Checking both signs bounds the absolute density. The result concerns the final remainder only when the update was evaluated on that remainder. It covers only the searched domain.
Additional analysis
Local positive-gain structure
Table 5 reports the rates at . The script evaluates the original binary graph, before scoping, with . Its local test uses , without an active density floor. These rates do not certify the candidates retained by the implemented search.
| Dataset | Clustering (%) | Shared neighbors (%) |
| Cora | 0.1 | 9.1 |
| PubMed | 0.0 | 12.1 |
| ca-HepPh | 22.5 | 43.7 |
| ca-AstroPh | 30.2 | 57.0 |
| coPapersDBLP | 78.0 | 91.6 |
| coPapersCiteseer | 83.3 | 93.9 |
| COLLAB | 84.3 | 96.5 |
Table 5. Percentage of nodes satisfying the clustering or shared-neighborhood positive-gain condition at . Tests use the original binary graph before scoping and do not apply a density floor. These rates describe available local structure, not the success rate of the implemented search.
The certificate rates are low on Cora and PubMed and high on the coauthorship and copaper graphs. Higher rates generally come with larger CF values. These rates describe local positive-gain structure. They are not bounds on the final CF.
Impact of the Regularization Parameter
We first derive the gain thresholds for several block shapes. We then measure how changing affects the residual and compression.
Threshold interpretation. Consider a single nonzero residual entry . For a singleton biclique , , the overlap-corrected density is the entry itself, , and the acceptance condition reads
which is exactly the singleton gain condition used in the proof of Theorem 1, claim 2. Since residual entries are integers, every nonzero entry satisfies , so for every nonzero residual entry yields positive singleton gain. Exact recovery then requires the singleton stopping certificate of Corollary 1. For , entries of magnitude 1 can no longer be removed by a singleton, and singleton corrections are never accepted on residuals with entries in .
Structure-dependent thresholds. The parameter controls which blocks have positive gain. Acceptance requires
The threshold is at least and increases with . When residual entries are bounded by 1 in magnitude (e.g. binary A before any overlap), we have , so a block of shape can be extracted, even when fully dense, only if
We call this bound the extraction limit for the block shape. Equation (21) gives:
Singleton (): threshold is ; extraction limit .
Star (, ): threshold is ; extraction limit . For large , the threshold approaches , below the singleton threshold, making wide stars easier to accept than singletons.
| Structure | Extraction limit () | ||
| Singleton | 1 | 1 | |
| Star () | 1 | 5 | |
| 2 | 2 | 1 | |
| 2 | 3 |
Table 6. Extraction limits for fully dense blocks when residual entries have magnitude at most one. Larger blocks allow higher .
biclique (): threshold is ; extraction limit .
biclique (, ): threshold is ; extraction limit .
Effect on residual norm. For a fixed residual, increasing raises the acceptance threshold. The search path can change, so the final residual norm need not increase with .
: every nonzero integer entry gives positive singleton gain. A stopping certificate covering all signed singleton supports therefore gives by Corollary 1. A finite seed search or budget limit alone does not give this certificate.
: unit entries cannot be removed by singleton updates. When residual entries have magnitude at most one, a star with leaves requires . Larger dense blocks may still be accepted. The singleton stopping certificate implies .
: when residual entries have magnitude at most one, stars and blocks are rejected, and acceptance requires . Theorem 1 gives a lower bound on CF, not compression optimality or monotone CF.
Binary input does not ensure bounded residual entries after overlapping updates. Figure 4 and Figure 5 show the measured trends. Small late blocks can reduce CF when their storage cost exceeds the residual entries they remove.
Figure 4. Normalised residual and compression factor CF as a function of . Dashed vertical lines mark (unit-singleton threshold) and (the range where the storage bound applies).
Figure 5. Normalised residual (top row) and compression factor (bottom row) as a function of the number of extracted bicliques , for five values of . (a) Les Misérables (). (b) SBM (, ). Dashed horizontal line in bottom row: (break-even point). On the SBM, converge after exactly 10 bicliques in this run. At the plotted , the residual reaches zero in both graphs. For small , CF declines at large once the remaining extractions are singletons and small stars whose index cost exceeds the edges they remove.
Comparison with a rank-one solver
We compare the AO heuristics with a mixed-integer solver for each greedy rank-one problem. Each sign is solved as a binary quadratic problem with a 60-second limit. We save the incumbent, solver status, bound and gap for both signs. A step is certified only when both signs are solved to optimality. Greedy and Fast use the current deterministic seed ordering.
We run the comparison on Karate Club, Les Misérables, and Dolphins for .
For each method, we report the number of extracted bicliques , the Compression Factor, and the residual Frobenius norm.
The methods often give similar CF and residual norms, but can return different numbers of blocks. This compares final decompositions; it does not establish the per-step gap to an exact oracle or test Proposition 3.
Why SVD-based Methods are Mismatched to our Objective
Standard sparse-plus-low-rank methods such as RPCA [8] decompose where is a real-valued low-rank matrix and is sparse. These are designed for settings where a dense continuous signal is corrupted by sparse noise. Our objective is different by construction: we seek a decomposition into binary integer rank-one bicliques plus a sparse integer residual. The two problems differ in what the low-rank component is allowed to be.
Table 7: Rank-one solver and AO heuristics on three small graphs as varies. We report the number of bicliques , compression factor CF, and residual norm after decomposition. Each signed solver subproblem has a 60-second limit. A dagger marks a decomposition with an uncertified step. Rank-one optima do not imply a global optimum for the final decomposition.
| Rank-one MIQP | Rank-one MIQP CF | Rank-one MIQP | SBDGreedy | SBDGreedy CF | SBDGreedy | SBDFast | SBDFast CF | SBDFast | |
| Karate | |||||||||
| 0.0 | 33 | 0.79 | 0.00 | 30 | 0.88 | 0.00 | 33 | 0.63 | 2.00 |
| 0.5 | 24 | 0.94 | 2.45 | 24 | 0.94 | 2.45 | 24 | 0.96 | 3.61 |
| 1.0 | 9 | 1.17 | 7.48 | 8 | 1.17 | 7.87 | 9 | 1.18 | 7.35 |
| 2.0 | 0 | 1.00 | 12.5 | 0 | 1.00 | 12.5 | 0 | 1.00 | 12.5 |
| 4.0 | 0 | 1.00 | 12.5 | 0 | 1.00 | 12.5 | 0 | 1.00 | 12.5 |
| Les Misérables | |||||||||
| 0.0 | 88 | 1.03 | 0.00 | 88 | 1.03 | 0.00 | 73 | 0.96 | 5.57 |
| 0.5 | 43 | 1.33 | 6.93 | 45 | 1.28 | 6.71 | 50 | 1.23 | 8.12 |
| 1.0 | 12 | 1.56 | 13.5 | 12 | 1.54 | 13.7 | 16 | 1.46 | 13.8 |
| 2.0 | 4 | 1.50 | 16.2 | 4 | 1.49 | 16.3 | 4 | 1.40 | 17.1 |
| 4.0 | 1 | 1.18 | 20.1 | 1 | 1.18 | 20.1 | 1 | 1.15 | 20.4 |
| Dolphins | |||||||||
| 0.0 | 86 | 0.00 | 89 | 0.69 | 0.00 | 79 | 0.62 | 5.29 | |
| 0.5 | 62 | 5.39 | 61 | 0.80 | 5.57 | 58 | 0.82 | 7.48 | |
| 1.0 | 14 | 1.09 | 13.6 | 10 | 1.09 | 14.4 | 16 | 1.07 | 13.4 |
| 2.0 | 0 | 1.00 | 17.8 | 0 | 1.00 | 17.8 | 0 | 1.00 | 17.8 |
| 4.0 | 0 | 1.00 | 17.8 | 0 | 1.00 | 17.8 | 0 | 1.00 | 17.8 |
Table 7.
SVD factors and community supports. For an isolated loopless clique of size , the leading eigenvalue is . Its scaled factor is . Equal-sized cliques have repeated eigenvalues, so their eigenvectors can mix. Inter-community edges can also spread the factors across communities, as in Figure 6. SVD does not enforce binary factors or a sparse remainder.
Figure 6. Top- symmetric factors of an SBM adjacency matrix (, , , ), nodes sorted by ground-truth community (red lines = block boundaries). An isolated loopless clique has scaled factor ; repeated eigenvalues allow mixtures. In this example, factors spread across communities, producing a real-valued, non-binary vector.
Sparsity on factors does not imply binariness. Our sparseSVD baseline alternates soft-thresholded row and column updates with rank-one deflation. It promotes sparsity on the factors, which might seem closer to our setting. However, sparsity does not make the factors binary. The low-rank component is a sum of sparse real-valued outer products, entries take arbitrary values in , not in . We verify this even in the most favorable case: SBM with , , , , SparseSVD rank set to the true , . Even here, 75.6% of entries of exceed 0.05 in magnitude, compared to the original graph’s 18.5% nonzeros (Figure 7).
Figure 7. Distribution of entries for SBM (, , , ), SparseSVD rank is 10, .
Scalability. On sparse graphs, each matrix-vector product costs . RPCA repeatedly applies singular-value thresholding to dense intermediate matrices, which increases memory use and runtime.
Full kernel comparison
Table 8 gives the per-width results for Figure 2.
Figure 2 compares SpMM speedups over cuSPARSE. SBD_base uses the same kernel without bicliques, so the SBD gap measures their effect. The largest gains are on coPapersDBLP, coPapersCiteseer, and COLLAB, which have high CF. On COLLAB, mean SBD speedup is at , at , and at (Appendix C.5). Factor multiplications add overhead on Cora and PubMed. Compression does not guarantee faster SpMM.
Feature width and retained blocks
On COLLAB, the fastest sampled prefix uses 30,242 of 53,646 blocks at , 1,722 at , and 308 at . Adding more blocks can slow down SpMM. These are measurements for the plotted configuration, not universal thresholds across GPUs. At , eight lanes per warp load the eight float4 feature groups. At , all 32 lanes load one group. This may affect memory throughput, but the curves alone do not establish bandwidth saturation or exclude cache effects. Profiling is needed to test that explanation.
Implementation details
SBDFast implementation (binary matrices)
SBDFast has two search phases. First, it proposes positive blocks using a binary mask of the positive residual entries. Then it searches for positive and negative blocks using the integer residual. Both phases maintain the exact residual and use it to check each proposal before acceptance. Negative entries can arise from holes or overlaps in positive blocks.
Parallel search and sequential acceptance. Workers process seed nodes in batches against a fixed residual. They return potential blocks, which are ordered by their search gains. We then check each block in this order. We recompute its gain on the current residual and accept it if the gain is positive and the density condition holds. After each acceptance, we subtract the block from the residual before checking the next proposal. Several blocks can therefore be accepted from one batch, reducing the number of parallel searches. In comparison, SBDGreedy accepts only the best block from each search.
Exact residual updates. The residual uses sparse row and column arrays, with separate lists for fill-ins. Each accepted block updates all entries in its support, including zeros (which can become fill-ins) and entries of the opposite sign. Compaction merges the extra lists into the sparse arrays and removes zeros. It changes the storage in the algorithm, not the residual.
Search settings. The seed budget controls search effort independently of the thread count. The main compression and runtime experiments use one signed sweep; the rank-one comparison uses up to 20 signed sweeps. The candidate row limit remains 400.
Guarantees. Every accepted block has positive gain on the current exact residual. Theorem 1 therefore gives residual decrease and objective descent for SBDFast. For integer input and , there are at most accepted blocks. The search remains heuristic: it does not certify that no positive-gain block remains. The stopping bounds require nonpositive gain checks on the final residual. Exact recovery requires the additional certificate in Corollary 1.
Experimental protocol and hyperparameters
Denoising
Search and evaluation. The Optuna sampler is TPE. Each graph has ten blocks of 20 nodes and . The noise levels are .
Search spaces. SBDGreedy searches log-uniformly, uniformly, and an integer step cap in . It uses 200 seeds and eight threads. RPCA, Kanada, and sparse SVD search uniformly. Sparse SVD fixes rank 10. Each search uses 30 trials. Savalle uses one 30-trial search with log-uniformly and uniformly.
Denoising solver defaults. RPCA uses 1,000 iterations and tolerance . Kanada uses 1,000 iterations and tolerance . Sparse SVD uses 100 power iterations per component and tolerance . Kanada uses ADMM penalty . Sparse SVD uses random initial vectors. Savalle uses 1,000 iterations for tuning and up to 5,000 for evaluation, with tolerance . A failed convergence check gets one retry at fixed .
SBDGreedy uses up to eight scoping rounds and 20 AO rounds per start. These caps, the seed and thread counts are fixed.
| Parameter | ||||
| SBD | 4.55 | 4.55 | 6.81 | 8.15 |
| SBD | 0.58 | 0.58 | 0.51 | 0.58 |
| SBD step cap | 19 | 19 | 98 | 83 |
| RPCA | 0.12 | 0.06 | 0.06 | 0.06 |
| Kanada | 0.12 | 0.12 | 0.06 | 0.06 |
| Sparse SVD | 0.31 | 0.41 | 0.50 | 0.75 |
| Savalle | 3.81 | 6.57 | 7.55 | 7.57 |
| Savalle | 0.21 | 0.07 | 0.08 | 0.09 |
Table 9. Selected denoising parameters for Table 1.
Decomposition runtime
Fixed settings. Both methods use and eight threads. SBDGreedy uses at most extractions, 64 seeds per sign and orientation, and . SBDFast uses a nominal seed budget of , 32 local starts, batches of 32 seeds, one signed sweep, and . Kanada uses . RPCA uses . Both allow up to 5,000 iterations. Sparse SVD extracts up to components, with and up to 100 iterations per component. Savalle uses the float64 symmetry-based ADMM solver, with , up to 5,000 iterations, and adaptive penalty starting at . If it does not converge, it retries with fixed under the same total time limit. All continuous solvers use a tolerance of with their respective stopping criteria. Each run has a 60-second compute limit.
Compression and cache selection
Search and fixed settings. Each graph uses 30 TPE trials with sampler seed 42. The search samples log-uniformly and uniformly. Each trial uses SBDFast with a nominal seed budget of 500,000, 32 local starts, batches of 32 seeds, one signed sweep, and eight threads. We select the highest CF (Table 10). CBM fixes .
| Dataset | ||
| Cora | 1.31 | 0.53 |
| PubMed | 1.31 | 0.53 |
| ca-HepPh | 1.23 | 0.50 |
| ca-AstroPh | 1.19 | 0.63 |
| coPapersDBLP | 1.51 | 0.67 |
| coPapersCiteseer | 1.11 | 0.74 |
| COLLAB | 1.35 | 0.70 |
Table 10. Parameters recorded in the selected decomposition caches used for Table 3 and SpMM.
Compression accounting
Entry-count model. Let , , and . CF counts one unit per membership, sign, and residual entry:
CF does not depend on integer width and excludes pointer arrays.
Kernel storage. The input CSR uses bytes. SBD stores int32 pointers, membership indices, and residual indices and values. Signs use int8. Factor values are one and are not stored. The row-factor and residual pointers have length . The column-factor pointers have length . Thus
These counts exclude features, outputs, temporary buffers, and allocator overhead.
CBM storage. We retain the authors’ accounting: , where counts delta entries and counts forest edges. This includes delta CSR and two forest-edge arrays. It excludes GPU branch offsets. Neither ratio measures total GPU memory.
CBM implementation. Our CBM wrapper uses a custom OpenMP decomposition and the authors’ GPU update kernels. It converts the forest to branch offsets, adjusts the branch count, and skips empty update launches. We fix .
SpMM and block-prefix measurements
We evaluate with float32 features. The kernel scripts do not sweep decomposition parameters or kernel configurations. CBM uses . Both kernel comparisons use ten warm-up launches and 50 timed launches. Features use seed 42. Reference CSR indices use int32. Every timed kernel is checked against sparse matrix multiplication within numerical tolerance. For the block-prefix experiment, we sort bicliques by area. We request 20 logarithmically spaced prefix lengths from one to all blocks and round them to integers. We rebuild the exact residual for each prefix. We vary and without repeating the decomposition search. The script times the reference and candidate in pairs, with defaults of 10 warm-up and 50 timed launches.
Regularization sweep
SBDGreedy uses a 500-step cap, , and eight threads. We use 64 seeds on Les Misérables and 200 on the SBM. The summary evaluates 36 values of between 0.05 and 2.5. The trajectories use .
CUDA Kernel Design
This appendix describes the CUDA kernels used for SpMM. SBD_base uses our kernel without bicliques, so comparison with SBD measures the effect of the decomposition.
Warp mapping. The kernel assigns one warp to each output row. Lanes traverse the same CSR neighbour list and process different groups of four features using float4 loads.
Register accumulation. Each lane accumulates its feature groups in registers. Column aggregation uses additions, signed biclique combination uses additions or subtractions, and residual accumulation uses FMAs. The kernels use no shared-memory staging. SBD stores the first-pass output in a global buffer of shape .
Memory accesses. Lanes read contiguous feature groups, giving coalesced accesses to the feature matrix. Actual memory traffic depends on cache behaviour.
Synchronisation. Each warp keeps its partial sums in registers and computes its row independently. The kernels use no __syncthreads() or programmer-managed shared memory. This avoids block barriers and shared-memory bank conflicts. Ready warps can overlap memory requests, helping to hide memory latency. The two passes execute in order on the same CUDA stream.
Two-pass computation. We compute in two passes. The first pass (QTX) assigns one warp per biclique and computes . The second pass (WSZ_RX) assigns one warp per output row and computes
The intermediate column sum is computed once and reused by every row in . This amortises column aggregation across rows sharing the same target set.
Performance regimes. The largest gains occur on graphs with many shared-neighbourhood blocks. On weakly compressible graphs, the cost of the two-pass computation can outweigh the benefit of reusing column sums. Table 8 gives the results for all graphs and widths.
SpMM baselines
Table 8 compares Sputnik [13], dgSPARSE, GE-SpMM [18], SBD_base, CBM, and SBD. SBD_base uses the raw adjacency matrix without bicliques.
Computational Resources
Hardware platforms. The SpMM experiments use three GPU platforms with a common software stack: PyTorch 2.11.0, Python 3.12 and CUDA 13.0. The SpMM benchmarks are run on each platform independently.
| GPU | VRAM | L2 Cache | Host CPU |
| NVIDIA RTX 3090 | 24 GB | 6MB | Intel Xeon Silver 4116 |
| NVIDIA A40 | 48 GB | 6MB | Intel Xeon Silver 4210 |
| NVIDIA L40S | 48 GB | 96MB | AMD EPYC 9124 |
Table 11. Hardware platforms used in this work.
Timing protocol. We report median per-launch latency measured with CUDA events. Both comparisons use ten warm-ups and 50 timed launches. Inputs stay on the GPU. SBD allocates output and intermediate buffers on each call; some baselines preallocate output. Timing excludes input transfer and decomposition.
Decomposition. The SBDFast CPU decomposition uses a pool of 8 worker threads on all platforms, matching the SLURM allocation (--cpus-per-task=8). Decomposition time is excluded from all SpMM figures; it is reported separately in the decomposition tables.
Reproduction settings. Appendix D.2 lists search budgets and timing settings. Total reproduction time depends on hardware and solver stopping behaviour. All experiments can be rerun in several hours.
Datasets
We evaluate our method on a diverse collection of benchmark graph datasets commonly used in graph representation learning and graph neural network (GNN) research. They cover citation, co-authorship, co-purchase, co-paper, and collaboration graphs.
Citation Networks. The citation network benchmarks include Cora, CiteSeer, and PubMed, which are standard node classification datasets introduced in early graph learning literature [32]. Cora contains scientific publications classified into machine learning topics, CiteSeer consists of scientific articles grouped into research categories, and PubMed contains biomedical publications from the PubMed database. Nodes correspond to documents and edges denote citation relationships.
Co-authorship Networks. We additionally evaluate on the co-authorship datasets CA-AstroPh and CA-HepPh [23], where nodes represent authors and edges indicate co-authorship relationships. These datasets are derived from collaboration networks in the astrophysics and high-energy physics communities and are widely used for large-scale graph representation benchmarking.
Co-paper Networks. The coPapersDBLP and coPapersCiteSeer datasets [14] represent paper similarity and co-occurrence relationships derived from the DBLP and CiteSeer corpora.
Social Interaction Graphs. Finally, we evaluate on the COLLAB dataset from the TUDataset collection [28], which is a scientific collaboration network commonly used for graph classification tasks. Graphs correspond to ego-networks of researchers and edges denote collaborative relationships. We use the disjoint union of all graphs in the dataset. This gives the single adjacency matrix reported in the tables.
All datasets are publicly available and have been extensively adopted in prior graph representation learning studies.
References
- [1]Joao Alves, Samir Moustafa, Siegfried Benkner, Alexandre P. Francisco, Wilfried Gansterer, and Luís M. S. Russo. Accelerating graph neural networks using a novel computation-friendly matrix compression format. In IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2025.DOI
- [2]Brendan P. W. Ames and Stephen A. Vavasis. Nuclear norm minimization for the planted clique and biclique problems. Mathematical Programming (MP), 2011.arxiv.org/abs/0901.3348
- [3]Sumanta Basu, Xianqi Li, and George Michailidis. Low rank and structured modeling of high-dimensional vector autoregressions. IEEE Transactions on Signal Processing (TSP), 2019.DOI
- [4]Melanie Beckerleg and Andrew Thompson. A divide-and-conquer algorithm for binary matrix completion. Linear Algebra and its Applications (LAA), 2020.DOI
- [5]Radim Belohlavek and Vilem Vychodil. Discovery of optimal factors in binary data via a novel method of matrix decomposition. Journal of Computer and System Sciences (JCSS), 2010.DOI
- [6]Maciej Besta and Torsten Hoefler. Survey and Taxonomy of Lossless Graph Compression and Space-Efficient Graph Representations. arXiv, 2018.arxiv.org/abs/1806.01799
- [7]Adrienne E. Campbell-Washburn, David Atkinson, Zoltan Nagy, Rachel W. Chan, Oliver Josephs, Mark F. Lythgoe, Roger J. Ordidge, and David L. Thomas. Using the robust principal component analysis algorithm to remove rf spike artifacts from mr images. Magnetic Resonance in Medicine (MRM), 2016.
- [8]Emmanuel J. Candès, Xiaodong Li, Yi Ma, and John Wright. Robust principal component analysis? Journal of the ACM (JACM), 2011.arxiv.org/abs/0912.3599
- [9]Junbo Chen, Shouyin Liu, and Min Huang. Low-rank and sparse decomposition model for accelerating dynamic mri reconstruction. Journal of Healthcare Engineering (JHE), 2017.DOI
- [10]Chen Dan, Kristoffer Arnsfelt Hansen, He Jiang, Liwei Wang, and Yuchen Zhou. Low Rank Approximation of Binary Matrices: Column Subset Selection and Generalizations. In International Symposium on Mathematical Foundations of Computer Science (MFCS), Leibniz International Proceedings in Informatics (LIPIcs), 2018.
- [11]Alan Frieze and Ravindran Kannan. A simple algorithm for constructing szemerédi’s regularity partition. The Electronic Journal of Combinatorics (E-JC), 1999.DOI
- [12]Alan Frieze and Ravindran Kannan. Quick approximation to matrices and applications. Combinatorica, 1999.DOI
- [13]Trevor Gale, Matei Zaharia, Cliff Young, and Erich Elsen. Sparse GPU kernels for deep learning. In International Conference for High Performance Computing, Networking, Storage and Analysis (SC), 2020.arxiv.org/abs/2006.10901
- [14]Robert Geisberger, Peter Sanders, and Dominik Schultes. Better approximation of betweenness centrality. In Workshop on Algorithm Engineering and Experiments (ALENEX), 2008.
- [15]R. L. Graham and H. O. Pollak. On the addressing problem for loop switching. The Bell System Technical Journal (BSTJ), 1971.DOI
- [16]David A. Gregory, Valerie L. Watts, and Bryan L. Shader. Biclique decompositions and hermitian rank. Linear Algebra and its Applications (LAA), 1999.DOI
- [17]Oktay Günlük, Raphael Andreas Hauser, and Réka Ágnes Kovács. Binary matrix factorization and completion via integer programming. Mathematics of Operations Research (MOR), 2024.DOI
- [18]Guyue Huang, Guohao Dai, Yu Wang, and Huazhong Yang. Ge-spmm: General-purpose sparse matrix-matrix multiplication on gpus for graph neural networks. In International Conference for High Performance Computing, Networking, Storage and Analysis (SC), 2020.arxiv.org/abs/2007.03179
- [19]Ian Jolliffe, Nickolay Trendafilov, and Mudassir Uddin. A modified principal component technique based on the lasso. Journal of Computational and Graphical Statistics (JCGS), 2003.DOI
- [20]Taiju Kanada, Masaki Onuki, and Yuichi Tanaka. Low-rank sparse decomposition of graph adjacency matrices for extracting clean clusters. In Asia-Pacific Signal and Information Processing Association Annual Summit and Conference (APSIPA ASC), 2018.DOI
- [21]Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017.arxiv.org/abs/1609.02907
- [22]Mehmet Koyutürk and Ananth Grama. Proximus: a framework for analyzing very high dimensional discrete-attributed datasets. In ACM International Conference on Knowledge Discovery and Data Mining (KDD), 2003.
- [23]Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graph evolution: Densification and shrinking diameters. ACM Transactions on Knowledge Discovery from Data (TKDD), 2007.arxiv.org/abs/physics/0603229
- [24]Yike Liu, Tara Safavi, Abhilash Dighe, and Danai Kout ra. Graph summarization methods and applications: A survey. ACM Computing Surveys (CSUR), 2018.
- [25]S.G. Mallat and Zhifeng Zhang. Matching pursuits with time-frequency dictionaries. IEEE Transactions on Signal Processing (TSP), 1993.DOI
- [26]Pauli Miettinen, Taneli Mielikäinen, Aristides Gionis, Gautam Das, and Heikki Mannila. The discrete basis problem. IEEE Transactions on Knowledge and Data Engineering (TKDE), 2008.
- [27]Kurt Miller, Michael Jordan, and Thomas Griffiths. Nonparametric latent feature models for link prediction. In Advances in Neural Information Processing Systems (NIPS), 2009.
- [28]Christopher Morris, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. TUDataset: A collection of benchmark datasets for learning with graphs. In ICML Workshop Graph Representation Learning and Beyond, 2020.arxiv.org/abs/2007.08663
- [29]Ankit Parekh and Ivan W. Selesnick. Improved sparse low-rank matrix estimation. Signal Processing, 2017.DOI
- [30]Benjamin Recht, Maryam Fazel, and Pablo A. Parrilo. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Review, 2010.
- [31]Pierre-André Savalle, Emile Richard, and Nicolas Vayatis. Estimation of simultaneously sparse and low rank matrices. In International Conference on Machine Learning (ICML), 2012.arxiv.org/abs/1206.6474
- [32]Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. AI Magazine, 2008.DOI
- [33]Bao-Hong Shen, Shuiwang Ji, and Jieping Ye. Mining discrete patterns via binary matrix factorization. In ACM International Conference on Knowledge Discovery and Data Mining (KDD), 2009.DOI
- [34]Zhongyuan Zhang, Tao Li, Chris Ding, and Xiangsun Zhang. Binary matrix factorization with applications. In IEEE International Conference on Data Mining (ICDM), 2007.DOI
- [35]Hui Zou, Trevor Hastie, and Robert Tibshirani. Sparse principal component analysis. Journal of Computational and Graphical Statistics (JCGS), 2006.






