Borrowing Microarray Biclustering to Scale Coded Delivery Under Arbitrary Cache Placement

Coded caching lets a server answer many users at once. If each user already stores pieces of files that other users want, the server can send one combined packet, formed by bitwise XOR of several pieces, and each user cancels out what it already holds. The theory behind this assumes a centralized placement: the server decides in advance exactly what every cache stores. Real caches are not filled that way. They fill up through local eviction rules and each user's own browsing or viewing history. Once cache contents are arbitrary, choosing the cheapest set of XOR packets becomes a hard covering problem. The best method available for it is exponential in the number of users, and it has only been tested up to ten users.

We propose to find good XOR groups the way microarray analysts find groups of co-regulated genes. We treat the matrix of "which user holds which requested piece" like a gene-by-condition expression matrix. We then apply spectral biclustering, a method that exposes checkerboard blocks by normalizing away row and column effects and reading block structure off the singular vectors. Near-all-ones blocks in the cache matrix are almost exactly the groups of pieces that can share one XOR packet. The normalization step matters for a specific reason. In genes, it removes "housekeeping" brightness. In caches, it should remove the analogous nuisance effects: users with large caches, and pieces that nearly everyone stores. These are the effects that heterogeneous, uncoordinated placement introduces. Candidate blocks are then trimmed into valid groups and passed to a small size-aware set-cover step. We claim that this gives near-best delivery rates at user counts where exact and exponential methods cannot run.

Core Claim

Under arbitrary placement, delivery can be written as a covering problem, following Optimal Coded Multicast in Cache Networks with Arbitrary Content Placement and An Approximation Algorithm for Optimal Clique Cover Delivery in Coded Caching. Each requested-but-missing piece is a vertex, and a group of pieces forms a clique if every requester in the group holds all the other pieces. Covering all vertices with cliques costs, per clique, the size of its largest piece, because shorter pieces are zero-padded.

Those papers solve this with the Size-Aware Coded Multicast algorithm (SACM), a weighted set cover with a $(1+\log K)$ guarantee. Its running time is $O(\tau_K K 2^K)$, where $K$ is the number of users and $\tau_K$ is the largest number of pieces tied to any user. It was evaluated only for $K \le 10$. The expensive part is generating candidate cliques.

