arXiv CSopen access

Balanced Co-Clustering of Users and Items for Embedding Table Compression in Recommender Systems

2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

machine learning, deep learning, neural networks

Balanced Co-Clustering of Users and Items for Embedding Table Compression in Recommender Systems Technical Report Runhao Jiang

Renchi Yang∗

Donghao Wu†

Hong Kong Baptist University Hong Kong SAR, China [email protected]

The Chinese University of Hong Kong Shenzhen, China [email protected]

arXiv:2604.18351v1 [cs.IR] 20 Apr 2026

Abstract

ACM Reference Format: Runhao Jiang, Renchi Yang, and Donghao Wu. 2018. Balanced Co-Clustering of Users and Items for Embedding Table Compression in Recommender Systems: Technical Report. In . ACM, New York, NY, USA, 14 pages. https: //doi.org/XXXXXXX.XXXXXXX

Recommender systems have advanced markedly over the past decade by transforming each user/item into a dense embedding vector with deep learning models. At industrial scale, embedding tables constituted by such vectors of all users/items demand a vast amount of parameters and impose heavy compute and memory overhead during training and inference, hindering model deployment under resource constraints. Existing solutions towards embedding compression either suffer from severely compromised recommendation accuracy or incur considerable computational costs. To mitigate these issues, this paper presents BACO, a fast and effective framework for compressing embedding tables. Unlike traditional ID hashing, BACO is built on the idea of exploiting collaborative signals in user-item interactions for user and item groupings, such that similar users/items share the same embeddings in the codebook. Specifically, we formulate a balanced co-clustering objective that maximizes intra-cluster connectivity while enforcing cluster-volume balance, and unify canonical graph clustering techniques into the framework through rigorous theoretical analyses. To produce effective groupings while averting codebook collapse, BACO instantiates this framework with a principled weighting scheme for users and items, an efficient label propagation solver, as well as secondary user clusters. Our extensive experiments comparing BACO against full models and 18 baselines over benchmark datasets demonstrate that BACO cuts embedding parameters by over 75% with a drop of at most 1.85% in recall, while surpassing the strongest baselines by being up to 346× faster.

Introduction

In modern recommender systems, deep learning models [68] have become the go-to approach for recommendations, typically working with embedding tables that map each category feature value, e.g., the ID of a user or item, to a unique vector representation. However, in industrial-scale scenarios, these embedding tables consume a vast amount of parameters, often reaching hundreds of GB or even TB, due to the need to represent billions of users/items [18]. For instance, embedding tables deployed in Baidu’s advertising systems may occupy up to 10 TB of storage [60], while at Meta’s scale, i.e., 3 billion monthly active users worldwide [19], the user embedding table in a recommender model can easily reach 715 GB of space for 64-dimensional vectors in 32-bit floating point. As a consequence, the expansion of embedding tables intensifies storage and hardware demands, thus impeding model scalability and deployment in real production environments [9, 66]. In recent years, embedding table compression (ETC) [31], which seeks to reduce the sizes of embedding tables with minimal degradation in precision, has emerged as a popular choice in industry [7, 49, 56, 57] and is gaining increasing traction in recommender systems [6, 9, 66]. Most existing works towards ETC generally follow three compression paradigms: pre-training, in-training, and post-training compressions, where the former generates the mappings for users/items in embedding tables before training recommendation models, while the latter two strategies compress the full embeddings when they are partially or fully learned. Despite being effective, the in-training/post-training scheme additionally introduces considerable training overhead, and still suffers from substantial memory footprint. A common treatment for pre-training ETC is to hash the user/item IDs down to a set of buckets with a manageable size through hashing functions [9, 16, 54, 66]. The users/items mapped to the same bucket will share the same embedding vectors in the reduced embedding tables (a.k.a. codebooks). Although this methodology is computationally efficient, it relies on hashing that is essentially random, which will represent unrelated users/items by the same embeddings, and hence, engendering severe embedding collisions and performance degradation [16, 66]. Subsequent studies alleviate embedding collision issues through the (i) employment of multiple hash functions [41, 66], (ii) incorporation of feature and frequency

CCS Concepts • Information systems → Clustering; Recommender systems; • Mathematics of computing → Graph algorithms.

Keywords Recommender Systems, Embedding Table Compression, Co-clustering ∗ Corresponding Author † Work done while an intern at HKBU

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. Conference’17, Washington, DC, USA © 2018 ACM. ACM ISBN 978-1-4503-XXXX-X/18/06 https://doi.org/XXXXXXX.XXXXXXX 1

Conference’17, July 2017, Washington, DC, USA

Runhao Jiang, Renchi Yang, & Donghao Wu

statistics [9, 16, 67], and (iii) learned hashing techniques [34, 49]. These methods either still incur subpar recommendation performance, or require additional user/item information or training costs. Most importantly, the collaborative signals underlying the useritem interactions are largely overlooked for ETC. Very recently, Wu et al. [56] made an attempt to exploit the collaborative information of users/items by reframing the ETC task as a graph clustering problem. They simply apply the highly-efficient Louvain algorithm [5] over the user-item interaction graph to derive clusters of users/items as their buckets, which surprisingly yield remarkable improvements in recommendation quality. Unfortunately, Louvain suffers from an inherent drawback of resolution limit [27], leading to suboptimal results. Inspired by the efficacy of leveraging collaborative signals, we make further inroads by presenting BACO, a fast and effective solution for ETC via BAlanced CO-clustering. Specifically, we first reveal two factors, i.e., intra-cluster connectivity and cluster-size balance, that are crucial to clustering for ETC, through an empirical study, which in essence correspond to the embedding collision and codebook collapse [49], respectively. Based thereon, we develop a theoretically-grounded balanced co-clustering framework aiming at optimizing these two factors, and establish its theoretical connections to classic graph clustering algorithms. Building on the framework, we propose a well-thought-out hybrid weighting scheme (HWS) for users and items, and develop a fast optimization solver through local greedy label propagation [38] to circumvent the resolution limit. To account for the multiple and evolving interests of users, BACO further constructs secondary clusters for users (SCU) rapidly based upon the primary clusters, thereby overcoming the representation limitation of each user without inducing additional space overhead. Our comprehensive empirical evaluations and ablation studies manifest that (i) our BACO can consistently achieve markedly superior recommendation quality over 18 ETC baselines, while often being highly efficient, and (ii) our proposed HWS and SCU strategies can conspicuously enhance recommendation accuracies even when working with other clustering baselines.

embeddings. Furthermore, xLightFM [23] proposes allocating various numbers of embeddings to different feature categories. Within multi-codebook frameworks, LightRec [32] and LISA [58] aim to differentiate codebooks using distinct mechanisms. In contrast to earlier methods that focus on low-dimensional dense embeddings, recent work CompresSAE [26] introduces a radically different strategy by converting original embeddings into high-dimensional but sparse representations, combining expressive capacity with compression. Vector quantization introduces significant computational and memory overhead during training, primarily due to the nearest neighbor search and the requirement to retain original embeddings. Decomposition-based Methods. Decomposition methods perform soft selection, where each feature aggregates all codebook embeddings using a real-valued index vector. DHE [25] decomposes the embedding table via hash functions and neural networks, whereas ANT [33] uses anchor vectors and sparse transformation. Recently, tensor train decomposition (TTD) has been employed to enhance compression by expressing multidimensional data as a product of smaller tensors [53, 59, 65]. However, achieving such high compression ratios entails additional computational costs during decomposition and lookup, potentially slowing down inference.

3 Preliminaries 3.1 Symbols and Terminology Symbols. We model the interactions between a user set U = {𝑢 1, 𝑢 2, . . . , 𝑢 | U | } and an item set V = {𝑣 1, 𝑣 2, . . . , 𝑣 | V | } as a bipartite network G = (U ∪ V, E), where the edge set E ⊆ U × V consists of all the user-item interactions. The neighbors of user 𝑢𝑖 (resp. item 𝑣 𝑗 ) are represented by N (𝑢𝑖 ) (resp. N (𝑣 𝑗 )). We denote by B ∈ {0, 1} | U | × | V | the bi-adjacency matrix of G, where B𝑖,𝑗 = 1 if user 𝑢𝑖 has interacted with item 𝑣 𝑗 , i.e., (𝑢𝑖 , 𝑣 𝑗 ) ∈ E, and 0 otherwise. B 0 We use A = B⊤ 0 ∈ {0, 1} ( | U |+| V | ) × ( | U |+| V | ) to represent the complete adjacency matrix of G. The degree of user 𝑢𝑖 (resp. item 𝑣 𝑗 ) is symbolized by 𝑑 (𝑢𝑖 ) (resp. 𝑑 (𝑣 𝑗 )) and the diagonal degree matrix is denoted by D ∈ R ( | U |+| V | ) × ( | U |+| V | ) . Throughout this paper, we use u ®𝑖 (resp. v® 𝑗 ) to denote the embedding vector of user 𝑢𝑖 (item 𝑣 𝑗 ). For notation convenience, U ∈ R | U | ×𝑑 and V ∈ R | V | ×𝑑 represent the embedding vectors of users in U and items in V, respectively, wherein the 𝑖-th row of U (resp. V) is U𝑖 = u ®𝑖 (resp. V𝑖 = v®𝑖 ). In recommender systems, U and V are often referred to as embedding tables of users and items, respectively. Given a cluster C𝑘 containing users and items, we define U𝑘 = C𝑘 ∩ U and V𝑘 = C𝑘 ∩ V. We use [𝐾] to denote the set of integers {1, 2, . . . , 𝐾 }. Table 1 lists frequently used notions in our paper.

Related Work

We review existing studies on ETC in the sequel and defer reviews on co-clustering and bipartite graph clustering to Appendix B. Hashing-based Methods. Hashing methods offer a straightforward and efficient means of compressing embedding tables by mapping IDs into a smaller index space using hash functions. For instance, the basic hashing method [54] simply employs random function to achieve compression. Although efficient, this approach may introduce collisions. [67] increases the probability that colliding objects are similar through LSH, while [41, 66] employ double hashing combined with other techniques to mitigate collisions. In contrast, ROBE [11] employs a more flexible indexing mechanism within compositional embeddings. Although these hash methods are generally efficient, their weak association with the data makes it difficult to maintain accuracy.

Modularity and CPM. The modularity [36] quantifies the goodness of a particular division of a network. Formally, given a unipartite network G and clusters {C1, C2, . . . , !C𝐾 }, the modularity is Í 2 𝑣𝑖 ∈C𝑘 𝑑 (𝑣𝑖 ) 1 Í𝐾 defined by | E | 𝑘=1 𝑠𝑘 − 𝛾 · , where 𝛾 > 0 stands |E|

Vector Quantization. Vector quantization (VQ) maps original embeddings to their most similar meta-embeddings, thereby bridging hash representations and the original data [69]. Saec [57] and MGQE [24] utilize feature frequency to guide the quantization of

for a resolution parameter [39], and 𝑠𝑘 = |{(𝑣𝑖 , 𝑣 𝑗 ) ∈ E |𝑣𝑖 , 𝑣 𝑗 ∈ C𝑘 }| is the actual number of edges within cluster C𝑘 . Intuitively speakÍ 2 ing, 𝑣𝑖 ∈ C𝑘 𝑑 (𝑣𝑖 ) /|E | can be interpreted as the expected number 2

Balanced Co-Clustering of Users and Items for Embedding Table Compression in Recommender Systems

Table 1: Frequently used symbols. Symbol U, V, E |U|,|V |,|E |

𝑢𝑖 , 𝑣𝑖 G, B A D U, V u ®𝑖 , v® 𝑗 C𝑘 U𝑘 , V𝑘 [𝐾 ] Z (𝑢) , Z (𝑣) 𝐾 (𝑢) , 𝐾 (𝑣) Y (𝑢) , Y (𝑣) (𝑢) (𝑣) 𝑤𝑖 , 𝑤 𝑗 w ® 𝑊 (𝑢) ,𝑊 (𝑣) 𝛾

Frequency SCC

Random EBMD

