Choosing Which Users Bridge Two Domains: Coverage-Aware Anchor Selection for Cold-Start Transfer

Cross-domain recommenders help a new user in a sparse domain (say, music) by borrowing what we know about them from a rich domain (say, movies). They learn the translation between the two domains from a small set of "overlapping" users who have histories in both. Every method in this area treats that overlap set as a given random sample. Papers then report robustness as the sample is randomly shrunk to 20% or 5%. In practice a platform often controls which users it asks to link accounts, and the semi-supervised learning literature shows that which seeds you label can matter more than how many. This note proposes to choose the overlapping users deliberately. The selection rule minimizes how far each future cold-start user sits from the nearest bridge user in the source-domain embedding space. The test is whether this closes much of the gap caused by scarce overlap, on its own and when combined with methods that smooth the learned translation.

The core idea fits in two sentences. A translation learned from a few bridge users is only trustworthy near those users, so its error on a new user grows with the distance to the closest bridge user and with how sharply the translation bends. Prior work reduces the bending (SCDR). We propose to reduce the distance by picking bridge users that cover the population of cold-start users, and to measure whether the two fixes add up.

Core Claim

Let $x_u$ be user $u$'s source-domain embedding and $y_u$ their true target-domain representation. Suppose, as an idealization, that $y = g(x)$ for an unknown map $g$ with Lipschitz constant $L_g$, meaning $g$ changes its output by at most $L_g$ times any change in its input. Let $f$ be the learned translation, with Lipschitz constant $L_f$. Let $s(u)$ be the bridge user in the selected set $S$ closest to $u$ in source space. The triangle inequality gives

$$\|f(x_u) - y_u\| \;\le\; \|f(x_{s(u)}) - y_{s(u)}\| \;+\; (L_f + L_g)\,\|x_u - x_{s(u)}\|.$$

Averaged over cold-start users, the second term is the Lipschitz factor times a facility-location cost, the average distance from each user to their nearest selected bridge user. The first term is training error, which is small when the model fits its seeds.

This decomposition says three things. SCDR, which applies sharpness-aware minimization (training that seeks flat regions of the loss), attacks $L_f$. Random seed sampling leaves the coverage term to chance. Minimizing that coverage term over the known population of source-only users is exactly the facility-location objective that INSITE used for medical-image seeds. The claim to test is that coverage-aware selection reduces cold-start error beyond random or activity-based selection at equal budget, and that the gain is additive with flatness regularization rather than redundant.

For contrastive models such as CDRIB, there is no explicit mapping $f$, and the relation between domains is noisy rather than functional. We therefore treat the bound as a motivating heuristic. Its prediction, that per-user error rises with distance to the nearest seed, is directly checkable.

Position Relative to Prior Work

Several papers motivate the gap, because they show overlap scarcity is the binding constraint but treat the overlap set as fixed. CDRIB aligns domains with a variational graph encoder and an information-bottleneck regularizer, which discards information not shared across domains. It reports robustness when overlap is randomly reduced to 20% and names zero-overlap extension as open. CDR-Adapter trains small contrastive adapters between frozen models and holds up at 5% overlap. DisCo splits users into intent channels to avoid transferring unrelated tastes. None of these asks which overlapping users should be in the set. Our proposal leaves their architectures untouched and changes only the seed set they receive.

Two papers constrain the design. SCDR shows that mappings trained on tiny overlap sets land in sharp minima, and that flattening helps most at the highest sparsity. That makes it the natural competitor and potential complement, since it targets the other factor in the bound. PSML finds that in social-network alignment, dense neighborhoods pull anchors and their neighbors into indistinguishable "fuzzy regions" when anchors are scarce. It fixes this by implanting artificial pseudo-anchors, placed with a meta-learner trained on an anchor-rich auxiliary network. This suggests random seeds, which concentrate where users are dense, may be doubly wasteful. Our approach differs from PSML in that it selects among real candidate anchors and needs no auxiliary labeled network.

INSITE supplies the method. It picks labeled seeds by optimizing submodular objectives, which reward covering the data but with diminishing returns for redundant picks: facility location for coverage and log-determinant for diversity. With 10 seed images on APTOS 2019, it reaches 0.89 accuracy versus 0.64 for random seeds. That result is about classification seeds for weak labeling functions. Whether it transfers to entity-correspondence seeds for cross-domain translation is untested, and that is the question here.

Research Program

The setting is a bridge budget. From a pool of users who could be linked across domains, the system may reveal both-domain histories for only $B$ of them. It then trains any cross-domain model and is evaluated on a fixed, held-out set of cold-start users whose target histories are hidden. Selection may use only source-domain information, because target histories of unselected candidates are unknown by assumption.

We will build three selectors, all on source-domain user embeddings from a single-domain model trained on all source users. The first is facility location, measured against the whole population of source-only users who will need recommendations. The second is log-determinant diversity. The third is a hybrid that adds a density-aware term penalizing multiple seeds inside one dense cluster, as a direct response to PSML's fuzzy-region finding.