Our claim is that a clique has a precise matrix signature. Let $A \in \{0,1\}^{K \times |V|}$ have $A_{k,v}=1$ if user $k$ caches piece $v$ or is the requester of $v$. A clique $C$ is then a set of columns whose requester rows $R(C)$ make the submatrix $A_{R(C),C}$ all ones. Finding cliques is therefore finding all-ones biclusters. Spectral Biclustering of Microarray Data: Coclustering Genes and Conditions finds such blocks in polynomial time with the singular value decomposition, after bistochastizing the matrix, meaning rescaling rows and columns until all row sums and all column sums are constant (Sinkhorn's algorithm). That paper reports "perfect separation of disease types" on lymphoma data only when this normalization is applied, and not with raw SVD.

We predict that the same normalization is what makes the spectral approach work on caches. Without it, the leading singular vectors of $A$ would mostly reflect cache size, the row effect, and piece popularity, the column effect, rather than the interaction structure that defines cliques.

Research Program

The algorithm has four stages. First, build $A$ from the observed caches and demands, and weight each column by the log of its piece size. This makes blocks mixing very different sizes less coherent, which is the zero-padding penalty expressed in matrix form. Second, normalize $A$ with one of three schemes from Kluger et al.: independent row and column rescaling, bistochastization, or log-interaction removal. Then take the top singular vector pairs and cut them into step-like segments, which yields candidate blocks.

Third, trim each block into valid cliques. Within a block, we greedily drop the column whose requester misses the most other columns until the clique condition holds. Each clique is also split by size bin, so that padding is bounded by a constant factor.

Fourth, solve the weighted set cover of Asghari et al.,

$$\min \sum_{c \in \mathcal{C}} w(c)\,x_c \quad \text{s.t.} \quad \sum_{c \ni v} x_c \ge 1\ \ \forall v \in V,$$

where $\mathcal{C}$ is our candidate pool plus all single pieces, $w(c)$ is the largest piece size in clique $c$, and $x_c \in \{0,1\}$ selects cliques. Including single pieces guarantees a feasible solution that is never worse than uncoded delivery. Because $|\mathcal{C}|$ is polynomial rather than exponential, the cover can be solved by greedy methods or an off-the-shelf integer solver.

The analysis half of the project asks when spectral candidates provably contain near-optimal cliques. The natural starting point is random placement. There, Decentralized Caching and Coded Delivery With Distinct Cache Capacities shows that the pieces cached by exactly a given subset of users concentrate by the law of large numbers. Under that model, $A$ is a structured random matrix, and bistochastization should cancel its heterogeneous row and column scales, the users' cache capacities and the file lengths. We aim for a statement of the form: if cache contents follow such a scaled model, the normalized top singular vectors recover the group structure with error that decays as files grow. This rate follows from concentration of the random matrix around its expected block structure.

Two other papers constrain the design. Decentralized Caching under Nonuniform File Popularity and Size: Memory-Rate Tradeoff Characterization and Fundamental Structure of Optimal Cache Placement for Coded Caching With Nonuniform Demands establish that skewed popularity and unequal sizes are the normal case rather than an edge case. This is precisely where the normalization step should matter.

The microarray literature supplies the method here, not the workload. We do not claim that genomic data should be delivered this way. The research file lists that as an open gap, but it has no delivery benchmark or trace to evaluate against.

Baselines

The naive reference point is uncoded delivery, which sends every missing piece separately. It anchors the rate axis, and our set cover is guaranteed never to exceed it.

The strongest existing competitor is SACM with its subfile-based optimizer, from An Approximation Algorithm for Optimal Clique Cover Delivery in Coded Caching. For 10 users, that paper reports up to a 72% bandwidth reduction over uncoded delivery and a 15% to 45% reduction relative to Graph Coloring Coded Multicast (GCCM). The companion paper, Optimal Coded Multicast in Cache Networks with Arbitrary Content Placement, reports 16% to 57% relative to Greedy Coded Multicast (GCM), and SACM exactly matched the optimum at $K=3$. We reimplement SACM and run it on identical placement instances, on the same hardware, with a common wall-clock cap. At $K \le 10$, beating it means matching its transmitted bits within a few percent at a fraction of the runtime. Above the size where SACM finishes within the cap, the comparison shifts to GCCM and GCM, which are its polynomial-time predecessors, and to exact integer programs on small instances. The research file contains no reported SACM result for $K>10$, so no number on Lacuna exists for that regime.

GCCM and GCM are size-blind colorings and greedy covers. They are the realistic scalable competitors, and they are run on the same instances.

Where placement follows the random fractional model, the Group-Based Decentralized scheme (GBD) of Amiri et al. gives a closed-form rate with reported gains of up to 34.43% over prior decentralized schemes. It serves as a structured reference to check that our method loses little when placement is not truly arbitrary.

Two ablations isolate the key ingredient. The first removes the normalization and runs raw SVD on $A$. The second replaces spectral candidates with an equal number of random or greedily grown cliques fed to the same set cover. Only if both ablations lose does the biclustering transfer earn its place.

Why not just…?

Why not just run SACM, or an integer solver, and accept the cost? Up to about ten users this is exactly right, and we treat SACM as ground truth there. The $2^K$ term in its complexity rules it out at 30 to 100 users, which is the size of a realistic cell or edge cluster. Our runtime-versus-$K$ experiment measures where it stops finishing. If SACM with a truncated candidate search stays competitive at large $K$, that result undercuts our proposal, and we will report it.

Why not just use a size-aware greedy cover with cheap candidates, or column generation on the linear relaxation? This is the real threat. A linear-programming relaxation that adds new cliques as it goes needs, at each step, a maximum-weight clique subproblem. That subproblem is itself NP-hard but often fast in practice, so it may match us. We include column generation with a time cap and a greedy grown-clique pool of equal size as competitors. If either ties the spectral pool on rate and runtime, we will conclude that the biclustering idea adds nothing beyond candidate diversity, and redirect the work toward the normalization insight alone.

Why not just apply ordinary spectral clustering to the conflict graph? Clustering the graph groups vertices, but it ignores the asymmetric "requester row inside the block" structure and the row and column scale effects. Kluger et al. found that unnormalized SVD and normalized cuts fail on expression data for exactly this kind of reason. The raw-SVD ablation and a normalized-cuts variant test whether the same failure appears here.

Proposed Experiments

First, we reproduce the arbitrary-placement simulator of Asghari et al.: $K \in \{3,6,8,10\}$, 100 random placements, and uniformly random piece sizes. We report total transmitted bits and runtime against SACM, GCCM, GCM, uncoded delivery, and the exact integer program at $K \le 6$.

Second, we scale to $K \in \{20, 50, 100\}$ under three placement regimes. The first is random fractional placement with heterogeneous capacities, the setting where GBD applies. The second is Zipf-distributed demand histories filled by LRU or LFU eviction, the kind of policies Ditto adapts online in Ditto: An Elastic and Adaptive Memory-Disaggregated Caching System; these produce genuinely arbitrary, correlated caches. The third regime uses heavy-tailed piece sizes.

Two checks are decisive. The method should come within 5% of SACM's bits at $K=10$. At $K=50$, it should beat the best of GCCM and GCM by a clear margin, with runtime growing polynomially in $K$. We also make a prediction that can falsify the analogy: the advantage of bistochastization over raw SVD should grow with capacity heterogeneity and popularity skew, and vanish under uniform centralized-style placement. If the gap does not track heterogeneity, the claimed reason for the method working is wrong, even if the method's rates look good.