Enhancing Long-Tail Bundle Recommendations Utilizing Composition Pattern Modeling

1 Introduction

Bundle recommendation aims to provide a collection of items as a convenient option to meet specific user demands [Cao Highly skewed distribution

∗Zhi Zheng and Hui Xiong are both corresponding authors

������ �����

Significant

performance disparity

���������

������ �����

��� ��� ��� ��� ��� ���

�������"�� �!���� �� �� ���� ����

(a)

et al., 2017a; Chen et al., 2019a; Hu et al., 2020; Zheng et al., 2021; Zheng et al., 2023]. Recently, bundle recommendation has gained significance attention in many online applications such as e-commerce and music streaming platforms, as it offers one-stop convenience for users and aligns with widely adopted marketing strategies [Ma et al., 2022; Chang et al., 2023].

In recent years, bundle recommendation has seen substantial progress mainly through matrix factorization-based approaches [Pathak et al., 2017; Cao et al., 2017a; Chen et al., 2019b; Brosh et al., 2022; He et al., 2019] and graph learningbased approaches [Deng et al., 2020; Zhang et al., 2022; Yu et al., 2022; Wei et al., 2023b; Ren et al., 2023]. Twoview graph-based modeling has emerged as an effective approach through a user-bundle view for modeling user-bundle interactions and a user-item view for modeling items compositions in different bundles. However, these approaches face critical limitations in handling long-tail bundle recommendation problem, which is very common in real-world scenarios. As shown in Figure. 1(a), we observe a highly skewed distribution of bundle interactions on Youshu [Chen et al., 2019b] dataset, where a small portion of bundles (head bundles) accumulates most interactions while the majority (tail bundles) receives few interactions. The performance curve of CrossCBR [Ma et al., 2022], which is a representative bundle recommendation method, plotted in the same figure reveals

�������"�� �!���� ��!�

���

���

���

���

���

���

���

���

���

���

���������

���������

significant performance disparity across bundles with varying interaction frequencies.

Indeed, some methods for long-tail item recommendation have already been conducted. For example, data augmentation methods adjust the training data distribution through resampling [Zhang and Hong, 2021; Park and Tuzhilin, 2008] or synthetic data generation [Tang et al., 2020; Wu et al., 2019] to enhance the interaction feature of tail items. Methods incorporating auxiliary information leverage item attributes [Zhu et al., 2020; Ouyang et al., 2021] or textual descriptions [Liang et al., 2020] to enrich tail item features. However, these approaches fail to address the unique challenges in long-tail bundle recommendations where both userbundle interactions and item compositions in different bundles need to be jointly considered.

To solve the above problems, we explore the potential of leveraging bundle composition patterns as a source of valuable signals for enhancing long-tail bundle recommendations. Specifically, we observe that different bundles naturally share common item composition patterns that reflect similar consumption behaviors across various scenarios (e.g., shared functional elements and usage contexts), as illustrated in Figure 1(b). Along this line, we propose to leverage these inherent patterns as stable signals for enhancing long-tail bundle representations. To achieve this goal, we need to address two notable challenges: (1)Composition Pattern Complexity. The complexity stems from the exponential explosion caused by the growing number of items and bundle sizes, complicating the modeling of composition patterns that are shared across different bundles. (2)Long-tail Noisy Feature Integration. The limited interaction records of tail bundles introduce noise from sparsity, leading to biased and underrepresented behavior features [Wei et al., 2023a]. When integrating these noisy features into the modeling process, the noise can propagate between different modeling views, which can further distort the bundle representations and degrade the model performance.

Therefore, in this paper, we propose Composition-Aware Long-tail Bundle Recommendation (CALBRec), a novel framework that jointly tackles the above challenges. Specifically, to address the Composition Pattern Complexity problem, we design a composition-aware tail adapter, which can model the shared composition patterns across bundles and adaptively integrate these patterns into bundle representations. Specifically, we employ an adaptive integration mechanism that minimizes pattern influence for head bundles while enhancing long-tail bundle representations, which ensures that tail bundles can benefit from shared composition patterns while preserving the effective representations of frequently interacted bundles. To tackle the Long-tail Noisy Feature Integration, we introduce a prototype learning module. Through mapping bundle representations from dual views into a set of learnable prototypes, this module achieves robust feature integration by comparing bundle assignments in a shared prototype space. This module enables effective representation learning for long-tail bundles despite their limited and biased interaction data. Our contributions are summarized as follows:

• Problem. We explicitly address the long-tail challenge in bundle recommendation, a challenging problem of significant impact in real-world scenarios.
• Method. We propose CALBRec, adaptively leveraging item composition patterns across different bundles to enhance long-tail bundle recommendation.
• Experiments. Extensive experiments on three public datasets validate that our method achieves significant improvements, particularly for long-tail bundles.

The code is available at https://anonymous.4open.science/r/ CALBRec-A291.

2 RelatedWorks

Bundle Recommendation. Prior work in bundle recommendation has mainly progressed along matrix factorizationbased methods [Pathak et al., 2017; Cao et al., 2017a] and graph learning-based methods [Deng et al., 2020; Chang et al., 2020; Bai et al., 2019]. Particularly, bundle recommendation research has explored various tasks, including accurate recommendation of existing bundles [Cao et al., 2017b], personalized bundle creation [Deng et al., 2021], leveraging conversational approaches [He et al., 2022], increasing diversity [Jeon et al., 2023], and improving recommendations for new bundles [Jeon et al., 2024]. However, the long-tail distribution challenge in bundle recommendation, which is prevalent in real-world scenarios, remains under-investigated. Existing methods typically assume sufficient historical interactions for all bundles, making it difficult to learn effective representations for tail bundles with limited interactions, leading to biased and underrepresented bundle features. Our work addresses this limitation by developing a framework specifically designed for long-tail bundle recommendations.

Graph-based Long-tail Methods. The problem of longtailed distributions in recommendation systems has motivated extensive research, with significant efforts made to address the issue of insufficient interactions for tail items [He et al., 2020; Liu et al., 2021; Deng et al., 2020; Zheng et al., 2022b; Chang et al., 2023]. Existing solutions typically fall into two categories: data augmentation methods and auxiliary information-based methods. Data augmentation methods aim to adjust the training data distribution to enhance the interaction features of tail items. Approaches such as resampling [Zhang and Hong, 2021; Park and Tuzhilin, 2008] balance the interaction distribution, while synthetic data generation methods [Tang et al., 2020; Wu et al., 2019] create additional samples to augment the characteristics of tail items. In contrast, auxiliary information-based methods focus on enriching the features of tail items by incorporating supplementary data, such as item attributes [Zhu et al., 2020; Wu et al., 2024] or textual descriptions [Liang et al., 2020; Zheng et al., 2022a], to improve their representation in the recommendation process. However, existing long-tail methods are limited in bundle recommendation scenarios, as they primarily focus on single-item interactions without considering the complex item compositions within bundles. Our work addresses this gap by developing a framework that jointly models both user-bundle interactions and bundle composition patterns in the long-tail context.

3 Preliminary

In this section, we present the problem formulation for bundle recommendation and the foundational model structure with dual-view design and embedding propagation mechanisms.

3.1 ProblemFormulation

Given a set of users U = {u1, u2, · · · , uM}, a set of bundles B = {b1, b2, · · · , bN}, and a set of items I = {i1, i2, · · · , iO}, where M, N, and O are the number of users, bundles, and items, respectively. The user-bundle interactions, user-item interactions, and bundle-item affiliations are denoted as XM×N = {xub|u ∈ U, b ∈ B}, YM×O = {yui|u ∈ U, i ∈ I}, and ZN×O = {zbi|b ∈ B, i ∈ I}, respectively. xub, yui, zbi ∈ {0, 1}, where 1 represents an interaction between the user-bundle or user-item pair, or the item belongs to a certain bundle. Note that since we deduplicate the historical bundle and item interactions for each user, each element of X and Y is a binary value rather than an integer. In addition, X and Y are separately generated, where users are allowed to directly interact with both bundles and individual items. Therefore, X and Y contain different information, which heuristically enables the cooperative effect between the two different views. The goal of bundle recommendation task is to learn a model from the historical {X, Y, Z} and predict the unseen user-bundle interactions in X.

3.2 Base Model

The base model employs a two-view graph structure to learn representations through user-bundle interactions and useritem interactions. Both views utilize LightGCN [He et al., 2020] for embedding propagation, formalized as:

where e(k) v represents node embeddings at layer k, and Nv denotes the neighbor set of node v.

User-bundle View. For user-bundle interactions, at layer k, user and bundle embeddings h(k) u and h(k) b are obtained through LightGCN propagation with their respective neighbor sets Nu and Nb. The final embeddings are computed by:

where hu, hb ∈ Rd represent user and bundle embeddings. User-item View. Similarly for user-item interactions, embeddings a(k) u and a(k) i are obtained through LightGCN propagation with neighbor sets N ′u and Ni, respectively. The final embeddings are computed by:

where au, ai ∈ Rd represent user and item embeddings, respectively. For each bundle b, its representation ab is obtained by averaging embeddings of its constituent items with ab = 1 |N ′ b | ∑i∈N ′ b ai, N ′ b denotes the set of items in bundle b.

Prediction Scores. Based on the embeddings from both views, we compute:

where hub and aub denote the matching scores in user-bundle view and user-item view, respectively.

4 Methodology

In this section, we outline the overall architecture of the CALBRec framework (as shown in Figure 2) and provide a detailed description of its key components. The main idea of CALBRec is leveraging composition patterns between head and tail bundles to enhance bundle representations for long-tail bundle recommendation. Specifically, we develop a composition-aware long-tail adapter that enhances tail bundle representations by modeling shared composition patterns and integrating them into bundle representations through an adaptive fusion mechanism. Furthermore, we propose to map the bundle representations into a set of learnable prototypes and introduce a prototype learning module to combine the composition patterns with interaction signals for tail bundles. These modules are integrated into a unified learning framework.

4.1 Composition-aware Long-tail Adapter

We first model the shared compositional patterns across bundles and then personalize feature fusion, enabling tail bundles to benefit from patterns learned from head bundles while preserving the strong features of frequently interacted bundles.

Compositional Pattern Modeling and Adaptive Integration. We first construct a global feature vector t, which is learnable and shared across all bundles to capture general composition patterns. Then, for each bundle b, we devise a personalization function ϕ that transforms t into a localized feature vector tb by considering both the representation of bundle b and its constituent items:

where hkb is the representation of bundle b in the user-bundle view at layer k, and aki represents the feature of item i in the user-item view that constitutes bundle b.

To personalize the global patterns to each bundle, we use a personalized function with complementary adaptation operations, while adjusting the degree of pattern integration:

where γ kb ∈ Rdk modulates the importance of different pattern dimensions through scaling, and βkb ∈ Rdk provides bundle-specific adjustments through shifting. The scaling factor is centered around one through (γ kb + 1) to maintain the original pattern information while allowing for adaptive adjustments. These adaptation vectors are computed as:

where Wk,∗ ∗ ∈ Rdk×dk are learnable parameters that transform the composition context into adaptation signals. This design enables each bundle to flexibly harness shared patterns, where the scaling operation governs the degree of pattern integration, and the shifting operation allows for targeted adjustments based on the compositional context.

However, not all bundles have the same need for complementary features. Head bundles with abundant interactions have already learned reliable representations from rich user feedback, while tail bundles with limited interactions can benefit more from the compositional patterns shared with similar head bundles. In the following, we will describe how CALBRec achieves differentiated control over feature fusion for head and tail bundles.

Frequency-aware Enhancement Control. To achieve this differentiated control, we design a frequency-aware enhancement mechanism that applies distinct strategies to head and tail bundles. For head bundles, we maintain their well-learned representations by minimizing additional pattern influence:

This constraint ensures that the final representations of head bundles primarily rely on their rich interaction signals.

For tail bundles, we enhance their representations through controlled pattern integration: ˆab = ab + λtb. Here, ab denotes the original representation and λ controls the degree of enhancement. This enhancement allows tail bundles to incorporate useful patterns while preserving their original characteristics, with the user-item view score computed using the enhanced representation for tail bundles as aub = aTu ˆab.

Through this frequency-aware control mechanism, we can effectively improve the representation quality of tail bundles while maintaining the strong performance of head bundles.

4.2 Dual-view Prototype Learning

To mitigate the impact of noise in user-bundle interaction data, we introduce a prototype learning module to map the bundle representations into a set of learnable prototypes and further combine the composition patterns with interaction signals for tail bundles.

First, we construct K trainable prototype vectors C ∈ RK×D to represent shared features at the bundle level, where D is the feature dimension. Instead of directly mapping bundle embeddings to the prototypes with maximum dot similarity, we use a soft assignment approach to assign bundles to multiple prototypes, which can mitigate the impact of mismatched mappings for biased representations of tail bundles. Specifically, we introduce assignment matrix Q ∈ RB×K , where each element Qb,m represents the assignment strength between the bundle b and prototype m. Then, we introduce the following constraints:

where 1B and 1K represent vectors of ones in the number of bundles and prototypes, respectively. These dual constraints ensure that each prototype receives equal total assignment weight from bundles and each bundle distributes equal weights across prototypes. This balanced assignment mechanism mitigates representation bias for tail bundles by avoiding forced one-to-one prototype mappings and allowing them to leverage interaction patterns from other bundles assigned to the same prototypes.

The solution satisfying these constraints can be obtained through the Sinkhorn-Knopp algorithm [Cuturi, 2013], which achieves fast convergence through iterative row and column normalization. Specifically, we establish initial assignment relationships by computing dot-product similarity between bundle embeddings and prototype vectors. Then we obtain Q through the Algorithm 1.

For the obtained assignment matrix Q, we further convert it into a probability distribution through a temperature-scaled softmax operation:

where Pb,m represents the probability of assigning bundle b to prototype m, and the temperature parameter τ controls the concentration of the distribution: a smaller τ produces more concentrated distributions that help reduce noise impact, while a larger τ encourages uniform distributions to preserve more association information.

The final prototype assignments are optimized through a contrastive objective detailed in Section 4.3.

Algorithm 1 Sinkhorn-Knopp Algorithm

Require: Initial probability matrix Q ∈ RB×K

Ensure: The optimal assignment matrix ˆQ

• 1: while not converged do
• 2: Row normalization: Q←Qdiag( 1 BQ1K )
• 3: Column normalization: Q← diag( 1 KQ⊤1B )Q
• 4: end while
• 5: ˆQ←Q

4.3 Model Optimization

Recommendation Objective. The Bayesian Personalized Ranking (BPR) loss [Rendle et al., 2012] is used as the main loss. The prediction score combines both views as ˆ yub = hub + aub, where hub and aub are defined in Eq. (1). The BPR loss is formulated as:

where pdata represents the user-bundle interaction distribution, b+ and b- denote the interacted and non-interacted bundles, respectively.

Composition-aware Adaptation Objective. In order to achieve the personalized composition pattern integration proposed in Section 4.1, we introduce a corresponding optimization objective. The loss function is defined as:

where Ib is the indicator function for head bundles (1 for head, 0 for tail), ℓ denotes the number of network layers, and tk-1 b is the pattern representation obtained through the adaptive fusion mechanism in Section 4.1 at layer k - 1.

This objective implements the frequency-aware enhancement control proposed in Section 4.1 by minimizing the pattern representation norm of head bundles: for head bundles, the influence of additional patterns is limited through L2 norm constraints; for tail bundles, no constraints are imposed, allowing them to fully utilize pattern enhancement obtained through adaptive fusion.

Prototype Contrastive Objective. Following Section 4.2, let Qh and Qa denote the assignment matrices for bundles from the user-bundle view and user-item view, respectively. The corresponding probability distributions after temperature-scaled softmax normalization are denoted as Ph and Pa , respectively. We formulate the prototypical contrastive loss between views as:

The cross-entropy loss encourages bundle representations from both views to be consistently assigned to the shared prototype space, where each prototype serves as a learnable center for capturing common patterns across bundles. By minimizing the discrepancy between assignment distributions Qh and Ph , we enable bundles with similar characteristics to be mapped to similar prototypes, regardless of their interaction frequencies. The bidirectional consistency constraints (hb → ab and ab → hb) further ensure that the learned prototypes effectively integrate information from both interaction patterns and compositional structures. The overall prototype contrastive loss is formulated as:

Overall Objective. The final objective function combines all three objectives:

where λ and γ are hyperparameters that balance different objectives. This multi-objective optimization framework both ensures overall recommendation performance and addresses the long-tail challenge through the two specially designed objectives. The hyperparameters are tuned on the validation set to balance the contribution of different objectives.

5 Experiments

In this section, we first introduce the experimental settings and then compare CALBRec with state-of-the-art methods. We further analyze model components through ablation studies and examine key parameter effects.

5.1 Experimental Setup

Datasets. We selected three real-world bundle recommendation datasets that represent diverse bundle recommendation scenarios: Youshu [Chen et al., 2019b] for book bundles; NetEase [Cao et al., 2017a] for music playlists, and iFashion [Chen et al., 2019c] for fashion outfits. The detailed statistics of the datasets are listed in Table 1. These datasets were selected for their varying bundle sizes and interaction sparsity patterns, enabling comprehensive evaluation of longtail bundle recommendation. Following [Ma et al., 2022; Chang et al., 2020; Deng et al., 2020], we split each dataset into training/validation/testing sets at a 7:1:2 proportion.

Evaluation Metrics. We evaluated the recommendation performance using Recall@k and nDCG@k. These metrics were chosen because Recall@k directly measures hit rate in top recommendations while nDCG@k considers ranking quality [Deng et al., 2020]. We set k to 20. Following the Pareto Principle [Box and Meyer, 1986; Reed, 2001], we separated bundles into head (top 20% most frequent) and tail (remaining 80%) groups to analyze model performance with different interaction frequencies. To ensure reliability, we conducted each experiment 5 times with different random initializations and reported average performance with standard deviations.

Baseline Methods. To fully demonstrate the effectiveness of CALBRec on long-tail bundle recommendation, we compared CALBRec with both bundle recommendation methods and long-tail methods.

Bundle Recommendation Methods:

• BundleNet [Deng et al., 2020]: This method builds a userbundle item tripartite graph, leverages GCN to learn the representations, and applies multi-task learning.
• BGCN [Chang et al., 2020; Chang et al., 2023]: This method that leverages graph convolutional networks to capture the complex interactions in bundle recommendation.
• CrossCBR [Ma et al., 2022]: A bundle recommendation method that integrates cross-domain information to improve recommendation performance.
• Coheat [Jeon et al., 2024]: A method designed for cold-

start settings, which aims to handle the challenge of recommending new bundles with limited historical data.

Long-tail Recommendation Methods:

• Over-sampling [Amirruddin et al., 2022]: This strategy samples from tail items and is more common in practice since user feedback data is highly valuable.
• Down-sampling [He et al., 2008]: Tail items remain unchanged and the head items are down-sampled.
• MeLU [Lee et al., 2019]: A meta-learning approach for cold-start prediction, extended to implicit feedback.
• MIRec [Zhang et al., 2021]: A transfer learning framework for long-tail recommendation in two-tower mode.
• MGL [Liu et al., 2020]: A meta-graph framework for long-tail recommendation via auxiliary item relations and popularity-aware contrastive meta-learning to address skewness and ensure consistency.

Hyper-parameter Settings. For all methods, the embedding size was set as 64, Xavier normal initialization was adopted, the models were optimized using Adam optimizer with the learning rate 0.001, and the batch size was set as 2048. We applied a grid search to optimize hyperparameters. The parameters of baselines were set following their official implementations and optimal configurations reported in the corresponding papers. All the models were trained using Pytorch and NVIDIA Titan-V GPUs.

5.2 Overall Performance

Comparison with Bundle Recommendation Methods. Table 2 presents the comparative analysis between CALBRec and baseline methods across three datasets. The results demonstrate that CALBRec achieves strong performance on tail bundles while maintaining competitive results across head bundles and overall metrics. Among baseline methods, contrastive learning improves performance as shown by CrossCBR over BGCN, while dual-view models (CrossCBR, CoHeat) outperform the single-view BundleNet. Building on these insights, CALBRec adopts a graph-based dual-view architecture with contrastive learning. CALBRec significantly outperforms existing methods in handling the performance gap between head and tail bundles. Specifically on the Youshu dataset, CrossCBR shows a Recall@20 gap of 0.277 between head and tail bundles, indicating that learning from imbalanced interaction data leads to strong head bundle performance but poor tail bundle recommendations. CALBRec addresses this limitation, significantly narrowing the performance gap by introducing composition pattern modeling, which achieves a 23.7% improvement in Recall@20 for tail bundles compared to CrossCBR and substantially reduces the disparity between head and tail bundle recommendations.