We will pair each selector with four downstream learners spanning the field: the two-stage embed-and-map pipeline (EMCDR), SCDR, CDRIB, and CDR-Adapter. The analysis has three parts. First, per-user error regressed on distance to the nearest seed, which tests the bound's core prediction. Second, an estimate of each trained model's local Lipschitz constant, to see whether selection and flatness act on separate terms. Third, gain as a function of budget, to locate where selection matters. We expect selection to matter most at the smallest budgets, echoing SCDR's finding that its gains are largest when data is sparsest.

As a secondary setting, we will run the same selectors for anchor choice in social-network alignment on Twitter-Foursquare and DBLP, with IONE as the embedding model. This tests whether coverage selection reduces the overly-close collapse that PSML documents.

Baselines

The naive reference point is uniform random selection of $B$ bridge users, averaged over at least ten draws. It reproduces the protocol every cited cross-domain recommendation paper uses when it downsamples overlap, so beating it by more than its draw-to-draw spread is the minimum bar.

The strongest simple heuristic is picking the $B$ most active source users. It is what a practitioner would do, and it plausibly helps because active users have better-estimated embeddings. It also plausibly hurts, because such users cluster in the densest region. It is run with the same budget and downstream models.

A generic coverage baseline, k-means centroids' nearest users, separates the value of submodular optimization from the value of any coverage-seeking rule.

The strongest existing method on this question is SCDR with random seeds. It is the only prior method designed specifically for scarce overlap, and it reports a 39.11% RMSE improvement over EMCDR at 80% sparsity on Amazon. For ranking-based comparison we will also run CDRIB with random seeds. It reports a 34.38% average MRR improvement over its baselines on Amazon Music-Movie, Phone-Electronics, Cloth-Sport and Game-Video. For absolute scale, DisCo reports HR@10 of 13.38% on Game-Video, against 12.66% for the runner-up. The file contains no reported absolute MRR for CDRIB under reduced overlap, so we will reproduce it ourselves.

Every model gets identical data splits, the same cold-start test users, and the same hyperparameter search budget per selector. Tuning uses a validation set of cold-start users disjoint from test. Beating SCDR means that coverage selection plus plain EMCDR matches SCDR-with-random-seeds, or that coverage selection plus SCDR beats SCDR-with-random-seeds by more than seed variance, at budgets of 5% and 20%.

The key ablation replaces the population-weighted facility-location target with facility location measured against the candidate pool only. This isolates whether aiming coverage at the deployment population, the users who will actually be cold-start, is the active ingredient.

Why not just…?

Why not just use sharpness-aware training and keep random seeds? Flatness shrinks $L_f$ but cannot shrink the distance from a cold-start user to the nearest seed. The bound suggests the two are complementary, but that is an argument, not evidence. If SCDR with random seeds matches SCDR with selected seeds, then selection is redundant, and our 2×2 comparison of selector against flatness is designed to reveal exactly that. We treat this as the main threat.

Why not just pick the most active users? It is a strong heuristic, and nothing in the file rules it out. PSML's observation that dense regions collapse under scarce anchors predicts it will waste budget on redundant users, but the actual comparison is an experiment we run, not a result we can cite.

Why not just expand the seed set with pseudo-labels? Pseudo-labeling needs an initial model good enough not to reinforce its own mistakes. DMT shows that single-model confidence filtering accumulates errors and that the dual-model fix can cost up to 8x training time. A better initial seed set benefits pseudo-labeling too. Selection is cheaper and upstream, so we test it first, and leave pseudo-labeling on top of selected seeds as a follow-up.

Why not just use active learning based on model uncertainty? Uncertainty requires a trained cross-domain model, which is circular at tiny budgets. It also tends to pick outliers, which covers little. We will include one round of uncertainty-based selection from a random warm start as an additional comparison at matched total budget.

Proposed Experiments and Decisive Checks

The main experiments use Amazon Book-Movie, Music-Movie, Phone-Electronic and Game-Video, with bridge budgets of 5%, 20% and 50% of candidate overlapping users. Metrics are MRR, HR@10 and NDCG@10 for ranking models and RMSE for SCDR/EMCDR, following each model's original protocol.

The first decisive check is whether facility-location selection beats both random and most-active selection with plain EMCDR at 5% budget. The second is whether it adds significant gain on top of SCDR. The third is whether per-user error increases monotonically with distance to the nearest seed, and whether selection's gain matches the observed reduction in coverage cost. If the second check fails, then flatness already absorbs what selection offers, and we will report that. If the third check fails, then the coverage explanation is wrong even if selection helps, and the mechanism needs revisiting.

The network-alignment runs on Twitter-Foursquare report precision at N against random anchors and against PSML's reported gain for DALUAP (139.12% improvement). They test whether choosing real anchors well recovers some of what implanted pseudo-anchors achieve, without an auxiliary network.