Resolving Overlapping Community Membership as Bandit Exploration for Cold Users

When a new user joins a large network, a recommender knows almost nothing about them. The network, though, often says something useful: the few friends they have, or the content they arrived with, suggest which groups they belong to. Real people belong to several groups at once. The same person can be a science-fiction fan, a parent and a follower of local politics. Current methods that share learning across users either force each person into one group or search the whole population for similar users every time they recommend an item. The first approach breaks multi-group people apart. The second does not scale.

We propose to treat a cold user as an uncertain mixture of overlapping communities and to make exploration, meaning the deliberate showing of uncertain items to learn something, target the question "which of your communities is speaking right now?" Each community keeps one shared, fast-learning preference model. A new user starts with a sparse guess of their memberships, taken from graph structure or content features. The system then prefers items on which the user's candidate communities disagree, because the user's reaction to those items reveals the most about their memberships. The cost of each decision depends on the handful of communities a user touches, not on the number of users. That property is the reason the idea is worth building now.

Core Claim

Our claim is that, for cold and low-activity users, a multimodal prior (one peak per overlapping community the user may belong to) combined with an exploration bonus that rewards resolving membership will earn more reward early than two alternatives. The first alternative is a single averaged prior built from the same information. The second is hard assignment to one cluster. We claim this holds at per-decision cost independent of the number of users $|V|$. The gain should concentrate on users whose memberships genuinely overlap. If it does not, the idea is wrong.

The closest prior work is On Context-Dependent Clustering of Bandits. Its method, CAB, already recognizes that users group differently depending on the item. It builds a fresh neighborhood of similar users for every candidate item by comparing all users' current estimates, which costs $O(|V| d)$ per candidate, where $d$ is the feature dimension. It uses no graph and has no prior membership for a newcomer. We keep CAB's insight that grouping depends on context, but move the grouping into a precomputed, sparse, overlapping community structure. We also make a cold user's membership an explicit latent quantity that rewards update online.

Research Program

The model. Let each community $k$ carry a ridge-regression preference estimate $\hat\theta_k$ with precision matrix $A_k$. This is the usual linear contextual bandit bookkeeping, a bandit being a learner that must choose actions while estimating their payoffs. Let user $u$ have a sparse membership vector $\pi_u$ over a small support $S_u$ of communities, plus a personal residual $\hat\delta_u$ that starts at zero. For an item with features $x$, the score is

$$\mathrm{UCB}_u(x) = \sum_{k \in S_u} \pi_{uk}\,\hat\theta_k^\top x + \hat\delta_u^\top x + \alpha \sqrt{\textstyle\sum_{k\in S_u} \pi_{uk}\, x^\top A_k^{-1} x} + \beta \sqrt{\mathrm{Var}_{k \sim \pi_u}\big[\hat\theta_k^\top x\big]}.$$

The terms have distinct roles. The first two terms predict the payoff. The $\alpha$ term is standard parameter uncertainty; it shrinks quickly because community models pool many users. The $\beta$ term is new: it is the spread of the candidate communities' predictions for this item under the user's current membership belief. It is large exactly on items where the user's possible communities disagree, and it vanishes once $\pi_u$ concentrates on one community.

Updating after feedback. After each observed reward, $\pi_u$ is updated by reweighting each community in $S_u$ by how well it predicted that reward. This is a cheap Dirichlet-style update over at most a few communities. The community statistics $A_k$ and the reward-weighted sums are updated with weight $\pi_{uk}$. The residual $\hat\delta_u$ takes over as the user's own data accumulates.

Why this fixes known failure modes. In Online Clustering of Bandits (CLUB), groups are connected components formed by pruning edges between users whose estimates differ. Edges are cut permanently, and inactive users remain stuck in one oversized group. Here, nothing is cut, and a cold user's weight moves smoothly between communities.

Where initial memberships come from. For users with edges, we run overlapping community detection offline. The primary method is link-community factorization with automatic community-count selection, NMFIB, from Link Community Detection Using Generative Model and Nonnegative Matrix Factorization. It clusters edges rather than nodes, so a node naturally inherits several memberships. A mixed-membership model in the style of GWN-LDA serves as a probabilistic alternative.

That source paper warns that NMF-style factorization struggles past tens of millions of edges. For the largest graphs, we therefore also build a local variant. It finds dense cores, following the core-expansion idea of Bing Liu et al., and assigns node memberships by truncated random walks from those cores, following Sarkar et al., whose short walks approximate global proximity at near-linear cost.

For users with no edges at all, we borrow the dropout-trained patching network of Graph Neural Patching for Cold-Start Recommendations (GNP). GNP trains a small network to map side features into the collaborative space by hiding warm users' embeddings during training. We retarget it to output a sparse membership distribution rather than a single vector. GNP supplies the method here but is entirely passive; our contribution is what happens after the first guess.

Theoretical analysis. We will analyze a planted model: users are sparse mixtures of $K$ community parameter vectors. The target is a regret bound for cold users that scales with the number of candidate communities per user, $|S_u|$, and with the separation between community predictions. Neither the number of users nor the per-user dimension should enter the bound. The comparison point is Graph Neural Bandits, which reports $O(\sqrt{T}\log n)$ regret, where $T$ is the number of rounds and $n$ the number of users. It gets there through two graph neural networks trained online and has no mechanism for users with no graph presence.

