Efficient Swing Computation for Retrieval in Large-Scale Recommender Systems
Runhao Jiang, Renchi Yang
cs.IR
2026-09-15
ASC/K-ASC approximate Swing with grouped and subset sampling. On MAG, top-100 is 99.9% precise in 1.5 ms vs Exact 8.5 s, keeping ~99% i2i recall at 4000× speedup.
Item-to-item retrieval still sits in the first stage of many industrial recommenders. Swing goes one hop past ordinary itemCF: the score of two items is a sum over pairs of their shared users, and each pair's weight falls as those two users share more items. That down-weights casual clickers and power users. Alibaba cold-start, Kuaishou, and Shopee ads have all used it in public writeups.
The cost is quadratic in degree. Exact Swing for a query item vq is O(d(vq)^2 · d̄). A popular item can have tens or hundreds of thousands of users, so one query walks millions to billions of user pairs. Production teams throw MapReduce at it, or cap neighbors at 600, which drops pairs that matter.
The paper asks for (ε,λ)-approximate Swing: relative error ε when the true score is at least λ, additive error ελ otherwise. Typical ε is 0.05, and λ is one percent of the maximum possible score. Set intersection uses QFilter++ tuned for bipartite neighborhoods (BSR layout plus SIMD). Cardinality-only mode can be up to about 3× faster still.
Two randomized estimators split the work. GNS groups repeated user pairs from naive Monte Carlo so each distinct pair is intersected once; the sample size follows a Chernoff bound for (ε,λ). USS still enumerates pairs, but samples a subset of the smaller neighborhood, materializes only that small intersection, and uses a cardinality count for the full overlap, skipping huge materializations. ASC picks the cheaper estimator with an empirical cost model. The runtime ratio ρ lives in [0.22, 0.67]; 0.5 worked across the datasets.
For top-K, K-ASC spends part of the sample budget on a coarse pass, keeps incremental lower and upper bounds, locks in clear top-K items, and spends the rest on borderline items, with an exact polish on a reduced candidate set when needed.
Eight real bipartite graphs, C++, -O3, AMD EPYC 7742, 1TB RAM. The two largest: Yambda, about 8.75M items and 1.34B edges; MAG, about 2.78M items and 1.10B edges. Queries are 1,000 uniform items and 200 items from the top 20% by degree. Baselines: Exact, truncate-at-600, Naïve-MC, GNS and USS alone, plus All-Pairs and WHIMP retargeted as candidate generators.
ASC is the fastest (ε,λ) method on all eight graphs for ε in {0.02, 0.05, 0.1, 0.2}. Versus GNS it is about 3× on popular queries and about 5× on random ones; versus Exact it reaches 100× on Yambda and MAG at ε=0.02. USS sits around 2× versus Exact. On small graphs ASC falls back to Exact.
For top-K, K-ASC holds above 99.97% precision on Yambda for every K, two-plus orders of magnitude faster than Exact, and about 5× faster than ASC. The headline MAG number: top-100 precision above 99.9% in 1.5 ms, against 8.5 s for Exact. Versus All-Pairs and WHIMP the gap is one to two orders of magnitude on the billion-edge graphs. On i2i recall against ItemCF, Adamic-Adar, Jaccard, SimRank, PPR, and Item2vec, exact Swing is already strong; ASC tracks that recall, and K-ASC on MAG is over 4000× faster than exact Swing at about 99% of its recall. Truncation is fast and loses quality, as section 6.3 shows.
Swing is already in production. What was missing was a single-node approximation with a proof. K-ASC turns "popular items do not finish" from a cluster job into a millisecond query, and it keeps a relative-error contract instead of the 600-neighbor cap. For teams that already retrieve with Swing, this is infrastructure, not another embedding. Code and data: HKBU-LAGAS/K-ASC.
Guarantees are probabilistic, with failure probability 10^-4; pathological head items may still force the expensive estimator. K-ASC's filter-refinement is for top-K; a full ranking still uses ASC. Experiments are single-node with 1TB RAM; sharded deployment is only discussed in an appendix. QFilter++ assumes SIMD and BSR layout, so constants move with hardware. There are no online A/B numbers; the i2i comparison stops at offline recall-latency curves. Swing itself remains collaborative structure only, with no content or cross-modal signal.