CS Paper Radar

Efficient Swing Computation for Retrieval in Large-Scale Recommender Systems

Runhao Jiang, Renchi Yang

cs.IR ·submitted 2026-09-15 08:42 UTC · v1
published

Abstract

Given a user-item graph $G$, a query item $v_q$ and a target item $v_t$, the Swing score $sw(v_q, v_t)$ of the item pair $(v_q, v_t)$ leverages the user-item-user interaction structure to evaluate their similarity. This measure is found to be highly effective in item-to-item (i2i) retrieval task and finds extensive applications in industrial-scale recommender systems. However, existing solutions towards computing Swing scores are either prohibitively expensive due to their quadratic time complexity w.r.t. the item degree, or rely on truncation heuristics that yield unsatisfactory quality, rendering them impractical particularly on graphs with billions of interactions. In this paper, we present ASC and $K$-ASC, two novel and efficient algorithms for approximate and top-$K$ Swing queries, to address the aforementioned limitations. Specifically, these algorithms provide rigorous theoretical guarantees in probabilistic relative and additive errors of Swing values. The basic idea of ASC is to combine two randomized algorithms, GNS and USS, in a simple yet non-trivial way to adaptively process high- and low-degree query items with minimal runtime cost. In particular, $K$-ASC offers practical efficiency and effectiveness for top-$K$ queries through a filter-refinement paradigm with carefully-designed heuristics. Extensive experiments over eight real datasets demonstrate that ASC and $K$-ASC can achieve orders of magnitude speed-up over competitors in terms of computational time while offering the same approximate and top-$K$ query result quality, and in particular, $K$-ASC is highly efficient on massive graphs including the billion-edge Yambda and MAG datasets.

Comment
23 pages. The technical report for the paper titled "Efficient Swing Computation for Retrieval in Large-Scale Recommender Systems" in SIGMOD 2027

Closest papers

Nearest neighbours by meaning across the whole index.

SPADE: Escaping the Popularity-Similarity Frontier to Measure Serendipitous Recommendations

cs.IR cs.AIcs.LG ·2026-09-25 ·Tobias Vente, Maarten Peirsman, Noah Daniëls, Hannu Toivonen, Bart Goethals
similarity 0.59
Abstract

Recommender systems engineer serendipity to foster active exploration and break predictable consumption cycles. The problem with existing offline beyond-accuracy metrics is that they often either isolate historical similarity or global popularity. We aim to design an evaluation metric that examines similarity, popularity, and actual user relevance. To achieve this, we introduce SPADE (Serendipitous Pareto Distance Evaluation). SPADE maps all items into a two-dimensional space to directly calculate a user-specific Pareto frontier of maximally popular and historically similar items. The final serendipity score is then computed by averaging the minimum Euclidean distance from this boundary strictly for the correctly recommended test-set items. Evaluating SPADE across five datasets and five baseline algorithms confirms its effectiveness; our results show that the metric successfully prevents algorithms from exploiting beyond-accuracy measures with irrelevant or non-personalized recommendations, reliably isolating serendipitous discoveries.

0.16

R2QRec: Learning Recommendation Queries from Retrieval Feedback

cs.IR ·2026-10-29 ·Weixin Chen, Shuchang Liu, Hailan Yang, Yuhan Zhao, Li Kang +11 more
hot direction similarity 0.58
Abstract

Query-based recommendation separates expressing user needs from locating matching items. Its central learning problem is how to turn item interactions into effective retrieval requests when interaction logs do not annotate queries. We present R2QRec, which uses a fixed retrieval system to construct query supervision and evaluate recommendation outcomes. Retrieval verification first selects generated expressions that recover observed items as supervised fine tuning targets, allowing retrieval behavior to determine the target wording. Policy refinement then evaluates generated query sets by the observed item's rank in their fused recommendation list. Log-rank feedback distinguishes outcomes beyond the recommendation cutoff, while a KL penalty constrains policy change relative to the supervised reference. The stages have distinct roles: verification identifies expressions to imitate, and policy refinement improves the combined ranking produced by newly generated queries. Only the query generator is trained; the retriever and item index remain fixed, and no query annotations or learned reward model are required. Across three public datasets, R2QRec achieves state-of-the-art overall recommendation performance among the evaluated methods. Extensive experiments demonstrate the effectiveness of the proposed design and its generalization across generators and domains.

