betaFeedback

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 1010 and SpMM speedups up to 6×6\times 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 AA is decomposed as A=L0+R0A = L_0 + R_0, where L0L_0 is a low-rank matrix that captures global or latent structure, and R0R_0 is a sparse matrix capturing localized deviations, outliers, or corruptions. We refer to R0R_0 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].

AbbreviationDescription
SLRSparse plus Low-Rank (matrix decomposition model)
SLRSSparse plus Low-Rank-and-Sparse (our graph-adapted model)
RPCARobust Principal Component Analysis
SPCASparse Principal Component Analysis
SBDSigned Biclique Decomposition (proposed framework)
SpMMSparse Matrix-Matrix Multiplication (A×XA \times X)
CFCompression Factor (∣A∣0/repr_cost|A|_0/\mathrm{repr\_cost})
CRMemory Compression Ratio (MB(CSR)/MB(format)\mathrm{MB}(\mathrm{CSR})/\mathrm{MB}(\mathrm{format}))
AOAlternating Optimization
ILPInteger Linear Programming (exact combinatorial solver)
CSRCompressed Sparse Row format
SBMStochastic 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 A\mathbf{A} (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 L0\mathbf{L}_0 is represented by a small number of sparse graph-supported low-rank components and R0\mathbf{R}_0 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 A\mathbf{A} is decomposed into a sparse low-rank block component L0\mathbf{L}_0 and a sparse signed residual R0\mathbf{R}_0. 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 Z/2Z\mathbb{Z}/2\mathbb{Z} [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 1+1=11+1=1, while arithmetic over Z/2Z\mathbb{Z}/2\mathbb{Z} satisfies 1+1=01+1=0. 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 max⁡(n+(A),n−(A))\max(n_{+}(\mathbf{A}), n_{-}(\mathbf{A})), where n+(A)n_{+}(\mathbf{A}) and n−(A)n_{-}(\mathbf{A}) 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 n≥1n \ge1, let [n]:={1,…,n}[n] := \{1, \ldots, n\}. For a matrix M∈Rn×m\mathbf{M} \in\mathbb{R}^{n \times m}, ∥M∥F\|\mathbf{M}\|_{\mathrm{F}} denotes the Frobenius norm, ∥M∥∗\|\mathbf{M}\|_{*} the nuclear norm, and ∥M∥1\|\mathbf{M}\|_{1} the entrywise ℓ1\ell_{1} norm. We denote by rank⁡(M)\operatorname{rank}(\mathbf{M}) the rank of Mandby\mathbf{M} and by|\mathbf{M}|_{0}$ its number of nonzero entries. Given a set S⊆[n]S \subseteq[n], we write 1S∈{0,1}n\mathbf{1}_{S} \in\{0,1\}^{n} for its indicator vector and ∣S∣|S| its cardinality. For an optimisation problem over a vector x\mathbf{x}, we denote an optimal solution by x∗\mathbf{x}^{*}. Throughout the paper, for a given integer-weighted directed graph, nn denotes the number of nodes, EE denotes set of edges and A∈Zn×n\mathbf{A} \in\mathbb{Z}^{n \times n} denotes an integer-weighted adjacency matrix. We write decompositions of the form

A=L0+R0,(1)\mathbf{A} = \mathbf{L}_{0} + \mathbf{R}_{0}, \tag*{(1)}

where L0\mathbf{L}_{0} is the structured component and R0\mathbf{R}_{0} is the residual. We use the notation L0\mathbf{L}_{0} 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 rank⁡(L0)≪n\operatorname{rank}(\mathbf{L}_{0}) \ll n and ∥R0∥0≪n2\|\mathbf{R}_{0}\|_{0} \ll n^{2}.

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 ℓ1\ell_{1} norm.

Robust principal component analysis. RPCA is a canonical sparse plus low-rank model. Given an observed matrix A\mathbf{A}, RPCA seeks a decomposition (1) by solving the convex optimisation problem

min⁡L0,R0∥L0∥∗+λ∥R0∥1subject toA=L0+R0,(2)\min_{\mathbf{L}_{0},\mathbf{R}_{0}} \|\mathbf{L}_{0}\|_{*} + \lambda\|\mathbf{R}_{0}\|_{1} \quad\text{subject to} \quad\mathbf{A} = \mathbf{L}_{0} + \mathbf{R}_{0}, \tag*{(2)}

where λ>0\lambda> 0 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-KK formulation estimates sparse vectors V1,…,VK\mathbf{V}_{1}, \ldots, \mathbf{V}_{K} through

min⁡U,V∥A−UVT∥F2+λ∑k=1K∥Vk∥1,subject to suitable normalization constraints.(3)\min_{\mathbf{U},\mathbf{V}} \|\mathbf{A} - \mathbf{U}\mathbf{V}^{\mathsf{T}}\|_{\mathrm{F}}^{2} + \lambda\sum_{k=1}^{K} \|\mathbf{V}_{k}\|_{1}, \quad\text{subject to suitable normalization constraints}. \tag*{(3)}

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 R0\mathbf{R}_{0} 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 A∈Zn×n\mathbf{A} \in\mathbb{Z}^{n \times n} be a directed integer-weighted adjacency matrix. For each component tt, let St,Tt⊆[n]S_t, T_t \subseteq[n] denote source and target node sets, and let αt∈{−1,+1}\alpha_t \in\{-1,+1\} denote its sign. We write wt=1St\mathbf{w}_t = \mathbf{1}_{S_t}, qt=1Tt\mathbf{q}_t = \mathbf{1}_{T_t}, where wt,qt∈{0,1}n\mathbf{w}_t, \mathbf{q}_t \in\{0,1\}^n are binary indicator vectors. A signed biclique is the rank-one integer matrix αtwtqtT\alpha_t \mathbf{w}_t \mathbf{q}_t^\mathsf{T}. Given KK components, SBD writes

A=L0(K)+R0(K)=∑t=0K−1αtwtqtT+R0(K).(4)\mathbf{A} = \mathbf{L}_0^{(K)} + \mathbf{R}_0^{(K)} = \sum_{t=0}^{K-1} \alpha_t \mathbf{w}_t \mathbf{q}_t^\mathsf{T} + \mathbf{R}_0^{(K)}. \tag*{(4)}

Since each biclique is rank one, rank⁡(L0(K))≤K\operatorname{rank}(\mathbf{L}_0^{(K)}) \le K. The decomposition has two goals. First, the biclique component L0(K)\mathbf{L}_0^{(K)} should capture the dominant structure of A\mathbf{A}, leaving a small residual R0(K)\mathbf{R}_0^{(K)}, i.e., ∥R0(K)∥F2≪∥A∥F2\lVert\mathbf{R}_0^{(K)} \rVert_F^2 \ll\lVert\mathbf{A} \rVert_F^2. Second, the representation should be compact. We encode each component by its supports and its sign, giving a storage cost of ∣St∣+∣Tt∣+1\lvert S_t\rvert+ \lvert T_t\rvert+ 1. The residual is stored sparsely. This motivates the cost ∑t=0K−1(∣St∣+∣Tt∣+1)+∥R0(K)∥0\sum_{t=0}^{K-1}(\lvert S_t\rvert+ \lvert T_t\rvert+ 1) + \lVert\mathbf{R}_0^{(K)} \rVert_0, and the corresponding compression factor

CF=∥A∥0∑t=0K−1(∣St∣+∣Tt∣+1)+∥R0(K)∥0.(5)\mathrm{CF} = \frac{\lVert\mathbf{A}\rVert_0}{\sum_{t=0}^{K-1}(\lvert S_t\rvert+ \lvert T_t\rvert+ 1) + \lVert\mathbf{R}_0^{(K)}\rVert_0}. \tag*{(5)}

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 KK, we search for an SBD as the following discrete regularized optimisation problem.

Fixed-rank signed biclique approximation. Given λ≥0\lambda\ge0 and K∈NK \in\mathbb{N}, solve

min⁡wt,qt∈{0,1}nαt∈{−1,+1} ∥A−∑t=0K−1αtwtqtT∥F2+λ∑t=0K−1(∥wt∥22+∥qt∥22).(6)\underset{\substack{\mathbf{w}_t,\mathbf{q}_t \in\{0,1\}^n\\ \alpha_t \in\{-1,+1\}}}{\min}\ \left\lVert\mathbf{A} - \sum_{t=0}^{K-1}\alpha_t \mathbf{w}_t\mathbf{q}_t^\mathsf{T}\right\rVert_F^2 + \lambda\sum_{t=0}^{K-1}\left(\lVert\mathbf{w}_t\rVert_2^2 + \lVert\mathbf{q}_t\rVert_2^2\right). \tag*{(6)}

The first term controls reconstruction error:

∥A−L0(K)∥F2=∥R0(K)∥F2.\left\lVert\mathbf{A} - \mathbf{L}_0^{(K)}\right\rVert_F^2 = \left\lVert\mathbf{R}_0^{(K)}\right\rVert_F^2.

The second term controls the length of the biclique component. Indeed, since wt\mathbf{w}_t and qt\mathbf{q}_t are binary, ∥wt∥22=∣St∣\lVert\mathbf{w}_t\rVert_2^2 = \lvert S_t\rvert and ∥qt∥22=∣Tt∣\lVert\mathbf{q}_t\rVert_2^2 = \lvert T_t\rvert. Thus, λ\lambda trades off reconstruction accuracy against biclique size. Small values of λ\lambda 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 A\mathbf{A} and all signed bicliques are integer-valued, the residual R0(K)\mathbf{R}_0^{(K)} is integer-valued. Therefore, ∥R0(K)∥0≤∥R0(K)∥F2\lVert\mathbf{R}_0^{(K)}\rVert_0 \le\lVert\mathbf{R}_0^{(K)}\rVert_F^2, 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 KK 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 R0(0)=A\mathbf{R}_0^{(0)} = \mathbf{A}. At iteration tt, the next component is chosen by solving the rank-one problem

(αt⋆,wt⋆,qt⋆)=arg⁡min⁡w,q∈{0,1}nα∈{−1,+1} ∥R0(t)−αwqT∥F2+λ(∥w∥22+∥q∥22).(7)(\alpha_t^\star,\mathbf{w}_t^\star,\mathbf{q}_t^\star) = \underset{\substack{\mathbf{w},\mathbf{q}\in\{0,1\}^n\\ \alpha\in\{-1,+1\}}}{\arg\min}\ \left\lVert\mathbf{R}_0^{(t)}-\alpha\mathbf{w}\mathbf{q}^\mathsf{T}\right\rVert_F^2 + \lambda\left(\lVert\mathbf{w}\rVert_2^2+\lVert\mathbf{q}\rVert_2^2\right). \tag*{(7)}

The residual is then updated as R0(t+1)=R0(t)−αt⋆wt⋆(qt)⊤\mathbf{R}_0^{(t+1)}=\mathbf{R}_0^{(t)}-\alpha_t^\star\mathbf{w}_t^\star(\mathbf{q}_t)^\top. 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:

Gλ(α,S,T,R0)=2α∑(i,j)∈S×TR0(i,j)−∣S∣∣T∣−λ(∣S∣+∣T∣).(8)G_\lambda(\alpha,S,T,\mathbf{R}_0)=2\alpha\sum_{(i,j)\in S\times T}R_0(i,j)-|S||T|-\lambda(|S|+|T|). \tag*{(8)}

Note that minimizing (7) is equivalent to maximizing GλG_\lambda.

Theorem 1. Let λ≥0\lambda\geq0. Start with R0(0)=A\mathbf{R}_0^{(0)}=\mathbf{A}. At each accepted step update R0(t+1)=R0(t)−αt1St1Tt⊤\mathbf{R}_0^{(t+1)}=\mathbf{R}_0^{(t)}-\alpha_t\mathbf{1}_{S_t}\mathbf{1}_{T_t}^{\top}, where Gt=Gλ(αt,St,Tt,R0(t))>0G_t=G_\lambda(\alpha_t,S_t,T_t,\mathbf{R}_0^{(t)})>0. Then:

  1. Residual decrease. Each step satisfies

∥R0(t+1)∥F2=∥R0(t)∥F2−Gt−λ(∣St∣+∣Tt∣).(9)\lVert\mathbf{R}_0^{(t+1)}\rVert_F^2=\lVert\mathbf{R}_0^{(t)}\rVert_F^2-G_t-\lambda(|S_t|+|T_t|). \tag*{(9)}

There are at most K≤∥A∥F2K\leq\lVert\mathbf{A}\rVert_F^2 steps. If λ>0\lambda>0, also K≤⌊∥A∥F2/(2λ)⌋K\leq\left\lfloor\lVert\mathbf{A}\rVert_F^2/(2\lambda)\right\rfloor.

  1. Constraints at stopping. Suppose that stopping certifies Gλ≤0G_\lambda\leq0 for every candidate in a set CKC_K, evaluated on the final residual. For each (α,S,T)∈CK(\alpha,S,T)\in C_K,

αdR0(K)(S,T)≤12+λ2(1∣S∣+1∣T∣),(10)\alpha d_{\mathbf{R}_0^{(K)}}(S,T)\leq\frac{1}{2}+\frac{\lambda}{2}\left(\frac{1}{|S|}+\frac{1}{|T|}\right), \tag*{(10)}

where dR(S,T)=∑i∈S,j∈TR(i,j)∣S∣∣T∣d_{\mathbf{R}}(S,T)=\frac{\sum_{i\in S,j\in T}R(i,j)}{|S||T|}. If both signs were checked for the same supports, this also bounds ∣dR0(K)(S,T)∣\lvert d_{\mathbf{R}_0^{(K)}}(S,T)\rvert.

  1. Compression bound. Define Jt=∥R0(t)∥F2+λ∑ℓ<t(∣Sℓ∣+∣Tℓ∣)J_t=\lVert\mathbf{R}_0^{(t)}\rVert_F^2+\lambda\sum_{\ell<t}(|S_\ell|+|T_\ell|). Jt+1=Jt−GtJ_{t+1}=J_t-G_t and JtJ_t is non increasing. For λ≥1\lambda\geq1,

CF≥∥A∥0JK+K.(11)\mathrm{CF}\geq\frac{\lVert\mathbf{A}\rVert_0}{J_K+K}. \tag*{(11)}

Also, Jt+tJ_t+t is non increasing for λ∈N∗\lambda\in\mathbb{N}^*. 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 ∣R0(K)(i,j)∣≤⌊(1+2λ)/2⌋\lvert R_0^{(K)}(i,j)\rvert\leq\lfloor(1+2\lambda)/2\rfloor for all i,ji,j. Thus R0(K)=0\mathbf{R}_0^{(K)}=0 for λ<1/2\lambda<1/2, and its entries have magnitude at most one for λ∈[1/2,3/2)\lambda\in[1/2,3/2).

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 dmin⁡d_{\min}, the update is

T←{j∈V:2α∑i∈SR0(i,j)>max⁡(∣S∣+λ,2dmin⁡∣S∣)}.T\leftarrow\left\{j\in V:2\alpha\sum_{i\in S}R_0(i,j)>\max(|S|+\lambda,2d_{\min}|S|)\right\}.

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 (kk-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 kk decomposition steps, defining w=(w0,…,wk−1)\mathbf{w}=(w_0,\ldots,w_{k-1}), Λ=diag⁡(α0,…,αk−1)\Lambda=\operatorname{diag}(\alpha_0,\ldots,\alpha_{k-1}), q=(q0,…,qk−1)\mathbf{q}=(q_0,\ldots,q_{k-1}), we obtain

A=∑t=0k−1αtwtqtT+R0(k)=wΛqT+R0(k).\mathbf{A}=\sum_{t=0}^{k-1}\alpha_t\mathbf{w}_t\mathbf{q}_t^{\mathsf{T}}+\mathbf{R}_0^{(k)} =\mathbf{w}\Lambda\mathbf{q}^{\mathsf{T}}+\mathbf{R}_0^{(k)}.

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: A\mathbf{A}, λ\lambda, dmin⁡d_{\min}, seed budget MM per sign, AO cap JJ, extraction cap Kmax⁡K_{\max}

  1. R0←A\mathbf{R}_0 \leftarrow\mathbf{A}

  2. repeat

  3. For each sign α\alpha, take up to MM rows ranked by ∑jmax⁡(αR0(i,j),0)\sum_j\max(\alpha R_0(i,j),0)

  4. for all signed seeds (u,α)(u,\alpha) in parallel do

  5. Form local candidate sets (U,V)(U,V) around uu; set S←{u}S\leftarrow\{u\}, T←VT\leftarrow V

  6. Alternate for at most JJ iterations

  7. Stop AO if both supports are unchanged or either is empty

  8. end for

  9. Select the nonempty candidate (α⋆,S⋆,T⋆)(\alpha^\star,S^\star,T^\star) with largest full gain

  10. if no candidate has positive gain then

  11. stop

  12. end if

  13. R0←R0−α⋆1S⋆1T⋆T\mathbf{R}_0\leftarrow\mathbf{R}_0-\alpha^\star\mathbf{1}_{S^\star}\mathbf{1}_{T^\star}^{\mathsf{T}}

  14. until at most Kmax⁡K_{\max} 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 (pin=1p_{\mathrm{in}}=1). We add inter-community edges with probability q∈{0.05,0.15,0.25,0.35}q\in\{0.05,0.15,0.25,0.35\}. We threshold LR\mathrm{LR} at 0.5 and measure F1\mathrm{F}_1 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 (L0=0L_0 = 0 and R0=AR_0 = A). 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 F∈{32,128,256}F \in\{32, 128, 256\} columns. Multiplication uses L0+R0=AL_0 + R_0 = A, 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 q≤0.15q \le0.15 and remains competitive as the inter-community noise increases. At q=0.25q = 0.25, 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.

Method0.050.150.250.35
Noisy input0.8080.5850.4570.375
Savalle1.0000.9890.8690.744
RPCA1.0001.0000.9990.707
Sparse SVD1.0000.9990.9700.749
Kanada1.0001.0001.0000.992
SBDGreedy (ours)1.0001.0000.9990.992

Table 1. SBM denoising F1 (↑\uparrow), K=10K = 10, N=200N = 200, pin=1p_{\mathrm{in}} = 1. 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 O(n2)O(n^2) 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

MethodCoraCiteSeerca-HepPhca-AstroPhCOLLAB
SBDGreedy5.995.59OOTOOTOOT
SBDFast0.0220.0260.350.6012.3
KanadaOOTOOTOOTOOMOOM
RPCA4.367.10OOTOOTOOM
Sparse SVD6.302.0855.0OOTOOM
SavalleOOTOOTOOTOOMOOM
DatasetNN∥A∥0\lVert A \rVert_0KKCFCRSBD\mathrm{CR}_{\mathrm{SBD}}CRCBM\mathrm{CR}_{\mathrm{CBM}}
Cora2,70810,5561811.050.991.06
PubMed19,71788,6481,6511.081.041.05
ca-HepPh12,008237,0102,4373.233.432.75
ca-AstroPh18,772396,16010,5192.152.701.73
coPapersDBLP540,48630,491,45886,8558.5710.35.98
coPapersCiteseer434,10232,073,44084,86211.314.49.91
COLLAB372,47424,572,15853,64610.912.211.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 6.37×6.37\times speedup at F=32F = 32 and remains above 3.8×3.8\times at F=128F = 128 and F=256F = 256. On coPapersCiteseer, SBD obtains 5.80×5.80\times speedup at F=32F = 32 and above 3.8×3.8\times 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 F∈{32,128,256}F \in\{32, 128, 256\} 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.

DatasetFFSputnikdgSPARSEGE-SpMMSBD_baseCBMSBD
Cora322.72±0.372.72 \pm0.371.25±0.161.25 \pm0.162.20±0.182.20 \pm0.181.70±0.281.70 \pm0.280.17±0.060.17 \pm0.061.45±0.191.45 \pm0.19
Cora1282.86±0.622.86 \pm0.621.41±0.121.41 \pm0.122.34±0.532.34 \pm0.531.75±0.401.75 \pm0.400.19±0.080.19 \pm0.081.64±0.261.64 \pm0.26
Cora2562.34±0.352.34 \pm0.351.21±0.041.21 \pm0.042.12±0.472.12 \pm0.471.49±0.211.49 \pm0.210.18±0.060.18 \pm0.061.49±0.201.49 \pm0.20
PubMed322.68±0.402.68 \pm0.401.43±0.131.43 \pm0.132.83±0.702.83 \pm0.701.83±0.301.83 \pm0.300.21±0.070.21 \pm0.071.68±0.311.68 \pm0.31
PubMed1281.84±0.261.84 \pm0.261.25±0.021.25 \pm0.021.80±0.251.80 \pm0.251.47±0.111.47 \pm0.110.25±0.100.25 \pm0.101.38±0.051.38 \pm0.05
PubMed2561.73±0.371.73 \pm0.371.17±0.101.17 \pm0.101.86±0.251.86 \pm0.251.39±0.021.39 \pm0.020.34±0.120.34 \pm0.121.34±0.061.34 \pm0.06
ca-HepPh322.21±0.292.21 \pm0.290.91±0.030.91 \pm0.031.72±0.361.72 \pm0.361.11±0.251.11 \pm0.250.19±0.060.19 \pm0.061.39±0.281.39 \pm0.28
ca-HepPh1281.70±0.161.70 \pm0.160.91±0.010.91 \pm0.011.20±0.161.20 \pm0.161.03±0.101.03 \pm0.100.23±0.050.23 \pm0.051.47±0.111.47 \pm0.11
ca-HepPh2561.60±0.091.60 \pm0.090.85±0.080.85 \pm0.081.24±0.141.24 \pm0.141.05±0.091.05 \pm0.090.31±0.060.31 \pm0.061.36±0.211.36 \pm0.21
ca-AstroPh322.00±0.192.00 \pm0.191.07±0.071.07 \pm0.071.77±0.281.77 \pm0.281.15±0.181.15 \pm0.180.23±0.070.23 \pm0.071.66±0.261.66 \pm0.26
ca-AstroPh1281.40±0.171.40 \pm0.171.02±0.031.02 \pm0.031.24±0.231.24 \pm0.231.11±0.171.11 \pm0.170.29±0.060.29 \pm0.061.37±0.161.37 \pm0.16
ca-AstroPh2561.32±0.191.32 \pm0.190.85±0.130.85 \pm0.131.28±0.251.28 \pm0.250.94±0.070.94 \pm0.070.44±0.070.44 \pm0.071.32±0.371.32 \pm0.37
coPapersDBLP321.56±0.431.56 \pm0.431.70±0.181.70 \pm0.182.13±0.042.13 \pm0.041.76±0.041.76 \pm0.041.89±0.321.89 \pm0.325.03±0.675.03 \pm0.67
coPapersDBLP1280.92±0.340.92 \pm0.341.07±0.041.07 \pm0.041.73±0.151.73 \pm0.151.68±0.231.68 \pm0.231.42±0.301.42 \pm0.303.23±0.943.23 \pm0.94
coPapersDBLP2560.92±0.340.92 \pm0.340.95±0.060.95 \pm0.061.72±0.161.72 \pm0.161.45±0.231.45 \pm0.231.50±0.311.50 \pm0.313.21±0.963.21 \pm0.96
coPapersCiteseer322.11±0.372.11 \pm0.371.79±0.251.79 \pm0.252.12±0.052.12 \pm0.051.78±0.071.78 \pm0.072.18±0.332.18 \pm0.335.80±0.745.80 \pm0.74
coPapersCiteseer1281.26±0.241.26 \pm0.241.03±0.051.03 \pm0.051.98±0.031.98 \pm0.032.15±0.062.15 \pm0.061.79±0.401.79 \pm0.403.92±1.193.92 \pm1.19
coPapersCiteseer2561.27±0.241.27 \pm0.240.92±0.090.92 \pm0.091.95±0.071.95 \pm0.072.09±0.082.09 \pm0.081.98±0.451.98 \pm0.453.89±1.193.89 \pm1.19
COLLAB322.21±0.272.21 \pm0.271.82±0.361.82 \pm0.362.09±0.062.09 \pm0.061.75±0.161.75 \pm0.162.60±0.342.60 \pm0.346.37±0.696.37 \pm0.69
COLLAB1281.26±0.291.26 \pm0.290.97±0.070.97 \pm0.071.91±0.051.91 \pm0.052.45±0.052.45 \pm0.051.86±0.391.86 \pm0.393.89±1.113.89 \pm1.11
COLLAB2561.27±0.281.27 \pm0.280.89±0.020.89 \pm0.021.91±0.031.91 \pm0.032.78±0.052.78 \pm0.052.02±0.452.02 \pm0.453.86±1.073.86 \pm1.07

Table 8. Mean ±\pm 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 F=32F = 32, it gives 1.75×1.75\times speedup compared with SBD’s 6.37×6.37\times, 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 KK bicliques, ordered by decreasing area. Increasing KK moves more of the graph from the sparse residual into the structured two-pass path, but the benefit depends on the feature dimension. At F=32F = 32, speedup continues to improve over a large range of KK: COLLAB reaches its best sampled speed using about 56% of the available bicliques, and coPapersCiteseer behaves similarly. At F=128F = 128 and F=256F = 256, 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 KK used on L40S, for F∈{32,128,256}F \in\{32, 128, 256\}. 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 6×6 \times 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 R=R0(t)R = R_{0}^{(t)} and B=αt1St1TtTB = \alpha_t \mathbf{1}_{S_t}\mathbf{1}_{T_t}^{\mathsf{T}}. Expanding the squared norm gives

∥R−B∥F2=∥R∥F2−2αt∑i∈St,j∈TtR(i,j)+∣St∣∣Tt∣.\lVert R-B\rVert_{F}^{2}=\lVert R\rVert_{F}^{2}-2\alpha_t\sum_{i\in S_t,j\in T_t}R(i,j)+\lvert S_t\rvert\lvert T_t\rvert.

Substituting the gain gives (9). Each accepted step strictly decreases the squared norm. This norm is a nonnegative integer, so there are at most ∥A∥F2\lVert A\rVert_{F}^{2} steps. For λ>0\lambda>0, nonempty supports give ∣St∣+∣Tt∣≥2\lvert S_t\rvert+\lvert T_t\rvert\ge2. Summing the decreases over K>0K>0 accepted steps yields

0≤∥R0(K)∥F2<∥A∥F2−2λK.(12)0\le\lVert R_{0}^{(K)}\rVert_{F}^{2}<\lVert A\rVert_{F}^{2}-2\lambda K. \tag*{(12)}

Hence K≤⌊∥A∥F2/(2λ)⌋K\le\left\lfloor\lVert A\rVert_{F}^{2}/(2\lambda)\right\rfloor. The bound also holds for K=0K=0.

(2) Constraints at stopping. Let R=R0(K)R=R_{0}^{(K)}. A nonempty candidate (α,S,T)∈CK(\alpha,S,T)\in C_K satisfies

2α∑i∈S,j∈TR(i,j)−∣S∣∣T∣−λ(∣S∣+∣T∣)≤0.2\alpha\sum_{i\in S,j\in T}R(i,j)-\lvert S\rvert\lvert T\rvert-\lambda(\lvert S\rvert+\lvert T\rvert)\le0.

Dividing by 2∣S∣∣T∣2\lvert S\rvert\lvert T\rvert gives (10). Checking both signs on the same supports bounds ∣dR(S,T)∣\lvert d_R(S,T)\rvert. The bound covers only candidates checked on this final residual.

(3) Compression factor. Every nonzero integer has squared magnitude at least one. Thus

∥R0(K)∥0≤∥R0(K)∥F2.(13)\lVert R_{0}^{(K)}\rVert_{0}\le\lVert R_{0}^{(K)}\rVert_{F}^{2}. \tag*{(13)}

For λ≥1\lambda\ge1, the representation cost satisfies

CK=∥R0(K)∥0+∑t<K(∣St∣+∣Tt∣)+K≤∥R0(K)∥F2+λ∑t<K(∣St∣+∣Tt∣)+K=JK+K.\begin{aligned} C_K&=\lVert R_{0}^{(K)}\rVert_{0}+\sum_{t<K}(\lvert S_t\rvert+\lvert T_t\rvert)+K\\ &\le\lVert R_{0}^{(K)}\rVert_{F}^{2}+\lambda\sum_{t<K}(\lvert S_t\rvert+\lvert T_t\rvert)+K=J_K+K. \end{aligned}

Since A≠0A\ne0, dividing ∥A∥0\lVert A\rVert_{0} by these costs gives (11). Equation (9) also gives Jt+1=Jt−GtJ_{t+1}=J_t-G_t. Hence

(Jt+1+t+1)−(Jt+t)=1−Gt.(J_{t+1}+t+1)-(J_t+t)=1-G_t.

For positive integer λ\lambda, an accepted gain is an integer with Gt≥1G_t\ge1. The right-hand side is nonpositive, so the lower bound on CFC_F does not decrease. □\square

Proof of Corollary 1. The certificate checks both signs on every singleton. Choose the sign of a nonzero R(i,j)R(i,j), where R=R0(K)R=R_{0}^{(K)}. Its gain satisfies

2∣R(i,j)∣−1−2λ≤0.2\lvert R(i,j)\rvert-1-2\lambda\le0.

Since the residual is integer-valued, ∣R(i,j)∣≤⌊(1+2λ)/2⌋\lvert R(i,j)\rvert\le\lfloor(1+2\lambda)/2\rfloor. Zero entries also satisfy this bound. It is zero for λ<1/2\lambda<1/2 and one for λ∈[1/2,3/2)\lambda\in[1/2,3/2). □\square

Theoretical analysis

Additional Analysis on SBD Objective

Expansion of the greedy SBD objective. Expanding the Frobenius norm in (7) and using the fact that ∥wtqt⊤∥F2=∥wt∥F2∥qt∥F2=∣St∣∣Tt∣\lVert w_tq_t^{\top}\rVert_F^2=\lVert w_t\rVert_F^2\lVert q_t\rVert_F^2=|S_t||T_t| for binary vectors, the minimization reduces to the following (dropping the constant ∥R0(t)∥F2\lVert R_0^{(t)}\rVert_F^2):

min⁡St,Ttαt∈{−1,+1}∣St∣∣Tt∣−2αt∑(i,j)∈St×TtR0(t)(i,j)+λ(∣St∣+∣Tt∣).(14)\min_{\substack{S_t,T_t\\ \alpha_t\in\{-1,+1\}}} |S_t||T_t|-2\alpha_t\sum_{(i,j)\in S_t\times T_t}R_0^{(t)}(i,j)+\lambda\left(|S_t|+|T_t|\right). \tag*{(14)}

Recall that we define the block density of a matrix M\mathbf{M} on S×TS\times T as:

dM(S,T)=1∣S∣∣T∣∑(i,j)∈S×TM(i,j).(15)d_{\mathbf{M}}(S,T)=\frac{1}{|S||T|}\sum_{(i,j)\in S\times T}\mathbf{M}(i,j). \tag*{(15)}

Substitution of the residual. Substituting R0(t)=A−∑i=0t−1αi∗wi∗qi∗⊤R_0^{(t)}=\mathbf{A}-\sum_{i=0}^{t-1}\alpha_i^*\mathbf{w}_i^*\mathbf{q}_i^{*\top} into (14) and using (15) yields:

min⁡St,Ttαt∈{−1,+1}∣St∣∣Tt∣(1−2αtdA(St,Tt))+2∑i=0t−1(αtαi∗)(wt⊤wi∗)(qt⊤qi∗)+λ(∣St∣+∣Tt∣).(16)\min_{\substack{S_t,T_t\\ \alpha_t\in\{-1,+1\}}}|S_t||T_t|\left(1-2\alpha_t d_{\mathbf{A}}(S_t,T_t)\right)+2\sum_{i=0}^{t-1}(\alpha_t\alpha_i^*)\left(\mathbf{w}_t^\top\mathbf{w}_i^*\right)\left(\mathbf{q}_t^\top\mathbf{q}_i^*\right)+\lambda\left(|S_t|+|T_t|\right). \tag*{(16)}

Since wt⊤wi∗=∣St∩Si∗∣\mathbf{w}_t^\top\mathbf{w}_i^*=|S_t\cap S_i^*| and qt⊤qi∗=∣Tt∩Ti∗∣\mathbf{q}_t^\top\mathbf{q}_i^*=|T_t\cap T_i^*| for binary vectors, the cross term satisfies:

∑i=0t−1(αtαi∗)(wt⊤wi∗)(qt⊤qi∗)=∣St∣∣Tt∣∑i=0t−1(αtαi∗)∣St∩Si∗∣∣St∣∣Tt∩Ti∗∣∣Tt∣.(17)\sum_{i=0}^{t-1}(\alpha_t\alpha_i^*)\left(\mathbf{w}_t^\top\mathbf{w}_i^*\right)\left(\mathbf{q}_t^\top\mathbf{q}_i^*\right)=|S_t||T_t|\sum_{i=0}^{t-1}(\alpha_t\alpha_i^*)\frac{|S_t\cap S_i^*|}{|S_t|}\frac{|T_t\cap T_i^*|}{|T_t|}. \tag*{(17)}

Factoring out ∣St∣∣Tt∣|S_t||T_t| from (16), the objective reduces to:

min⁡St,Ttαt∈{−1,+1}∣St∣∣Tt∣⋅C(St,Tt,αt).(18)\min_{\substack{S_t,T_t\\ \alpha_t\in\{-1,+1\}}}|S_t||T_t|\cdot C(S_t,T_t,\alpha_t). \tag*{(18)}

where:

C(St,Tt,αt)=1−2αtdA(St,Tt)+2∑i=0t−1(αtαi∗)∣St∩Si∗∣∣St∣∣Tt∩Ti∗∣∣Tt∣+λ∣St∣+λ∣Tt∣.(19)C(S_t,T_t,\alpha_t)=1-2\alpha_t d_{\mathbf{A}}(S_t,T_t)+2\sum_{i=0}^{t-1}(\alpha_t\alpha_i^*)\frac{|S_t\cap S_i^*|}{|S_t|}\frac{|T_t\cap T_i^*|}{|T_t|}+\frac{\lambda}{|S_t|}+\frac{\lambda}{|T_t|}. \tag*{(19)}

Interpretation of CC. The three terms in (19) have distinct roles:

  • Density reward −2αtdA(St,Tt)-2\alpha_t d_{\mathbf{A}}(S_t,T_t): rewards bicliques that are aligned with the block structure of A\mathbf{A}. For nonnegative A\mathbf{A}, this term favours αt=+1\alpha_t=+1 when the block density is positive. For signed input, it favours the sign of dA(St,Tt)d_{\mathbf{A}}(S_t,T_t).

  • Signed overlap penalty 2(αtαi∗)∣St∩Si∗∣∣St∣∣Tt∩Ti∗∣∣Tt∣2(\alpha_t\alpha_i^*)\frac{|S_t\cap S_i^*|}{|S_t|}\frac{|T_t\cap T_i^*|}{|T_t|}: acts as an implicit memory mechanism. Same-sign overlap (αtαi∗=+1)(\alpha_t\alpha_i^*=+1) raises CC, discouraging the algorithm from covering the same region twice with the same sign. Opposite-sign overlap (αtαi∗=−1)(\alpha_t\alpha_i^*=-1) lowers CC, encouraging self-correction via an opposite-sign biclique on a previously covered region.

  • Size penalty λ/∣St∣+λ/∣Tt∣\lambda/|S_t|+\lambda/|T_t|: tends to zero as both supports grow and equals 2λ2\lambda for a singleton, penalising small bicliques more strongly. The parameter λ\lambda directly controls this bias.

We denote overlap-corrected density as d~t(St,Tt)=dA(St,Tt)−∑i=0t−1αi∗∣St∩Si∗∣∣St∣∣Tt∩Ti∗∣∣Tt∣\tilde{d}_t(S_t,T_t)=d_A(S_t,T_t)-\sum_{i=0}^{t-1}\alpha_i^*\frac{|S_t\cap S_i^*|}{|S_t|}\frac{|T_t\cap T_i^*|}{|T_t|}.

C(St,Tt,αt)<0C(S_t,T_t,\alpha_t)<0 implies:

αtd~t(St,Tt)>12(1+λ∣St∣+λ∣Tt∣).(20)\alpha_t\tilde{d}_t(S_t,T_t)>\frac{1}{2}\left(1+\frac{\lambda}{|S_t|}+\frac{\lambda}{|T_t|}\right). \tag*{(20)}

Since the right-hand side is strictly positive, αt∗=sign⁡(d~t(St,Tt))\alpha_t^*=\operatorname{sign}(\tilde{d}_t(S_t,T_t)) and

∣d~t(St,Tt)∣>12(1+λ∣St∣+λ∣Tt∣).(21)\left|\tilde{d}_t(S_t,T_t)\right|>\frac{1}{2}\left(1+\frac{\lambda}{|S_t|}+\frac{\lambda}{|T_t|}\right). \tag*{(21)}

Acceptance requires the absolute residual density to exceed 12(1+λ/∣St∣+λ/∣Tt∣)\frac{1}{2}(1+\lambda/|S_t|+\lambda/|T_t|). Here d~t(St,Tt)=dR(t)(St,Tt)\tilde{d}_t(S_t,T_t)=d_{R^{(t)}}(S_t,T_t) is the current residual density. This has three consequences: (i) the threshold is at least 12\frac{1}{2}; for λ>0\lambda>0, it approaches 12\frac{1}{2} from above for large blocks and grows for small ones, so small blocks must be denser to be accepted; (ii) larger λ\lambda raises the threshold; in particular, when residual entries are bounded by 11 in magnitude (e.g. binary AA before any overlap), ∣St∣×∣Tt∣|S_t|\times|T_t| block can be extracted, even when fully dense, only if λ/∣St∣+λ/∣Tt∣<1\lambda/|S_t|+\lambda/|T_t|<1; (iii) same-sign past overlap reduces αtd~t\alpha_t\tilde{d}_t, requiring higher raw density dAd_A to justify revisiting an already-covered region.

Derivation of the AO closed-form update

Separability of the gain at fixed SS. Fix the sign α\alpha and the source set SS. Recall that the gain reads

Gλ(α,S,T,R0)=2∑j∈Tα∑i∈SR0(i,j)⏟cj(S,α)−∣S∣∣T∣−λ(∣S∣+∣T∣).(22)G_\lambda(\alpha,S,T,R_0)=2\sum_{j\in T}\underbrace{\alpha\sum_{i\in S}R_0(i,j)}_{c_j(S,\alpha)}-|S||T|-\lambda(|S|+|T|). \tag*{(22)}

where cj(S,α)=α∑i∈SR0(i,j)c_j(S,\alpha)=\alpha\sum_{i\in S}R_0(i,j). GλG_\lambda decomposes as

Gλ(α,S,T,R0)=∑j∈T(2cj(S)−∣S∣−λ)−λ∣S∣.(23)G_\lambda(\alpha,S,T,R_0)=\sum_{j\in T}\left(2c_j(S)-|S|-\lambda\right)-\lambda|S|. \tag*{(23)}

Each jj contributes independently: including jj in TT improves the gain if and only if

cj(S,α)∣S∣=1∣S∣∑i∈SαR0(i,j)>12+λ2∣S∣.(24)\frac{c_j(S,\alpha)}{|S|}=\frac{1}{|S|}\sum_{i\in S}\alpha R_0(i,j)>\frac{1}{2}+\frac{\lambda}{2|S|}. \tag*{(24)}

The optimal TT at fixed SS therefore consists exactly of all columns whose average connection to SS exceeds 12+λ2∣S∣\frac{1}{2}+\frac{\lambda}{2|S|}. Denoting this set by

T∗={j:cj(S)∣S∣>12+λ2∣S∣},(25)T^*=\left\{j:\frac{c_j(S)}{|S|}>\frac{1}{2}+\frac{\lambda}{2|S|}\right\}, \tag*{(25)}

we have

Gλ(α,S,T∗,R0)≥Gλ(α,S,T,R0)for any T.(26)G_\lambda(\alpha,S,T^*,R_0)\geq G_\lambda(\alpha,S,T,R_0)\quad\text{for any }T. \tag*{(26)}

Symmetrically, for fixed TT, the corresponding update S∗S^* satisfies

Gλ(α,S∗,T,R0)≥Gλ(α,S,T,R0)for any S.(27)G_\lambda(\alpha,S^*,T,R_0)\geq G_\lambda(\alpha,S,T,R_0)\quad\text{for any }S. \tag*{(27)}

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 dmin⁡d_{\min} (binary matrices). For a current residual R0∈{0,1}n×nR_0\in\{0,1\}^{n\times n} and sign α=+1\alpha=+1, entries (i,j)∈S×T(i,j)\in S\times T with R0(i,j)=0R_0(i,j)=0 are holes: subtracting 1S1TT\mathbf{1}_S\mathbf{1}_T^\mathsf{T} from R0R_0 sets them to −1-1, adding nonzero residual entries at those positions. The hole count equals exactly ∣S∣∣T∣(1−dR0(S,T))|S||T|(1-d_{R_0}(S,T)), so controlling dR0(S,T)d_{R_0}(S,T) directly limits holes.

We impose a per-node density floor: include jj only if cj(S,α)/∣S∣>dmin⁡c_j(S,\alpha)/|S|>d_{\min}. Combined with (24), this gives

2α∑i∈SR0(i,j)>max⁡(∣S∣+λ,  2dmin⁡∣S∣),(28)2\alpha\sum_{i\in S}R_0(i,j)>\max\left(|S|+\lambda,\;2d_{\min}|S|\right), \tag*{(28)}

Setting dmin⁡=0d_{\min}=0 recovers the pure half-step. Averaging gives αdR0(S,T)>dmin⁡\alpha d_{R_0}(S,T)>d_{\min} for a nonempty AO output. For a binary current residual and positive sign, this bounds holes by ∣S∣∣T∣(1−dmin⁡)|S||T|(1-d_{\min}).

Neighbourhood initialisation. Seeds are ranked separately by positive and negative residual. We take up to MM seeds per sign and orientation (row or column), giving at most 4M4M starts per extraction. Algorithm 1 shows the row-seed case.

For sign α\alpha, we expand the neighbourhood along entries with αR0(i,j)>0\alpha R_0(i,j)>0. 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 T0⊆VT_0 \subseteq V be the current nonempty column set and let d=∣T0∣d=|T_0|. For each row ii, define

ci(T0,α)=α∑j∈T0R(i,j).c_i(T_0,\alpha)=\alpha\sum_{j\in T_0}R(i,j).

The row update keeps ii whenever

2ci(T0,α)>hd,hd=max⁡{d+λ,2dmin⁡d}.2c_i(T_0,\alpha)>h_d,\qquad h_d=\max\{d+\lambda,2d_{\min}d\}.

Proposition 1 (Shared-neighborhood certificate). Assume that there is a nonempty set P⊆UP\subseteq U such that

ci(T0,α)≥cmin⁡for all i∈P,c_i(T_0,\alpha)\ge c_{\min}\qquad\text{for all }i\in P,

with

2cmin⁡>hd2c_{\min}>h_d

and

∣P∣(2cmin⁡−d−λ)>λd.|P|(2c_{\min}-d-\lambda)>\lambda d.

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 PP passes the update threshold. At fixed T0T_0, the gain can be written as

Gλ(α,S,T0,R)=∑i∈S(2ci(T0,α)−d−λ)−λd.G_\lambda(\alpha,S,T_0,R)=\sum_{i\in S}(2c_i(T_0,\alpha)-d-\lambda)-\lambda d.

Let S1S_1 be the row support returned by the update. Since every selected row has positive contribution,

Gλ(α,S1,T0,R)≥∑i∈P(2ci(T0,α)−d−λ)−λd≥∣P∣(2cmin⁡−d−λ)−λd>0.\begin{aligned} G_\lambda(\alpha,S_1,T_0,R)\ge\sum_{i\in P}(2c_i(T_0,\alpha)-d-\lambda)-\lambda d \\ &\ge|P|(2c_{\min}-d-\lambda)-\lambda d>0. \end{aligned}

Each later exact coordinate update maximizes the gain with the other support fixed. Hence the gain cannot decrease.

For the initialization T0=N(u)T_0=\mathcal{N}(u) and α=+1\alpha=+1,

ci(T0,+1)=∑j∈N(u)R(i,j).c_i(T_0,+1)=\sum_{j\in\mathcal{N}(u)}R(i,j).

For a binary residual, this is the number of neighbors shared by ii and the seed uu. A second certificate uses the clustering coefficient.

Proposition 2 (Clustering certificate). Let RR be the adjacency matrix of a simple undirected binary graph. Let uu have degree du>1d_u>1 and clustering coefficient CuC_u. Then the block

S=T=N(u)S=T=\mathcal{N}(u)

has positive gain for α=+1\alpha=+1 if and only if

Cu>du+2λ2(du−1).C_u>\frac{d_u+2\lambda}{2(d_u-1)}.

Proof. Let eue_u be the number of edges between the neighbors of uu. Then

2eu=Cudu(du−1).2e_u = C_u d_u(d_u - 1).

For S=T=N(u)S=T=\mathcal{N}(u),

Gλ(+1,S,T,R)=4eu−du2−2λdu.G_\lambda(+1,S,T,R)=4e_u-d_u^2-2\lambda d_u.

Thus Gλ>0G_\lambda>0 if and only if

Cu>du+2λ2(du−1).C_u>\frac{d_u+2\lambda}{2(d_u-1)}.

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 RR, a sign α\alpha, and scoped domains U,VU,V. Let (S⋆,T⋆)(S^\star,T^\star) be a positive-gain fixed point of the actual updates, including the density floor and tie rule. Let T0⊆VT_0\subseteq V be the nonempty initial column set and define

h0=max⁡{∣T0∣+λ,  2dmin⁡∣T0∣}.h_0=\max\{|T_0|+\lambda,\;2d_{\min}|T_0|\}.

Proposition 3 (Recovery of a fixed point). Assume

2ci(T0,α){>h0,i∈S⋆,≤h0,i∈U∖S⋆.2c_i(T_0,\alpha) \begin{cases} >h_0, & i\in S^\star,\\ \le h_0, & i\in U\setminus S^\star. \end{cases}

One row update followed by one column update recovers (S⋆,T⋆)(S^\star,T^\star).

Proof. The separation condition makes the first row update select exactly S⋆S^\star. Since the target is a fixed point, the next column update returns T⋆T^\star.

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 T0=N(u)T_0=\mathcal{N}(u), ci(T0,+1)c_i(T_0,+1) 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 SS returns no column in VV, then

αdR(S,{j})≤max⁡{12+λ2∣S∣,dmin⁡}for every j∈V.\alpha d_R(S,\{j\})\le\max\left\{\frac{1}{2}+\frac{\lambda}{2|S|},d_{\min}\right\} \quad\text{for every }j\in V.

This follows by reversing the update inequality and dividing by 2∣S∣2|S|. 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 λ=1\lambda= 1. The script evaluates the original binary graph, before scoping, with T0=N(u)T_0 = \mathcal{N}(u). Its local test uses hd=d+λh_d = d + \lambda, without an active density floor. These rates do not certify the candidates retained by the implemented search.

DatasetClustering (%)Shared neighbors (%)
Cora0.19.1
PubMed0.012.1
ca-HepPh22.543.7
ca-AstroPh30.257.0
coPapersDBLP78.091.6
coPapersCiteseer83.393.9
COLLAB84.396.5

Table 5. Percentage of nodes satisfying the clustering or shared-neighborhood positive-gain condition at λ=1\lambda= 1. 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 λ\lambda

We first derive the gain thresholds for several block shapes. We then measure how changing λ\lambda affects the residual and compression.

Threshold interpretation. Consider a single nonzero residual entry R0(t)(i,j)≠0\mathbf{R}_0^{(t)}(i,j) \ne0. For a singleton biclique St={i}S_t = \{i\}, Tt={j}T_t = \{j\}, the overlap-corrected density is the entry itself, d~t({i},{j})=R0(t)(i,j)\tilde{d}_t(\{i\},\{j\}) = \mathbf{R}_0^{(t)}(i,j), and the acceptance condition reads

∣R0(t)(i,j)∣>12(1+2λ),\left|\mathbf{R}_0^{(t)}(i,j)\right| > \frac{1}{2}(1+2\lambda),

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 ∣R0(t)(i,j)∣≥1\left|\mathbf{R}_0^{(t)}(i,j)\right| \ge1, so for λ<12\lambda< \frac{1}{2} every nonzero residual entry yields positive singleton gain. Exact recovery then requires the singleton stopping certificate of Corollary 1. For λ≥12\lambda\ge\frac{1}{2}, entries of magnitude 1 can no longer be removed by a singleton, and singleton corrections are never accepted on residuals with entries in {−1,0,1}\{-1, 0, 1\}.

Structure-dependent thresholds. The parameter λ\lambda controls which blocks have positive gain. Acceptance requires

∣d~t(St,Tt)∣>12(1+λ∣St∣+λ∣Tt∣).\left|\tilde{d}_t(S_t,T_t)\right| > \frac{1}{2}\left(1+\frac{\lambda}{|S_t|}+\frac{\lambda}{|T_t|}\right).

The threshold is at least 12\frac{1}{2} and increases with λ\lambda. When residual entries are bounded by 1 in magnitude (e.g. binary A before any overlap), we have ∣d~t∣≤1\left|\tilde{d}_t\right| \le1, so a block of shape ∣St∣×∣Tt∣|S_t| \times|T_t| can be extracted, even when fully dense, only if

λ∣St∣+λ∣Tt∣<1.\frac{\lambda}{|S_t|}+\frac{\lambda}{|T_t|} < 1.

We call this bound the extraction limit for the block shape. Equation (21) gives:

  • Singleton (∣St∣=∣Tt∣=1|S_t| = |T_t| = 1): threshold is ∣d~t∣>12(1+2λ)|\tilde{d}_t| > \frac{1}{2}(1+2\lambda); extraction limit λ<12\lambda< \frac{1}{2}.

  • Star (∣St∣=1|S_t| = 1, ∣Tt∣=k|T_t| = k): threshold is ∣d~t∣>12(1+λ+λ/k)|\tilde{d}_t| > \frac{1}{2}(1+\lambda+\lambda/k); extraction limit λ<kk+1\lambda< \frac{k}{k+1}. For large kk, the threshold approaches 12(1+λ)\frac{1}{2}(1+\lambda), below the singleton threshold, making wide stars easier to accept than singletons.

Structure∣St∣|S_t|∣Tt∣|T_t|Extraction limit (λ<\lambda<)
Singleton1112\frac{1}{2}
Star (k=5k = 5)1556\frac{5}{6}
2×22 \times2221
2×32 \times32365\frac{6}{5}

Table 6. Extraction limits for fully dense blocks when residual entries have magnitude at most one. Larger blocks allow higher λ\lambda.

  • 2×22 \times2 biclique (∣St∣=∣Tt∣=2|S_t| = |T_t| = 2): threshold is ∣d~t∣>12(1+λ)|\tilde{d}_t| > \frac{1}{2}(1 + \lambda); extraction limit λ<1\lambda< 1.

  • 2×32 \times3 biclique (∣St∣=2|S_t| = 2, ∣Tt∣=3|T_t| = 3): threshold is ∣d~t∣>12(1+5λ6)|\tilde{d}_t| > \frac{1}{2}(1 + \frac{5\lambda}{6}); extraction limit λ<65\lambda< \frac{6}{5}.

Effect on residual norm. For a fixed residual, increasing λ\lambda raises the acceptance threshold. The search path can change, so the final residual norm need not increase with λ\lambda.

  • λ<12\lambda< \frac{1}{2}: every nonzero integer entry gives positive singleton gain. A stopping certificate covering all signed singleton supports therefore gives R0(K)=0R_0^{(K)} = 0 by Corollary 1. A finite seed search or budget limit alone does not give this certificate.

  • λ∈[12,1)\lambda\in[\frac{1}{2}, 1): unit entries cannot be removed by singleton updates. When residual entries have magnitude at most one, a star with kk leaves requires λ<k/(k+1)\lambda< k/(k + 1). Larger dense blocks may still be accepted. The singleton stopping certificate implies ∣R0(K)(i,j)∣≤1|R_0^{(K)}(i,j)| \leq1.

  • λ≥1\lambda\geq1: when residual entries have magnitude at most one, stars and 2×22 \times2 blocks are rejected, and acceptance requires 1/∣St∣+1/∣Tt∣<1/λ1/|S_t| + 1/|T_t| < 1/\lambda. 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 ∥R0(K)∥F/∥A∥F\lVert R_0^{(K)}\rVert_F/\lVert A\rVert_F and compression factor CF as a function of λ\lambda. Dashed vertical lines mark λ=12\lambda= \frac{1}{2} (unit-singleton threshold) and λ=1\lambda= 1 (the range where the storage bound applies).

Figure 5. Normalised residual ∥R(K)∥F/∥A∥F\lVert R^{(K)} \rVert_F / \lVert A \rVert_F (top row) and compression factor CFK\mathrm{CF}_K (bottom row) as a function of the number of extracted bicliques KK, for five values of λ\lambda. (a) Les Misérables (N=77N = 77). (b) SBM (K=10K = 10, N=200N = 200). Dashed horizontal line in bottom row: CF=1\mathrm{CF} = 1 (break-even point). On the SBM, λ∈{1.0,1.5}\lambda\in\{1.0, 1.5\} converge after exactly 10 bicliques in this run. At the plotted λ=0.3\lambda= 0.3, the residual reaches zero in both graphs. For small λ\lambda, CF declines at large KK 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 λ∈{0,0.5,1,2,4}\lambda\in\{0, 0.5, 1, 2, 4\}.

For each method, we report the number of extracted bicliques KK, 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 A=L0+R0\mathbf{A} = \mathbf{L}_0 + \mathbf{R}_0 where L0\mathbf{L}_0 is a real-valued low-rank matrix and R0\mathbf{R}_0 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 λ\lambda varies. We report the number of bicliques KK, 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.

λ\lambdaRank-one MIQP KKRank-one MIQP CFRank-one MIQP ∥R0∥F\lVert R_0\rVert_FSBDGreedy KKSBDGreedy CFSBDGreedy ∥R0∥F\lVert R_0\rVert_FSBDFast KKSBDFast CFSBDFast ∥R0∥F\lVert R_0\rVert_F
Karate
0.0330.790.00300.880.00330.632.00
0.5240.942.45240.942.45240.963.61
1.091.177.4881.177.8791.187.35
2.001.0012.501.0012.501.0012.5
4.001.0012.501.0012.501.0012.5
Les Misérables
0.0881.030.00881.030.00730.965.57
0.5431.336.93451.286.71501.238.12
1.0121.5613.5121.5413.7161.4613.8
2.041.5016.241.4916.341.4017.1
4.011.1820.111.1820.111.1520.4
Dolphins
0.0860.69†0.69^{\dagger}0.00890.690.00790.625.29
0.5620.81†0.81^{\dagger}5.39610.805.57580.827.48
1.0141.0913.6101.0914.4161.0713.4
2.001.0017.801.0017.801.0017.8
4.001.0017.801.0017.801.0017.8

Table 7.

SVD factors and community supports. For an isolated loopless clique of size BB, the leading eigenvalue is B−1B-1. Its scaled factor is (B−1)/B 1Sk\sqrt{(B-1)/B}\,\mathbf{1}_{S_k}. 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-KK symmetric factors σk uk\sqrt{\sigma_k}\,u_k of an SBM adjacency matrix (K=10K=10, N=200N=200, pin=1.0p_{\mathrm{in}}=1.0, pout=0.1p_{\mathrm{out}}=0.1), nodes sorted by ground-truth community (red lines = block boundaries). An isolated loopless clique has scaled factor (B−1)/B 1Sk\sqrt{(B-1)/B}\,\mathbf{1}_{S_k}; 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 L0SparseSVD=∑kσkukvkTL^{\mathrm{SparseSVD}}_0=\sum_k \sigma_k u_k v_k^{\mathsf{T}} is a sum of sparse real-valued outer products, entries take arbitrary values in R\mathbb{R}, not in {0,1}\{0,1\}. We verify this even in the most favorable case: SBM with K=10K=10, N=200N=200, pin=1.0p_{\mathrm{in}}=1.0, pout=0.1p_{\mathrm{out}}=0.1, SparseSVD rank set to the true KK, λ=0.1\lambda=0.1. Even here, 75.6% of entries of L0SparseSVDL^{\mathrm{SparseSVD}}_0 exceed 0.05 in magnitude, compared to the original graph’s 18.5% nonzeros (Figure 7).

Figure 7. Distribution of L0SparseSVDL_0^{\mathrm{SparseSVD}} entries for SBM (K=10K = 10, N=200N = 200, pin=1.0p_{\mathrm{in}} = 1.0, pout=0.1p_{\mathrm{out}} = 0.1), SparseSVD rank is 10, λ=0.1\lambda= 0.1.

Scalability. On sparse graphs, each matrix-vector product costs O(E)O(E). 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 6.37×6.37\times at F=32F = 32, 3.89×3.89\times at F=128F = 128, and 3.86×3.86\times at F=256F = 256 (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 F=32F = 32, 1,722 at F=128F = 128, and 308 at F=256F = 256. Adding more blocks can slow down SpMM. These are measurements for the plotted configuration, not universal thresholds across GPUs. At F=32F = 32, eight lanes per warp load the eight float4 feature groups. At F=128F = 128, 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 λ≥0\lambda\ge0, there are at most ∥A∥F2\lVert A\rVert_F^2 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 pin=1p_{\mathrm{in}} = 1. The noise levels are q∈{0.05,0.15,0.25,0.35}q \in\{0.05, 0.15, 0.25, 0.35\}.

Search spaces. SBDGreedy searches λ∈[0.5,20]\lambda\in[0.5, 20] log-uniformly, dmin⁡∈[0.5,1]d_{\min} \in[0.5, 1] uniformly, and an integer step cap in {5,…,100}\{5, \ldots, 100\}. It uses 200 seeds and eight threads. RPCA, Kanada, and sparse SVD search χ∈[10−3,1]\chi\in[10^{-3}, 1] uniformly. Sparse SVD fixes rank 10. Each search uses 30 trials. Savalle uses one 30-trial search with τ∈[10−3,20]\tau\in[10^{-3}, 20] log-uniformly and γ∈[10−3,1]\gamma\in[10^{-3}, 1] uniformly.

Denoising solver defaults. RPCA uses 1,000 iterations and tolerance 10−710^{-7}. Kanada uses 1,000 iterations and tolerance 10−610^{-6}. Sparse SVD uses 100 power iterations per component and tolerance 10−510^{-5}. Kanada uses ADMM penalty ρ=5\rho= 5. Sparse SVD uses random initial vectors. Savalle uses 1,000 iterations for tuning and up to 5,000 for evaluation, with tolerance 10−610^{-6}. A failed convergence check gets one retry at fixed ρ=16\rho= 16.

SBDGreedy uses up to eight scoping rounds and 20 AO rounds per start. These caps, the seed and thread counts are fixed.

Parameterq=0.05q = 0.05q=0.15q = 0.15q=0.25q = 0.25q=0.35q = 0.35
SBD λ\lambda4.554.556.818.15
SBD dmin⁡d_{\min}0.580.580.510.58
SBD step cap19199883
RPCA λ\lambda0.120.060.060.06
Kanada λ\lambda0.120.120.060.06
Sparse SVD λ\lambda0.310.410.500.75
Savalle τ\tau3.816.577.557.57
Savalle γ\gamma0.210.070.080.09

Table 9. Selected denoising parameters for Table 1.

Decomposition runtime

Fixed settings. Both methods use λ=0.5\lambda= 0.5 and eight threads. SBDGreedy uses at most 2n2n extractions, 64 seeds per sign and orientation, and dmin⁡=0d_{\min} = 0. SBDFast uses a nominal seed budget of 2n2n, 32 local starts, batches of 32 seeds, one signed sweep, and dmin⁡=0.7d_{\min} = 0.7. Kanada uses λ=0.5\lambda= 0.5. RPCA uses 1/n1/\sqrt{n}. Both allow up to 5,000 iterations. Sparse SVD extracts up to nn components, with λ=0.1\lambda= 0.1 and up to 100 iterations per component. Savalle uses the float64 symmetry-based ADMM solver, with τ=γ=0.1\tau= \gamma= 0.1, up to 5,000 iterations, and adaptive penalty starting at ρ=1\rho= 1. If it does not converge, it retries with fixed ρ=16\rho= 16 under the same total time limit. All continuous solvers use a tolerance of 10−610^{-6} 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 λ∈[0.5,4]\lambda\in[0.5, 4] log-uniformly and dmin⁡∈[0.5,1]d_{\min} \in[0.5, 1] 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 α=0\alpha= 0.

Datasetλ\lambdadmin⁡d_{\min}
Cora1.310.53
PubMed1.310.53
ca-HepPh1.230.50
ca-AstroPh1.190.63
coPapersDBLP1.510.67
coPapersCiteseer1.110.74
COLLAB1.350.70

Table 10. Parameters recorded in the selected decomposition caches used for Table 3 and SpMM.

Compression accounting

Entry-count model. Let s=∑k∣Sk∣s = \sum_k |S_k|, t=∑k∣Tk∣t = \sum_k |T_k|, and r=∥R0∥0r = \lVert R_0 \rVert_0. CF counts one unit per membership, sign, and residual entry:

CF=∥A∥0s+t+K+r.\mathrm{CF} = \frac{\lVert A \rVert_0}{s + t + K + r}.

CF does not depend on integer width and excludes pointer arrays.

Kernel storage. The input CSR uses BA=4(N+1)+8∥A∥0B_A = 4(N + 1) + 8\lVert A \rVert_0 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 N+1N + 1. The column-factor pointers have length K+1K + 1. Thus

BSBD=4(2N+K+3)+4(s+t)+8r+K,CRSBD=BA/BSBD.B_{\mathrm{SBD}} = 4(2N + K + 3) + 4(s + t) + 8r + K,\qquad\mathrm{CR}_{\mathrm{SBD}} = B_A/B_{\mathrm{SBD}}.

These counts exclude features, outputs, temporary buffers, and allocator overhead.

CBM storage. We retain the authors’ accounting: BCBM=4(N+1)+8d+8eB_{\mathrm{CBM}} = 4(N + 1) + 8d + 8e, where dd counts delta entries and ee 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 α=0\alpha= 0.

SpMM and block-prefix measurements

We evaluate F∈{32,128,256}F \in\{32, 128, 256\} with float32 features. The kernel scripts do not sweep decomposition parameters or kernel configurations. CBM uses α=0\alpha= 0. 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 KK and FF 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, dmin⁡=0d_{\min} = 0, and eight threads. We use 64 seeds on Les Misérables and 200 on the SBM. The summary evaluates 36 values of λ\lambda between 0.05 and 2.5. The trajectories use λ∈{0.3,0.6,0.8,1,1.5}\lambda\in\{0.3, 0.6, 0.8, 1, 1.5\}.

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 K×FK \times F.

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 ∑kαkwkqk⊤X\sum_k \alpha_k w_k q_k^\top X in two passes. The first pass (QTX) assigns one warp per biclique and computes zk=∑j∈qkX[j]z_k = \sum_{j \in q_k} X[j]. The second pass (WSZ_RX) assigns one warp per output row and computes

∑k:i∈wkαkzk+∑jRijX[j].\sum_{k:i \in w_k} \alpha_k z_k + \sum_j R_{ij}X[j].

The intermediate column sum zkz_k is computed once and reused by every row in wkw_k. 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.

GPUVRAML2 CacheHost CPU
NVIDIA RTX 309024 GB6MBIntel Xeon Silver 4116
NVIDIA A4048 GB6MBIntel Xeon Silver 4210
NVIDIA L40S48 GB96MBAMD 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. [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. [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. [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. [4]Melanie Beckerleg and Andrew Thompson. A divide-and-conquer algorithm for binary matrix completion. Linear Algebra and its Applications (LAA), 2020.DOI
  5. [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. [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. [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. [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. [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. [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. [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. [12]Alan Frieze and Ravindran Kannan. Quick approximation to matrices and applications. Combinatorica, 1999.DOI
  13. [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. [14]Robert Geisberger, Peter Sanders, and Dominik Schultes. Better approximation of betweenness centrality. In Workshop on Algorithm Engineering and Experiments (ALENEX), 2008.
  15. [15]R. L. Graham and H. O. Pollak. On the addressing problem for loop switching. The Bell System Technical Journal (BSTJ), 1971.DOI
  16. [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. [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. [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. [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. [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. [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. [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. [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. [24]Yike Liu, Tara Safavi, Abhilash Dighe, and Danai Kout ra. Graph summarization methods and applications: A survey. ACM Computing Surveys (CSUR), 2018.
  25. [25]S.G. Mallat and Zhifeng Zhang. Matching pursuits with time-frequency dictionaries. IEEE Transactions on Signal Processing (TSP), 1993.DOI
  26. [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. [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. [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. [29]Ankit Parekh and Ivan W. Selesnick. Improved sparse low-rank matrix estimation. Signal Processing, 2017.DOI
  30. [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. [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. [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. [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. [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. [35]Hui Zou, Trevor Hastie, and Robert Tibshirani. Sparse principal component analysis. Journal of Computational and Graphical Statistics (JCGS), 2006.

Paper details

vlnc:W_aygedy79
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents