Trusting Social Ties Only While Tastes Agree: Streaming Preference Sketches for Social Recommendation

Social recommenders assume that friends like similar things, and they pass preference signals along friendship links. That assumption fails most of the time. On Yelp, the share of social links that join users with matching preferences is reported at only 0.0154 (Challenging Low Homophily in Social Recommendation). On Flickr, 81% of links connect users with no common item interactions (IDVT). A whole line of work therefore "denoises" the social graph by scoring each link against the two users' behavior and pruning or down-weighting the bad ones. Every one of these methods scores a link once, on a frozen snapshot, with an expensive learned module. Real platforms do not work that way. Two colleagues who both read thrillers this year may diverge next year, and a single link may be useful for books but not for games. A link's usefulness is a moving, item-dependent quantity, and on a graph with hundreds of millions of users nobody can afford to rescore every link with a neural network after each click.

We propose to maintain, for every social link, a running estimate of how much its two endpoints currently agree in what they consume. The estimate is computed from small fixed-size summaries of each user's recent item history, called sketches: compact bit arrays that approximate set overlap and can be updated in constant time when an item is added or removed. Recommendation then sends signals only through links whose current agreement is high, and only for the item category being scored. Propagation is refreshed lazily, only when a user's link agreements have changed enough to matter. The result is a social denoiser whose per-event cost does not grow with graph size and whose link weights follow drifting tastes, rather than staying fixed at whatever a training snapshot recorded.

Core Claim

Our claim has two parts, and each can be tested on its own. The first part is that, in timestamped social-recommendation data, the agreement carried by a social link drifts enough that link confidences frozen at training time go measurably stale. If this holds, any static denoiser loses accuracy as the deployment window lengthens. The second part is that a cheap, non-learned confidence signal can track this drift and match or beat learned static denoisers under chronological evaluation, at a small fraction of their cost. That signal is a time-windowed, category-conditioned overlap estimate between endpoint sketches. If the first part fails, so that agreements are stable, the proposal reduces to an efficiency contribution, and we will report it as such.

Concretely, let $S_u^k(t)$ be the set of items in category $k$ that user $u$ interacted with during the window $(t-W, t]$, where $W$ is the window length. The confidence of social link $(u,v)$ for category $k$ at time $t$ is

$$c_{uv}^k(t) = \frac{n_0 + \widehat{J}\big(S_u^k(t), S_v^k(t)\big)\, m_{uv}^k(t)}{n_0 + m_{uv}^k(t)}\cdot \pi_k .$$

Here $\widehat{J}$ is the sketch estimate of Jaccard overlap, the size of the intersection divided by the size of the union. The count $m_{uv}^k(t)$ is the smaller of the two users' window counts, so it measures how much evidence exists. The constant $n_0$ is a pseudo-count, and $\pi_k$ is the base rate of agreement in category $k$. Together they pull the estimate toward the base rate when evidence is thin. This shrinkage matters for sparse and cold-start users, whose links prior work found to be the most valuable (DSL) and the most important to keep (GDMSR). When scoring item $i$ in category $k$ for user $u$, the social contribution is a sum over $u$'s neighbors $v$, each weighted by $c_{uv}^k(t)$, so the same link can be open for one category and closed for another.

Where This Sits

The static social denoisers motivate the work and supply the target behavior. GBSR learns link confidence from behavioral overlap with an information-bottleneck objective. SHaRe cuts links whose endpoints have low interaction-embedding similarity and adds links between similar users. GDMSR scores ties with a Transformer over interaction histories and prunes more aggressively for high-degree users. IDVT thresholds an embedding-based interest-confidence score. All four compute confidence once on a fixed graph, and DSL, IDVT and GDMSR name dynamic social ties as future work. We keep their central insight, that behavior should validate links, and change three things: the validator is cheap, it is recomputed continuously, and it is conditioned on category, which addresses the domain-averaging problem raised in Modeling Users' Multifaceted Interest Correlation for Social Recommendation.

The heavier robustness methods constrain the design by showing what does not scale. SGIL trains on several perturbed copies of the graph, which costs one to three times the runtime of a standard GNN. RecFlow requires solving an ordinary differential equation at inference, which its authors call demanding at million-node scale. SGIL also makes the strongest argument against us. It warns that, without ground-truth labels for links, explicit filtering can remove real signal. We take this seriously. Our gate is soft and shrunk toward a prior rather than a hard cut, and our experiments measure directly whether it hurts the users SGIL's argument would predict it hurts.

