2177（）下一页聚类和构造用户核心集加速大规模Top-K推荐系统放大图片作者：Jun-Yu JiangXiang，Patrick H.陈伟，谢卓瑞，王伟美国加州大学洛杉矶分校计算机科学系{jyunyu,patrickchen,chohsieh,weiwang}@cs.ucla.edu摘要Top-K推荐系统旨在为各种实际应用生成少量但令人满意的个性化推荐，例如电子商务的项目推荐和社交网络的链接然而，用户和项目的数量可能是巨大的，从而导致无数的潜在推荐以及在评估和排名所有可能性的瓶颈。现有的基于最大内积搜索（MIPS）的方法独立地处理每个用户的项目排序问题，并且没有探索用户之间的关系。在本文中，我们提出了一种新的模型聚类和导航到p-K的浏览器（CANTOR），以加快计算的top-K建议的基础上潜在因素模型。首先提出了一个基于聚类的框架，利用用户关系将用户划分为亲和组，每个亲和组包含具有相似偏好的用户。然后，CANTOR通过构建一个理论上保证与用户潜在向量差异的集合覆盖，推导出每个亲和力组的代表向量的核心集使用这些代表性向量的核心集，近似最近邻搜索，然后应用到获得一个小集合的候选项目为每个亲和组中的每个用户计算推荐时使用的亲和组。这种方法可以显着减少计算，而不影响推荐的质量。在六个公开的大规模真实世界数据集上进行了大量的实验，用于项目推荐和个性化链接预测。实验结果表明，CANTOR算法能显著提高矩阵分解模型的求解速度，并具有较高的精度.例如，CAN-TOR可以在百万用户网络中以99.5%的精确度@1实现355.1倍的加速比，而最先进的方法只能以99.0%的精确度@1获得93.7倍的加速比。关键词大规模top-K推荐系统;潜在因子模型;近似最近邻搜索ACM参考格式：放大图片作者：Jun-YuJiangXiang，Patrick H. ChenDong，Cho-Jui Hsiehand Wei Wang. 2020年。加速大规模Top-K推荐系统的用户核心集的划分和构造。2020年网络会议（WWW）平等贡献。本文在知识共享署名4.0国际（CC-BY 4.0）许可下发布。作者保留在其个人和公司网站上以适当的署名传播作品的权利WWW©2020 IW 3C 2（国际万维网大会委员会），在知识共享CC-BY 4.0许可下发布。ACM ISBN 978-1-4503-7023-3/20/04。https://doi.org/10.1145/3366423.3380283’20),ACM，美国纽约州纽约市，11页。https://doi.org/10.1145/3366423.33802831介绍随着近十年来互联网用户的爆炸式增长，构建大规模的个性化推荐系统已经成为许多在线应用的核心问题。 例如，用户项目推荐系统在电子商务市场中取得了许多成功[23]，而社交网络中的链接预测可以被视为推荐系统的变体[2，33]。 为了建立推荐系统，协同过滤潜在因素模型由于其有效性和简单性而受到广泛关注。更确切地说，每个用户或项目可以表示为潜在空间中的低维向量，使得用户向量和项目向量之间的内积能够指示用户-项目偏好。此外，这些潜在向量可以通过使用足够的训练数据优化损失函数来学习。例如，矩阵分解[19]已被经验证明在广泛的应用领域[11]中优于传统的基于最近邻的方法。在获得用户和项目的潜在向量后，为了对每个用户进行项目推荐，推荐系统需要计算所有用户-项目对的内积 虽然学习用户和项目的潜在向量是有效的和可扩展的大多数现有的模型，推荐系统可能需要大量的时间来评估所有的用户项目对。 更具体地说，学习潜在向量的时间复杂度仅与训练数据中的用户-项目对的数量成比例，训练数据是所有可能的用户-项目对的一个小子集，但是找到最佳推荐需要检查所有m个用户和n个项目之间的所有Omn个内积。因此，二次复杂度成为大规模推荐系统的一个障碍例如，计算和排名所有偏好得分可能需要一天以上的时间，因此系统无法每天更新[12]。为了使大规模的推荐系统实用化，加速用户和项目特征向量的内积的计算和排序过程是至关重要的，以便有效地为所有用户获得top-K推荐为了加速内积的计算，最大内积搜索（MIPS）[27，31，34]是可行的方法之一。 局部敏感哈希（LSH）[16]和PCA树[32]可以在将问题简化为最近邻搜索后应用于解决MIPS。为了减少为给定用户进行推荐的计算，可以使用聚类算法[7]找到一小组候选项，其潜向量与用户的潜向量具有较大的内积，或者通过一些贪婪算法[12，34]分别对潜向量中的每个维度的条目进行排序。本质上，现有的大多数MIPS算法放大图片作者：Jun-Yu JiangXiang，Patrick H.陈伟，谢卓瑞，王伟WWW2178∈∈∈（）下一页×{} ∈{}（）{|∈}采用两阶段策略，将计算分解为准备过程和预测过程。在准备阶段，这些方法将构建合适的数据结构[34]或减少排名候选者的数量[7]，并且这些准备好的数据结构用于在推理阶段对查询向量进行有效的最大内积搜索然而，这些现有的MIPS算法中的大多数具有以下两个弱点，使得它们对于实际应用通常不切实际：（1）它们仅关注以相当大的准备时间为代价优化给定用户的推理速度，但是对于推荐系统，总体执行时间（包括准备和推理时间两者）更重要，因为系统需要随着新数据的到达而频繁地重新训练。（2）所有的MIPS方法都是为了快速地确定查询向量的最高项集然而，在推荐系统中，查询不是任意向量。 它们是用户潜在的因素，通常具有很强的聚类结构，这是大多数MIPS算法所忽略的。为了加快整体执行时间，我们的主要思想是利用用户之间的关系。 更准确地说，具有相似潜在因素的用户更有可能分享相似的项目偏好，这可能通过他们的高内积来反映。然而，现有的推荐系统加速方法没有考虑用户关系和用户潜在向量的分布。例如，现有的贪婪策略[12，34]只考虑项目潜在向量的值 一些基于邻近图[26，35]和聚类算法[7]的研究也仅减少了项目的搜索空间。在推理阶段，这些方法将对每个用户的推荐视为对数据结构和算法的独立查询。因此，它可能非常耗时，特别是对于无数用户和巨大的候选项空间。在本文中，我们提出了一种新的模型，用于聚类和导航到p-K搜索器（CANTOR），利用用户关系的知识，以加速生成推荐的过程中，所有用户与一个给定的潜在因素模型。CANTOR包括两个阶段：准备和预测。在准备阶段，我们的目标是将共享相似兴趣的用户聚类到亲和组中，并为每个亲和组计算一小部分首选项 更具体地，用户向量（从给定的潜在因素模型生成）用于聚类亲和性组。为了进一步加快准备时间，少数代表性向量的用户核心集导出为每个亲和组，并用于获得一个小的组中的用户的偏好项目的有效的近似最近邻搜索算法。最后，在预测阶段，可以通过对相应亲和性组的这些优选项目进行排名来检索每个用户的前K个项目，这可以比对所有项目进行评估和排名更有效地完成 我们将我们的贡献总结如下：据我们所知，本文是第一个工作，专注于准备时间和用户关系，以加速大规模的top-K推荐系统的预测过程。增强准备时间对于推荐系统及时容纳大量输入数据至关重要，这在以前没有被研究过与独立地处理每个用户的传统方法相比，基于用户潜在向量的分布将用户聚类成亲和性组提供了预测过程的显著加速亲和组的代表向量为具有相似偏好的用户提供了理论上保证的精度。近似最近邻搜索被应用于有效地检索满意的建议，为每个用户从一个小的候选项目集。在六个公开数据集上进行的实验表明，CANTOR可以显著加速大规模top-K推荐系统的项目推荐和个性化链接预测。深入的分析表明，所提出的框架的鲁棒性和有效性。2问题陈述在本节中，我们首先介绍符号，然后正式定义本文的目标 假设我们有一个不完整的m n单类矩阵R = Rij0，1 m×n，其中m和n是系统中的用户数和项目数。如果用户i偏好训练数据中的项目j，则Rij=1;否则，Rij=0。基于R的矩阵分解算法学习d维用户和项目特征向量，分别记为PR m×d和QR n×d，其中Rn=P QT R m×n反映了潜在的偏好.为了计算每个用户的前K个推荐，我们需要在Ri=Rij′中找到具有K个最高评分的项目。j′1.一、 . . M. 注意，对于社交网络中的个性化链接预测，m=n其中目标是建议其他用户作为推荐项目。虽然当R稀疏时可以快速地学习矩阵分解模型，但是推断前K个推荐需要计算和排序每个用户i的所有项目j的得分R_i_j。因此，推理过程可能是耗时的，具有O nmd的时间复杂度，当n和m较大时，这变得难以处理。为了解决这个问题，本文的目标是加快高精度top-K推理机的推理时间。更具体地说，给定训练矩阵P和Q，我们的目标是提出一种有效的方法，近似每个用户的前K3TOP-K推荐系统的用户核心集构造在本节中，我们将介绍用于加速top-K推荐系统的CANTOR，从几个关键的初步想法开始3.1初步为了利用用户之间的关系，我们首先将推荐系统中的用户的亲合组定义如下：定义1. （亲和组）亲和组At是共享对项目的相似兴趣的用户的集合。尽管可以使用任何相似性度量，在本文中，我们采用余弦相似性作为度量来定义亲和组。根据这个定义，对于同一亲和组中的用户，满意推荐的集合应该是相似的这表明针对亲和组中的所有用户的最高推荐被限制到项目的小子集，并且这样的项目子集可以通过以下方式来学习：···聚类和构造用户核心集加速大规模Top-K推荐系统WWW2179...N（）∈.表1：符号及其描述的总结符号描述m，nDK用户数和项目潜在向量的维数最高建议数R∈Rm×nP∈Rm×dQ∈Rn×dP∈Ru×d一类偏好矩阵所有用户的用户潜在向量所有项目的项目潜在向量采样用户潜在向量UrAvtz（p）PtC（pi，K）StNst（pi）Ct二次抽样用户数m个用户的关联组数r个亲和群的集合，其中A ={At |t = 1. . . 对于亲和群At，亲和组指标为用户向量，p为亲和组中用户的潜向量，A为t指标，前K项为p，T为 Q，评价充分。我用于亲和组At的用户coreset对于pi，st中最近的coreset代表亲和组A的前K项的精简项集tϵW自适应代表选择中相似性阈值离群值的新代表数GEFS项向量的邻近图最近邻动态列表的大小仅检查组中的少数仔细选择的用户，导致优选项目集的以下定义。定义2. （优选项目集）亲和组的优选项目集c是组中用户（潜在地）满意的项目的集合，并且优选项目集的大小通常比项目的总数小得多，即， |C|你好因此，我们只需要检查首选项集以生成顶级建议，从而比检查所有项的替代方案节省大量时间。为了鲁棒地生成每个亲和组的首选项集，我们从该组中生成一些代表来计算首选项集。 这在统计上比仅使用潜在空间中的“质心”用户更鲁棒，并且比使用组中的所有用户更有计算效率。定义3.（亲和组的用户核心集）亲和组A t的δ-用户核心集st是潜在代表向量的（小）集合，以保留At中用户的项目偏好，使得<$q∈Q，i∈At：piqT− Nst（pi）qT≤δ，哪里St pist是pi的最近的核心集代表;δ>0是一个足够小的常数。用户核心集合中的代表向量能够很好地捕捉到用户在亲和组中的兴趣注意，代表向量不必与组中的实际用户潜在向量相同。基于给定矩阵分解的推荐算法图1：建议的集群和导航到p-K集群（CANTOR）的一般框架.3.2框架概述图1显示了CANTOR的总体框架 该框架包括两个阶段：准备和预测。在如算法1所示的准备阶段中，m个用户潜在向量P首先被子采样为Pi，并且被聚类到r个亲和性组At中，其中质心向量vt是从对应的用户向量Pi计算的，其中t = 1。. . R. 对于每个亲和群At，我们的目标是导出一个小的用户核心集St。 为此，我们提出了一种自适应的代表选择方法（算法2）来构建Greatest在数学上证明集合覆盖可以是亲和组的核心集之后，为每个亲和组的用户潜在向量的集合覆盖。最后，对每个亲和组，利用其核心集st进行近似最近邻搜索，得到一个小的偏好项集ct.在预测阶段（算法4），CANTOR首先为每个用户定位相应的亲和组At，然后对优选项目集ct中的少量项目进行排名，从而有效地提供满意的推荐。总之，表1进一步总结了本文中的所有主要符号。3.3准备阶段为了克服传统方法经历的极长准备时间的障碍，我们提出利用潜在空间中的用户向量之间的相似性来加速，如算法1所示。通过用户聚类的亲和组建模大多数传统算法仅依赖于项目潜在向量[30]和邻近图[14，35]的相似性来加速推荐，而没有使用用户之间的关系，潜在用户矢量P项目潜在向量Q二次采样后的用户矢量或P矢量子采样最大余弦相似聚类层LAffinityGroup建模（rcentroidsvt）AffinityGroupsA1，. .. AR层1适应性代表选择（算法2）代表性集合s 1，. ..， S R优选物品设定ct8pi组指示符z（pi）优选项目集cz（pi）将项目j2c按pTq排序z（p）我我JTop-K推荐pi的项目指数At的首选项集构造预测阶段（算法3）准备阶段（算法1）放大图片作者：Jun-Yu JiangXiang，Patrick H.陈伟，谢卓瑞，王伟WWW2180recommendationi=1不∈Rr（（））i（）下一页∈·········∈∈（）下一页（）下一页∈||≪6vi=j∈{j |I [j]=i} P [j];12I = arg maxtvTP;=1=1ti、（二）.其中Pt ={p i |z（pi）= t}包含用户的潜在向量，算法1：CANTOR的制备过程输入：用户潜在向量P;项目潜在向量Q;度每一个用户de <$m;所需的数量K输出：质心向量vt和首选项集ct每个亲和聚类At，t = 1。. . R.1超参数：亲和组的数量r;小世界图搜索大小efs。二次抽样用户数;050010001500200005001000150020002P=多项式_采样（P，de <$mu，u）;P∈Ru×d;度数度数3v1，···，vr= 0;I= 0，I∈Ru×1;i=1(a) 用户分布(b) 项分送4 重复5，对于i=1，···，7vi=vi/vi2;8I = arg maxtvTP;图2：Amazon数据集中不同程度的用户和项目分布由于我们的任务是加速最大内积搜索，9直到收敛;10 int n = nums（nums，nums）;11c1，. . . ，cr = 0，. . . ，;13 对于i=1，R然后，可以通过最大余弦相似性准则更新每个相似性组At的中心点向量vt，如下：.|P|Pvti不. ···，做t.|P-2|P∥215si= AdaptiveClustering（Pi，n，w）;16为qsido17i= QueryProximityGraph（G，s，K）;18ci=cti;属于亲和群At。因此，每个亲和基团At可以通过迭代地运行等式（1）和（2）来获得质心向量vt。然而，当用户数量m较大时，迭代地执行等式（1）和（2）仍然可能花费长的计算时间。为了解决这个问题，我们建议对一部分19返回ct，vt，对于所有t=1，···，r。用户潜在向量的分布。 为了利用用户关系的知识，我们提出了一个基于聚类的框架来建模用户亲和组。设r为所有m个用户的亲和组的数量，其中r学习质心向量。此外，我们根据一类矩阵R中的度分布对特征向量进行采样。例如，图2a显示用户的度分布通常遵循幂律分布。因此，我们不使用均匀采样，而是以与其次数的对数函数成比例的概率对用户i进行采样，如下所示：.n是CANTOR中的超参数我们将所有m个用户划分为r个不相交的聚类，作为亲和组A ={At |t= 1. . . 基于r}在用户潜在向量P ={p i |i = 1。. . m}。另外每个P（X=i）对数j=1Rij，（3）亲和群At在潜在空间中具有质心向量vtRd具有潜在向量pi的每个用户i属于Az p，其中z pi是表示为：z（pi）=arg max vTpi。（一）令C pi，K是用户i的前K个优选项目，其被定义为：{j|pTqj≥pTqj′，nj′gC（pi，K）且|C（pi，K）|=K}，其中X表示目标采样过程的随机变量我们稍后将在定理2中证明，基于子采样的近似误差将渐近有界。在学习了r个亲和性组A1，Ar的质心v1，vr，Rd和相应的用户潜在向量P1，Pr之后，可以构造每个组A1，，的优选项目集合Ct，使得用户向量P1，t仅需要在该优选项目集合上搜索最佳推荐。然而，天真的做法，generatec t需要O（nd）操作来检查所有n个项目i i，以便导出At中每个用户的最佳候选。每个其中Q是项j的潜在向量。直观地，如果用户i和k在相同的亲和性组中，则他们的优选集合C p i，K和C p k，K可能由于他们的相似兴趣而具有实质上的重叠。 这促使我们为同一亲和性组A t中的用户计算优选项目集ct，使得每个ct仅包含所有n个项目的小子集，即，ctn. 代替计算pk和所有项目潜在因子qQ之间的内积，我们可以将候选集缩小为ct，并且仅评估ct中的项目以找到用户k的前K个预测。A组中，A组中，A组中，D组中，A组中，D组中，A组中，D组中，|Pt|（d）考虑到所有|Pt|组中的用户来构造优选项集Ct。Coreset构造作为寻找集合覆盖。为了加速构造亲和群At的偏好项集ct的过程，我们希望找到At的δ-用户核心集，并且仅使用它而不是整个At来构造ct。我们首先定义了δ-集覆盖的概念，然后证明了每个δ-集覆盖对应于一个δ-核集.107107106106105105104104103103102102101101100100用户数量的项目i=114P=PJ |pj ∈ P，I [j]=i;聚类和构造用户核心集加速大规模Top-K推荐系统WWW2181{j|S∅I[j]|||| ≪ ||（）下一页||∈（）下一页（）下一页（）下一页（）下一页（）（）（）下一页（）下一页5si=j∈{j |I [j]=i} P [j];定义4. （n-集覆盖）st是Pt的n-覆盖，如果n-Nst（p）∈ st，使得对所有p∈Pt，Nst（p）PT ≥ n，其中n是实数，Nst（pi）∈ st表示pi在st中的最近向量.定理1. 给定At的一个n-覆盖st，存在一个δ使得S-覆盖st是仿射群At的δ-用户余集。证明见附录A。因此，我们可以通过找到一个具有更大δ的覆盖来构造一个具有任意小δ的用户核心集。算法2：自适应代表性选择输入：亲和性组的用户潜在向量P、迭代次数T、阈值T、新代表的数量w;输出：代表向量s。1初始化s=0;2 I = arg maxtsTP;3 重复4对于i = 1.... |S|做P的采样子集，并渐近推广有界6错误. 表示PAt为P个生成用户的相同采样过程si=si/si2;不向量pi属于At。我们将得到以下结果：7I = arg maxts P;定理2. 对于亲和群At，给定任何查询q，8个离群值=TI[j]Pj {\displaystylep};<从P中提取的k个样本{pi}的覆盖将满足以下条件：9对于j∈离群值，的t概率至少为1−γ的不等式：10从1画出i。. . w;min我..Nst（pi）qT −ptqT.Σ≤δ+2log（1/γ）。K11I[j]= |S |+ i;12如果离群值，则13将w个向量附加到s;14，直至离群值=0;请注意，我们在附录B中演示了证明。定理2表明，我们可以构造子-15个离群值={j|STPj<{\displaystylep};采样向量具有渐近保证的内积值与同一亲和性组内的真实分布的差。因此，我们的任务变成了找到所有At的一个覆盖，并构造它的首选项集ct。因此，我们提出了一种快速的自适应代表选择方法，以有效地构建一个子采样的用户潜在向量为每个亲和力组的覆盖算法2中总结。 对于每个仿射群At，应用自适应代表选择方法，得到几个代表性的仿射覆盖st. 如果存在至少一个用户的特征向量与所有代表向量的余弦相似度低于1/2，则算法迭代地生成更多的代表，直到每个用户与至少一个代表向量具有高余弦相似度。因此，集群覆盖的数量st必须小于或等于集群中的用户向量的数量Pt，并且在实践中，在大多数情况下，stPt。注意，自适应代表选择方法独立地应用于每个亲和性组At然后，利用最小覆盖集构造优选项集，以从O（|Pt|D=O（|St|nd）。用于首选项集构造的邻近图导航。为了避免检查所有n个项目（O nd复杂度）在首选项集的建设，我们采用近似最近邻搜索（ANNS）的方法来加速计算。我们采用了一种基于邻近图的模型[26，35]，该模型显示了ANNS的最新性能。具体地，生成邻近图，其中项目向量是节点，并且相似项目向量的节点通过边连接。由于推荐系统中的项目度倾向于遵循图2b所示的幂律分布，因此该邻近图具有小世界属性[5]，具有稀疏边缘，提供节点之间的高可达性。因此，我们应用分层可导航小世界图[25，26]的模型来获得每个亲和组At的首选项集ct。16将P离群值附加到s;17 返回s。为了将项向量Q的邻近图构造为分层小世界图G，我们迭代地将项向量插入到图中，其中每个节点q具有至多efs近似最近邻居的列表Eq，当插入其他项向量时，该列表Eq可以动态更新，其中efs是超参数。此外，图中的边被组织为层次结构，使得连接具有其对应项向量的高内积值的项的边处于底层，并且连接其向量具有低内积值的项的边处于顶层，从而缩小最近邻居的搜索空间。设L e表示边e的对应层。给定两条边e i和e j，如果L e i> L e j，则由边ei连接的节点具有比边ej更小的内积分数。为了简单起见，令Eq，l表示第l层中通过边连接到节点q的节点的列表。最后，项向量Q的层次小世界图G可以在O dn log n [26，35]中构造，其中n是项的总数;efs被视为常数超参数。注意，efs控制着搜索最近邻的效率和准确性之间的权衡，因为它决定了搜索空间的大小和实际最近邻的潜在覆盖范围。分层小世界图G提供了利用分层贪婪搜索算法高效地查询向量q的K个最近邻居的能力。更具体地说，我们可以通过将查询向量从底层导航到顶层来遍历图G，以导出q的K个近似最近邻，如算法3所示，每个查询的时间复杂度为O d log n。对于每个亲和群At，我们执行小世界图查询以近似每个代表向量st，i，k。然后，通过对各个top-k集合进行联合操作，可以构造首选项集合ct。、另一个很好的属性是，我们可以找到一个集封面上放大图片作者：Jun-Yu JiangXiang，Patrick H.陈伟，谢卓瑞，王伟WWW2182∈（）下一页{1}|（}）i2logits =piQcz（pi）1MYKSK，K算法3：QueryProximityGraph输入：层次小世界图G;查询向量q;输出近似最近邻个数K输出：G中的K个最近向量1p=在G中随机选择一个入口节点;表2：六个实验数据集的统计注意，可以通过将每个用户视为项目并且以与向用户推荐项目的方式类似的方式向用户推荐其他用户来将个性化链接预测问题映射到项目推荐问题，并且在这种情况下，用户和项目的数量相等。2 对于l=1到L，不3p= arg maxr∈{p′|p′E（p，l）}qr;4返回E（p，L）中的K个最近节点到q;算法4：CANTOR的预测过程输入：用户潜在向量pi;项目潜在向量Q;顶级推荐的数量K输出：用户i的估计的前K个推荐的索引。1 z（pi）=arg maxtvTpi;T.t.项目[20]。对于个性化链接预测的任务，我们遵循intn = nums（n，K）;4返回topIndices。作为？|st|ct=用户：YouTube、Flickr和维基百科[20]。请注意，六个实验数据集中的四个，亚马逊，YouTube，Flickr和维基百科，可在科布伦茨网络集合中找到[20]。评价 为了衡量一个近似算法的前K推荐的质量，我们评估前Kap，i=13.4预测阶段定义.. 一 .我使用潜在向量预测用户的热门推荐其中Yi和Si是通过近似计算的前K项，对于每个亲和性组At，CANTOR依赖于由质心向量vtRd和优选项目集ct参数化的聚类模型。更准确地说，我们首先计算亲和群指示符z（p）为：z（pi）=arg maxvTpi，（5）算法hKm和fKul用于用户i的内部预测计算;m是用户的数量。 为了衡量每个算法的速度，我们报告了加速比，该加速比由O mn个内积的完整集合所消耗的挂钟时间的比率来定义，以找到前K个推荐除以近似算法的挂钟时间Rr基线方法。 为了评估我们提出的康托，我们同意-并且在优选项目集合QI的对应项目向量上评估全向量矩阵积P T Q I，I=jjcz p。然后对计算的结果进行排序以向用户提供最终的前K个推荐。算法4示出了预测过程的过程。4实验在本节中，我们进行了大量的实验和深入的分析，以证明CANTOR的性能4.1实验设置实验数据集。我们评估了两个常见任务的性能：项目推荐和个性化链接预测，使用六个公开的真实世界大规模数据集，如表2所示。对于项目推荐任务，MovieLens 20 M数据集（MovieLens）[15]由用户和电影之间的2000万个评级组成; Last.fm 360 K数据集（ Last.fm ） [6] 包 含约 360 K 用 户 的 首 选 艺 术 家 ; Amazonratings（Amazon）数据集包括数百万用户之间的评级，将以下五种算法作为比较的基准方法近似链接预测（英语：Approximatelink prediction）[12]对每个维度的潜在因子的条目进行排序，以构建完整内积的保证近似。Greedy-MIPS（GMIPS）[34]是一种用于解决MIPS问题的贪婪算法，通过改变算法中的计算预算参数来SVD-softmax（SFDS）[30]是一种用于快速softmax计算的低秩近似方法。我们改变SVD的秩来控制预测速度和准确性之间的权衡。快速图解码器（FGD）[35]直接将小世界图于所有项目Q，并导航以获得具有用户潜在向量的推荐项目作为邻近图上的查询它还提供了仅使用邻近图导航的直接基线。学习筛选（L2S）[7]是第一个基于聚类的NLP任务快速预测方法，具有最先进的推理时间结果，但准备时间长。CANTOR的灵感来自L2S中的聚类步骤，因此L2S充当了·····;以前的研究[12]在三个群体中构建了三个社交网络，C（st，i，K）。（四）精确度@K（P@K）的近似建议，任务数据集项目MovieLens建议Last.fm亚马逊#（用户）#（项目）138,49326,744359,293160,1532,146,0571,230,915任务数据集个性化链路预测YouTubeFlickr维基百科#（用户）#（项目）1,503,8411,503,8411,580,2911,580,2911,682,7591,682,759聚类和构造用户核心集加速大规模Top-K推荐系统WWW2183表3：两个任务中六个数据集的前K推荐结果的比较请注意，P@K测量近似完整内积计算的前K个建议的精度SU指示基于推断前K个推荐的原始全内积时间的速度比例如，9.4x意味着该方法的计算时间比完全内积计算时间快9.4倍PT表示预测过程中的准备时间，IT表示预测过程中的推理时间秒、分钟和小时的时间单位分别表示为s、m和h每个数据集的完整内积方法的计算时间为71秒（MovieLens），1，017秒（Last.fm），92，828秒（Amazon），56，824秒（Youtube），71，653秒（Flickr）和72，723秒（Wikipedia）。任务项目推荐数据集MovieLensLast.fm亚马逊方法苏PT它P@1P@5苏PT它P@1P@5苏PT它P@1P@5-大约0.7x0.19s99.00s0.7530.6710.5x1.40s36.78m0.3780.4670.2x23.42s107.34h0.5290.559GMIPS3.9倍N/A18.41s1.0000.9722.3xN/A7.55m0.9970.9661.8xN/A14.57h0.9930.952SVDS1.0x0.10s69.00s1.0001.0000.9x0.10s19.25m0.9840.9841.3x5.32s19.46h0.9520.953FGD2.8x4.94s20.10s1.0000.99910.9x0.49m1.07m0.9970.98819.7x42.76m35.83m0.9860.977L2s3.0x22.15s1.72s1.0001.0009.0x1.77m0.12m0.9930.98021.2x71.02m1.86m0.9880.979Cantor9.4x6.17s1.36s1.0000.99937.1x0.37m0.09m0.9990.99829.0x52.13m1.26m0.9940.991任务个性化链路预测数据集YouTubeFlickr维基百科方法苏PT它P@1P@5苏PT它P@1P@5苏PT它P@1P@5-大约0.1x0.3m129.2h0.3640.4320.4x0.29m53.44h0.5450.5810.2x0.39m130.61h0.3740.480GMIPS1.4xN/A11.12h0.9870.9652.0xN/A10.10h0.9870.9623.6xN/A5.64h0.9910.974SVDS1.0x0.03m15.30h0.9650.9631.4x0.03m14.00h0.9520.9461.4x0.03m14.83h0.9490.944FGD44.8x10.28m10.85m0.9890.98137.5x17.61m14.25m0.9850.98093.7x4.18m8.76m0.9900.985L2s6.9x135.93m0.79m0.9840.9688.3倍142.84m0.58m0.9890.98022.4x53.38m0.84m0.9880.968Cantor112.7x7.75m0.65m0.9930.98554.7x21.31m0.53m0.9940.990355.1x2.45m0.97m0.9950.991直接基线在我们的实现中，随机子采样应用于选择一个子集的用户训练L2S。请注意，[34]已经表明Greedy-MIPS优于其他MIPS算法，包括LSH-MIPS [27，31]，采样MIPS [3]和PCA-MIPS [1]，因此我们在比较中省略了其他MIPS算法。虽然基于Bandit的方法[13，21，22]具有优雅的数学性质和理论界限，但我们最初没有包括它们，因为它们在实际情况下通常比其他方法例如，SCLUB [21]是最先进的基于Bandit的方法之一，在官方实现的Amazon和Wikipedia数据集上仅实现了0.81倍和0.62倍的加速。这是因为基于带宽的方法独立地操作每个维度，并且不能从线性代数运算的低级优化中实施细节。 对于每个数据集，LIBMF库[8]用于训练非负MF（NMF）模型。更具体地说，隐向量的维数是10，而模型是用所有数据训练100次迭代的。注意，我们采用NMF模型是因为CANTOR-Approx的限制，但CANTOR对矩阵类型没有任何限制我们使用BLAS优化的NumPy在Python中实现了CANTOR[4]。对于基线方法，GMIPS，SVDS，FGD和L2 S的实现由原作者提供并高度优化，而我们利用高效的C++实现EST-Approx。所有实验均在64位Linux Ubuntu 16.04服务器上运行，该服务器具有512 GB内存和单线程机制，采用Intel® Xeon® CPU E5-2698 v42.2 GHz。CANTOR中的超参数 对于CANTOR中超参数的一般设置，我们固定子采样用户数潜在向量u为50，000，聚类数r为8。 对于自适应代表性选择，我们将自适应选择中的迭代次数T设置为10，相似度阈值为0.99。自适应代表选择算法中的新代表的数量w被设置为8。 我们还调整了动态最近邻列表的大小efs在每个数据集的分层小世界图的建设，以达到可接受的准确度分数。因此，数据集MovieLens、Last.fm、Amazon、YouTube、Flickr和Wikipedia的efs选择分别为200、200、1，500、500、1，500和4.2性能比较为了公平地比较性能，对于每个数据集，我们调整参数，使每个方法可以大致达到0.99 P@1的准确度。表3显示了CANTOR和所有基线方法在六个数据集上的效率和精度得分请注意，由于GMIPS的开源库没有将执行时间分解为准备和预测时间，因此报告的时间包括准备和预测过程。 在基准方法中，FGD表现最好，因为它利用了最先进的近似最近邻搜索算法来检索每个用户的推荐。虽然L2S是推理过程中最有效的基线，但其准备过程很慢，因此整体加速比进一步降低。 SVDS在准备过程中可以有效地分解偏好矩阵，但仍需要多次检查所有项目才能达到足够的精度，加速效果不理想。此外，值得注意的是，尽管在理论上，X-Approx需要比完整评估更少的乘法，但实际上在实践中并没有提供任何加速。类似于基于放大图片作者：Jun-Yu JiangXiang，Patrick H.陈伟，谢卓瑞，王伟WWW218416141210810110210310410.9950.990.98510546444240383634323010110210310410.90.80.70.61051614121086410110210310.90.80.70.60.50.40.30.20.10807060504030201010110210310.90.80.70.60.50.4使用的抽样用户数(a) MovieLens3230282610.90.80.70.6130125120115110105使用的抽样用户数(b) Last.fm10.90.80.70.60.50.40.33252752251751257525小世界图搜索大小efs(a) MovieLens10.950.9740640540440340240140小世界图搜索大小efs(b) Last.fm10.980.960.940.921011021031041051011021031041051011021030.8540101102103使用的抽样用户数(c) 亚马逊64626058565452101102103104105使用的抽样用户数(e)Flickr10.90.80.70.60.50.4550500450400350使用的抽样用户数(d) YouTube加速P@1101102103104105使用的抽样用户数(f)维基百科10.80.60.40.2085075065055045035025015050小世界图搜索大小efs(c) 亚马逊101102103小世界图搜索大小efs(e)Flickr10.980.960.940.920.90.880.860.840.820.80.7855050045040035030025020015010050小世界图搜索大小efs(d) YouTube101102103小世界图搜索大小efs(f)维基百科10.990.980.97图3：在六个数据集中，不同数量的抽样用户u上方法，这是因为每个维度都是独立处理的，因此模型无法从线性代数运算的任何低级优化中获益。我们的方法CANTOR显着优于所有的基线方法，在加快整体执行时间，以提供所有数据集的前K建议。 更具体地说，CANTOR的预测过程的推理时间与L2S相似（这也减少了候选项集以减少计算），但CANTOR的准备过程要快得多。这是因为很好地利用了用户潜在向量之间的相似性，以避免不必要的和冗余的计算。4.3子采样用户潜在向量的数量u由于只有一小部分用户特征向量将被二次采样用于用户聚类，我们验证了二次采样用户的数量如何影响效率和准确性。 图3显示了六个数据集中不同数量的抽样用户的P@1得分和CANTOR加速比。很明显，较少的采样用户潜在向量的数量伴随着更大的加速比和更低的P@1得分。然而，CANTOR一般可以在抽样超过图4：在六个数据集中，不同大小的超参数efs上在所有数据集中大约有