Description The user set, item set and edge set. The number of users, items, and all the edges. A user in U , and a item in V . The bipartite network and its bi-adjacency matrix. The complete adjacency matrix of G . The diagonal degree matrix of A. The embedding tables of users and items. The embedding vector of user 𝑢𝑖 and item 𝑣 𝑗 . A cluster containing users and items. The user set and the item set of cluster C𝑘 . The set of integers {1, 2, . . . , 𝐾 } . The compressed embedding table for users and items. The numbers of clusters for users and items. The sketching matrices of users and items. The weights for user 𝑢𝑖 and item 𝑣 𝑗 . The vector containing the weights of users and items. The total weight of the users and items in G . The coefficients for objective term in Eq. (6)

Recall@20

GraphHash SBC

Recall@20 16

(a) #cross-cluster links

LP BACO

Recall@20

0.02 0.03 0.04 0.05

8 0 0.2 0.4 0.6 0.8 1

0 0.2 0.4 0.6 0.8 1

(b) Gini coefficient (users) (c) Gini coefficient (items)

Figure 1: Recommendation performance (Recall@20) v.s. averaged #cross-cluster links and Gini coefficients on Gowalla for mappings and codebooks. Given a space budget 𝐵 for the codebooks, i.e., the total number of embedding vectors in codebooks for users and items, the ETC task ensures 𝐾 (𝑢 ) + 𝐾 (𝑣) ≤ 𝐵. In model training, given a user 𝑢𝑖 (resp. item 𝑣 𝑗 ), the compressed embedding Z 𝑓(𝑢(𝑖) ) (resp. Zℎ(𝑣) ) is first retrieved before entering into (𝑗) training. For example, the predicted rating for user 𝑢𝑖 and item 𝑣 𝑗 is ⟩, and the loss function like LBPR = obtained as 𝑦ˆ𝑖,𝑗 = ⟨Z 𝑓(𝑢(𝑖) ) , Zℎ(𝑣) (𝑗) Í Í Í − 𝑢𝑖 ∈ U 𝑣𝑘 ∈ N (𝑢 ) 𝑣 𝑗 ∉N (𝑢 ) ln 𝜎 (𝑦ˆ𝑖,𝑘 − 𝑦ˆ𝑖,𝑗 ) + 𝜆 · ∥U∥ 2 + ∥V∥ 2 , is computed with U = Y (𝑢 ) Z (𝑢 ) and V = Y (𝑣) Z (𝑣) accordingly.

of edges in cluster C𝑘 . In particular, higher (resp. lower) resolutions lead to more (resp. fewer) communities, and a larger modularity value indicates a better partitioning of the network G. Barber [2] extended modularity to bipartite networks, formulating bipartite modularity as follows: (𝑢)

Conference’17, July 2017, Washington, DC, USA

(𝑣) !

𝐾 · 𝜎𝑘 𝜎 1 ∑︁ 𝑠𝑘 − 𝛾 · 𝑘 |E| |E|

3.3

(1)

Construction of Sketching Matrices

𝑘=1

There are generally three categories of approaches for constructing the sketching matrices Y (𝑢 ) and Y (𝑣) : random sketching, learned sketching, and clustering-based sketching. Random sketching simply employs hashing functions as mappings 𝑓 : U → [𝐾 (𝑢 ) ] and ℎ: V → [𝐾 (𝑣) ]. Each user or item is assigned to a random sketch (a random one-hot vector) [54]. Subsequent works [11, 41, 46, 66] resort to compositional embeddings, which basically apply two or more hashing functions to the IDs of users and items, such that each user or item is associated with two or more embeddings in the codebook, which can be combined via summation, element-wise multiplication, or concatenation, etc. Note that this approach yields denser sketching matrices as each row Y𝑖(𝑢 ) and Y (𝑣) 𝑗 comprise multiple non-zero entries. Instead of generating random sketches, the learned sketching [34, 49] methodology learn the sketch of each user or item by training models to reconstruct sketching matrices. After every few epochs, sketching matrices Y (𝑢 ) and Y (𝑣) are regenerated upon current embeddings Y (𝑢 ) Z (𝑢 ) and Y (𝑣) Z (𝑣) to achieve a better fit. By interpreting sketching matrices Y (𝑢 ) and Y (𝑣) as node-cluster (𝑢 ) indicator matrices, e.g., Y𝑖,𝑘 = 1 if 𝑢𝑖 belongs to the 𝑘-th user cluster and 0 otherwise, the rationale of clustering-based sketching is to group “similar” users in U and items in V into 𝐾 (𝑢 ) and 𝐾 (𝑣) clusters, respectively. GraphHash [56] implements this idea by clustering users and items over the bipartite network structure G, attaining markedly superior effectiveness over random sketching and significantly higher efficiency than learned sketching.

Í Í where 𝜎𝑘(𝑢 ) = 𝑢𝑖 ∈ U𝑘 𝑑 (𝑢𝑖 ) (resp. 𝜎𝑘(𝑣) = 𝑣𝑖 ∈ V𝑘 𝑑 (𝑣𝑖 )) denotes the sums of degrees of nodes in C𝑘 and set U (resp. V). An alternative quality function like the modularity is called the Constant Potts Model (CPM) [47], whose mathematical formula Í𝐾 𝑠𝑘 − 𝛾 · | C2𝑘 | , which can also be extended tion is defined by 𝑘=1 to bipartite networks by substituting |U𝑘 | · |V𝑘 | for | C2𝑘 | , i.e., Í𝐾 𝑘=1 (𝑠𝑘 − 𝛾 · |U𝑘 | · |V𝑘 |). In the literature [48], both quality functions can be efficiently and effectively optimized by the prominent Louvain algorithm invented by Blondel et al. [5].

3.2

Problem Statement

Let Z (𝑢 )

(𝑢)

(𝑣)

∈ R𝐾 ×𝑑 (resp. Z (𝑣) ∈ R𝐾 ×𝑑 ) be the codebook (a.k.a. compressed embedding table) for users (resp. items), where 𝐾 (𝑢 ) ≪ |U|, 𝐾 (𝑣) ≪ |V |, and each row vector stands for an embedding vector. The embedding table compression1 (ETC) in recommender systems aims to find a mapping 𝑓 : U → [𝐾 (𝑢 ) ] and a mapping ℎ: V → [𝐾 (𝑣) ] such that each user 𝑢𝑖 (resp. item 𝑣 𝑗 ) can be represented by an embedding vector Z 𝑓(𝑢(𝑖) ) (resp. Zℎ(𝑣) ). (𝑗) The foregoing mappings 𝑓 and ℎ can be equivalently repre(𝑢) sented by sketching matrices Y (𝑢 ) ∈ {0, 1} | U | ×𝐾 and Y (𝑣) ∈ (𝑣) (𝑢 ) (𝑣) | V | ×𝐾 {0, 1} , respectively. Each row Y𝑖 (resp. Y 𝑗 ) therein is a one-hot vector, usually called “sketch of user 𝑖 (resp. item 𝑣 𝑗 )” [49]. Accordingly, U = Y (𝑢 ) Z (𝑢 ) and V = Y (𝑣) Z (𝑣) . Notice that given sketching matrices Y (𝑢 ) and Y (𝑣) , recommendation models only need to learn codebook Z (𝑢 ) and Z (𝑣) in the course of training. As such, the space overhead originally incurred for storing the embedding tables U and V in the recommender systems is reduced from 𝑂 ((|U| + |V |) ·𝑑) to 𝑂 (|U| + |V | + (𝐾 (𝑢 ) + 𝐾 (𝑣) ) ·𝑑)

Empirical Study. To gain deeper insights, we empirically study the correlation between final recommendation performance and the characteristics of sketching matrices produced by various methods from the perspective of clustering. Specifically, we generate sketching matrices using hashing-based methods (Random and Frequency) and clustering-based methods (GraphHash, LP, EMBD, SCC, SBC, and

1We follow the “pre-training” compression setting for parameter efficiency [49].

Conference’17, July 2017, Washington, DC, USA

Runhao Jiang, Renchi Yang, & Donghao Wu

Table 2: The unified balanced co-clustering framework. Method

(𝑢)

(𝑣)

𝛾

𝑤𝑖

𝑤𝑗

Louvain (Modularity) [5]

𝑑 (𝑣 𝑗 )

𝑑 (𝑢𝑖 ) |E |

|E |

Louvain (CPM) Leiden (Modularity) [48]

>0 >0

𝑑 (𝑢𝑖 ) |E |

|E |

Leiden (CPM) [48] LP [38] LPAb [3]

>0 0 >0

1 𝑑 (𝑢𝑖 ) √

1 𝑑 (𝑣 𝑗 ) √

|E |

SCC [12] Our BACO

0 >0

𝑑 (𝑢𝑖 ) √

√

1 √

|E |

√

1 √

𝑑 (𝑣 𝑗 )

√1 |V |

that Y can be converted into Y (𝑢 ) and Y (𝑣) by mapping the clusters of users and items into consecutive column indices, respectively.

Opt. solver

Maximizing Intra-cluster Connectivity. The first objective in our BACO aims to identify clusters {C1, . . . , C𝐾 } such that the intracluster connectivity is maximized. More concretely, users and items that are densely connected via interactions in E should fall into the same clusters since it connotes a high correlation or similarity between users (resp. items). This leads to the maximization of the number of connections within the same clusters, i.e., intra-cluster connectivity, which can be formulated as follows:

Louvain Louvain Louvain Louvain LP LP Eigensolver BACO

𝐾 ∑︁ ∑︁

max C1 ,...,C𝐾

our proposed BACO) on the Gowalla dataset. Figure 1 plots the recall@20 scores (𝑦-axis) achieved by the above methods, and their respective average number of cross-cluster links and the Gini coefficients of their user and item cluster sizes (𝑥-axis). Particularly, fewer cross-cluster links connections suggest that related users/items are well grouped, implying rare embedding collisions. A low Gini coefficient signals that clusters are nearly equal in size, indicating codebook embeddings are used evenly across users or items (i.e., mild codebook collapse). From Figure 1(a), when inter-cluster connectivity is excessively high (see methods circled in red), recommendation performance suffers regardless of whether codebook usage (measured by the Gini coefficient) is uniform or uneven (Figures 1(b) and 1(c)). In contrast, LP generates clusters of users and items with a minimal number of cross-cluster links, but causes high Gini coefficients that indicate severe embedding collision and codebook collapse, and hence, result in poor recommendations. GraphHash and BACO obtain much better recall scores by balancing these two factors. From the foregoing observations, we can derive the following insight: the underlying clusters of high-quality sketching matrices should minimize intercluster connectivity while avoiding imbalanced cluster sizes.

(2)

The objective can be further transformed into a trace maximization problem with indicator matrix Y and adjacency matrix A of G:

max C1 ,...,C𝐾

𝐾 ∑︁ ∑︁

⇔ max

𝐾 ∑︁ ∑︁

B𝑖,𝑗 ⇔ max

C1 ,...,C𝐾

𝑘=1 𝑢𝑖 ,𝑣 𝑗 ∈ C𝑘

⇔ max

𝐾 ∑︁ ∑︁ ∑︁

A𝑖,| U |+𝑗

𝑘=1 𝑢𝑖 ,𝑣 𝑗 ∈ C𝑘

Y𝑖,𝑘 · A𝑖,| U |+𝑗 · Y | U |+𝑗,𝑘

𝑘=1 𝑢𝑖 ∈ U 𝑣 𝑗 ∈ V 𝐾 ∑︁

(Y⊤ AY)𝑘,𝑘 ⇔ max Trace(Y⊤ AY).

(3)

𝑘=1

Such an optimization task is equivalent to the mincut problem for graph partitioning in the literature [43], which is proved NP-hard. Weighted Exclusive Lasso for Size Balance. As remarked earlier in § 3.3, in overly imbalanced clusters, substantial users/items with low relevance are likely to be grouped together, which yields severe embedding collision and codebook collapse, and thus, degrades performance. As a remedy, in BACO, we additionally include a weighted exclusive lasso to balance the sizes/volumes of the 𝐾 clusters. Specifically, instead of treating all users and items equally, we assign a weight 𝑤𝑖(𝑢 ) (resp. 𝑤 𝑗(𝑣) ) to each user 𝑢𝑖 (item 𝑣 𝑗 ). Let Í Í 𝑊 (𝑢 ) = 𝑢𝑖 ∈ U 𝑤𝑖(𝑢 ) and 𝑊 (𝑣) = 𝑣 𝑗 ∈ V 𝑤 𝑗(𝑣) be the total weight of the users and items in G, respectively. Accordingly, we define the volume of a cluster C𝑘 as