0.25

ReSID: Rethinking Long-Tail Retrieval in Generative Recommendation through Item Reachability

cs.IR ·2026-11-12 ·Muyu Zou, Shunye Tang, Yi Xu, Haibo Xing, Yandong Wang +2 more
code/data similarity 0.58
Abstract

Generative recommendation (GR) represents items with discrete Semantic IDs (SIDs) and casts retrieval as sequence generation. Under skewed interaction distributions and tight serving budgets, GR struggles to retrieve long-tail items. In this work, we are the first to study long-tail reachability across the complete pipeline of SID construction, decoding, and matching. We find that under equal code lengths, parallel SID construction consistently outperforms sequential SIDs on tail items. Moreover, even when full generation fails, decoded sequences carry locally consistent information that retrieves relevant tail items via partial matching. Yet this recovery is bounded by upstream search, failing once beam search prunes all prefixes completable within a fixed mismatch tolerance. Motivated by these findings, we propose ReSID to jointly preserve and recover tail candidates. Built on long parallel SIDs, ReSID pairs popularity-debiased and user-semantic-aware beam search to keep promising paths alive with partial SID matching to recover items from surviving tokens. ReSID achieves state-of-the-art long-tail retrieval while maintaining competitive overall accuracy, with lower latency and higher throughput under narrow beams. ReSID is deployed in our production system, serving main user traffic with substantial business gains. We release our complete code and model checkpoints to support full reproducibility and real-world deployment at https://github.com/Gabriel-reina/ReSID.

0.15

SwapRec: Warming Up Cold Items Through Training-Time Swaps

cs.IR cs.MM ·2026-09-01 ·Marta Moscati, Jan Malte Lichtenberg, Davide Abbattista, Antonio De Candia, Laura Boggia +1 more
published similarity 0.58
Abstract · Accepted at DaQuaMRec @ RecSys 2026: Second International Workshop on Data Quality-Aware Multimodal Recommendation

Interactions with cold items negatively impact real-time personalization of ID-based recommender systems. This is because the use of such interactions degrades user preference estimates, whereas excluding cold items from the user profile prevents real-time recommendation updates. In industrial scenarios, one heuristic often applied to address this shortcoming at inference time is to replace, i.e., "swap", cold-start items by their most similar "warm" neighbor, where similarity is inferred from the items' side information. In this paper, we demonstrate that sequential models, most often used for real-time personalization, are not robust to such swaps, and propose SwapRec, an approach to address this issue. SwapRec relies on using the same swap heuristics already at training time. We apply SwapRec to state-of-the-art models for sequential recommendation and analyze its impact by means of quantitative experiments in three recommendation domains (online shopping, movie, music). The experimental results show that, irrespective of the underlying sequential architecture, our easy-to-implement SwapRec approach allows for substantially more accurate recommendations when in presence of interactions with cold items, simultaneously leading to a larger percentage of cold items in the recommendation lists.

0.23

Theoretically Sound Item Similarity Measures for Recommender Systems

cs.IR ·2026-10-25 ·Noah Daniëls, Joey De Pauw, Bart Goethals
similarity 0.58
Abstract

Quantifying the similarity between items is fundamental to neighborhood-based collaborative filtering, yet many commonly used similarity measures are heuristics that lack theoretical justification. The use of heuristics forces practitioners to rely on empirical trial-and-error, offering little insight into why certain measures outperform others or how they might be improved. In this paper, we present a principled approach for designing item similarity measures grounded in probabilistic modeling and parameter estimation. By adopting this formal perspective, we derive two previously overlooked similarity measures based on the Bernoulli and multinomial distributions. Through an extensive ablation study we highlight the critical role of bias, probabilistic smoothing, treating the unknowns correctly, and choosing appropriate probability distributions. Finally, we show that the commonly used cosine similarity can be interpreted as the solution to a specific optimization problem, thereby providing a novel perspective on this decades-old heuristic.

0.20

SAHC-NS: Structure-Aware and Hardness-Calibrated Negative Sampling for Implicit Collaborative Filtering

cs.IR ·2026-08-17 ·Jiayi Wu, Zhengyu Wu, Xunkai Li, Hongchao Qin, Rong-Hua Li +1 more
similarity 0.57
Abstract

Negative sampling is a key component of implicit collaborative filtering (CF), as it enables recommenders to effectively learn user preferences. Existing negative sampling methods mostly follow a two-stage paradigm: they first construct a candidate negative pool for each user and then select negative samples from the pool according to predefined sampling rules. However, these methods usually overlook the hardness variation of candidate negative pools across users, making it difficult to adaptively adjust the hardness and informativeness of negative samples according to candidate-pool conditions. In addition, most existing samplers evaluate candidate negatives mainly through a matching score computed from the final aggregated user and item embeddings, while ignoring the structural differences captured by multi-hop neighborhood aggregation. As a result, the training value of negatives may be insufficiently characterized. To address these issues, we propose SAHC-NS, a Structure-Aware and Hardness-Calibrated Negative Sampling method. Specifically, SAHC-NS uses the mean and standard deviation of layer-wise matching scores to capture the overall matching strength and cross-layer structural discrepancy of candidate negatives, respectively. This enables SAHC-NS to select informative negatives by taking cross-layer structural discrepancy into account, rather than relying solely on final matching scores. Moreover, SAHC-NS introduces a candidate-pool-aware hardness calibration module to dynamically adjust negative augmentation strength according to candidate-pool hardness, producing hardness-controllable negatives. Extensive experiments demonstrate the superiority of SAHC-NS over existing negative sampling methods.

0.30

Learning a Ranking from Human Feedback in Log-Concave Random Utility Models

cs.LG ·2026-10-06 ·Diego Alovisetti, Marco Mussi, Alberto Maria Metelli
theory similarity 0.57
Abstract

We study the problem of recovering the ranking of a fixed set of items according to their unknown numerical utilities. At each interaction with the environment, a learner presents the item set to a human and receives comparative feedback of two types. Under full-ranking feedback, each interaction reveals a noisy ranking of all items, whereas under winner-only feedback, it reveals only the item ranked first. In both settings, we model human feedback using a random utility model with log-concave noise and study the number of observations needed to recover an $ε$-accurate ranking with high probability. This novel criterion tolerates ordering errors only between items whose utilities differ by less than $ε$. For both feedback types, we establish worst-case sample-complexity lower bounds and develop algorithms that match these bounds up to logarithmic factors. Neither algorithm requires knowledge of the noise distribution, while only requiring an upper bound on its variance. Our results show that the ranking problem under winner-only feedback is intrinsically harder by exposing the sample complexity dependence on the minimum winning probability across the item set.

0.34

Rank-Deviation Quality: A Distance-Aware Metric for Multi-Answer Retrieval and Ranking Evaluation

cs.IR ·2026-08-26 ·Xiaokun Zhou, Alessandro Moschitti, Danielle Class
similarity 0.57
Abstract

We introduce Rank-Deviation Quality (RDQ), an evaluation metric for retrieval and ranking systems that adapts to queries with varying numbers of reference items, from a single correct answer to many valid results. RDQ scores a candidate ranking against an ordered reference list (ORL): each retrieved reference item contributes its output-position weight multiplied by a rank-deviation penalty, and items outside the ORL receive zero credit. Application-specific parameters control tolerance to misordering. Larger values emphasize retrieving valid reference items, whereas smaller values place more weight on matching their reference order. The output-position weights can reflect visibility in the application's interface, such as a vertical list or a carousel. Unlike metrics that require absolute relevance grades, RDQ operates on ordinal rankings, which annotators can produce through pairwise or listwise judgments. Unlike rank-correlation measures such as Kendall's tau, RDQ accounts for both which items are returned and how they are ordered. On a 5,000-query point-of-interest (POI) dataset with 12 systems, RDQ has the highest median empirical power@100 among the 13 evaluated metric configurations. It reaches mean tau >= 0.8 agreement with its own full-query ordering at 200 queries; RBP(0.9), the strongest tested non-RDQ configuration, reaches the same threshold at 250. On TREC Deep Learning benchmarks, where NDCG uses native graded labels and RDQ uses ordinal tiers derived from them, RDQ reaches comparable median power at n=25, while NDCG is higher at n=100.

0.54