Comparison with Long-tail Methods. The results show that CALBRec consistently surpassed the baselines across the tail-bundle scenario, verifying its superiority. Specifically, CALBRec achieves significant improvements of 28.46% on average on Youshu and NetEase datasets, while showing moderate improvements on iFashion. This performance differential can be explained by the dataset characteristics (Table 1): iFashion has substantially smaller bundles (3.86 items) while Youshu and NetEase contain larger bundles (37.03 and 77.80 items, respectively). The results suggest that our composition pattern modeling and prototype learning mechanisms are particularly effective when applied to bundles with richer compositional structures, as evidenced by the superior performance on Youshu and NetEase.

5.3 Ablation Study

To validate the effectiveness of each component of our model, we conducted ablation studies comparing the full model with four variants: (1) no-adapter: which eliminated the composition-aware long-tail adapter module; (2) no-prototype: which removed dual-view prototype learning module; (3) no-sharing: which replaced the global pattern in composition-aware adapter module with independently sampled random vectors from standard normal distribution; (4) no-comp: which removed bundle-specific pattern personalization process by eliminating item vectors in Eq. 2. Figure 3 presents comparative results on Youshu and NetEase datasets in the long-tail scenario. CALBRec demonstrates consistent superior performance across all variants. Notably, removing the long-tail adapter resulted in the most significant degradation, with Recall@20 decreasing by 16.4% and 11.3% on Youshu and NetEase respectively, highlighting the importance of composition-aware long-tail adapter in leveraging shared patterns between head and tail bundles.

5.4 Effect of the Parameter

Impact of the Number of Prototypes. As shown in Figure 4(a), the impact of prototype numbers varies across datasets. Specifically, the Youshu dataset shows notable performance variations, with accuracy declining beyond 500 prototypes. This performance degradation occurs because Youshu is relatively small (Table 1), where excess prototypes begin to memorize individual bundle characteristics rather than extracting generalizable composition patterns. Conversely, the larger NetEase and iFashion datasets maintain robust performance with increased prototypes. Based on these empirical findings, we configure K as 300, 2000, and 2000 for Youshu, NetEase and iFashion, respectively.

Impact of the Ratio of Head Bundles. To investigate the impact of the head-tail ratio, we evaluate CALBRec by varying the head ratio from 10% to 50% on three datasets, as shown in Figure 4(b). The experimental results reveal performance degradation when the ratio increases to 50%, with Youshu showing the largest decline of 7.61% from its peak at 20%, followed by NetEase with 2.62% and iFashion with 0.51%. The high ratio of 50% forces the model to treat a substantial portion of tail bundles as head features, undermining our strategy of distinctive enhancement for head and tail bundles described in Section 4.1. Our empirical results indicate that a moderate ratio of 20% achieves the optimal balance between preserving head representations and enhancing tail features across all evaluated datasets.

6 Conclusion

In this paper, we addressed the challenge of long-tail bundle recommendation and proposed the Composition-Aware Long-tail Bundle Recommendation (CALBRec) framework. CALBRec aims to leverage the inherent composition patterns across different bundles as valuable signals for recommendation enhancement. Specifically, we first designed a novel composition-aware long-tail adapter that effectively captures the shared composition patterns and enhances individual bundle representations adaptively. Additionally, a prototype learning module was introduced to facilitate robust feature integration against the noise in sparse interaction data. Extensive experiments on three public datasets demonstrated that CALBRec significantly improves recommendation performance, particularly for long-tail bundles. In the future, we will explore the potential of leveraging composition patterns in more tasks such as personalized bundle creation, diversity enhancement, and conversational bundle recommendations.

Acknowledgments

This work was supported in part by the National Key R&D Program of China(Grant No.2023YFF0725001),in part by the National Natural Science Foundation of China(Grant No.92370204),in part by the guangdong Basic and Applied Basic Research Foundation(Grant No.2023B1515120057).in part by Guangzhou-HKUST(GZ) Joint Funding Program(Grant No.2023A03J0008), Education Bureau of Guangzhou Municipality.