arXiv:2606.09623v1 [cs.LG] 8 Jun 2026
Constrained user–item allocation for e-commerce marketing campaigns
Maja Lindström∗ Department of Computing Science Integrated Science Lab Umeå University SE-901 87 Umeå, Sweden [email protected]
Natalija Glisovic† KTH Royal Institute of Technology Stockholm, SE-114 28, Sweden
Jan von Pichowski‡ Chair of Machine Learning for Complex Networks Center for Artificial Intelligence and Data Science (CAIDAS) University of Würzburg DE-97070 Würzburg, Germany Tommy Löfstedt§ Department of Computing Science Umeå University SE-901 87 Umeå, Sweden
Martin Rosvall¶ Department of Physics Integrated Science Lab Umeå University SE-901 87 Umeå, Sweden
Abstract When running marketing campaigns, retailers must decide which products to promote and which users to target. These decisions are inherently coupled: effective campaigns match users and items with strong mutual affinity into non-overlapping groups of predefined sizes. However, existing approaches assume predefined campaign structure or decouple item selection from user assignment, and cannot discover campaign groupings directly from joint interaction patterns. We therefore formalize this campaign problem as auto-targeting: jointly selecting users and items to construct multiple disjoint campaigns. To solve this combinatorial problem, we propose three complementary strategies: (i) constrained spectral biclustering to find dense regions in the user–item affinity matrix, (ii) greedy local search with pairwise swaps for combinatorial refinement, and (iii) a multi-armed bandit framework to escape local optima through exploration. We evaluate these methods on a synthetic dataset, the Amazon Reviews benchmarks, and large-scale proprietary commercial data, and compare the results to simulated annealing as a baseline. The results show that biclustering consistently achieves the highest campaign quality, lift, and fairness scores. While biclustering runs efficiently on smaller datasets, its runtime increases substantially on very large ones, where bandit-based methods instead offer a scalable alternative. ∗ ORCID: 0009-0009-9224-4646 † ORCID: 0009-0002-8554-2513 ‡ ORCID: 0009-0001-1541-6477 § ORCID: 0000-0001-7119-7646 ¶ ORCID: 0000-0002-7181-9940
1
Introduction
Matching users to items is central in e-commerce marketing. When retailers run promotional campaigns through advertising, personalized promotions, or email marketing, they face a combinatorial assignment problem. The goal is to assign users and items to campaigns such that each campaign contains a cohesive cohort, while simultaneously ensuring that each user and item appears in only one campaign [1]. Existing approaches address this problem in a decoupled manner, first selecting products to promote and then identifying suitable audiences [2, 3]. Other lines of work span client selection [4, 5, 6] and budget allocation across campaigns [2, 7, 8]. When products are fixed in advance, assignment is typically handled using graph-based audience expansion [3, 9] or large-scale bipartite matching [10, 11]. More recent work combines offline optimization with real-time pacing, where campaign allocations are planned in advance and adjusted during delivery to meet budget and exposure targets [12, 13]. Other work learns joint user–item representations that can support both recommendation and advertising objectives [14, 15]. However, these methods decouple item selection from user assignment and break a bidirectional dependency: the best users for a campaign depend on which items it contains, and the best items depend on who will be interested in them. Searching one side while holding the other fixed misses groupings that only emerge from joint optimization over interaction patterns. In contrast to existing work, we propose a novel matching task, which we refer to as auto-targeting, that jointly optimizes user and item assignments without predefined campaigns, allowing the campaign structure to emerge from the underlying affinities. In modern e-commerce systems, users and items are represented as vector embeddings learned from historical interactions, such as purchases or clicks [16]. These embeddings capture latent user preferences and product characteristics in a shared space, where proximity reflects affinity [17]. We formulate the problem as jointly partitioning user and item embeddings into matched clusters that maximize within-cluster affinity, where each cluster corresponds to a distinct campaign. To solve this problem, we propose three complementary methods. (i) Biclustering identifies dense regions in the user–item affinity matrix via matrix decomposition. (ii) Alternating greedy optimization with local swap refinement performs combinatorial local search over assignments. (iii) A multi-armed bandit formulation treats campaigns as arms, with exploration through UCB1 or Thompson Sampling, allowing the search to escape local optima. In addition to the three proposed approaches, we use simulated annealing as a baseline against which to assess their performance. The contributions of this work are as follows: • We formalize auto-targeting as a joint optimization problem over users, items, and campaign structure, a task with direct commercial relevance that existing methods do not address. • We adapt three complementary approaches (constrained spectral biclustering, greedy local search, and multi-armed bandits) and evaluate them on a synthetic benchmark, the Amazon Reviews datasets, and large-scale proprietary commercial data. • We show that biclustering consistently achieves the highest quality, lift, and fairness across all settings, while bandit-based methods offer a scalable alternative on large-scale data.
2
Related Work
Most work on campaign assignment treats either the item set or the audience as fixed, then optimizes the remaining side [4, 5, 3, 10]. Some recent methods learn joint user–item representations to support both recommendation and advertising objectives [14, 15]. Others combine budget-level optimization with real-time delivery adjustments [12, 13]. However, all these approaches assume a predefined campaign structure or decouple which items appear in a campaign from which users receive it. Jointly partitioning both users and items into disjoint campaigns without predefined structure has not been addressed. The best groupings only emerge when both sides are optimized together. We drew on three lines of related work and adapted each to this coupled setting. Spectral co-clustering. Spectral co-clustering methods jointly partition rows and columns of an affinity matrix via singular value decomposition (SVD) relaxations of bipartite graph cuts followed by k-means rounding [18, 19, 20, 21, 22]. These methods uncover block structure efficiently, but none 2
imposes constraints on cluster size or enforces disjoint coverage. Because size limits and disjoint coverage are central to campaign design, we extend spectral co-clustering by oversampling candidate biclusters, pruning oversized candidates, and selecting the best non-overlapping subsets. Combinatorial optimization. Greedy maximization of submodular set functions yields provable approximation guarantees for a broad class of assignment algorithms [23, 24, 25]. For graph bisection and clustering problems, local search methods with pairwise swaps and alternating optimization have been effective [26, 27, 28]. Both methods assume fixed sets of items or clusters. To construct user and item groups simultaneously under size constraints, we alternate greedy allocation between users and items, refine assignments with capacity-aware swaps, and keep the best assignment across iterations. Bandit learning. Multi-armed bandit algorithms such as UCB1 [29] and Thompson Sampling [30] balance exploration and exploitation. Extensions handle non-stationary rewards [31, 32] and couple arms through shared capacity budgets [33, 34], but none handles non-stationarity and couplings simultaneously. In this setting, each campaign arm’s reward shifts as opposing assignments change, and all arms compete for the same capacity budget. We adapt bandit methods to this coupled, non-stationary setting by maintaining rolling-window statistics, enforcing campaign capacity limits, and alternating between user and item assignment phases.
3
Auto-Targeting
We define auto-targeting as the problem of jointly constructing campaigns by assigning users and items into multiple disjoint groups under both group and global constraints. Each campaign consists of a set of users and items, and the objective is to partition them into disjoint groups that maximize within-campaign affinity subject to the given constraints. This leads to a combinatorial optimization problem that is not directly addressed by existing methods. Compared to traditional settings, we do not require campaigns to be predefined and the user–item assignments are fully coupled: both the group structure and the assignments should be inferred jointly rather than determined sequentially. 3.1
Problem Formulation
Let K denote the number of campaigns, and for each k ∈ {1, . . . , K}, let Ik and Uk denote the sets of assigned items and users, respectively. We then propose the problem max
{Ik ,Uk }K k=1
K X X X
affinity(i, u)
(1)
k=1 i∈Ik u∈Uk
subject to Ik ∩ Ij = ∅, ∀k ̸= j, Uk ∩ Uj = ∅, ∀k ̸= j, |Ik | = I, ∀k, τmin ≤ |Uk | ≤ τmax , ∀k,
where I denotes the number of items per campaign, and τmin and τmax define lower and upper bounds on the number of users per campaign. The first two constraints ensure that each item and each user is assigned to at most one campaign. The third constraint enforces a fixed number of items per campaign, while the fourth bounds the number of users per campaign. This asymmetry is motivated by practice, where campaigns are typically built around a curated product assortment of fixed size (e.g., a themed collection), while the target audience can vary within operational bounds determined by budget, channel capacity, or delivery constraints. In practice, additional campaign-specific constraints could be applied, such as restricting which items are eligible for a given campaign. This results in a large-scale combinatorial optimization problem, where exact solutions are typically infeasible. The focus is therefore on computing high-quality approximate solutions under practical runtime constraints. 3.2
Combined User–Item Embedding Space
While the formulation in Equation (1) does not depend on a specific embedding, the affinity score is usually derived from distances in a joint embedding space in practice, where higher affinity 3
corresponds to closer proximity between users and items. In this work, users, u, and items, i, are represented in a shared D-dimensional embedding space, with embedding vectors vu , vi ∈ RD . As a result, users and items that form coherent clusters in the embedding space are expected to be assigned to the same campaign. For the synthetic data, embeddings are constructed to align with predefined campaigns, ensuring that performance is independent of representation quality. For the public benchmark and the industrial data, embeddings are learned from historical interaction data and capture latent user preferences and item characteristics in a shared space. Details on the embedding construction are provided in Appendix Appendix B. 3.3
Affinity Values of User–Item Combinations
The affinity function in Equation (1) measures the similarity between users and items in the shared embedding space. Let U ∈ RNu ×D denote a matrix of user embeddings and I ∈ RNi ×D a matrix of item embeddings. The affinity matrix, A ∈ RNi ×Nu , is defined as Aiu = exp(Ii · UTu ), where Aiu represents the affinity between item i and user u. The dot product, Ii · UTu , captures similarity between embeddings, with larger values indicating stronger alignment. The exponential transformation ensures non-negative affinities and increases the contrast between high- and low-affinity pairs. The resulting matrix, A, defines a weighted bipartite graph between items and users and serves as the basis for any subsequent optimization method. 3.4
Affinity-Based Evaluation Metrics
Campaign assignments are evaluated using metrics computed from the affinity matrix, A: utility (total affinity), along with normalized and distributional measures to compare across methods. Utility measures the total affinity across all campaigns, Utility =
K X X X
Aiu .
(2)
k=1 u∈Uk i∈Ik
Utility corresponds directly to the objective in Equation (1). However, it depends on the number of assigned users and items, and may favor methods that assign more users within the allowed constraints. To account for the number of users and items, quality (the average affinity) is computed within each campaign, X X 1 Qualityk = Aiu , (3) |Uk | |Ik | u∈Uk i∈Ik
and captures the coherence of user–item assignments independent of the campaign size. Lift normalizes quality relative to the global average affinity, Liftk =
1 Nu Ni
Qualityk PNi PNu i=1
u=1 Aiu
,
(4)
and measures the improvement over a random assignment. A lift greater than 1 indicates abovechance affinity. Finally, the Gini coefficient measures how utility is distributed across users. Let vu denote the average affinity of user u to the items in their assigned campaign. The Gini coefficient is PNu PNu v=1 |vu − vv | G = u=1 P . (5) Nu 2Nu u=1 vu A value of 0 indicates uniform utility across users, while higher values indicate that a small subset of users accounts for most of the total affinity. These metrics capture complementary aspects of performance, including overall utility, assignment quality, and the distribution of utility across users.
4
Approaches for Auto-Targeting
4.1
Constrained Spectral Biclustering
We built the proposed method on spectral co-clustering [18], which partitions a bipartite affinity matrix into groups of rows and columns with high mutual association. In this setting, this corresponds 4
to identifying candidate campaigns consisting of items and users with high affinity. The goal is not only to identify biclusters, but to construct feasible campaigns under minimum and maximum size constraints. To this end, we adapt spectral co-clustering in three steps: (i) we oversample the number of biclusters to generate a diverse set of candidates, (ii) we prune each bicluster to satisfy size constraints, and (iii) we rank and select a subset of high-quality, non-overlapping campaigns. The proposed method begins by applying spectral co-clustering to the affinity matrix A ∈ RNi ×Nu . Given a target number of campaigns k, we compute k ′ = αk biclusters, where α ≥ 2 is an overpartitioning factor that ensures a sufficiently large candidate pool after pruning for size constraints and overlap removal. This yields a set of candidate biclusters B = {B1 , . . . , Bk′ }, where each bicluster Bc consists of a set of item indices, Rc , and user indices, Cc . The campaign constraints are enforced through post-processing. Biclusters that did not satisfy the minimum size constraint are discarded. For biclusters that exceed the maximum size, items and users are pruned based on their average affinity within P the bicluster. Specifically, given a bicluster, (Rc , Cc ), item scores are computed as sr = |Cc |−1 u∈Cc Aru , with r ∈ Rc , and the top items according to sr P are retained. b c denote the resulting item set. User scores are then computed as su = |R b c |−1 Let R b c Aru , r∈R with u ∈ Cc , and the top users are retained to obtain Cbc . This sequential pruning introduces a mild order dependency, as items are selected before users. In practice, however, we found this one-pass refinement to be stable and computationally efficient. After pruning, biclusters are discarded that no longer satisfy the minimum size constraints. The remaining candidates are ranked by their b c | |Cbc |)−1 P b P b Aru , where Bc denotes the pruned bicluster, (R b c , Cbc ). density δ(Bc ) = (|R r∈Rc u∈Cc Finally, the top k biclusters are selected as the resulting campaigns according to δ(Bc ). Algorithm details are found in Appendix Appendix A.4. 4.2
Multi-Armed Bandit Optimization
Another approach to refine campaign assignments is to use a multi-armed bandit that treats each campaign as an arm. The core challenge is to balance exploitation, assigning entities to their highest-affinity campaigns, and exploration of alternative configurations that may yield higher overall affinity [35]. The setting in this work departs from classical bandit formulations in two ways: rewards are endogenous, as the affinity of an entity to a campaign depends on the current composition of that campaign’s members, and arms are coupled through shared capacity constraints [33]. We address these challenges using exponentially discounted reward statistics and capacity-aware allocation. The optimization procedure alternates between user and item assignment phases, with the initial item assignment randomized to break symmetries. The affinity of entity e to campaign k is computed as the sum of affinities between e and the currently assigned entities of the complementary type: when assigning users, affinities are summed over the items in campaign k, and vice versa. Assignments are then based on bandit-augmented scores, s̃ek = sek + bonusk , where sek denotes the affinity of entity e to campaign k, computed as the sum of affinities between e and the currently assigned entities of the complementary type (see Equation (6) in Appendix A.1), and the bonus term encourages exploration of under-visited campaigns. We consider two strategies. p The first adapts UCB1 [29] by adding to the affinity score a confidence bound of the form s̄k 2 ln t/nk , where s̄k is the mean absolute score across entities and nk is the number of assignments to campaign k. The scaling by s̄k ensures that the exploration bonus is commensurate with the reward magnitude. The second uses Thompson Sampling [30], where each score is perturbed by additive Gaussian noise εk ∼ N (0, σk s̄k ), where σk = (nk + 1)−1/2 , so that the perturbation shrinks as campaign k receives more assignments. In both cases, entities are processed in descending order of s̃ek , and when a campaign reaches capacity, remaining entities fall through to their next-best option. To adapt to changing compositions, the bandit statistics are discounted via exponential decay. The optimization procedure runs for at most nrounds iterations, with early stopping to detect convergence. Full algorithmic details, including the UCB1 and Thompson Sampling formulations, decayed updates, and regret decomposition, are provided in Appendix Appendix A.3. 4.3
Greedy Local Search Optimization
In the greedy local search approach, assignments are computed using a greedy procedure with capacity constraints. For each entity, the change in score is evaluated when assigning it to each campaign, and entities are processed in order of decreasing score improvement using a priority queue. 5
This ensures that high-impact assignments are made early while respecting constraints such as the maximum number of users or items per campaign. Entities that can not be assigned without violating constraints are left unassigned. To improve the solution further, a local search step is applied based on pairwise swaps (Appendix Appendix A.2). For two entities assigned to different campaigns, it is evaluated whether exchanging their assignments increase the objective, and the swap is performed if it leads to an improvement while simultaneously maintaining feasibility. This step helps to escape poor local optima that arise from the greedy assignment. The algorithm is initialized with a random assignment of items that satisfies capacity constraints. Updates are then alternating between user and item updates for at most t iterations, where each iteration consists of one user-assignment pass followed by one item-assignment pass. 4.4
Sequential Simulated Annealing
The discrete assignments induce an exponentially large feasible space, making exact optimization impractical. We therefore use simulated annealing [SA; 36] to approximate solutions to the combinatorial optimization problem in Equation (1). We decompose the global problem into K sequential subproblems. At step k, a campaign, (Ik , Uk ), is constructed by optimizing over the remaining unassigned users and items under the cardinality constraints. Once selected, its users and items are removed from subsequent steps, ensuring disjointness across campaigns. For a fixed campaign, a feasible state is a bicluster, (Ik , Uk ), that satisfies the size constraints. We define a neighborhood of each state using add, remove, and swap operations that preserve feasibility. Starting from a random feasible initialization, SA perform a stochastic local search with temperaturecontrolled acceptance. Given a candidate move with objective change ∆, the move is accepted if ∆ > 0, or with probability exp(∆/T ), where T follows an exponential cooling schedule (see Appendix appendix A.7). This allows the search to escape local optima early on, while gradually becoming more greedy as the temperature decreases.
5
Results and Discussion
The objective of this evaluation is not to recover a global optimum, which is computationally infeasible at the scales we consider, but to identify methods that achieve high-quality campaign assignments under practical runtime constraints. We therefore assess performance as a trade-off between solution quality and computational efficiency. All methods are evaluated on synthetic data, public benchmarks, and proprietary commercial datasets. The synthetic data provides a controlled setting with a known structure, while the Amazon benchmarks enable reproducibility on real-world interaction data. The proprietary datasets are further used to assess performance in practical deployment scenarios. The dataset characteristics and the experimental setting can be found in Appendix Appendix A.5. Across all datasets (Table 1), biclustering consistently achieves the highest lift and quality, while also producing more balanced assignments as reflected in lower Gini coefficients. In terms of runtime (Table 2), the bandit-based methods are generally the most efficient on larger datasets, while greedy optimization is slower due to the repeated local search steps. Biclustering exhibits a more variable profile: it is highly efficient on smaller datasets, but became computationally expensive as the dataset sizes increase. For example, biclustering completed in 72 seconds on IKEA but required over 3,900 seconds on the interior design dataset, illustrating that its runtime scales steeply with the size of the affinity matrix. The relative performance differences depend on the structure of the underlying interaction data. For the Amazon datasets, biclustering shows a clear advantage, particularly for Musical Instruments, where the less restrictive filtering (70% threshold) retains a broader and less structured interaction matrix compared to the 5-core filtering (retaining only users and items with at least five interactions) used for Baby Products. In contrast, for Baby Products, 5-core filtering retains only users and items with at least five interactions, removing low-activity entities and producing a denser matrix with more shared interaction patterns. In this setting, the underlying structure is easier to recover, and the performance gap between methods is smaller. This suggests that when the underlying structure is easier to recover, simpler optimization strategies can perform competitively. 6
On the IKEA dataset, all methods follow similar trends, with biclustering achieving the best overall performance. However, absolute scores are lower compared to the Amazon datasets, reflecting weaker affinities in the interaction data and less pronounced cluster structure. For the interior design dataset, biclustering substantially outperforms the other methods, achieving more than double the lift and quality. This indicates that capturing joint user–item structure is particularly important in largescale commercial settings. At the same time, all methods exhibit relatively high Gini coefficients, suggesting that a small subset of users contributes disproportionately to the overall performance. Biclustering mitigates this effect, producing more balanced assignments. SA performs substantially worse than the proposed methods across all datasets (Table 1), while also incurring substantially higher computational cost (Table 2). A likely explanation is that the local, single-entity moves used in SA are not well suited to the high-dimensional and combinatorial structure of the user–item assignment problem. As a result, the method struggles to make meaningful progress within a reasonable runtime, particularly on large datasets. 5.1
Synthetic Data
To evaluate the campaign assignment algorithms under controlled conditions, a synthetic datasets is generated that had a known underlying campaign structure. d-dimensional user and item embeddings are drawn from a multivariate Gaussian centered at a campaign-specific vector. A small variance
Table 1: Results across all datasets. Stochastic methods report mean ± 95% confidence intervals over 10 runs. Biclustering is deterministic and thus run once. Simulated Annealing is run once with a fixed random seed due to its high computational cost. The best values per dataset are shown in bold. Dataset Method Lift ↑ Gini ↓ Quality ↑ IKEA
Greedy Biclustering Bandit Thompson Bandit UCB1 Sim. Annealing
2.22 ± 0.04 2.32 2.23 ± 0.03 2.24 ± 0.03 1.11
0.03 ± 0.01 0.02 0.03 ± 0.01 0.03 ± 0.01 0.15
11.2 ± 0.2 11.7 11.3 ± 0.2 11.3 ± 0.2 5.6
Baby Products
Greedy Biclustering Bandit Thompson Bandit UCB1 Sim. Annealing
170 ± 1 176 168 ± 2 173 ± 1 93
0.37 ± 0.01 0.17 0.36 ± 0.01 0.33 ± 0.01 0.44
1513 ± 10 1575 1497 ± 17 1541 ± 9 832
Musical Instruments
Greedy Biclustering Bandit Thompson Bandit UCB1 Sim. Annealing
91 ± 12 152 89 ± 9 88 ± 11 3
0.45 ± 0.04 0.37 0.43 ± 0.03 0.51 ± 0.04 0.69
777 ± 102 1305 762 ± 73 756 ± 96 28
Interior Design
Greedy Biclustering Bandit Thompson Bandit UCB1 Sim. Annealing
71 ± 3 183 71 ± 7 72 ± 5 2
0.61 ± 0.04 0.53 0.58 ± 0.06 0.64 ± 0.05 0.64
605 ± 23 1562 611 ± 60 612 ± 42 4
Table 2: Runtime in minutes (except Simulated Annealing which is reported in hours). Stochastic methods report mean results with 95% confidence intervals, computed over 10 runs. IKEA Baby Products Musical Instruments Interior Design Greedy Biclustering Bandit Thompson Bandit UCB1 Sim. Annealing
7.4 ± 2.3 1.2 4.5 ± 0.9 1.6 ± 0.1 6.5 (h)
56.2 ± 0.1 5.1 7.9 ± 1.6 5.8 ± 0.4 37.4 (h)
7
74.3 ± 15.7 62.8 51.9 ± 5.5 45.0 ± 3.0 95.3 (h)
63.7 ± 10.9 66.2 68.6 ± 9.1 54.6 ± 4.0 98.9 (h)
Synthetic Data
Bandits (Thomp.) Bandits (UCB1)
embedding dim. 0
Lift=1.31, Gini=0.007 Lift=1.28, Gini=0.027
1.0
Biclustering
Greedy
Sim. Annealing
Lift=1.23, Gini=0.051 Lift=1.31, Gini=0.005 Lift=1.23, Gini=0.051 Lift=1.31, Gini=0.003
0.5 0.0 −0.5 −1.0 −1.0−0.5 0.0 0.5 1.0 −1.0−0.5 0.0 0.5 1.0 −1.0−0.5 0.0 0.5 1.0 −1.0−0.5 0.0 0.5 1.0 −1.0−0.5 0.0 0.5 1.0 −1.0−0.5 0.0 0.5 1.0 embedding dim. 1 embedding dim. 1 embedding dim. 1 embedding dim. 1 embedding dim. 1 embedding dim. 1
Figure 1: Small-scale 2-d synthetic dataset with 25 items and 250 users including 3 campaigns with 5 items and 50 users. Random baseline campaigns are compared across the given methods.
1.0
1.0
0.8
0.8
0.8
0.6
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0.0 0.00 1,000 0.05 1,250 1,500 0.10 0.15 To 1,750 t a l 2,000 e 0.20 c n I t e 2,250 0.25 r ia m s 2,500 0.30 Va 2,750 3,000 0.35
0.0 1,000 15,000 1,250 20,000 1,500 25,000 To 1,750 s r t a l 2,000 e 30,000 I t e 2,250 Us m s 2,500 35,000 o t a l 2,750 T 3,000 40,000
AMI
1.0
0.2
Bandit (Thompson) Bandit (UCB1) Greedy Biclustering (Tuned)
0.0 0.00 15,000 0.05 20,000 0.10 0.15 To 25,000 t a l 30,000 e 0.20 nc Us 0.25 r ia e r s 35,000 0.30 Va 40,000 0.35
(a) Users vs. variance with 1,500 items.
(b) Items vs. variance with 30,000 users
(c) Users vs. items
Figure 2: Performance on synthetic data measured by AMI as a function of cluster variance and problem size. The campaigns are constrained to contain at most 1,500 users and 5 items. ensures that entities within the same campaign are closely aligned, leading to a high affinity within campaigns. To simulate realistic sparsity and background noise, additional items and users are drawn randomly from a uniform distribution. These background entities are thus not strongly affiliated with any campaign, creating a mixture of dense campaign clusters embedded within a larger population of noisy entities. It is possible that the added noise could lead to a better campaign compared to the initial synthetic campaigns. Consequently, the ground truth campaigns are considered an approximation of the best campaigns. Notably, for the small-case synthetic data in Figure 1, biclustering found those better campaigns. The Gini score for biclustering improved compared to the initial campaigns. Figure 2 presents an evaluation of the methods’ performances as the problem becomes progressively more difficult by increasing the cluster variance and the number of users and items. As exemplified in Figure 1, doubling the variance would lead to overlaps between the green and blue campaigns. A higher variance thus reduces the separation between campaigns, while additional users and items introduce noise, making the underlying structure more difficult to recover. However, we observe in Figure 2 that biclustering is particularly robust to increasing cluster variance, maintaining strong performance even as campaign separation diminishes. In comparison, increasing the number of background users or items has a comparatively smaller effect on performance. This suggests that overlaps between campaigns (controlled by variance) is more detrimental than increasing the number of background users and items, even as the problem scales in both dimensions.
8
Greedy
Biclustering
Bandits (Thompson Sampling)
Bandits (UCB1 Sampling)
40
80
75
75
20
60
50
50
0
40
25
25
20
20
0
0
40
0
25
25
60
20
50
50
80
40
75
100
60 80
60
40
20
0
20
40
60
60
40
20
0
100
20
75 100 80
60
40
20
0
20
40
60
40
20
0
20
40
60
Figure 4: A t-SNE representation of user and item embeddings for the Amazon Musical Instruments dataset, colored by campaign assignment. Each panel shows the result of a different method.
Leather Pads Replacement for Saxophone
Saxophone Ligature Tenor Sax
Saxophone Cleaning and Care
Metal Sax Mouthpiece w/ Optimum Ligature Kit
Alto Saxophone Pack
Figure 5: Qualitative analysis of campaigns produced by biclustering on the Amazon Musical Instruments dataset. Each row shows the five items assigned to a single campaign, with shortened product titles and representative images.
5.2
Analysis
To understand why biclustering consistently outperforms the other methods, we examine the structure of the embedding space, the qualitative coherence of the top campaign, and the distributional properties of the affinity matrix for the Amazon Musical Instrument dataset. More details and results for the other datasets can be found in Appendix Appendix C. Campaign structure in embedding space. Figure 4 shows a joint t-SNE projection of user and item embeddings, colored by campaign assignment. Under this projection, biclustering appears to produce more compact and well-separated clusters, while the greedy and bandit methods yield more diffuse groupings with greater inter-campaign overlap. As t-SNE is a qualitative visualization, the quantitative results in Table 1 provide a more reliable basis for comparison. Qualitative campaign coherence. Figure 5 shows the five items assigned to the highest-quality campaign based on metric performance. Although the items span different product sub-categories, such as cleaning supplies, mouthpiece accessories, and replacement parts, they all serve the common goal of owning and maintaining a saxophone. This suggests that biclustering recovers campaigns aligned with latent user intent rather than surface-level product taxonomy. Top 10% 100.0% of mass
Cumulative % of total affinity mass
100 Uniform (no concentration) Affinity concentration. The structure of the affinity maTop 5% 80.6% of mass trix can help to further explain the results. As seen in 80 Figure 3, the distribution of the affinity values is heav60 ily right-skewed: the top 1% of (i, u) pairs account for Top 1% 38.2% of mass 38% of total affinity mass, and the top 10% account for 40 essentially all of it. At the same time, per-user preferences are diffuse, for the median user, the single highest-affinity 20 item captures only 0.5% of their total affinity. Because 0 0.1% 1% 10% 100% the signal is globally concentrated in a small fraction of Top X% of (item, user) pairs (log scale) pairs but no single pair is dominant for any given user, methods that operate on individual entities, such as greedy Figure 3: Affinity mass concentration assignment, lack a strong signal to act on. Biclustering, by across (item, user) pairs contrast, aggregates many weak per-user affinities across a block of users and items simultaneously, recovering coherent high-affinity regions that would not be apparent from a single entry alone.
9
5.3
Limitations and Future Work
While the proposed framework provides a flexible approach to joint user–item campaign assignment, several limitations remain. The methods are heuristic and do not provide guarantees on solution quality, and the greedy and bandit-based methods may converge to local optima. Scalability remains a challenge for very large datasets, as biclustering becomes computationally expensive as the affinity matrix grows. The formulation also assumes a static setting with fixed user–item affinities, whereas in practice user preferences and item availability evolve over time. Finally, we consider a simplified constraint structure; incorporating overlapping audiences, budget limits, or fairness requirements across user groups remains an open challenge. This work is motivated by commercial marketing applications, where automated campaign assignment could improve the relevance and efficiency of promotional targeting. While this has potential benefits for both retailers and users, it also raises concerns around privacy, as the framework relies on learned user embeddings derived from behavioral data. Deployment in practice should be accompanied by appropriate transparency and fairness considerations, particularly to avoid reinforcing existing disparities in how different user groups are targeted.
6
Conclusion
We formalized campaign assignment as a joint optimization problem over users, items, and campaign structure, a setting existing methods do not address. We adapted spectral co-clustering, greedy local search, and bandit-based optimization to this coupled setting with capacity constraints, and the results reveal a consistent pattern: explicitly modeling user–item affinity drives substantial gains in campaign quality. Constrained biclustering best recovers coherent high-affinity regions, consistently outperforming alternative approaches. Bandit-based methods offer improved scalability on large datasets, highlighting a trade-off between solution quality and runtime. These findings show that recovering the joint user–item structure is key for effective campaign design.
7
Acknowledgments
We thank Theodor Jonsson and Christian Persson at Siftlab AB for helpful discussions and help with generating the embeddings. M.L. and N.G. were supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP)[37], funded by the Knut and Alice Wallenberg Foundation. J.P. acknowledges funding by the German Ministry of Research, Technology and Space (BMFTR) under grant agreement No. 16IS24072E (COMFORT). M.R. was supported by the Swedish Research Council under grant 2023-03705 The computations were enabled by resources provided by the Swedish National Infrastructure for Computing at the High Performance Computer Center North (HPC2N) in Umeå, Sweden, partially funded by the Swedish Research Council through grant agreement no. 2018-05973, and by the National Academic Infrastructure for Supercomputing in Sweden (NAISS), partially funded by the Swedish Research Council through grant agreement no. 2022-06725.
10
References [1] Yong-Hyuk Kim and Yourim Yoon. A note on mathematical modelling of practical multicampaign assignment and its computational complexity, 2009. [2] Tereza Sedlářová Nehézová, Roman Kvasnička, Helena Brožová, Robert Hlavatý, and Lucie Kvasničková Stanislavská. A robust optimization approach to budget optimization in online marketing campaigns. Central European Journal of Operations Research, 2025. [3] Md Mostafizur Rahman, Daisuke Kikuta, Yu Hirate, and Toyotaro Suzumura. Graph-based audience expansion model for marketing campaigns. In Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR ’24, pages 2970–2975, New York, NY, USA, 2024. Association for Computing Machinery. [4] Fabrice Talla Nobibon, Roel Leus, and Frits C.R. Spieksma. Optimization models for targeted offers in direct marketing: Exact and heuristic algorithms. European Journal of Operational Research, 210(3):670–683, 2011. [5] Mikhail Bilenko and Matthew Richardson. Predictive client-side profiles for personalized advertising. In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD ’11), pages 413–421, San Diego, CA, USA, 2011. Association for Computing Machinery. [6] Björn Rafn Gunnarsson, Seppe vanden Broucke, and Jochen De Weerdt. Optimizing marketing campaign targeting using uncertainty-based predictive modelling. In Proceedings of the 2019 IEEE International Conference on Data Mining Workshops (ICDMW), pages 326–332, Beijing, China, 2019. IEEE. [7] Soheil Eshghi, Victor M. Preciado, Saswati Sarkar, Santosh S. Venkatesh, Qing Zhao, Raissa D’Souza, and Ananthram Swami. Spread, then target, and advertise in waves: Optimal budget allocation across advertising channels. IEEE Transactions on Network Science and Engineering, 7(2):750–763, 2020. [8] Benjamin Han and Jared Gabor. Contextual bandits for advertising budget allocation. In Proceedings of the 17th ACM International Workshop on Data-Driven Advertising and Targeting (ADKDD ’20), New York, NY, USA, 2020. Association for Computing Machinery. [9] Chenyi Zhuang, Ziqi Liu, Zhiqiang Zhang, Yize Tan, Zhengwei Wu, Zhining Liu, Jianping Wei, Jinjie Gu, Guannan Zhang, Jun Zhou, and Yuan Qi. Hubble: An industrial system for audience expansion in mobile marketing. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD ’20), pages 2455–2463, New York, NY, USA, 2020. Association for Computing Machinery. [10] Aranyak Mehta. Online matching and ad allocation. Foundations and Trends in Theoretical Computer Science, 8(4):265–368, 2013. [11] Denis Xavier Charles, Max Chickering, Nikhil R. Devanur, Kamal Jain, and Manan Sanghi. Fast algorithms for finding matchings in lopsided bipartite graphs with applications to display ads. In Proceedings of the ACM Conference on Electronic Commerce (EC ’10), pages 121–128, New York, NY, USA, 2010. Association for Computing Machinery. [12] Xiao Cheng, Chuanren Liu, Liang Dai, Peng Zhang, Zhen Fang, and Zhonglin Zu. An adaptive unified allocation framework for guaranteed display advertising. In Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining, WSDM ’22, pages 132–140, New York, NY, USA, 2022. Association for Computing Machinery. [13] Jian Xu, Kuang-chih Lee, Wentong Li, Hang Qi, and Quan Lu. Smart pacing for effective online ad campaign optimization. In Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD ’15), pages 2217–2226, New York, NY, USA, 2015. Association for Computing Machinery. [14] Xiangyu Zhao, Xudong Zheng, Xiwang Yang, Xiaobing Liu, and Jiliang Tang. Jointly learning to recommend and advertise. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD ’20, pages 3319–3327, New York, NY, USA, 2020. Association for Computing Machinery. 11
[15] Qifang Zhao, Tianyu Li, Meng Du, Yu Jiang, Qinghui Sun, Zhongyao Wang, Hong Liu, and Huan Xu. Unimatch: A unified user-item matching framework for the multi-purpose merchant marketing. In Proceedings of the 39th IEEE International Conference on Data Engineering, pages 3309–3321, Piscataway, NJ, USA, 2023. IEEE. [16] Yunke Qu, Tong Chen, Quoc Viet Hung Nguyen, and Hongzhi Yin. Budgeted embedding table for recommender systems. In Proceedings of the 17th ACM International Conference on Web Search and Data Mining, WSDM ’24, pages 557–566, New York, NY, USA, 2024. Association for Computing Machinery. [17] Walid Bendada, Guillaume Salha-Galvan, Thomas Bouabça, and Tristan Cazenave. On the consistency of average embeddings for item recommendation. In Seventeenth ACM Conference on Recommender Systems, RecSys ’23, 2023. [18] Inderjit S Dhillon. Co-clustering documents and words using bipartite spectral graph partitioning. In Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, pages 269–274, 2001. [19] Hongyuan Zha, Xiaofeng He, Chris Ding, Horst Simon, and Ming Gu. Bipartite graph partitioning and data clustering. In Proceedings of the 10th International Conference on Information and Knowledge Management (CIKM ’01), pages 25–32, New York, NY, USA, 2001. Association for Computing Machinery. [20] Inderjit S. Dhillon, Yuqiang Guan, and Brian Kulis. Kernel k-means, spectral clustering and normalized cuts. In Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD ’04), pages 551–556, New York, NY, USA, 2004. Association for Computing Machinery. [21] Tao Wu, Austin R. Benson, and David F. Gleich. General tensor spectral co-clustering for higher-order data. In Proceedings of the 30th Conference on Neural Information Processing Systems (NeurIPS 2016), pages 1–9, Barcelona, Spain, 2016. Curran Associates, Inc. [22] Wenqing Su, Xiao Guo, Xiangyu Chang, and Ying Yang. Spectral co-clustering in multi-layer directed networks. Computational Statistics & Data Analysis, 198:107987, 2024. [23] George L. Nemhauser, Laurence A. Wolsey, and Marshall L. Fisher. An analysis of approximations for maximizing submodular set functions—I. Mathematical Programming, 14(1):265–294, 1978. [24] Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne VanBriesen, and Natalie Glance. Cost-effective outbreak detection in networks. In Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD ’07), pages 420–429, New York, NY, USA, 2007. Association for Computing Machinery. [25] Andreas Krause and Daniel Golovin. Submodular function maximization. In Tractability: Practical Approaches to Hard Problems, pages 71–104. Cambridge University Press, 2014. [26] Brian W. Kernighan and Shen Lin. An efficient heuristic procedure for partitioning graphs. The Bell System Technical Journal, 49(2):291–307, 1970. [27] Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, and Angela Y. Wu. A local search approximation algorithm for k-means clustering. Computational Geometry, 28(2-3):89–112, 2004. [28] Pranjal Awasthi, Maria-Florina Balcan, and Konstantin Voevodski. Local algorithms for interactive clustering. In Proceedings of the 31st International Conference on Machine Learning (ICML ’14), pages 550–558, Beijing, China, 2014. JMLR.org. [29] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47(2):235–256, 2002. [30] William R Thompson. On the likelihood that one unknown probability exceeds another. Biometrika, 25(3/4):285–294, 1933. 12
[31] Qinyi Chen, Negin Golrezaei, and Djallel Bouneffouf. Non-stationary bandits with autoregressive temporal dependency. In Advances in Neural Information Processing Systems 36 (NeurIPS 2023), pages 7895–7929, New York, NY, USA, 2023. Curran Associates, Inc. [32] Han Qi, Fei Guo, and Li Zhu. Thompson sampling for non-stationary bandit problems. Entropy, 27(1):51, 2025. [33] Shipra Agrawal and Nikhil R. Devanur. Bandits with concave rewards and convex knapsacks. In Proceedings of the Fifteenth ACM Conference on Economics and Computation (EC ’14), pages 989–1006, New York, NY, USA, 2014. Association for Computing Machinery. [34] Shang Liu, Jiashuo Jiang, and Xiaocheng Li. Non-stationary bandits with knapsacks. In Advances in Neural Information Processing Systems 35 (NeurIPS 2022), volume 35 of Advances in Neural Information Processing Systems, New Orleans, LA, USA, 2022. Neural Information Processing Systems Foundation. [35] S. Ji. Balancing exploration and exploitation: An analytical review of three classical bandit algorithms. Academic Journal of Science and Technology, 19(2):531–535, 2026. [36] Scott Kirkpatrick, C Daniel Gelatt Jr, and Mario P Vecchi. Optimization by simulated annealing. science, 220(4598):671–680, 1983. [37] http://wasp-sweden.org. Addressing sparsity in multi-market retail: A vision-language [38] Theodor Jonsson. model enriched transformer for robust personalization. Dissertation retrieved from: https://urn.kb.se/resolve?urn=urn:nbn:se:umu:diva-241504, 2025. [39] Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. In Journal of Machine Learning Research (JMLR), pages 2579–2605, Tilburg, The Netherlands / Toronto, Canada, 2008. JMLR.org.
A
Implementation Details
This appendix provides implementation details that complement the method descriptions in Section 3. All three algorithms share the same affinity computation, Aiu = exp(Ii · U⊤ u ). A.1
Score Aggregation
The affinity of entity e to campaign k is computed as a dense matrix product. Letting D ∈ {0, 1}Ni ×K and D′ ∈ {0, 1}Nu ×K be the current item- and user-assignment indicator matrices, we form
Su = A⊤ D ∈ RNu ×K , Si = A D′ ∈ RNi ×K , (6) u i where column k of Su (resp. Si ) gives sk (resp. sk ) for every user/item. The full affinity matrix, A, is pre-computed before the optimization begins. A.2
Greedy Local Search: Allocation and Swap Details
Heap-greedy allocation Entities are processed with a min-heap (negated scores). Each entity is initialized with its best feasible campaign and, once assigned, is re-enqueued with its next-best option. Stale heap entries, where the stored score differs from the current score by more than 10−6 , are discarded. Campaign capacities are tracked with a count vector. Capacity checks are only required when an entity first enters a campaign, since swaps between entities within the same campaign leave capacities unchanged. Sliding-window local search At the start of each pass, entity indices are shuffled. For an entity e1 at position p, positions p + 1, . . . , p + W (mod N ) are considered as swap candidates, where we set the window size to W = 128. A swap (e1 , k1 ) ↔ (e2 , k2 ) is accepted when the entities belong to different campaigns, the joint score improves, sk2 (e1 ) + sk1 (e2 ) > sk1 (e1 ) + sk2 (e2 ), and capacity constraints remain satisfied. Each local search phase runs for at most P = 10 passes, with early stopping triggered after 3 consecutive passes with no accepted swaps. 13
Outer loop The algorithm alternates between user and item assignment for at most T = 10 outer iterations. Early stopping is applied if the improvement in the objective fell below ϵ = 10−4 for P = 3 consecutive iterations. The best solution encountered across all iterations is retained. A.3
Bandit Optimization: Algorithmic Details
The bandit approach follows the same alternating structure as the greedy method but replaces heapgreedy allocation with bandit-augmented scoring. We ran the optimization for up to T = 50 outer iterations, with early stopping triggered after 10 consecutive iterations without improvement below ϵ = 10−4 . UCB1 bonus scale The mean score magnitude used in the UCB1 bonus is defined as 1 X s̄k = |sek | + 10−8 , Ne e where Ne is the number of entities being assigned. This scaling ensures that the exploration bonus is commensurate with the reward magnitude. The exploration coefficient c is treated as a hyperparameter and selected via a sweep over c ∈ {0.1, 0.5, 1.0, 2.0, 5.0, 10.0}, choosing the value that yields the highest final quality. Thompson Sampling noise For Thompson Sampling, a noise vector εk ∈ RNe is drawn from N (0, σk s̄k ),
with σk = (nk + 1)−1/2 ,
where the +1 term ensures a well-defined variance when campaign k has received no assignments (nk = 0). The count nk is incremented after each assignment to campaign k. Greedy assignment with bandit scores Entities are inserted into a max-heap keyed by s̃ek∗ , where k ∗ = arg maxk s̃ek . When a campaign reaches capacity, its augmented P score P is2 set to −∞ and the entity is re-enqueued with its next-best option. Bandit statistics (nk , rk , rk ) are updated using the unaugmented reward, sek . Non-stationarity To account for non-stationarity, we optionally apply exponential decay with window parameter w, updating statistics each round by a factor (1 − 1/w). Regret decomposition As described in Section 4.2, the cumulative regret satisfies R(T ) ≤ Ruser (T ), since item reassignment can only improve or maintain the score obtained after user assignment. The gap quantifies how often item updates correct suboptimal user assignments. A.4
Constrained Spectral Biclustering: Algorithm Details
We implement spectral co-clustering using sklearn.cluster.SpectralCoclustering with random_state=0. Given a target of k campaigns, we generate k ′ = αk candidate biclusters, where α is selected via a sweep over α ∈ {1, 2, 3, 4, 5, 6}, choosing the value that yields the highest final quality after constraint enforcement. Each candidate bicluster is pruned to satisfy minimum and maximum size constraints by selecting the rows and columns with highest average affinity to the opposing side. Biclusters that do not satisfy minimum size constraints are discarded. The remaining candidates are ranked by their density, and the top k non-overlapping biclusters are selected as campaigns. Unlike the greedy and bandit approaches, biclustering is a single-pass procedure (T = 1) and does not iteratively optimize the objective in Eq. 1, as it is based on a normalized-cut relaxation. A.5
Experimental Settings
All stochastic methods (Greedy, Bandit with Thompson Sampling, and Bandit with UCB1) are run 10 times, and results are reported as mean ± 95% confidence intervals. Biclustering is deterministic given random_state=0 and is therefore run once. 14
Table 3: Dataset characteristics. Users and items refer to counts after preprocessing. Campaign constraints specify the number of campaigns K, items per campaign I, and, U , the range of users per campaign. Dataset Users Items Filter Source K I U Synthetic IKEA Baby Products Musical Instruments Interior Design
15 000–40 000 49 962 150 777 361 313 500 000
1 500 23 551 36 002 149 515 121 700
— 5-core 5-core 70 % —
Generated Proprietary Amazon Amazon Proprietary
5 5 5 5 5
5 5 5 5 5
up to 1 500 200–1 000 5 000–20 000 3 000–10 000 2 000–8 000
For each method, we construct k = 5 campaigns, with dataset-specific constraints on the number of users and items per campaign. The affinity matrix A is precomputed and stored in memory throughout optimization. All experiments are conducted on an Intel Xeon E7-8860v4 system with 3072 GiB RAM per node. Runtime measurements are reported separately. A.6
Dataset characteristics
Table 3 summarizes the dataset characteristics for the experiments conducted. A.7
Simulated Annealing: Algorithmic Details
Our approach employs a variant of simulated annealing tailored for the discrete nature of the targeting problem. The algorithm maintains temperature-dependent exploration via probabilistic acceptance of moves. State Representation and Neighborhood The state of a campaign is represented as a tuple (I, U ) of item and user indices. The neighborhood is defined through three mutation operations: • Add: Randomly select an available item or user and add it to the current set. • Remove: Randomly remove an item or user from the current set (if constraints allow). • Swap: Remove one item/user and add a different available one. The algorithm randomly selects add/remove/swap with equal probability (subject to feasibility), ensuring diverse exploration of the solution space. Acceptance Criterion At iteration t, given temperature Tt and current score st , a move to state with score s′t is accepted if: ∆s ′ st > st or U(0, 1) < exp , where ∆s = s′t − st (7) Tt This is the standard Metropolis criterion, enabling uphill moves with decreasing probability as temperature decreases. Cooling Schedule and Early Stopping The temperature follows a geometric cooling schedule: Tt = T0 · αt
(8)
where T0 = 2.0 is the initial temperature and α = 0.9999995 is the cooling rate. The algorithm terminates when either: 1. Tt drops below Tmin = 0.001, or 2. After Lmin = 6 × 106 iterations, if relative score improvement over the last P = 100,000 iterations is below tolerance ϵ = 10−5 . To enable early stopping with useful intermediate estimates while allowing selective refinement, we employ a two-phase optimization: 15
Phase 1: Quick Initial Pass Each campaign is optimized for L1 = 1 × 106 iterations, providing preliminary solutions. This phase provides baseline performance estimates for all campaigns within reasonable wall-clock time. Phase 2: Adaptive Refinement Campaigns are sorted by Phase 1 scores in descending order. Each campaign then undergoes refinement for an additional L2 = 5 × 106 iterations. Crucially, each campaign is refined independently with access to the full original user/item pools, minus only the selections already made by previously-refined campaigns in Phase 2. This design ensures that high-performing campaigns are refined with maximal available resources, avoiding the degradation that occurs when resource pools are sequentially depleted.
B
Embedding Construction
Our formulation assumes that users and items are represented in a shared embedding space, where proximity reflects affinity. While the optimization framework itself is agnostic to how these embeddings are obtained, their quality directly impacts the resulting campaign assignments. For the real-world datasets, we adopt embeddings constructed using an interaction-driven recommendation framework as described in [38]. In this approach, each item i ∈ I is represented by a learnable embedding vector ei ∈ RD , while user representations are derived from historical interaction data. Specifically, a user embedding zu is computed by aggregating the embeddings of recently interacted items, followed by normalization. This yields a contextual representation that reflects the user’s current preferences. Affinity between users and items is computed via inner products in the embedding space, which capture compatibility between user preferences and item characteristics. This is consistent with standard embedding-based recommendation models, where observed interactions are used to learn representations that assign higher similarity to relevant user–item pairs. To address sparsity and cold-start effects, the embedding pipeline incorporates auxiliary item representations derived from multimodal data. In particular, visual and textual features are combined using a vision–language model to produce semantic meta-embeddings, which are used to initialize or refine item embeddings when interaction data is limited. This ensures that even infrequent or newly introduced items are placed meaningfully in the shared space. For the synthetic experiments, embeddings are constructed directly to reflect a known groundtruth campaign structure. Users and items within the same campaign are sampled from Gaussian distributions centered around campaign-specific latent vectors, ensuring high within-campaign affinity and controlled separation between campaigns.
C
Campaign Exploration
C.1
t-SNE Visualization
To visually assess whether the proposed methods produce geometrically coherent campaigns, we project user and item embeddings jointly into two dimensions using t-SNE [39]. User and item representations share the same latent space, exp(uT i), thus a joint projection reveals whether each method produces geometrically coherent campaign clusters. We apply PCA pre-reduction to 10 dimensions before running t-SNE to reduce computational cost. t-SNE is preferred over a linear projection such as PCA for the final visualization because it preserves local neighborhood structure, making cluster separation visually interpretable. Figure 6 show the resulting projections for the Amazon Baby Products datasets (Amazon Musical Instruments in section 5.2 . We randomly subsample 15,000 users and 8,000 items in each case for ease of comparison. Biclustering produces the most compact and well-separated clusters, consistent with its quantitative performance (Tables1). The greedy and bandit-based methods yield more diffuse clusters with greater inter-campaign overlap, particularly for Thompson Sampling. 16
Greedy 80
80
60
60
40
40
20
20
0
0
20
20
Biclustering
Bandits (Thompson Sampling)
80
60
40
20
0
20
40
60
60
40
40
20
20 0 20
20
40
40
60
60
80
0
40
40
Bandits (UCB1 Sampling)
80
80
60
40
20
0
20
40
60
80
60
40
20
0
20
40
80
60
40
20
0
20
40
Figure 6: A t-SNE projection of user and item embeddings for the Amazon Baby Products dataset, colored by campaign assignment. Each panel shows the result of a different method.
C.2
Qualitative Analysis
We perform a qualitative analysis of the campaign produced by spectral biclustering, the best performing method. From the top performing campaign, based on the metrics defined in 3, we extract the product titles and images of the five assigned items. Results for Amazon Musical Instruments can be found in Section 5.2 and Figure 7 show the results of the Amazon Baby Products datasets. For Amazon Baby Products, the campaign is centered around diapers and related accessories. The assigned items include cleaning pads, a diaper bag, a storage organizer frequently associated with diaper use in customer reviews, and training pants. Similar to Amazon Musical Instruments, the products here span across multiple sub-categories (e.g. storage, cleaning), but share a common goal of managing diaper needs. These examples illustrate that the campaigns identified by biclustering are not only quantitatively strong in terms of affinity metrics but also qualitatively interpretable, an important property for deployment in real-world marketing systems where campaign coherence is crucial.
Changing Pad Liners
Storage Organizer Container Bin
Arm and Hammer Diaper Bag
Diaper Change Organizer
Training Pants
Figure 7: Qualitative analysis of campaigns produced by biclustering on the Amazon Baby Products dataset. Each row shows the five items assigned to a single campaign, with shortened product titles and representative images.
D
Properties of the Affinity Matrix
We analyze the affinity matrix A ∈ RNi ×Nu , where Aiu = exp Ii · U⊤ u
for item embedding Ii and user embedding Uu . This affinity matrix experiments uses a matrix of 8,000 items × 15,000 users, yielding 120M entries from the Amazon Musical Instrument dataset. Diffuse per-user preferences Unlike recommendation settings where users have a small number of dominant preferences, campaign affinity is spread thinly across items. For the median user, their single highest-affinity item captures only 0.5% of their total affinity, the top 100 items capture 14.5% (Figure 8). This motivates a group-based approach where no individual (i, u) pair is informative in isolation, but biclustering can aggregate weak signals into coherent campaign cohorts. 17
100
% of total user affinity captured
80
60
40
20
0
0
20
40 60 Number of top items (per user)
80
100
Figure 8: Per-user affinity concentration: median fraction of total user affinity captured by top-k items (shaded band = IQR). Biclustering recovers the signal To validate that our algorithm exploits genuine structure rather than noise, we measure the global rank of the affinity values selected by biclustering. Across K = 5 campaigns, 92.4% of selected cells rank in the global top 1%, while covering only 0.0038% of the matrix. Campaign-level lifts relative to the global mean range from 60× to 171×, confirming that spectral co-clustering reliably identifies high-signal submatrices. These properties show that campaign assignment operates in a regime of sparse, concentrated signal within a large low-affinity background where it favors methods like biclustering that reason over matrix blocks rather than individual entries, consistent with the results across all datasets.
E
Progression Comparison
We evaluate the quality-versus-time progression on the Amazon baby products dataset in Figure 9. For each stochastic method (Greedy, Thompson Sampling, UCB1), we run 10 independent trials and record quality after each optimization step, defined as an outer iteration for Greedy and a round of assignments for the bandit methods. We plot all trajectories to assess convergence speed and variability. Biclustering is deterministic and non-iterative, so we instead evaluate it by subsampling 10% to 100% of users and items and recomputing the affinity matrix for each subset. The curves reveal markedly different optimization dynamics across methods. Thompson Sampling and UCB1 converge rapidly, reaching near-peak quality within the first 50–100 seconds, with tight trajectory bundles indicating low variance across trials. Greedy is considerably slower and we truncate the plot at 1,500 seconds for readability. Biclustering follows a fundamentally different pattern: rather than iterating to convergence, its quality grows steadily with the fraction of users and items included, reaching its maximum on the full dataset at around 310 seconds.
18
Greedy
Quality
1600 1400
1400
1200
1200
1000
1000
800
800
600
600
400
400
200
200
0
0 0
200
400
600
1600
Quality
Thompson
1600
800
UCB1
1000
1200
1400
0
200
400
600
0
200
400
600
1600
1400
1400
1200
1200
1000
1000
800
800
600
600
400
400
200
200
0
800
1000
1200
1400
800
1000
1200
1400
Biclustering
0 0
200
400
600
800
Time (s)
1000
1200
1400
Time (s)
Figure 9: Quality progression of the Amazon baby products dataset over time.
19