The closest temporal work is DeBaTeR. It adds learned time embeddings to user and item embeddings and reweights user-item edges by time-aware similarity. It never touches user-user links, and its confidence comes from the model's own embeddings, which are themselves shaped by the propagation being denoised. Our confidence comes from raw behavior, so it is independent of the model.

The streaming and scaling papers supply the machinery. Virtual Odd Sketch maintains Jaccard estimates under insertions and deletions in constant time by XOR-ing into a shared bit array. Because deletion is as cheap as insertion, a sliding window is simply an insert when an interaction arrives and a delete when it expires. Salting the hash with the category gives per-category sketches without extra arrays. CODEN contributes two ideas. The first is parameter-free Personalized PageRank (a random-walk-with-restart propagation that needs no training) as the structural operator. The second is lazy refresh, which recomputes a node only when its accumulated change passes a threshold. CODEN assumes every edge is valid; we feed it gated edges instead. TRicci prunes dynamic graphs by temporal curvature with no reference to preferences, so it is our test of whether geometry alone is enough.

Research Program

The first stage is a measurement study that decides whether the dynamic premise holds. On chronologically ordered Yelp, Ciao, Epinions and Douban data, using their review timestamps, we compute exact windowed per-category agreement for every social link at monthly checkpoints. We then report three quantities: how often a link crosses the median-agreement threshold between checkpoints, how agreement decays with the time since a link's confidence was last computed, and how much category-conditioned agreement differs from pooled agreement on the same link. This stage needs no model and settles the first part of the claim.

The second stage builds the system. Each user keeps a windowed sketch in a shared, category-salted bit array that is updated on every interaction event. Link confidences are not stored. They are computed on demand from the two endpoint sketches whenever propagation touches the link. This avoids the cost of degree times events that eager updating would impose on celebrity hubs, which are exactly the anisotropic noise sources described in RecFlow. A user's social representation is a Personalized PageRank propagation of item-side embeddings over the confidence-weighted social graph. It is combined with a LightGCN-style user-item embedding that is trained offline and refreshed on a fixed schedule. A user's propagation is recomputed when the summed absolute change in confidence on their links since the last refresh exceeds $\lambda$, mirroring CODEN's trigger. The only learned parts are the item-side encoder and a scalar mixing weight. The window $W$, the pseudo-count $n_0$, the threshold $\lambda$ and the sketch width are set on a validation period.

The third stage is analysis. We trace accuracy as a function of time since deployment for both frozen and live confidences. We break results down by user activity level, to test SGIL's warning about removing signal. We break them down by endpoint degree, to see whether hub links are the ones being closed. Finally, we compare sketch error against exact Jaccard as user activity becomes more skewed, the collision regime that the VOS authors flag.

Baselines

The naive reference points are a LightGCN-style model trained only on user-item interactions, which ignores the social graph entirely, and the same model with raw, unweighted social propagation. GBSR and SGIL both report that raw social graphs often do worse than pure collaborative filtering, so a method that cannot beat the interaction-only model has failed outright. Both naive models are retrained on the same schedule as our system.

The strongest existing methods for denoising accuracy are GBSR and SGIL. GBSR reports improving "NDCG@20 by 17.06% over the strongest baseline" on Douban-Book, and SGIL reports "NDCG@10 improvements of 6.2% to 8.3%" across Douban-Book, Yelp and Epinions. Both figures are relative gains under the original static random splits. We found no reported absolute result on Lacuna for any social denoiser under chronological streaming evaluation, so we will rerun both ourselves. We train each on the initial period using its released hyperparameter ranges, with the same tuning budget in GPU-hours that our method gets. We evaluate in two modes: frozen, and retrained at each checkpoint. The retrained mode is the strongest fair version of a static method. Beating it means equal or better NDCG@20 and Recall@20 averaged over the stream, at substantially lower update compute. Beating frozen GBSR by a widening margin over time would confirm that confidences go stale.

