Efficient Swing Computation for Retrieval in Large-Scale Recommender Systems
Runhao Jiang, Renchi Yang
cs.IR
2026-09-15
香港浸会大学的ASC/K-ASC用分组采样与用户子集采样自适应估Swing相似度,在MAG上top-100精度超过99.9%、1.5毫秒对Exact的8.5秒;i2i召回相对精确Swing仍约99%,加速超过4000倍。
工业推荐的召回层大量用item-to-item。Swing比普通itemCF多看一层user-item-user「秋千」结构:两个物品的分,是它们共同用户两两贡献之和,贡献与这对用户的共同物品数成反比,用来压掉随便点的人和超级活跃用户。阿里冷启动、快手、Shopee广告都公开用过。
代价在度数的平方。精确计算对查询物品vq是O(d(vq)^2 · d̄)。热门商品交互用户可以上十万,一对物品要扫百万到十亿量级用户对。工业界常用MapReduce硬扛,或把邻居截断到600,后者会丢关键用户对。
先把任务写成(ε,λ)-近似Swing:分数高于λ时要相对误差ε,低于λ时只保证加性误差ελ。典型ε=0.05,λ取最大可能分的百分之一。集合交用针对二部图改过的QFilter++(BSR编码加SIMD),只数交集大小时还能再快,文中提到最多约3倍。
两条随机估计器互补。GNS把朴素蒙特卡洛里重复抽到的用户对合并,每对只做一次交,样本数按Chernoff定,保证(ε,λ)。USS仍枚举用户对,但对度数较小的一侧做子集抽样,只物化小交集,大交集用计数,避开热对的全量物化。ASC用经验代价模型在两者里选便宜的那个,经验比值ρ落在[0.22,0.67],取0.5在数据上够用。
Top-K再升级成K-ASC:先花一部分样本做粗估,用增量维护的上下界筛出稳进top-K的人和边界人,剩余样本只打磨边界,必要时在缩小后的候选上做精确细化。
八张真实二部图,C++、-O3、AMD EPYC 7742、1TB内存。最大两张:Yambda约875万物品、13.4亿边;MAG约278万物品、11.0亿边。查询分1000个均匀样本和200个度数前20%热门样本。对照包括Exact、截断600、Naïve-MC、拆开的GNS/USS,以及改来做候选生成的All-Pairs和WHIMP。
ASC在八张图、ε∈{0.02,0.05,0.1,0.2}下都是近似查询里最快的。相对GNS,热门查询大约3倍、随机查询大约5倍;在Yambda和MAG、ε=0.02时相对Exact可到100倍。USS相对Exact大约稳在2倍。小图上ASC会自己退回Exact。
Top-K上K-ASC在Yambda对所有K都做到99.97%以上精度,时间相对Exact少两个数量级以上,再比ASC快约5倍。摘要里的对照:MAG上top-100平均精度超过99.9%、1.5毫秒,Exact要8.5秒。相对All-Pairs/WHIMP,十亿边图上快一到两个数量级。i2i召回对比ItemCF、Adamic-Adar、Jaccard、SimRank、PPR、Item2vec时,精确Swing本身就强;ASC几乎贴着它的召回,K-ASC在MAG上相对精确Swing加速超过4000倍,召回仍约99%。截断基线快,但质量掉在论文第6.3节的对比里。
Swing早就在用,缺的是可证明误差的单机近似。K-ASC把「热门物品算不动」从集群作业收成毫秒级查询,还保留相对误差保证,不必靠截断600这种伤质量的启发式。对已经把Swing当召回通道的团队,这是基础设施升级,不是又一个嵌入模型。代码和数据在HKBU-LAGAS/K-ASC。
近似保证是概率的,失败概率取10^-4,极端热门查询仍可能要退回更贵的估计器。K-ASC的过滤-精炼针对top-K,要全量排分仍走ASC。实验是单机1TB内存,分片部署只在附录讨论。QFilter++吃SIMD和BSR布局,换硬件常数会变。论文没有报告接入在线推荐后的业务指标,i2i对比停在离线召回-时延曲线。Swing分数本身也继承原定义:只看协同结构,不含内容与跨模态。