Methodology

In this section, we first present our framework BACO for co-clustering users and items in § 4.1 and unify classic graph clustering algorithms into this framework through rigorous theoretical analyses in § 4.2. Building on this framework, we propose the hybrid weighting scheme (HWS) specialized for users and items in the context of e-commerce in § 4.3, followed by constructing co-clusters via an efficient optimization solver in § 4.4. Lastly, to alleviate the embedding collision and codebook collapse issues in co-clusters, § 4.5 introduces a simple but effective approach to create secondary clusters for users (SCU).

4.1

B𝑖,𝑗 .

𝑘=1 𝑢𝑖 ,𝑣 𝑗 ∈ C𝑘

∑︁

vol(𝐶𝑘 ) =

𝑢𝑖 ∈ U𝑘

∑︁

𝑤𝑖(𝑢 ) +

𝑤 𝑗(𝑣) ,

(4)

𝑣 𝑗 ∈ V𝑘

which is a summation of the weights of the users and items therein. Ideally, the volumes of all clusters should be comparable to each other, i.e., minimizing the weighted exclusive lasso:

The Balanced Co-Clustering Framework

We frame the construction of sketching matrices Y (𝑢 ) and Y (𝑣) as co-clustering users and items in G into 𝐾 disjoint co-clusters {C1, . . . , C𝐾 }. Particularly, we represent the node-cluster memberships by an indicator matrix Y ∈ {0, 1} ( | U |+| V | ) ×𝐾 , where Y𝑖,𝑘 = 1 if user 𝑢𝑖 ∈ C𝑘 , Y | U |+𝑗,𝑘 = 1 if item 𝑣 𝑗 ∈ C𝑘 , and 0 otherwise. Note

min

𝐾 ∑︁

vol(𝐶𝑘 ) −

𝐶 1 ,𝐶 2 ,...,𝐶𝐾

𝑊 (𝑢 ) + 𝑊 (𝑣) 𝐾

2 ⇔

min

∥w ® ⊤ Y∥ 22

𝐶 1 ,𝐶 2 ,...,𝐶𝐾

𝑘=1

⇔

min 𝐶 1 ,𝐶 2 ,...,𝐶𝐾

Trace(Y⊤ w ®w ® ⊤ Y).

(5)

Balanced Co-Clustering of Users and Items for Embedding Table Compression in Recommender Systems

where w ® ∈ R | U |+| V | is a vector containing the weights of users and items, e.g., w ® 𝑖 = 𝑤𝑖(𝑢 ) for user 𝑢𝑖 ∈ U and w ® | U |+𝑗 = 𝑤 𝑗(𝑣) for item 𝑣 𝑗 ∈ V.

Algorithm 1: The Basic BACO Algorithm Input: Bipartite graph G, space budget 𝐵, integer 𝑇 , and coefficient 𝛾 Output: Sketching matrices Y (𝑢 ) and Y (𝑣) /* Initializing labels of users and items */ 1 ℓ (𝑢𝑖 ) ← 𝑖 ∀𝑢𝑖 ∈ U and ℓ (𝑣 𝑗 ) ← |U| + 𝑗 ∀𝑣 𝑗 ∈ V; 2 𝑡 ← 0; /* Updating labels of users and items */ (𝑢 ) + 𝐾 (𝑣) > 𝐵 and 𝑡 < 𝑇 do 3 while 𝐾 4 for 𝑥𝑖 ∈ G do 5 L𝑖 ← {ℓ (𝑦 𝑗 )|𝑦 𝑗 ∈ N (𝑥𝑖 ) ∪ 𝑥𝑖 }; 6 for 𝑘 ∈ L𝑖 do 7 if 𝑥𝑖 ∈ U then 8 Compute 𝑝 (𝑘) according to Eq. (13);

Overall Objective. Combining the foregoing intra-cluster connectivity maximization (Eq. (3)) and weighted exclusive lasso minimization (Eq. (5)) leads to the overall objective of BACO: max Trace(Y⊤ AY) − 𝛾 · Trace(Y⊤ w ®w ® ⊤ Y),

(6)

where the coefficient 𝛾 can be used to strengthen the weight of the cluster size balance term.

4.2

Theoretical Insights

Next, we conduct a theoretical investigation of BACO framework, so as to (i) establish its connections to several classic clustering algorithms over bipartite graphs, and (ii) uncover its indirect impact on the downstream user and item embeddings U and V.

(Y⊤ AY)𝑘,𝑘 =

𝑘 ∈ L𝑖 12

B𝑖,𝑗 · 𝛿 (𝑢𝑖 , 𝑣 𝑗 ) =

𝑢𝑖 ∈ U 𝑣 𝑗 ∈ V

∑︁