For scalable dynamic learning, the strongest baseline is CODEN with its standard ungated propagation. It reports completing continuous prediction on Papers100M in "3.3 hours on a single GPU" versus TGL's "98.3 hours and 4 GPUs". We use CODEN's own lazy propagation code with and without our gate, so the comparison changes only the edge weights. Beating it means better accuracy at a wall-clock cost within a small constant factor.

For preference-blind sparsification, we prune TRicci-style at matched sparsity. TRicci preserved "97.7% of the full-graph ROC-AUC on average" at 80% edge removal on transaction networks. We prune the social graph to the same fraction that our gate effectively closes, so any difference reflects which links are kept, not how many.

Three ablations isolate the key ingredients. Frozen sketches compute confidence once at training time, which isolates tracking over time. Pooled sketches drop category conditioning. An embedding gate replaces $\widehat{J}$ with cosine similarity of the model's own user embeddings, in the manner of DeBaTeR-A and IDVT, which isolates whether behavior-derived confidence beats model-derived confidence.

Why not just…?

Why not just drop the social graph and use collaborative filtering? For users with ample history this may be nearly as good, and we expect the interaction-only model to be close on them. The case for social links rests on sparse users. DSL reports gains of 76.9% in HR@10 and 96.2% in NDCG@10 on Epinions, which it attributes largely to users with few interactions. Our breakdown by activity level shows whether gated social propagation still helps those users under chronological splits. If it does not, the social signal is not worth maintaining, and we will say so.

Why not just retrain GBSR or SHaRe nightly on snapshots? This is the most serious threat. If agreement drifts slowly relative to the retraining interval, nightly retraining captures nearly everything. Our measurement stage quantifies drift at monthly and finer checkpoints, and the retrained-GBSR baseline measures the accuracy-versus-compute frontier directly. Our claim survives only if the live gate matches retrained accuracy at much lower cost, or beats it within the interval between retrains. On the small public datasets the compute argument is weak. It becomes meaningful only in the scaling experiment, so we treat accuracy parity and cost as separate findings.

Why not just gate with the model's own embedding similarity, which is just as cheap? A dot product is indeed as cheap as a sketch comparison, so cost does not justify the choice. The argument is about circularity and freshness. Embeddings are produced by propagating over the noisy links they are meant to judge. They change only when the model is retrained, while sketches change with every event. The embedding-gate ablation settles this. If it matches the sketch gate, the contribution reduces to live, category-conditioned gating, regardless of where the signal comes from.

Why not just sparsify by curvature, as TRicci does? TRicci's high retention was measured on transaction and comment graphs where structure tracks the prediction target. On social graphs, structurally strong links can join users with no shared taste, as the noise ratios reported by SHaRe and IDVT indicate. The matched-sparsity comparison, broken down by endpoint degree, shows whether geometry keeps the hub links that behavior would close.

Proposed Experiments

We split Yelp, Ciao, Epinions and Douban chronologically: an initial training period followed by a stream evaluated at rolling checkpoints with Recall@20 and NDCG@20. We also report the frozen-versus-live gap as a function of time since training. As a robustness check we follow GDMSR's protocol of injecting up to 50% random social links, and additionally inject a "hub" variant that connects many users to a few high-degree accounts, which mimics anisotropic noise.

The public social-recommendation benchmarks are small, with tens of thousands of users, so scale is tested separately. On the Reddit data behind TGB, we treat tgbl-comment reply events (more than 30M timestamps) as social ties and subreddit participation as the item stream, in the spirit of tgbn-reddit. This construction depends on the two sources sharing user identifiers, which we must verify before relying on it. We report per-event update latency, propagation refreshes per hour, memory, and node-affinity NDCG@10. On this task TGB reports that a moving-average heuristic reaches 0.559 against TGN's 0.315, so that heuristic is a mandatory reference point. We also run throughput-only tests on Papers100M with a synthetic item stream, to compare against CODEN's cost profile.

Three outcomes are decisive. If measured link agreement is stable over time and frozen confidences lose nothing, the dynamic claim is false. If the embedding gate equals the sketch gate, the behavioral-sketch claim is false. If gated propagation fails to beat the interaction-only model for low-activity users, the social signal is not worth maintaining. Success requires the live sketch gate to widen its lead over frozen static denoisers as deployment time grows, to match retrained GBSR or SGIL within a small margin at a fraction of their update cost, and to keep sketch-induced error small under skewed activity.