Baselines

Naive reference points. The reference points are one independent linear bandit per user (LinUCB-IND) and one global bandit for everyone (LinUCB-ONE). A Gang of Bandits reports that its graph-regularized methods reached "nearly double the cumulative reward" of LinUCB-IND on Last.fm; no absolute number is given. CLUB and GCLUB report that LinUCB-ONE suffers high asymptotic regret. Both references are run on the same replay logs with the same exploration-constant grid.

Disjoint clustering bandits. These are CLUB, GCLUB from Graph Clustering Bandits for Recommendation, and GOB.Lin with its BLOCK variant. They are the direct competitors on the claim that overlap matters. For all bandit baselines, no reported CTR or regret figures were found on Lacuna; the source papers state only qualitative wins. We will therefore re-run them ourselves, with the same features, the same graph, and an equal hyperparameter-search budget.

The strongest existing method. CAB is the strongest competitor on the overlap question itself. No reported CTR number was found on Lacuna for CAB on Tuenti, KDD Cup 2012 or Avazu. We run CAB both exactly and with a subsampled-user approximation matched to our per-decision wall-clock budget. Beating CAB means matching or exceeding its cold-user reward at equal compute, and clearly exceeding it once compute is capped at a fixed per-decision budget as $|V|$ grows.

The passive cold-start reference. GNP reports a 45% relative Recall gain and a 39% relative NDCG gain over DropoutNet/Heater on CiteULike, and 1,054 seconds of inference time versus 1,483 for Heater on WeChat. We use GNP with greedy serving, and GNP with standard LinUCB started from its projected embedding.

Ablations of the key ingredient. Two ablations isolate what is new. The first is collapse-to-mean: identical memberships and community models, but the mixture is replaced by its average vector with matched prior variance, turning it into a single-peak prior. The second sets $\beta=0$, which keeps the mixture but removes membership-directed exploration. Beating the collapse-to-mean ablation on high-overlap users is the result that establishes the claim.

Why not just…?

Why not just run GNP's projected embedding as the prior for LinUCB? This is the most serious threat, because it supplies side information and uncertainty at almost no engineering cost. The weakness is structural. If a user genuinely sits between two communities with opposed tastes on some topic, the averaged embedding predicts lukewarm interest. Its uncertainty is also not aimed at the disagreement, so exploration is spread over all directions rather than the informative ones. This is exactly what the collapse-to-mean ablation measures with identical inputs. If that ablation matches our method even on high-overlap users, we will report that the multimodal structure is unnecessary.

Why not just assign each cold user to their single most likely community and run per-cluster bandits? This is cheaper and is the natural reading of GOB.Lin.BLOCK. GOB.Lin's own results show that BLOCK wins on fragmented Delicious but loses on Last.fm, where it cuts cross-cluster sharing. That pattern is consistent with overlap mattering unevenly across datasets. We test hard assignment directly (the top-1 community from the same $\pi_u$), stratified by membership entropy. We expect parity on low-entropy users and a gap only on high-entropy ones.

Why not just pool over graph neighbors with personalized random walks, without communities? A purely local smoother avoids offline community detection entirely. For a user with two edges, however, the local neighborhood is tiny and noisy. Kloumann's observation that seed-set expansion from sparse seeds fails to separate overlapping memberships suggests this degrades precisely in our regime. We include walk-weighted neighbor pooling at matched cost; if it ties us on users with fewer than five edges, communities add nothing.

Why not just make CAB faster with approximate nearest-neighbor search? This is plausible, and it is why CAB is run under a matched compute budget with subsampling. Our remaining advantage would be twofold: a membership prior for users with no history, which CAB lacks, and a memory footprint that is fixed per community.

Proposed Experiments

Synthetic study. We plant $K$ community parameter vectors and generate users as sparse mixtures with one to three memberships. The overlap fraction varies from 0 to 60%, and edges are drawn from a mixed-membership block model. This is where theory and practice must agree. The decisive check is that our advantage over collapse-to-mean and hard assignment grows with the overlap fraction and is roughly zero when overlap is zero.

Real-data replay. We use Last.fm and Delicious, which have social graphs and have been used by GOB.Lin and GCLUB. We also use Yahoo! 18k, whose randomly logged traffic allows unbiased replay, plus Tuenti and MovieLens 100k. For each dataset, 20% of users are held out as strictly cold and introduced online with no history. We report cumulative reward over their first 10, 25 and 50 interactions, broken down by the entropy of their initial memberships.

Content-only cold start. CiteULike and XING test users or items with no edges, using the patching network to initialize memberships. Warm-user reward is tracked throughout, to confirm we avoid the warm-entity penalty that GNP identifies.

Scalability. We measure per-decision latency and memory as $|V|$ grows. The scale ladder runs from subsampled graphs up to the full CiteSeer co-authorship graph, with about 400,000 authors, used as a user graph with synthetic rewards. The comparison is against exact and subsampled CAB and against GOB.Lin. We expect our latency curve to stay flat and CAB's to grow linearly.

Robustness to the community detector. We repeat the replay with NMFIB, GWN-LDA-style memberships and the core-plus-walk variant. If gains are specific to one detector, the claim narrows to that detector.

What would kill the proposal. The idea fails if the collapse-to-mean ablation or GNP-prior LinUCB matches us on high-entropy cold users across two or more real datasets.