/* Re-labeling users and items ℓ (𝑢 ) : {ℓ (𝑢𝑖 )|𝑢𝑖 ∈ U} → [𝐾 (𝑢 ) ]; (𝑢 ) (ℓ (𝑢 )) ∀𝑢 ∈ U; 14 𝑓 (𝑢𝑖 ) ← ℓ 𝑖 𝑖 (𝑣) 15 ℓ : {ℓ (𝑣 𝑗 )|𝑣 𝑗 ∈ V} → [𝐾 (𝑣) ]; (𝑣) (ℓ (𝑣 )) ∀𝑣 ∈ V; 16 ℎ(𝑣 𝑗 ) ← ℓ 𝑗 𝑗 /* Constructing sketching matrices (𝑢 ) 17 Y ← 1 ∀𝑢𝑖 ∈ U and Y (𝑣) ← 1 ∀𝑣 𝑗 ∈ V; 𝑖,𝑓 (𝑢 ) 𝑗,ℎ (𝑣 )

B𝑖,𝑗

B𝑖,𝑗 · 𝛿 (𝑢𝑖 , 𝑣 𝑗 ).

𝑖

𝑗

(8)

𝑢𝑖 ∈ U 𝑣 𝑗 ∈ N (𝑢𝑖 )

It can be observed that the key differences of these algorithms lie in the choices of parameter 𝛾, weights of users and items, as well as the solver used for optimization.

Analogously, the second term −𝛾 · Trace(Y⊤ w ®w ® ⊤ Y) is equal to ∑︁ ∑︁ −𝛾 · w ®𝑖 · w ® | U |+𝑗 · 𝛿 (𝑢𝑖 , 𝑣 𝑗 ).

Impact on User and Item Embeddings. The overall objecive in Eq. (9) can be rewritten as

𝑢𝑖 ∈ U 𝑣 𝑗 ∈ V

Along this line, our overall objective in Eq. (6) can be rewritten as ∑︁ ∑︁ max B𝑖,𝑗 − 𝛾 · 𝑤𝑖(𝑢 ) · 𝑤 𝑗(𝑣) · 𝛿 (𝑢𝑖 , 𝑣 𝑗 ). (9) Y

𝑡 ← 𝑡 + 1;

𝑘=1 𝑢𝑖 ,𝑣 𝑗 ∈ C𝑘

𝑘=1

∑︁ ∑︁

𝐾 ∑︁ ∑︁

ℓ (𝑥𝑖 ) ← arg max 𝑝 (𝑘);

The first intra-cluster connectivity term in Eq. (6) can be equivalently expressed by 𝐾 ∑︁

else Compute 𝑝 (𝑘) according to Eq. (14);

9 10

Connections to Other Clustering Methods. We define the Kronecker 𝛿 function as follows: ( 1 if 𝑢𝑖 , 𝑣 𝑗 ∈ C𝑘 , i.e., Y𝑖 = Y | U |+𝑗 , 𝛿 (𝑢𝑖 , 𝑣 𝑗 ) = (7) 0 otherwise.

Trace(Y⊤ AY) =

Conference’17, July 2017, Washington, DC, USA

max C1 ,...,C𝐾

𝑢𝑖 ∈ U 𝑣 𝑗 ∈ V

𝐾 ∑︁ ∑︁

∑︁

B𝑖,𝑗 − 𝛾 · 𝑤𝑖(𝑢 ) · 𝑤 𝑗(𝑣) .

𝑘=1 𝑢𝑖 ∈ U𝑘 𝑣 𝑗 ∈ V𝑘

From the perspective of each user 𝑢𝑖 , if we are given fixed item clusters {V1, . . . , V𝐾 }, 𝑢𝑖 is assigned to the user cluster U𝑘 when its total penalized interaction weight with items in V𝑘 is minimized, i.e., ∑︁ (10) 𝜅 (𝑢𝑖 ) = arg max B𝑖,𝑗 − 𝛾 · 𝑤𝑖(𝑢 ) · 𝑤 𝑗(𝑣) = 𝑘.

Together with the above formulation, we are enabled to unify existing clustering algorithms tailored to bipartite graphs including the modularity- and CPM-based Louvain [5] and Leiden [48], Label Propagation (LP) [38], Spectral Co-clustering (SCC) [12], and LPAb [3] into our BACO framework, as summarized in Table 2, based on their respective optimization functions theoretically analyzed in the following lemmata.

1≤ℓ ≤𝐾

𝑣 𝑗 ∈ Vℓ

Accordingly, users 𝑢𝑖 and 𝑢𝑙 are assigned to the same cluster U𝑘 if and only if 𝜅 (𝑢𝑖 ) = 𝜅 (𝑢𝑙 ) = 𝑘. Recall that in the resulting user and item embeddings U and V, users or items from the same clusters will share the same embedding vector in the codebook Z (𝑢 ) and Z (𝑣) (see § 3.2). The above Eq. (10) implies that users with similar interaction patterns with 𝐾 sets of items are likely to have the same embedding vectors. A similar conclusion can be made for item embeddings when the user clusters are fixed.

Lemma 4.1. Given bipartite graph G, the adoption of Louvain, Leiden, or LPAb over G can maximize the following form of the biÍ Í 𝑑 (𝑢 ) ·𝑑 (𝑣 ) partite modularity: 𝑢𝑖 ∈ U 𝑣 𝑗 ∈ V B𝑖,𝑗 − 𝛾 · 𝑖 | E | 𝑗 · 𝛿 (𝑢𝑖 , 𝑣 𝑗 ), Í Í or the following form of the CPM: 𝑢𝑖 ∈ U 𝑣 𝑗 ∈ V B𝑖,𝑗 − 𝛾 · 𝛿 (𝑢𝑖 , 𝑣 𝑗 ). Lemma 4.2. The optimization objective of both LP and SCC can be Í Í expressed as maxY 𝑢𝑖 ∈ U 𝑣 𝑗 ∈ V B𝑖,𝑗 · 𝛿 (𝑢𝑖 , 𝑣 𝑗 ). 5

Conference’17, July 2017, Washington, DC, USA

4.3

Runhao Jiang, Renchi Yang, & Donghao Wu

Hybrid Weighting Scheme

Algorithm 2: The Complete BACO Algorithm Input, output, and Lines 1-2 are the same as Algorithm 1 (𝑢 ) + 𝐾 (𝑣) > 𝐵 ′ and 𝑡 < 𝑇 do 3 while 𝐾 Lines 4-17 are the same as Algorithm 1; 18 Rerun Lines 4-10 in Algorithm 1 for each 𝑥𝑖 ∈ U; (𝑢 ) (𝑢 ) ]; 19 ℓscu : {ℓ (𝑢𝑖 )|𝑢𝑖 ∈ U} → [𝐾 (𝑢 ) 20 𝑓scu (𝑢𝑖 ) ← ℓscu (ℓ (𝑢𝑖 )) ∀𝑢𝑖 ∈ U; (𝑢 ) 21 Y ← 1 ∀𝑢𝑖 ∈ U; 𝑖,𝑓scu (𝑢 )

As pinpointed in Table 2, previous clustering methods unified into the BACO framework all adopt the same weighting functions for 𝑑 (𝑥 ) users and items in G, either a degree-related function √ used |E|

in the bipartite modularity or a constant (e.g., 1) used in the CPM. However, this simple strategy neglects the intrinsic distinction of users and items in the context of recommendation systems, and hence, causes flawed cluster assignments. More precisely, recall that in Eq. (10), user 𝑢𝑖 is assigned to clusÍ ter C𝑘 if 𝑣 𝑗 ∈ C𝑘 B𝑖,𝑗 − 𝛾 · 𝑤𝑖(𝑢 ) · 𝑤 𝑗(𝑣) is maximal. When the weight

𝑖

𝑑 (𝑣 )

𝑤 𝑗(𝑣) = √ 𝑗 is adopted for items, user 𝑢𝑖 will be prone to join

if 𝑥𝑖 is a user in U, and by ∑︁ 𝑝 (𝑘) ←

|E|

the cluster of its interacted items with low degrees (i.e., unpopular 𝑑 (𝑣 ) items) due to the penalty term −𝛾 · 𝑤𝑖(𝑢 ) · √ 𝑗 , which is counter|E|

𝑢 𝑗 ∈ N (𝑥𝑖 )∩C𝑘

intuitive. In BACO, we view all items interacted by user 𝑢𝑖 equally instead, leading to the following weight for item 𝑣 𝑗 𝑤 𝑗(𝑣) = √︁

(11)

|V |

On the other hand, item 𝑣 𝑗 will be merged to cluster C𝑘 with Í maximal 𝑢𝑖 ∈ C𝑘 B𝑖,𝑗 − 𝛾 · 𝑤𝑖(𝑢 ) · 𝑤 𝑗(𝑣) . In this case, item 𝑣 𝑗 will prioritize the cluster of users with lower weights 𝑤𝑖(𝑢 ) . Recall that in real-world scenarios, compared to those who interacted with plenty of items, the interaction with item 𝑣 𝑗 from a user 𝑢𝑖 with fewer interactions conveys a stronger preference and interest. Intuitively, 𝑣 𝑗 should be more likely to be grouped with 𝑢𝑖 . Given this observation, we resort to the degree-related weight for users, as exemplified below: 𝑤𝑖(𝑢 ) = √︁Í

𝑑 (𝑢𝑖 )

𝑢 ℓ ∈ U 𝑑 (𝑢 ℓ )

4.4

𝑑 (𝑢𝑖 ) = √︁ . |E |

(12)

The Optimization Algorithm

(14)

4.5

Generating Secondary Clusters for Users

Although our basic BACO in Algorithm 1 can achieve an effective balance and optimization of two terms in Eq. (6), and thus, produce good divisions of users and items, as empirically validated in § 5.4 and § 5.5, it suffers from a fundamental deficiency of representing each user via exactly one embedding in codebooks, whilst e-commerce users have multiple, evolving interests and often share taste similarities with various user groups. To remedy this issue while maintaining parameter efficiency, we propose to assign each user to two clusters, which demands a small space of 𝑂 (|U|) for additional user sketches, leading to a new space budget for the codebooks: 𝐵 ′ ← 𝐵·𝑑 −𝑑 | U | . Accordingly, the loop condition at Line 3 in Algorithm 1 will be changed to 𝐾 (𝑢 ) + 𝐾 (𝑣) > 𝐵 ′ . Next, the task is to construct the secondary clusters for users. Specifically, as displayed in Algorithm 2, we employ a simple but effective SCU strategy, which only repeats Lines 4-10 in Algorithm 1 for each user in U for once to generate updated cluster labels as their secondary clusters (Line 18). BACO then maps users to 𝐾 (𝑢 ) consecutive integers based on the secondary cluster labels, i.e.,

𝐾 (𝑣) ← |{ℓ (𝑣 𝑗 )|𝑣 𝑗 ∈ V}|.

In each iteration, BACO picks each user or item from G and updates its label to the one with the highest likelihood among all the labels of its adjacent neighbors, akin to the label propagation scheme [38]. Specifically, for each node 𝑥𝑖 ∈ G, BACO first collects its candidate label set L𝑖 from the neighbors and 𝑥𝑖 at Line 5. Then, for every label 𝑘 ∈ L𝑖 , we calculate its likelihood by ∑︁ ∑︁ 𝑝 (𝑘) ← B𝑖,𝑗 − 𝛾 𝑤𝑖(𝑢 ) · 𝑤 𝑗(𝑣) (13) 𝑣 𝑗 ∈ N (𝑥𝑖 )∩C𝑘

𝑤 𝑗(𝑢 ) · 𝑤𝑖(𝑣)

𝑢 𝑗 ∈ U𝑘

Remark. Although Louvain can be applied to optimize our objective in Eq. (9) with minor changes, its optimization strategy tends to merge small clusters, leading to the resolution limit issue [27] on bipartite networks. In other words, Louvain will greedily group nodes with low connectivity for higher overall modularity. The empirical cluster size distributions reported in Figure 7 confirm this problem, and Table 5 manifests its detrimental effects on recommendation performance.

The pseudo-code of our optimization solver for BACO is illustrated in Algorithm 1. Given the bipartite graph G = (U, V, E), the space budget 𝐵 for codebooks, the maximum number 𝑇 of iterations, and a coefficient 𝛾, BACO begins by assigning a unique cluster label ℓ (𝑢𝑖 ) ← 𝑖 (resp. ℓ (𝑣 𝑗 ) ← |U| + 𝑗) to each user 𝑢𝑖 (item 𝑣 𝑗 ) (Line 1) and reset the iteration count (Line 2). Afterwards, Algorithm 1 starts an iterative procedure (Lines 3-12) to update the labels of users and items until the total number of labels for users and items 𝐾 (𝑢 ) + 𝐾 (𝑣) reaches the space budget 𝐵, where 𝐾 (𝑢 ) and 𝐾 (𝑣) are defined as 𝐾 (𝑢 ) ← |{ℓ (𝑢𝑖 )|𝑢𝑖 ∈ U}|,

∑︁

if it is an item in V (Lines 6-10). Next, at Line 11, the new label of 𝑥𝑖 is set to the one with the maximum likelihood. Note that the first term in the likelihood 𝑝 (𝑘) measures the intra-cluster connectivity of 𝑥𝑖 to its adjacent items (resp. users) with label 𝑘, while the second term considers the penalty 𝛾 · 𝑤 𝑗(𝑢 ) · 𝑤𝑖(𝑣) for all items (resp. users) with label 𝑘. In essence, this label updating rule is to maximize the objective Eq. (9) locally for each target node 𝑥𝑖 in a greedy fashion. After that, Algorithm 1 maps the cluster labels of users and items to consecutive integers [𝐾 (𝑢 ) ] and [𝐾 (𝑣) ], respectively, followed by relabeling all the users and items accordingly (Lines 13-16). Based thereon, we can construct sketching matrices Y (𝑢 ) and Y (𝑣) at Line 17 with the new labels.

1 .

B 𝑗,𝑖 − 𝛾

𝑣 𝑗 ∈ V𝑘

Balanced Co-Clustering of Users and Items for Embedding Table Compression in Recommender Systems

Table 3: Statistics of datasets used in experiments. Dataset Beauty Gowalla Yelp2018 AmazonBook

#Users 22,363 29,858 31,668 52,643

#Items 12,101 40,981 38,048 91,599

#Interactions 198,502 1,027,370 1,561,406 2,984,108

• Hashing methods: Random, Frequency Hashing [16, 66], Double Hashing [66], Hybrid Hashing [66], LSH [10], CCE [49], LEGCF [34]. • Graph clustering methods: (Double)GraphHash [56], Leiden [48], LP [38], EBMD [27], infomap [40], BiMLPA [45], BRIM [37]. • Co-clustering methods: SCC [12], SBC [29], ITCC [13].

Density 0.073% 0.084% 0.130% 0.062%

Evaluation Protocol. We evaluate top-𝐾 item recommendation performance using two widely adopted ranking metrics: Recall@𝐾 and NDCG@𝐾, with 𝐾 = 20 by default. The metrics are averaged over all users in the test set. For fair comparison, all methods are implemented with an identical experimental protocol, employing the classical LightGCN [22] model as the backbone and the BPR loss function. Further experimental details are provided in Appendix C.

: U → [𝐾 (𝑢 ) ] at Lines 19-20. Eventually, for each user 𝑢

𝑓scu 𝑖 ∈ U, (𝑢 ) we set the entry Y𝑖,𝑓 that corresponds to its secondary cluster (𝑢 ) scu 𝑖 in its sketch to 1 (Line 21).

4.6

Complexity Analysis

In Algorithm 1, each iteration accesses the labels of neighbors in 𝑂 (|E |) time at Lines 3-4. Since only one label is updated at each step (Line 11), at most two clusters are affected. By maintaining global sums of cluster weights and updating them whenever label changes, the computation of Eq. (13) or Eq.(14) can be done in 𝑂 (1). To ensure termination over disconnected G, we impose a maximum number 𝑇 (typically 8) of iterations on the iterative procedure (Lines 4-11). In practice, the label propagation process (Lines 3-12) can usually converge and terminate rapidly [38], i.e., the actual number of iterations is less than 𝑇 .2 Therefore, Algorithm 1 takes 𝑂 (𝑇 |E |) time. Similarly, obtaining the secondary cluster labels requires only 𝑂 (|E |) time. At Lines 13-17 and 19-21, clusters are mapped to sets of consecutive integers, which takes 𝑂 (|U| + |V |) time. Overall, the time complexity of the complete BACO is 𝑂 (|U| + |V | + 𝑇 |E |). The space complexity is bounded by 𝑂 (|U| + |V | + |E |) due to the storage of G and clusters.

5.2

Recommendation Performance Evaluation

Table 4 reports the mean Recall@20 and NDCG@20 performance of BACO and the baselines across four datasets, averaged over 5 independent runs using the best hyperparameters. The results under other top-𝐾 (10, 50) values are quantitatively similar, and thus, are deferred to appendix. We can make the following observations. Firstly, our proposed algorithm consistently outperforms all baselines across all tested datasets, with marked improvements. For instance, our algorithm surpasses the best baselines by considerable margins of 0.28%, 1.29%, 0.88%, and 0.47% in terms of Recall@20 on Beauty, Gowalla, Yelp2018, and AmazonBook, respectively. Particularly, BACO attains an average improvement of 0.96% in recall and 0.56% in NDCG over state-of-the-art community detection methods, and offers significantly faster runtime. Additionally, BACO consistently maintains outstanding performance, while SCC and Leiden tend to fail on certain datasets. These results demonstrate the effectiveness of our BACO in exploiting and integrating collaborative information for recommendation across diverse contexts, enabled by its hybrid weighting schemes and refined secondary cluster design. Moreover, compared with simple hash methods (e.g., Random and Frequency), which rely solely on statistical probabilities, graphbased methods (e.g., GraphHash and LP) consistently demonstrate superior performance across most datasets because of their ability to incorporate graph structural information. Unlike conventional clustering algorithms (e.g., 𝑘-means), most community detection methods (such as Infomap, BiMLPA, and BRIM) do not provide control over the cluster number, which leads to fewer parameters but inferior performance in our experiments. In addition, SCC, as a classical co-clustering method, serves as the strongest baseline on Beauty and Yelp2018, but incurs a much higher computational cost.

Experiments

This section experimentally evaluates BACO against 18 ETC baselines in recommendations, and conducts related ablation studies and component analyses to answer the following research questions: • RQ1: How does BACO perform in terms of accuracy compared to full models and ETC baselines in recommendation tasks? (§ 5.2) • RQ2: How does BACO perform in terms of computation efficiency and parameter reduction compared to ETC baselines? (§ 5.3) • RQ3: How effectively do the HWS and SCU enhance the performance of BACO? (§ 5.4 and § 5.5) All experiments are conducted on a Linux machine equipped with an NVIDIA Ampere A100 GPU (80 GB), AMD EPYC 7513 CPUs (2.6 GHz), and 1 TB RAM. The codes and datasets are made publicly available at https://github.com/HKBU-LAGAS/BACO.

5.1

Conference’17, July 2017, Washington, DC, USA

Experimental Setup 5.3

Datasets. Table 3 summarizes the four datasets used in the retrieval task, including Beauty [51], Gowalla [8], Yelp2018 [56], AmazonBook [21], each representing a specific recommendation domain and all publicly available. For each dataset, we randomly divide the data into 80% for training, 10% for validation, and 10% for testing.

Efficiency and Parameter Reduction

Figure 2 presents the runtime costs of BACO and four top-performing baselines, as listed in Tables 3. Note that the 𝑦-axis is in logarithmic scale, and the running time is measured in seconds (sec). Baselines with the best clustering quality are marked with ★. As shown in Figure 2, BACO consistently offers superior efficiency while attaining the best performance across all datasets. Compared to the best baselines in Table 4, BACO achieves speedups of 400×, 2.1×, 346×, and 1.7× on Beauty, Gowalla, Yelp2018, and AmazonBook, respectively. Specifically, BACO is at least 346× faster than

Baselines. For a thorough evaluation, we include 18 ETC baselines in the experiments, broadly categorized into three groups: 2 As validated by our empirical results in Appendix C.2.

Conference’17, July 2017, Washington, DC, USA

Runhao Jiang, Renchi Yang, & Donghao Wu

Table 4: Recommendation Performance (𝑘 = 20). Best results highlighted in blue and runner-up underlined. Beauty

Gowalla

Yelp2018

AmazonBook

Method #Params↓ R@20↑ N@20↑ #Params↓ R@20↑ N@20↑ #Params↓ R@20↑ N@20↑ #Params↓ R@20↑ N@20↑ Full Model Random Frequency Hashing [16] Double Hashing [66] Hybrid Hashing [66] LSH [10] CCE [49] LEGCF [34] GraphHash [56] DoubleGraphHash [56] LP [38] Leiden [48] EBMD [27] infomap [40] BiMLPA [45] BRIM [37] SCC [12] SBC [29] ITCC [13] BACO v.s. Baselines v.s. Full Model

SCC

2.206M 0.529M 0.529M 0.529M 0.529M 1.049M 0.529M 0.529M 0.529M 0.529M 0.530M 0.529M 0.536M 0.025M 0.001M 0.003M 0.529M 0.529M 0.529M 0.529M -76.0%

10.931 4.696 4.367 4.132 4.564 5.566 7.400 7.908 8.167 6.266 7.883 7.943 8.095 4.614 3.765 8.253 8.801 6.816 4.812 9.079 +0.278 -1.852

5.769 2.347 2.194 2.080 2.307 2.787 3.699 3.738 4.272 3.198 4.088 4.141 4.037 2.252 1.708 4.013 4.476 3.345 2.437 4.574 +0.098 -1.195

EBMD

18.204 9.214 8.574 9.215 10.182 9.768 10.455 8.463 15.325 12.377 11.749 15.406 10.313 5.893 6.397 8.074 13.792 10.458 7.685 16.692 +1.286 -1.512

11.600 5.909 5.480 5.994 6.581 6.253 6.851 5.125 9.658 7.905 7.464 9.738 6.564 3.590 3.920 5.150 8.817 6.715 5.156 10.674 +0.936 -0.926

GraphHash

Leiden

4.534M 0.742M 0.742M 0.742M 0.742M 1.049M 0.742M 0.742M 0.742M 0.742M 0.743M 0.743M 0.746M 0.016M 0.007M 0.002M 0.743M 0.742M 0.742M 0.742M -83.6%

4.462M 0.977M 0.977M 0.977M 0.977M 1.049M 0.977M 0.977M 0.977M 0.977M 0.977M 0.979M 0.996M 0.037M 0.008M 0.001M 0.977M 0.977M 0.977M 0.976M -78.1%

8.867 4.894 4.931 5.293 6.090 4.707 5.505 4.349 6.244 5.134 5.423 6.230 4.947 4.335 4.462 4.483 6.633 4.831 4.375 7.510 +0.877 -1.357

BACO

5.526 3.114 3.142 3.366 3.884 2.952 3.538 2.685 3.882 3.236 3.391 3.852 3.088 2.688 2.767 2.789 4.124 3.023 2.844 4.763 +0.639 -0.763

GraphHash

BACO

time (sec)

★

time (sec) 103 103 102

★

(a) Beauty

8.8 8.4

10 1

0.1

(b) Gowalla

8.0

★

7.6 1/2

1/3

1/4

1/5

1/6

1/2

1/3

R@20

coclustering methods. Furthermore, when compared to highly efficient modularity maximization approaches (e.g., GraphHash and Leiden), BACO surpasses them both in speed and in clustering quality. While LP is slightly more efficient owing to its lightweight label propagation, our method consistently outperforms LP in clustering quality, achieving recall improvements in the range of 1.2% to 4.9%. Figure 3 presents the Recall@20 results under varying compression ratios ranging from 1/2 to 1/6. As the ratio increases, BACO and other graph-based algorithms exhibit distinct trends in performance across different datasets, with an overall trend of initial improvement followed by a decline. Specifically, for Yelp2018 and AmazonBook, BACO’s performance hits a nadir at ratio 1/2 and peaks around 1/4 or 1/5, while for Beauty and Gowalla, it rises initially then drops as the ratio increases. Unlike hashing methods, graph-based approaches rely on sufficiently large communities to leverage user/item homogeneity before collisions influence performance. Therefore, we recommend setting the compression ratio to at least 1/5, as lower values can degrade performance to random hashing levels.

1/2

1/5

1/6

1/5

1/6

R@20

7.7 7.4 7.1 6.8 6.5 6.2 5.9

Figure 2: Efficiency of strong methods in constructing sketching matrices. (best baselines in Table 4 are marked with ★)

1/4

(b) Gowalla

(a) Beauty

(d) AmazonBook

SCC

17.0 16.4 15.8 15.2 14.6 14.0 13.4

5.487 1.704 1.497 1.687 1.884 2.167 2.124 5.033 3.501 2.275 5.115 2.199 0.736 1.708 1.440 3.615 2.372 1.790 5.240 +0.125 -0.247

R@20

9.2

102 10

0.1

time (sec) 103

102

10 1

time (sec) ★

8.416 2.485 2.184 2.398 2.800 3.214 3.233 7.261 5.194 3.483 7.426 3.332 1.166 3.765 2.302 5.558 3.556 2.610 7.892 +0.466 -0.524

Leiden

R@20 9.6

102

9.231M 1.255M 1.255M 1.255M 1.255M 2.097M 1.255M OOM 1.255M 1.255M 1.255M 1.256M 1.261M 0.018M 0.001M 0.001M 1.255M 1.255M 1.255M 1.255M -86.4%

8.5 8.0 7.5 7.0 6.5 6.0 5.5 1/3

1/4

1/5

1/6

1/2

1/3

1/4

(d) AmazonBook

Figure 3: Performance when varying parameter ratios. Table 5: Impact of Weighting Schemes. Weighting Scheme

Beauty

Gowalla

Yelp2018

AmazonBook

R@20↑ N@20↑ R@20↑ N@20↑ R@20↑ N@20↑ R@20↑ N@20↑ Louvain (HWS) Louvain (CPM) Leiden (HWS) Leiden (CPM) Modularity CPM reverse HWS BACO w/o SCU

8.551 8.489 8.559 8.725 8.452 8.159 8.159 8.619

4.480 4.417 4.455 4.492 4.380 4.169 4.169 4.406

15.844 16.008 15.705 15.888 16.246 16.009 15.935 16.393

9.974 10.364 10.007 10.258 10.355 10.262 10.147 10.537

6.504 7.211 6.563 7.152 7.296 6.849 7.116 7.344

4.088 4.588 4.158 4.576 4.661 4.341 4.461 4.679

7.754 6.999 7.760 7.066 7.566 7.322 7.261 7.669

5.314 4.747 5.314 4.825 5.164 5.111 5.028 5.237

Balanced Co-Clustering of Users and Items for Embedding Table Compression in Recommender Systems

Table 6: Impact of Secondary Clusters for Users. Weighting Scheme

Beauty

Gowalla

Yelp2018

Conference’17, July 2017, Washington, DC, USA

capacity. Our experiments and ablations demonstrate competitive recommendation quality, substantial parameter reductions, and considerable speedups against strong baselines.

AmazonBook

R@20↑ N@20↑ R@20↑ N@20↑ R@20↑ N@20↑ R@20↑ N@20↑ GraphHash w/ SCU Leiden w/ SCU LP w/ SCU BACO w/o SCU BACO w/ SCI BACO w/ SCU & SCI BACO

5.4

9.073 8.910 8.428 8.619 8.530 8.982 9.079

4.725 4.670 4.366 4.406 4.306 4.555 4.574

15.856 15.924 11.517 16.393 15.892 16.503 16.692

9.930 10.041 7.292 10.537 10.195 10.476 10.674

6.567 6.530 5.120 7.344 7.209 7.648 7.510

4.117 4.084 3.186 4.679 4.544 4.844 4.763

7.655 7.605 3.540 7.669 7.393 7.801 7.892

5.108 5.101 2.323 5.237 5.084 5.214 5.240

Acknowledgments This work is partially supported by the National Natural Science Foundation of China (No. 62302414), the Hong Kong RGC YCRG (No. C2003-23Y), and Guangdong and Hong Kong Universities “1+1+1” Joint Research Collaboration Scheme, project No.: 2025A0505000002.

References

Impact of Weighting Schemes

[1] Arindam Banerjee, Inderjit Dhillon, Joydeep Ghosh, Srujana Merugu, and Dharmendra S Modha. 2004. A generalized maximum entropy approach to bregman co-clustering and matrix approximation. In SIGKDD. 509–514. [2] Michael J Barber. 2007. Modularity and community detection in bipartite networks. Physical Review E 76, 6 (2007), 066102. [3] Michael J Barber and John W Clark. 2009. Detecting network communities by propagating labels under constraints. Physical Review E 80, 2 (2009), 026129. [4] Elena Battaglia, Federico Peiretti, and Ruggero Gaetano Pensa. 2024. Coclustering: A survey of the main methods, recent trends, and open problems. CSUR 57, 2 (2024), 1–33. [5] Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. 2008. Fast unfolding of communities in large networks. Journal of statistical mechanics 2008, 10 (2008), P10008. [6] Ting Chen, Martin Renqiang Min, and Yizhou Sun. 2018. Learning k-way ddimensional discrete codes for compact embedding representations. In ICML. PMLR, 854–863. [7] Yizhou Chen, Guangda Huzhang, Anxiang Zeng, Qingtao Yu, Hui Sun, Heng-Yi Li, Jingyi Li, Yabo Ni, Han Yu, and Zhiming Zhou. 2023. Clustered embedding learning for recommender systems. In TheWebConf. 1074–1084. [8] Eunjoon Cho, Seth A Myers, and Jure Leskovec. 2011. Friendship and mobility: user movement in location-based social networks. In SIGKDD. 1082–1090. [9] Benjamin Coleman, Wang-Cheng Kang, Matthew Fahrbach, Ruoxi Wang, Lichan Hong, Ed Chi, and Derek Cheng. 2023. Unified Embedding: Battle-tested feature representations for web-scale ML systems. NeurIPS 36 (2023), 56234–56255. [10] Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S Mirrokni. 2004. Localitysensitive hashing scheme based on p-stable distributions. In SCG. 253–262. [11] Aditya Desai, Li Chou, and Anshumali Shrivastava. 2022. Random Offset Block Embedding (ROBE) for compressed embedding tables in deep learning recommendation systems. MLSys 4 (2022), 762–778. [12] Inderjit S Dhillon. 2001. Co-clustering documents and words using bipartite spectral graph partitioning. In SIGKDD. 269–274. [13] Inderjit S Dhillon, Subramanyam Mallela, and Dharmendra S Modha. 2003. Information-theoretic co-clustering. In SIGKDD. 89–98. [14] Liang Feng, Qianchuan Zhao, and Cangqi Zhou. 2020. Improving performances of Top-N recommendations with co-clustering method. ESA 143 (2020), 113078. [15] Bin Gao, Tie-Yan Liu, Xin Zheng, Qian-Sheng Cheng, and Wei-Ying Ma. 2005. Consistent bipartite graph co-partitioning for star-structured high-order heterogeneous data co-clustering. In SIGKDD. 41–50. [16] Benjamin Ghaemmaghami, Mustafa Ozdal, Rakesh Komuravelli, Dmitriy Korchev, Dheevatsa Mudigere, Krishnakumar Nair, and Maxim Naumov. 2022. Learning to collide: Recommendation system model compression with learned hash functions. arXiv (2022). [17] Gérard Govaert. 1995. Simultaneous clustering of rows and columns. Control and Cybernetics 24 (1995), 437–458. [18] Huifeng Guo, Wei Guo, Yong Gao, Ruiming Tang, Xiuqiang He, and Wenzhi Liu. 2021. Scalefreectr: Mixcache-based distributed training system for ctr models with huge embedding table. In SIGIR. 1269–1278. [19] Udit Gupta, Carole-Jean Wu, Xiaodong Wang, Maxim Naumov, Brandon Reagen, David Brooks, Bradford Cottel, Kim Hazelwood, Mark Hempstead, Bill Jia, et al. 2020. The architectural implications of facebook’s dnn-based personalized recommendation. In HPCA. IEEE, 488–501. [20] John A Hartigan. 1972. Direct clustering of a data matrix. JASA 67, 337 (1972), 123–129. [21] Ruining He and Julian McAuley. 2016. Ups and downs: Modeling the visual evolution of fashion trends with one-class collaborative filtering. In TheWebConf. 507–517. [22] Xiangnan He, Kuan Deng, Xiang Wang, Yan Li, Yongdong Zhang, and Meng Wang. 2020. Lightgcn: Simplifying and powering graph convolution network for recommendation. In SIGIR. 639–648. [23] Gangwei Jiang, Hao Wang, Jin Chen, Haoyu Wang, Defu Lian, and Enhong Chen. 2021. xLightFM: Extremely memory-efficient factorization machine. In SIGIR. 337–346.

Table 5 presents the recall and NDCG results achieved by BACO, integrated with various weighting schemes as summarized in Table 2, within our unified framework. Overall, HWS consistently outperforms competing methods in most cases, indicating that our scheme is better suited for real-world recommendation scenarios. Specifically, when combined with HWS, BACO achieves average improvements of 0.12% in recall and 0.07% in NDCG across datasets compared to other strategies. Notably, on AmazonBook, all algorithms achieve their best performance when combined with HWS. In particular, the Leiden algorithm achieves the highest performance, demonstrating that HWS can be effectively integrated into various frameworks to further enhance their effectiveness. The only exception occurs on the small-scale Beauty dataset, where HWS is slightly outperformed by CPM, yet it still surpasses the baselines in Table 4.

5.5

Impact of Secondary Clusters for Users

As illustrated in Table 6, the integration of secondary clusters for users in BACO significantly reduces hash collisions, resulting in average improvements of 0.29% in recall and 0.10% in NDCG over the version without secondary clusters (w/o SCU). Particularly, on Beauty, GraphHash equipped with SCU yields notable gains of 0.9% in recall and 0.5% in NDCG, whereas using random secondary labels in DoubleGraph leads to a drop in performance. Notably, introducing secondary item clusters (w/ SCI) generally results in diminished performance, likely due to the dilution of user-level personalization as numerous items are added to clusters. In contrast, SCU sharpens user differentiation. Including both SCU and SCI decreases performance versus SCU alone, since excessive secondary labels may lead to potential conflicts. An exception occurs on Yelp2018, where BACO with both SCU and SCI fortuitously aligns with the dataset’s structure. Our results indicate that employing SCU alone is both sufficient and appropriate for all methods, offering a more reasonable approach than employing the double hash trick.

Conclusion

This paper presents BACO, a simple, fast, and effective framework to compress embedding tables through balanced co-clustering of users and items. Through maximizing intra-cluster connectivity and enforcing balanced cluster sizes, BACO alleviates embedding collisions and codebook collapse, as well as aligns with established graph clustering methodologies. We further introduce a hybrid weighting scheme, an efficient label-propagation solver that sidesteps resolution limits, and secondary user clusters that expand representational 9

Conference’17, July 2017, Washington, DC, USA

Runhao Jiang, Renchi Yang, & Donghao Wu

[24] Wang-Cheng Kang, Derek Zhiyuan Cheng, Ting Chen, Xinyang Yi, Dong Lin, Lichan Hong, and Ed H Chi. 2020. Learning multi-granular quantized embeddings for large-vocab categorical features in recommender systems. In TheWebConf. 562–566. [25] Wang-Cheng Kang, Derek Zhiyuan Cheng, Tiansheng Yao, Xinyang Yi, Ting Chen, Lichan Hong, and Ed H Chi. 2021. Learning to embed categorical features without embedding tables for recommendation. In SIGKDD. 840–850. [26] Petr Kasalický, Martin Spišák, Vojtěch Vančura, Daniel Bohuněk, Rodrigo Alves, and Pavel Kordík. 2025. The Future is Sparse: Embedding Compression for Scalable Retrieval in Recommender Systems. In RecSys. 1099–1103. [27] Junghoon Kim, Kaiyu Feng, Gao Cong, Diwen Zhu, Wenyuan Yu, and Chunyan Miao. 2022. ABC: attributed bipartite co-clustering. PVLDB 15, 10 (2022), 2134– 2147. [28] Diederik P Kingma and Jimmy Ba. 2014. Adam: A method for stochastic optimization. arXiv (2014). [29] Yuval Kluger, Ronen Basri, Joseph T Chang, and Mark Gerstein. 2003. Spectral biclustering of microarray data: coclustering genes and conditions. Genome research 13, 4 (2003), 703–716. [30] Daniel B Larremore, Aaron Clauset, and Abigail Z Jacobs. 2014. Efficiently inferring community structure in bipartite networks. Physical Review E 90, 1 (2014), 012805. [31] Shiwei Li, Huifeng Guo, Xing Tang, Ruiming Tang, Lu Hou, Ruixuan Li, and Rui Zhang. 2024. Embedding compression in recommender systems: A survey. CSUR 56, 5 (2024), 1–21. [32] Defu Lian, Haoyu Wang, Zheng Liu, Jianxun Lian, Enhong Chen, and Xing Xie. 2020. Lightrec: A memory and search-efficient recommender system. In TheWebConf. 695–705. [33] Paul Pu Liang, Manzil Zaheer, Yuan Wang, and Amr Ahmed. 2021. Anchor & Transform: Learning Sparse Embeddings for Large Vocabularies. In ICLR. [34] Xurong Liang, Tong Chen, Lizhen Cui, Yang Wang, Meng Wang, and Hongzhi Yin. 2024. Lightweight embeddings for graph collaborative filtering. In SIGIR. 1296–1306. [35] David Melamed. 2014. Community structures in bipartite networks: A dualprojection approach. PloS one 9, 5 (2014), e97823. [36] Mark EJ Newman and Michelle Girvan. 2004. Finding and evaluating community structure in networks. Physical review E 69, 2 (2004), 026113. [37] John Platig, Peter J Castaldi, Dawn DeMeo, and John Quackenbush. 2016. Bipartite community structure of eQTLs. PLoS computational biology 12, 9 (2016), e1005033. [38] Usha Nandini Raghavan, Réka Albert, and Soundar Kumara. 2007. Near linear time algorithm to detect community structures in large-scale networks. Physical Review E 76, 3 (2007), 036106. [39] Jörg Reichardt and Stefan Bornholdt. 2006. Statistical mechanics of community detection. Physical Review E 74, 1 (2006), 016110. [40] Martin Rosvall and Carl T Bergstrom. 2008. Maps of random walks on complex networks reveal community structure. PNAS 105, 4 (2008), 1118–1123. [41] Hao-Jun Michael Shi, Dheevatsa Mudigere, Maxim Naumov, and Jiyan Yang. 2020. Compositional embeddings using complementary partitions for memory-efficient recommendation systems. In SIGKDD. 165–175. [42] Xiaoxiao Shi, Wei Fan, and S Yu Philip. 2010. Efficient semi-supervised spectral co-clustering with constraints. In ICDM. IEEE, 1043–1048. [43] Mechthild Stoer and Frank Wagner. 1997. A simple min-cut algorithm. JACM 44, 4 (1997), 585–591. [44] Raphael Tackx, Fabien Tarissan, and Jean-Loup Guillaume. 2017. ComSim: a bipartite community detection algorithm using cycle and node’s similarity. In CNA. Springer, 278–289. [45] Hibiki Taguchi, Tsuyoshi Murata, and Xin Liu. 2020. Bimlpa: community detection in bipartite networks by multi-label propagation. In ICNS. Springer, 17–31. [46] Dan Tito Svenstrup, Jonas Hansen, and Ole Winther. 2017. Hash embeddings for efficient word representations. NeurIPS 30 (2017). [47] Vincent A Traag, Paul Van Dooren, and Yurii Nesterov. 2011. Narrow scope for resolution-limit-free community detection. Physical Review E 84, 1 (2011), 016114.

[48] Vincent A Traag, Ludo Waltman, and Nees Jan Van Eck. 2019. From Louvain to Leiden: guaranteeing well-connected communities. Scientific reports 9, 1 (2019), 1–12. [49] Henry Tsang and Thomas Ahle. 2023. Clustering the sketch: dynamic compression for embedding tables. NeurIPS 36 (2023), 72155–72180. [50] Ulrike Von Luxburg. 2007. A tutorial on spectral clustering. Statistics and computing 17, 4 (2007), 395–416. [51] Chenyang Wang, Yuanqing Yu, Weizhi Ma, Min Zhang, Chong Chen, Yiqun Liu, and Shaoping Ma. 2022. Towards representation alignment and uniformity in collaborative filtering. In SIGKDD. 1816–1825. [52] Hongjun Wang, Yi Song, Wei Chen, Zhipeng Luo, Chongshou Li, and Tianrui Li. 2024. A Survey of Co-Clustering. TKDE 18, 9, Article 224 (Nov. 2024), 28 pages. [53] Qinyong Wang, Hongzhi Yin, Tong Chen, Zi Huang, Hao Wang, Yanchang Zhao, Nguyen Quoc Viet Hung, Maarten van Steen, Tie-Yan Liu, Yennun Huang, and Irwin King. 2020. Next Point-of-Interest Recommendation on ResourceConstrained Mobile Devices. In TheWebConf. 906–916. [54] Kilian Weinberger, Anirban Dasgupta, John Langford, Alex Smola, and Josh Attenberg. 2009. Feature hashing for large scale multitask learning. In ICML. 1113–1120. [55] Chao-Yuan Wu, Alex Beutel, Amr Ahmed, and Alexander J Smola. 2016. Explaining reviews and ratings with paco: Poisson additive co-clustering. In TheWebConf. 127–128. [56] Xinyi Wu, Donald Loveland, Runjin Chen, Yozen Liu, Xin Chen, Leonardo Neves, Ali Jadbabaie, Mingxuan Ju, Neil Shah, and Tong Zhao. 2025. GraphHash: Graph Clustering Enables Parameter Efficiency in Recommender Systems. In TheWebConf. 357–369. [57] Xiaorui Wu, Hong Xu, Honglin Zhang, Huaming Chen, and Jian Wang. 2020. Saec: similarity-aware embedding compression in recommendation systems. In SIGOPS. 82–89. [58] Yongji Wu, Defu Lian, Neil Zhenqiang Gong, Lu Yin, Mingyang Yin, Jingren Zhou, and Hongxia Yang. 2021. Linear-time self attention with codeword histogram for efficient recommendation. In TheWebConf. 1262–1273. [59] Xin Xia, Hongzhi Yin, Junliang Yu, Qinyong Wang, Guandong Xu, and Quoc Viet Hung Nguyen. 2022. On-Device Next-Item Recommendation with SelfSupervised Knowledge Distillation. In SIGIR. ACM, New York, NY, USA, 546–555. [60] Zhiqiang Xu, Dong Li, Weijie Zhao, Xing Shen, Tianbo Huang, Xiaoyun Li, and Ping Li. 2021. Agile and accurate CTR prediction model training for massive-scale online advertising systems. In SIGMOD. 2404–2409. [61] Renchi Yang and Jieming Shi. 2024. Efficient high-quality clustering for large bipartite graphs. SIGMOD 2, 1 (2024), 1–27. [62] Renchi Yang, Jieming Shi, Keke Huang, and Xiaokui Xiao. 2022. Scalable and effective bipartite network embedding. In SIGMOD. 1977–1991. [63] Renchi Yang, Yidu Wu, Xiaoyang Lin, Qichen Wang, Tsz Nam Chan, and Jieming Shi. 2024. Effective clustering on large attributed bipartite graphs. In KDD. 3782–3793. [64] Tzu-Chi Yen and Daniel B Larremore. 2020. Community detection in bipartite networks with stochastic block models. Physical Review E 102, 3 (2020), 032309. [65] Chunxing Yin, Bilge Acun, Carole-Jean Wu, and Xing Liu. 2021. Tt-rec: Tensor train compression for deep learning recommendation models. MLSys 3 (2021), 448–462. [66] Caojin Zhang, Yicun Liu, Yuanpu Xie, Sofia Ira Ktena, Alykhan Tejani, Akshay Gupta, Pranay Kumar Myana, Deepak Dilipkumar, Suvadip Paul, Ikuhiro Ihara, et al. 2020. Model size reduction using frequency based double hashing for recommender systems. In RecSys. 521–526. [67] Kunpeng Zhang, Shaokun Fan, and Harry Jiannan Wang. 2018. An Efficient Recommender System Using Locality Sensitive Hashing. In HICSS. 780–789. [68] Shuai Zhang, Lina Yao, Aixin Sun, and Yi Tay. 2019. Deep learning based recommender system: A survey and new perspectives. CSUR 52, 1 (2019), 1–38. [69] Taiyan Zhang, Hongtao Wang, Yunqian Fan, Kunda Yang, Jichuan Zeng, and Renchi Yang. 2026. A Survey of Item Identifiers in Generative Recommendation: Construction, Alignment, and Generation. TechRxiv 2026, 0126 (2026).

Balanced Co-Clustering of Users and Items for Embedding Table Compression in Recommender Systems

Trace(Y⊤ AY), which can be simplified as maxY Trace(Y⊤ AY) since Í𝐾 Í Trace(Y⊤ DY) = 𝑘=1 |E | is a constant. This objec𝑥 ∈ C𝑘 𝑑 (𝑥) = Í Í tive can also be rewritten as maxY 𝑢𝑖 ∈ U 𝑣 𝑗 ∈ N (𝑢𝑖 ) B𝑖,𝑗 · 𝛿 (𝑢𝑖 , 𝑣 𝑗 ) by Eq. (8). □

Theoretical Proofs Proof of Eq. (5). First, we expand 𝐾 ∑︁

vol(𝐶𝑘 ) 2 +

Í𝐾 𝑘=1

vol(𝐶𝑘 ) −

𝑊 (𝑢) +𝑊 (𝑣)

𝐾

(𝑊 (𝑢) + 𝑊 (𝑣) ) 2 2vol(𝐶𝑘 ) · (𝑊 (𝑢) + 𝑊 (𝑣) ) − . 𝐾 𝐾2

B Detailed Related Works B.1 Co-Clustering

𝑘=1

It can be further reorganized as =

𝐾 ∑︁

vol(𝐶𝑘 ) 2 +

𝑘=1

𝐾 ∑︁

𝐾 ∑︁ (𝑊 (𝑢) + 𝑊 (𝑣) ) 2

𝐾2

−

𝐾 ∑︁

2vol(𝐶𝑘 )

(𝑊 (𝑢) + 𝑊 (𝑣) ) 𝐾

Co-clustering seeks to reveal associations between row and column clusters through the simultaneous clustering of both dimensions in a data matrix. Initially, Hartigan [20] advocated co-clustering of variables and cases, enabling direct interpretation of the resulting clusters. Dhillon [12] established a connection between coclustering and spectral graph partitioning. Regarding the spectral co-clustering algorithm, Kluger et al. [29] enabled different cluster numbers per dimension, Gao et al. [15] resolved higher-order problems, and Shi et al. [42] integrated constraint information. Employing information theory transforms co-clustering into an optimization problem, where different association measures yield distinct algorithms: [17, 20] utilizes a least-squares criterion, ITCC [13] maximizes mutual information, and BCC [1] optimizes the Bregman divergence. Numerous model-based and matrix factorization-based algorithms have also been proposed, as reviewed in detail in previous surveys [4, 52]. Recently, co-clustering techniques have accelerated improvements in recommender systems. For instance, Wu et al. [55] incorporated sampling techniques to accelerate recommendations, while Feng et al. [14] improved accuracy by limiting recommended items to the same cluster. However, these methods are typically employed to supplement information and enhance accuracy, with limited focus on addressing the memory constraints of embedding tables.

𝑘=1

(𝑊 (𝑢) + 𝑊 (𝑣) ) 2 2(𝑊 (𝑢) + 𝑊 (𝑣) ) 2 − , 𝐾 𝐾

vol(𝐶𝑘 ) 2 +

𝑘=1 (𝑢) (𝑣) 2 2(𝑊 (𝑢) +𝑊 (𝑣) ) 2 2 . Since 2(𝑊 𝐾+𝑊 ) is a con𝑘=1 vol(𝐶𝑘 ) − 𝐾 Í𝐾 Í𝐾 (𝑢) (𝑣) 2 ⇔ min 𝑘=1 vol(𝐶𝑘 ) 2 . stant, min 𝑘=1 vol(𝐶𝑘 ) − 𝑊 𝐾+𝑊 𝐶 ,...,𝐶 𝐶 ,...,𝐶

Í𝐾

i.e.,

𝐾

!2 By Eq. (4),

Í𝐾

2 𝑘=1 vol(𝐶𝑘 ) =

Í 𝑤𝑖(𝑢 ) + 𝑤 𝑗(𝑣) , 𝑘=1 𝑣 𝑗 ∈ C𝑘 ∩V 𝑢𝑖 ∈ C𝑘 ∩U

Í𝐾

= ∥w ® ⊤ Y∥ 22 = Trace(Y⊤ w ®w ® ⊤ Y), which completes the proof.

□

Proof of Lemma 4.1. By the definition of bipartite modularity (𝑢) (𝑣) Í𝐾 𝜎𝑘 ·𝜎𝑘 = by Barber [2] (Eq. (1)), we can derive that 𝑘=1 𝑠𝑘 − 𝛾 · | E | Í Í Í𝐾 Í 𝑢𝑖 ∈U𝑘 𝑑 (𝑢𝑖 ) · 𝑣 𝑗 ∈V𝑘 𝑑 (𝑣 𝑗 ) , leading to 𝑢𝑖 ,𝑣 𝑗 ∈ C𝑘 B𝑖,𝑗 − 𝛾 · 𝑘=1 |E| (𝑢)

𝐾 ∑︁

𝑠𝑘 − 𝛾 ·

𝜎𝑘

(𝑣) !

· 𝜎𝑘

|E|

𝑘=1

𝐾 ∑︁

∑︁

B𝑖,𝑗 − 𝛾 ·

𝑘=1 𝑢𝑖 ,𝑣 𝑗 ∈C𝑘

𝑑 (𝑢𝑖 ) · 𝑑 (𝑣 𝑗 ) |E|

∑︁ ∑︁

𝑑 (𝑢𝑖 ) · 𝑑 (𝑣 𝑗 ) B𝑖,𝑗 − 𝛾 · · 𝛿 (𝑢𝑖 , 𝑣 𝑗 ). |E| 𝑣 ∈V

Conference’17, July 2017, Washington, DC, USA

𝑢𝑖 ∈U 𝑗

Likewise, from the definition of bipartite CPM [47], it follows that 𝐾 ∑︁ 𝑘=1

B.2

(𝑠𝑘 − 𝛾 · | U𝑘 | · | V𝑘 | ) =

𝐾 ∑︁

∑︁

𝑘=1 𝑢𝑖 ,𝑣 𝑗 ∈C𝑘

𝑢𝑖 ∈U 𝑣 𝑗 ∈V

As for LPAb [3], it basically leverages label propagation to optimize the modularity by assigning a new label to 𝑢𝑖 as follows: Í 𝛾 𝑙 (𝑢𝑖 ) = arg max 𝑣 𝑗 ∈ C𝑘 B𝑖,𝑗 − E · 𝑑 (𝑢𝑖 ) · 𝑑 (𝑣 𝑗 ). It is equivalent to 1≤𝑘 ≤𝐾 Í Í 𝑑 (𝑢 ) ·𝑑 (𝑣 ) max 𝑢𝑖 ∈ U 𝑣 𝑗 ∈ V B𝑖,𝑗 − 𝛾 · 𝑖 E 𝑗 , which locally maximizes the function and together sum up to an overall objective matching our final form. □ Proof of Lemma 4.2. According to [3, 38], each step in LP determines the cluster label of target node 𝑢𝑖 by the following way: Í 𝑘 ∗ = arg max 𝑣 𝑗 ∈ C𝑘 ∩N (𝑢𝑖 ) 𝛿 (𝑢𝑖 , 𝑣 𝑗 ), which is to locally maximize 1≤𝑘 ≤𝐾 Í 𝑣 𝑗 ∈ N (𝑢𝑖 ) B𝑖,𝑗 · 𝛿 (𝑢𝑖 , 𝑣 𝑗 ) for node 𝑢𝑖 . If we consider all nodes in U, it leads to an overall objective of LP: max Y

∑︁

𝑢𝑖 ∈U 𝑣 𝑗 ∈N (𝑢𝑖 )

B𝑖,𝑗 · 𝛿 (𝑢𝑖 , 𝑣 𝑗 ) = max Y

∑︁ ∑︁

Bipartite Graph Clustering

Bipartite graph clustering is a method for uncovering underlying structural properties in diverse relationship networks [63]. A straightforward approach is to transform the bipartite graph into a unipartite graph, thereby allowing the application of conventional graph clustering methods, e.g., [36, 50]. Moreover, projection-based methods [35, 44, 61] generate a unipartite graph to yield higherquality clusters, but this often results in a much denser graph structure. Approaches specifically developed for bipartite graph clustering include spectral clustering [12, 29], statistical modeling [30, 64], and graph embeddings [62]. However, the aforementioned methods often involve considerable computational overhead, whereas modularity maximization [5, 27, 48] and label propagation [38, 45] methods are recognized for their computational efficiency. Its influence diffusion-based structure enables continuous and enhanced information exchange between users and items, making it particularly well-suited for recommendation systems. Recently, Wu et al. [56] innovatively exploited user-item interaction graphs to compress embedding tables for recommendation tasks. However, their approach simply applies modularity maximization, without adequately considering the unique data characteristics and clustering biases of recommender systems.

B𝑖,𝑗 · 𝛿 (𝑢𝑖 , 𝑣 𝑗 ).

𝑢𝑖 ∈U 𝑣 𝑗 ∈V

Since SCC is the version of spectral clustering on bipartite graphs, whose objective function is often framed as a trace minimization problem: minY Trace(Y⊤ (D − A)Y) ⇔ minY Trace(Y⊤ DY) − 11

Conference’17, July 2017, Washington, DC, USA

GraphHash

Runhao Jiang, Renchi Yang, & Donghao Wu

BACO

Leiden

R@20

full

In this section, we present the parameters not detailed in the main text. We utilize the Adam [28] optimizer with a learning rate of 0.001 and a mini-batch size of 1024, and an embedding dimension of 64 across all datasets. Training is conducted for up to 1000 epochs, with early stopping(patience of 50 epochs) and validation strategies employed to prevent overfitting. Following the settings in [56], we assign half of the hash bins to the highest-frequency entities in both the Frequency Hashing [16] and Hybrid Hashing, and employ the user-item interaction graph as the feature in LSH [10]. In addition, CCE [49] and LEGCF [34] require dynamic updates, but for fairness, their sketching matrices are updated only in the first epoch, while hash labels for other methods are fixed before training. We retain the original implementations of infomap [40], BiMLPA [45], BRIM [37], as these methods inherently perform adaptive cluster detection without explicit control over the number of communities. For a fair comparison, we adjust our parameter 𝛾 to match the target size of the embedding table, as in Table 7. As shown in Figure 4, our empirical study confirms that the parameter converges at an exponential rate. The parameter achieves around 20% compression ratio and tends to be stable after 5 iterations. Thereon, we fix the parameter 𝑇 to 5.

N@20 12.0 11.5 11.0 10.5 10.0 9.5 9.0

22 20 18 16 14 12 0-25%

0-25%

25-50% 50-75% 75-100%

(a) Gowalla (Recall)

(b) Gowalla (NDCG)

R@20

N@20 11.0

10 9 8 7 6 5

10.5 10.0 9.5 9.0 0-25%

25-50% 50-75% 75-100%

0-25%

25-50% 50-75% 75-100%

(d) Yelp2018 (NDCG)

Figure 5: Performance breakdown by test user frequency. BACO

GraphHash N@20

R@20 11.0 10.7 10.4 10.1 9.8 9.5 9.2

17.0 16.6 16.2 15.8 15.4 15.0 4

(a) Recall

C.3

(b) NDCG

Figure 6: Impact of resolution paramater 𝛾.

C Additional Experimental Details C.1 Datasets Details

Í ACCL =

We conduct our experiments on four benchmark datasets, each widely utilized in recommendation research [22, 51, 56] and realworld scenarios. The datasets are detailed as follows: • Beauty: A subset of Amazon product reviews, encompassing user interactions of beauty products. • Gowalla: A check-in dataset capturing user location-sharing behaviors on the Gowalla platform. • Yelp2018: Extracted from the 2018 Yelp Challenge, this dataset contains user interactions with local businesses. • AmazonBook: A subset of Amazon product reviews, containing user interactions with books.

C.2

D.2

Table 7: Parameter setting in BACO

Beauty

7.57

5.50

Gowalla

AmazonBook

Paras ratio 100%

75% 50% 25% 0% 0

Figure 4: Embedding table parameters ratio of BACO versus iteration count.

, Gini =

! Í𝑖 𝐾 2 ∑︁ 𝑖 𝑗 =1 | C𝑗 | · − Í𝐾 . 𝐾 𝑖=1 𝐾 𝑘=1 | C𝑘 |

User Subgroup Evaluation

This experiment investigates the efficacy of algorithms across user groups, which are categorized by their activity frequency percentiles in the training data. In the Figure 5, we report the average metrics of each degree subgroup for both the top-performing baselines and the full model. All methods follow the trend of the full model and perform better with power users. Notably, BACO, which achieves the best overall performance, substantially mitigates the shortcomings of existing algorithms with respect to tail users. These observations indicate that substantial improvements can still be

4.73

Yelp2018

𝐾 2

B𝑖,𝑗

To comprehensively assess the performance of BACO, we additionally report Recall@𝐾 and NDCG@𝐾 for 𝐾 = 10 and 𝐾 = 50, using the same embedding table size as shown in Table 4. As shown in Table 8, BACO consistently outperforms all baseline approaches across all datasets, with improvements of up to 1.987% in Recall and 1.192% in NDCG, achieving substantial improvements in both evaluation settings. Overall, these results demonstrate the substantial effectiveness of BACO under both strict and relaxed scenarios.

Parameter Beauty Gowalla Yelp2018 AmazonBook 0.13

C𝑘 ,Cℓ ∈C 𝑢𝑖 ∈C𝑘 ,𝑣 𝑗 ∈Cℓ

D Additional Experimental Results D.1 Recommendation Performance Evaluation

Parameter Settings

𝛾

Evaluation Metrics

Given a set of C = {C1, C2, . . . , C𝐾 } of 𝐾 disjoint co-clusters, each containing both users and items, we provide the formal mathematical definitions of the averaged cross-cluster links(ACCL) and the Gini coefficient in Figure 1 as follows:

Balanced Co-Clustering of Users and Items for Embedding Table Compression in Recommender Systems

Conference’17, July 2017, Washington, DC, USA

Table 8: Recommendation Performance (𝑘 = 10 or 50). Best results highlighted in blue and runner-up underlined. Beauty

Gowalla

Yelp2018

AmazonBook

Method R@10↑ N@10↑ R@50↑ N@50↑ R@10↑ N@10↑ R@50↑ N@50↑ R@10↑ N@10↑ R@50↑ N@50↑ R@10↑ N@10↑ R@50↑ N@50↑ Full Model 7.619 4.814 16.343 6.998 12.917 9.837 29.010 Random 3.054 1.874 7.555 3.009 6.368 5.015 15.097 Frequency Hashing [16] 2.926 1.763 7.637 2.945 5.852 4.597 14.331 2.872 1.717 7.035 2.779 6.491 5.133 15.172 Double Hashing [66] Hybrid Hashing [66] 3.028 1.786 7.704 2.976 6.901 5.451 16.061 LSH [10] 3.613 2.179 8.720 3.470 6.481 5.191 14.244 CCE [49] 4.953 2.993 11.478 4.629 7.391 5.844 16.710 LEGCF [34] 4.989 2.914 12.391 4.754 5.413 4.046 13.230 GraphHash [56] 5.776 3.579 12.294 5.224 10.672 8.074 24.442 DoubleGraphHash [56] 3.883 2.439 9.307 3.826 8.711 6.720 19.949 LP [38] 5.465 3.415 12.162 5.094 8.026 6.253 19.144 Leiden [48] 5.540 3.446 12.165 5.108 10.753 8.203 24.245 EBMD [27] 5.443 3.290 11.961 4.949 7.061 5.501 16.816 infomap [40] 2.922 1.767 7.521 2.893 4.085 2.997 9.511 BiMLPA [45] 2.293 1.295 6.806 2.381 4.423 3.262 10.430 5.418 3.236 12.875 5.082 5.595 4.378 12.935 BRIM [37] SCC [12] 5.920 3.640 13.072 5.456 9.667 7.467 21.880 SBC [29] 4.360 2.630 10.506 4.192 7.220 5.665 17.084 ITCC [13] 3.096 1.925 7.648 3.090 5.461 4.419 12.163 BACO 6.308 3.733 14.036 5.643 11.701 9.052 26.429 v.s. Baselines +0.388 +0.093 +0.964 +0.187 +0.948 +0.849 +1.987 v.s. Full Model -1.311 -1.081 -2.307 -1.355 -1.216 -0.785 -2.581

14.538 5.602 4.334 7.588 3.048 2.414 7.108 3.071 2.451 7.705 3.170 2.504 8.151 3.856 3.112 7.511 2.858 2.255 8.586 3.533 2.808 6.319 2.747 2.071 12.112 3.863 3.013 10.007 3.245 2.529 9.481 3.358 2.636 12.152 3.898 3.000 8.352 3.080 2.407 4.556 2.690 2.081 4.986 2.751 2.140 6.518 2.702 2.080 11.016 4.167 3.224 8.522 3.060 2.377 6.439 2.788 2.258 13.344 4.790 3.767 +1.192 +0.623 +0.543 -1.194 -0.812 -0.568

16.334 7.796 5.689 4.542 15.093 7.603 9.055 4.375 1.677 1.445 4.679 2.448 9.262 4.482 1.459 1.243 4.095 2.127 9.542 4.587 1.626 1.374 4.393 2.304 11.172 5.486 1.726 1.418 4.892 2.471 8.274 4.033 2.287 1.899 6.260 3.212 10.148 4.960 2.117 1.710 5.937 2.975 8.060 3.795 11.709 5.542 5.081 4.264 11.851 6.477 9.708 4.635 3.708 2.778 9.221 4.519 10.291 4.868 2.278 1.830 6.435 3.181 11.764 5.536 5.174 4.300 11.927 6.513 9.628 4.525 2.182 1.780 6.052 3.058 8.074 3.827 0.749 0.584 2.248 1.067 8.284 3.930 0.699 0.545 2.106 0.996 8.025 3.809 1.438 1.121 4.387 2.081 12.246 5.832 3.622 2.909 9.869 4.941 9.164 4.354 2.389 1.944 6.508 3.300 8.291 4.069 1.753 1.471 4.701 2.465 13.739 6.668 5.357 4.315 13.221 6.868 +1.493 +0.836 +0.183 +0.015 +1.294 +0.355 -2.596 -1.127 -0.332 -0.227 -1.872 -0.734

made for low-frequency users, and our framework provides a potential solution to address this challenge.

more uniform size, thereby failing to fully leverage the inherent graph structure.

D.3

Table 9: Average distance of full embeddings and codebooks.

Parameter Analysis

In Figure 6, we vary 𝛾 in the range [4, 10] on Gowalla , where the compression ratio parameter spans [1/10, 1/5]. BACO consistently surpasses GraphHash across all resolutions. Furthermore, increasing the resolution(with a corresponding increase in the embedding table size) leads to an improvement in Recall for BACO, whereas GraphHash fails to achieve further performance gains. Regarding NDCG, BACO maintains stable performance, while GraphHash demonstrates a decline, due to its coarse clustering strategy.

D.4

Gowalla user item

user

item

VL]H

102

101

100

6RUWHG,'

(a) GraphHash

100

6RUWHG,' (b) Leiden

user item

all

Table 9 presents the average distances between the hashing embeddings and the full model embeddings for users, items, and the combined set. The results indicate that embeddings produced by BACO are more closely aligned with those of the full model, corroborating its superior performance as reported in Table 9. Moreover, the SCU strategy in BACO substantially reduces the user-side distance, with only minimal impact on item-side conflicts. Nevertheless, the overall improvement for both users and items is more significant.

total

103 102 101 100

all

GraphHash 5.444 4.976 5.174 5.291 4.894 5.074 Leiden 5.401 4.951 5.141 5.449 4.970 5.188 SCC 5.405 4.872 5.097 5.038 4.794 4.905 BACO w/o SCU 5.069 4.909 4.977 5.180 4.847 4.998 4.854 4.980 4.927 4.751 4.982 4.877 BACO

Clustering Result Analysis VL]H

Yelp2018

Method

VL]H

6RUWHG,'

D.5

Figure 7: Cluster size distributions of GraphHash, Leiden, BACO.

Additional Large-scale Datasets

Table 10: Summary statistics about large-scale datasets.

We further examine the differences in clustering between BACO and strong baselines by analyzing cluster size distribution and embedding distance. As illustrated in Figure 7, BACO exhibits a more heterogeneous cluster size distribution compared to GraphHash and Leiden, with a greater prevalence of both small and large clusters. This pattern arises because our method groups low-degree nodes into large clusters, facilitating mutual information sharing, while assigning high-degree nodes to smaller or singleton clusters to minimize conflicts. In contrast, other methods tend to produce clusters of

Dataset MovieLens SteamGame

#Users 200,808 2,567,538

#Items 65,032 15,474

#Interactions 20,228,336 7,793,069

Density 0.155% 0.020%

We further evaluate BACO on MovieLens and SteamGame, two large-scale datasets with 20M interaction edges and 2M nodes, respectively, as shown in Table 10. We select the three optimal baselines, namely GraphHash, Leiden, and SCC, for performance evaluation on large-scale datasets. Note that since SCC relies on 13

Conference’17, July 2017, Washington, DC, USA

Runhao Jiang, Renchi Yang, & Donghao Wu

Table 11: Performance comparison on large-scale datasets. MovieLens

Therefore, we only present the results of GraphHash, Leiden, and BACO. As shown in Table 11, BACO overall outperforms all the baselines with fewer embedding table parameters. Compared to the best baselines, BACO achieves improvement of over 0.4% in Recall@20 across both datasets. In terms of speed, BACO saves 25% of the running time relative to Leiden on MovieLens data. On SteamGame, BACO runs 1.5s longer than Leiden, yet it achieved relative improvements of 7.3% and 9.9% in Recall@20 and NDCG@20, respectively. The reason lies in our compact weighting schemes, which are tailored to the recommendation task.

SteamGame

Method Param↓ R@20↑ N@20↑ Param↓ R@20↑ N@20↑ Full Model GraphHash Leiden BACO v.s. Baselines v.s. Full Model

17.0M 2.26M 2.26M 2.19M -87.1%

25.980 20.631 20.878 21.362 +0.484 -4.618

20.294 165.3M 8.004 3.752 14.669 22.6M 6.354 2.821 14.778 22.6M 6.439 2.830 14.802 21.7M 6.912 3.111 +0.024 +0.473 +0.281 -5.492 -86.9% -1.092 -0.641

the costly SVD technique, it fails to finish running within 10 hours.

Record · ID 120536 · SHA-256 32e8124f463f57f9
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.