二部图高效相似搜索及近似算法

308ˆ（）下一页O（|U|）的方式（）（）ˆ二部图上的高效相似搜索杨仁池renchi@nus.edu.sg新加坡国立大学摘要二分图上的相似性搜索旨在从图中检索彼此相似的节点，其在诸如在线广告、推荐系统等各种领域中找到应用现有的相似性度量要么（i）忽略了二分图的独特属性，要么（ii）无法准确地捕捉节点之间的高阶信息，导致次优的结果质量。最近，隐藏的个性化网页排名（HPP）被应用到这个问题，并发现是更有效的与以前的相似性措施相比。然而，HPP计算的现有解决方案会产生显著的计算成本，使其效率低下，特别是在大型图上。在本文中，我们首先确定HPP的固有缺陷，并克服它提出双向HPP（BHPP）。然后，我们将二部图上的相似性搜索问题转化为近似 BHPP 计算问题，并给出了一个有效的解决方案APPROX-BHPP。具体而言，AppR ox-BHPP通过以优化和非平凡的方式将确定性图遍历与矩阵运算相结合来提供具有最佳计算复杂性的严格理论精度保证此外，由于几个精心设计的优化，我们的解决方案在实际效率上取得了显着的增益。在7个真实二部图上将BHPP与现有的8种相似性度量进行了比较，实验结果表明BHPP在查询重写和项目推荐方面是有效的。此外，App R ox-BHPP在小型和大型数据集上的计算时间方面通常优于基线解决方案多达几个数量级。CCS概念• 计算理论→图算法分析;·信息系统→相似性度量。关键词二部图;相似搜索;近似算法ACM参考格式：杨仁池2022年二部图上的高效相似搜索。 在ACM Web Conference 2022（WWW '22）的会议记录中，2022年4月25日至29日，虚拟活动，法国里昂。ACM，美国纽约州纽约市，11页。https://doi.org/10.1145/3485447.3511959本 作 品 采 用 知 识 共 享 署 名 国 际 协 议 （ Creative Commons AttributionInternational）授权4.0许可证。WWW©2022版权归所有者/作者所有。ACM ISBN978-1-4503-9096-5/22/04。https://doi.org/10.1145/3485447.35119591引言二分图是一种普遍存在的数据结构，用于建模两组异构对象之间的关系，例如查询-网页，客户-产品，以及作者-论文。二分图上的相似性搜索是数据挖掘中的一项基本任务，并在在线广告[8，11，22]，推荐系统[33，43，44]，生物医学分析中找到了许多实际应用。[20，61]和其他域[58，63，69]。 给定具有两个节点划分U和V以及U中的节点u的二分图G，G上的相似性搜索的目标是基于预定义的相似性度量从U中检索与u相似的节点。理想情况下，一个良好的相似性度量不仅可以量化节点之间的直接和间接的相互作用与二分结构的考虑，但也是计算友好的;换句话说，相似性度量可以捕获复杂的拓扑信息，节点周围的成本效益。在文献中，过多的相似性措施[7，30，35，38，41，42，62，73，74]的一般图或集。这些措施要么忽视了二分图的特殊属性，或未能纳入节点之间的高阶信息，因此，在二分图挖掘任务的性能低于标准杆。 在[37]中，Jeh和Widow提出了众所周知的相似性度量，即。SimRank是一种基于递归定义的二分图的相似性度量方法：如果两个节点与相似的节点相关，则两个节点相似。 SimRank在随后的工作中进一步增强[11，22]，将证据度量和无标度属性纳入其定义中。虽然这种基于SimRank的相似性度量获得了令人鼓舞的结果，但由于其递归定义，它们需要巨大的此外，它们在无标度二分图中产生次优的相似性得分[22]。 最近的研究[19，23]提出了一种很有前途的相似性度量HPP，它在二分图的各种应用中表现出很高的结果质量。具体地说，HPP被定义为图G上的个性化PageRank（PPR）[30，38]，该图G是基于仅具有U中的节点的二分图G构造的。之前用于HPP计算的方法需要高达2的空间成本，G的物化，这是禁止大型图。因此，现有的一般图上的PPR计算技术不能有效地解决这个问题，这带来了很大的技术挑战。此外，HPP值πu，u，i是有偏差的，因为它描述了从源节点u的角度来看的u，i的相关性，而不管目标节点u，i的角度如何。为了解决这个问题，我们提出通过节点u和ui的双向HPP（BHPP）来测量节点u和u i之间的相似性，即πu，ui+πui，u，这在效率上提出了额外的挑战本文对BHPP的计算进行了深入的研究，并做出了以下贡献。首先，我们将二分图上的相似性搜索问题形式化为具有绝对误差保证的近似BHPP查询问题，并指出WWW杨仁池309（）下一页O（|E|·）|E|（）下一页∈∈（）（）（）下一页（）（）（）（·）（）（）（（））∈ing节点ui（分别v），即，j..（）下一页ˆ∈（）L我LJ（（））（）（（））w（ui，vj）w（vj，ui）用于PPR计算的现有技术中没有一种可以简单地应用于有效地解决该问题。此外，我们提出了App R ox-BHPP，它以查询节点u和绝对误差阈值μi作为输入，并返回近似BHPP值β ′ u，ui，对于U中的每个节点ui，最多具有μi的绝对误差，具有log1的近似线性时间复杂度，其中表示输入图形中的边数。最后但并非最不重要的是，在7个真实数据集上，对BHPP在两个重要的图挖掘任务上的有效性以及App R ox- BHPP的查询效率进行了广泛的实验评估。 我们的实验结果表明，BHPP实现了优越的性能相比，现有的相似性的措施，我们提出的应用程序的ox-BHPP是数量级快于基线解决方案。本文的其余部分组织如下。第2节回顾了相关工作。第3节定义了符号和问题。在第四节中，我们给出了应用程序的算法设计-BHPP确定性图遍历与随机游走，以提高效率。特别是在Ref. [82]，Wuet al. 将前推[10]与幂迭代[57]结合起来，这与我们在第4.1节中提出的SS-Push的精神相似。然而，他们的方法是为一般图设计的，并且采用了与我们完全不同的推策略。另一个流行的研究方向集中在单源top-k PPR查询[25，48，49，51，52，70，80，81，86]，它返回具有top-k最高近似/精确PPR值的节点。几项研究[9，16，48，50，76，78]调查了PPR查询w.r.t. 单个节点对或目标节点。 最近的研究集中在动态图[13，18，56，84-86]和并行/分布式设置[27，28，34，46，67，77，79]，这超出了本文的范围。3预赛3.1符号设G=（U∈V，E）是一个二部图1，其中节点可以是几种有效的技术。我们的解决方案和竞争对手划分为两个不相交的集合：U={u1，u2，···，u}，其中car-||在第5节中进行了评估。最后，第6节对本文进行了总结。引理和定理的证明见附录A。二进制|U|且V ={v1，v2，···，v |个文件夹|}U关于cardinality|.|. 每个2相关工作2.1二部图上的相似搜索在文献[7，30，38，41，42，62]中，针对图上的相似性搜索提出了大量的相似性度量这些测度主要是针对一般图而设计的，忽略了二部结构。见参考文件 [37]，Jeh和Widom提出了在二分图上进行相似性搜索的二分SimRank。尽管它的有效性，SimRank遭受O n 4的高时间复杂度，其中n是图中的节点数。在随 后 的 工 作 中 [11] ， Antonellis et al. 设 计 一 个改 进 版 的SimRank，ui，vj，w ui，vj连接U中的节点ui和节点vj在V中，权重为w ui，vj。 注意，每条边ui，vj，w ui，vj都是无向的;因此w ui，vj=wvj，ui和vj，ui，wvj，ui E。我们用N u（分别）表示Nv）节点u的邻居的集合（相应地，V），和D U（分别）。dv）节点u的度（分别地，v）。矩阵和向量用粗体和小写字母表示，例如。，M和x。我们用Mi表示（相应地，M，i）第i行（相应地，列）M的向量，并且由Mi，j表示第i行和第j列的元素我们使用U R |U |×|V|（分别） V R |V |×|U|），以表示前进（resp. 后向转移矩阵。具体来说，对于每个节点ui∈U和每个节点vj∈V，我们有U（ui，vj）=，且V（vj，ui）=，称为SimRank++，并已显示出有效的应用程序ws（ui）ws（vj）SimRank++在赞助搜索的查询重写问题最近，在参考文献[22]中引入了P-SimRank，它通过引入无标度属性来优化SimRank和SimRank++其中ws（u，i）（resp.ws（v，j））是连接到ws（ui）=.v∈N（u）w（ui，vl），ws（vj）=.u∈N（v）w（vj，ul）（1）都是计算上昂贵的，特别是对于大型图，并且具有一些固有的缺点[22]。 在最近的工作[19]，邓等人。 提出HPP，将PPR[30，38]扩展到广义迭代框架中的二分图。 为了实现对大规模二分图的动态相似性搜索，Epasto et al. [23]提出了一个MapReduce框架，它支持几个流行的相似性度量的实时计算，如邻居相交，Jaccard系数，Katz指数[ 41 ]和HPP。此外，在Ref. [54]，作者采用基于命中时间的相似性度量来从搜索日志中识别相关查询。Tong等人 [72]研究了动态二分图中的节点相似性跟踪。2.2PPR计算这项工作也与PPR计算高度相关，因为HPP是从二分图构建的图上的PPR在过去的几年里，PPR在文献中得到了广泛的研究，如[59]所述。存在大量文献[10，12，18，24，3845，47，52，57，64，65，68，80，82，83，86]用于单源PPR查询。其中，[10，38操作，[12，24，47，65]使用大量随机游走估计PPR值，最近的几项节点集U的隐藏转移矩阵[19]P定义为：P= U·V ∈ R|U |×|U|，其中每个（ui，vj）条目通过下式计算：P（ui，uj）=vl ∈N（ui）<$N（uj）U（ui，vl）·V（vl，uj）.（二更）在P中，非零条目的数量最多可以为O （ |U|2 ）当n ∈V有O（|U|）neigh borsinU.3.2问题定义给定一个二分图G，两个节点u，ui在U中，重新开始概率α0，1，隐藏个性化PageRank（HPP）[19，23]πu，uiui w.r.t.u被定义为从u开始的重新开始随机（RWR）[71]将在ui结束的概率。更准确地说，在每个步骤中，源自u的RWR（i）以α概率终止于当前节点ul，或者（ii）基于转移概率P（ul，uj）导航到节点uj。在数学上，HPP值π（u，ui）用公式表示如下[12]：π（u，ui）=∞∞=0α（1−α）<$·P<$（u，ui）.（3）本质上，HPP是基于G构造的加权图G上的个性化PageRank（PPR）[30，38]，其中节点集1按照惯例，我们考虑无向二部图。边缘二分图不幸的是，这些基于SimRank的措施二部图上的高效相似搜索WWW310ˆˆ()∀ ∈（）（）w（vu）ws（v）jw（u五）ws（u）j（）∈（||） 的方式·（·）·（）（）∈·∈（||·（/））（）∈（）下一页−2（1 +1/3） ·l n（|U|/pf）（）∈需要进行O2随机游走的总数算法1：重复迭代输入：二分图G，初始向量e，重新开始概率α和迭代次数t。输出：π。1 π←e;2对i<$1到t做π<$e+（ 1−α）·（π·U）·V;算法2：选择IvePUSH输入：二分图G，目标节点u，重新开始概率α和错误阈值αb。输出：{←π−（ui，u）|ui∈U}，<$r−u（·）.1<$r−u（u）<$1;<$r−u（x）<$0<$x∈U<$V且x<$u;2<$π−（ui，u）<$0<$ui∈U;3 π←α·π;3 而true确实←−4 returnπ;G的权是U，边的权定义为Pu，uiu，uiU[19，23]。 本文将G上的PPR称为HPP，以区别于G上的朴素PPR。 回想一下，PPR通常仅从节点u和π u，ui <$π ui，u的角度测量节点u i的相关性。因此，HPP是一种有偏的相似性度量，具有有限的有效性。为了弥补这一点，我们建议通过节点u和ui之间的双向隐藏个性化PageRank（BHPP），即模型的相似性。、β（u，ui）= π（u，ui）+ π（ui，u）.（四）4对于u i∈Us. t. ru（ui）>bdo对于vj∈N（ui），6<$r−u（vj）<$<$r−u（vj）+（1−α）· j，i·←r−u（ui）;7<$π−（ui，u）<$<$<$π−（ui，u）+α·<$r−u（ui）;8<$r−u（ui）<$0;9，其中vi∈Vs. t. ←r−u（vi）>0do10对于uj∈N（vi）do11r−u（uj）+j，i·←r−u（vi）;12<$r−u（vi）<$0;13如果ui∈Us. t. ←r−u（ui）≤b则break;本文着重于计算近似BHPP值。我们考虑近似BHPP查询，如定义3.1中所定义的。定义3.1（查询-近似BHPP查询）。 给定一个二分图G =UV，E，一个查询节点u U和一个错误阈值ε，一个λ-近似BHPP查询返回一个近似BHPP值βu′（ui），对于每个n odeui∈U，满足|β（u，ui）− β ′（u，ui）|≤ 100%。（五）3.3基本技术二分图G上的HPP计算的现有解决方案[19，23]首先构造隐藏转移矩阵P，然后直接应用PPR计算技术[57]与P。 这些解决方案不能有效地处理大型图，因为它们需要P的物化，由于巨大的构建时间和存储空间（在最坏的情况下高达O U 2），这是非常昂贵的。Epasto等人 在Ref. [23]用于可扩展的HPP计算，其依赖于大量的计算资源。此外，现有方法主要针对14转{←π−（ui，u）|i∈U};在加权图上采样，MonteCAR lo需要在预处理阶段构建每个节点的邻域的别名结构[75]，导致巨大的开销。3.3.2电力时代[57]。 通过迭代地求解以下线性方程组[57]（方程组的变体）来估计HPP值。（3）：π u = α·eu+（1 − α）·π u·P，（7）其中euR1×|U|是一个独热向量，其入口值为1u和0在其他地方，π uui =πu，uiuiU，P=UV. 算法1给出了当输入图G和e=eu时，近似π u的伪码-注意，算法1通过将矩阵乘法π P解耦和重新排序为πU V（第2行）来消除对具体化P的需要，从而将每次迭代中的矩阵-向量乘法的成本降低到O（|E|）的。为了得到π（u，ui）的估计，至多如果是绝对误差，算法1至少需要t=log11− 1计算粗略估计的HPP值，而不是回答1−αf近似BHPP查询。在下文中，我们首先介绍了三种基本技术，这些技术适合于HPP计算，同时避免了矩阵P的物化，然后解释了如何利用它们来回答近似BHPP查询。[15]矩阵乘法的迭代，这导致总时间复杂度为O Elog1f。假设有一个很大的误差阈值，例如，则f = 0。1，但它仍然需要大约14次矩阵-向量乘法迭代，这是相当昂贵的。3.3.1Mon T eCar L o [24]. 回想一下，HPP值π（u，ui）为：3.3.3[9]第一个问题。不像蒙特卡洛和伊特鲁-定义为从u开始的RWR终止于ui的概率。因此，一个简单而直接的方法是模拟从u开始的许多随机游走，然后使用在ui处结束的随机游走的分数作为n。 π（u，ui）的估计。根据[24]，我们eRATI on 方法，其返回近似的HPP 值w.r.t.源节点u，SelectIVEPUSH估计到目标节点u的HPP值，即，，πui，u uiU.算法2示出了SelectI vePUSH的伪代码。简而言之，SelectI vePUSH是一个确定性的确保对于每个u∈U从u到G的图遍历。最初，算法2设置残差我|π′（u，ui）− π（u，ui）|<宾馆（6）←r−u 对于源节点u，u=1，对于G中的其他节点，u = 0，以及←−概率至少为1pf。如先前的工作[49，80]所示，MonteC AR lo效率相当低，因为它需要对大量的随机游走进行采样。此外，为了便于随机游走，作为近似HPP值πui，u=0uiU（第1-2行）。接下来，它迭代地将所选节点的残差推送到它们的邻居。在每一次迭代中，给定绝对误差阈值Rlb，如果re是任意nodeui∈U，且residue<$r−u（ui）>nb（第4行），对于版本的MonteC AR lo，它递归地推送残基（即，RWR的还未停止的部分）期间沿着边缘FWWW杨仁池311（）（）{（）| ∈}.←−（）下一页（）≤.∈（）（）u∈Ui∈（）...βOα22（）（）∈（）（）（）（||·（/））·ϵui，SelectI vePush的每个邻居vJ将vj（1-α）·w（vj，ui）·<$r−u（ui），并将 <$r−u（ui）的α部分转移到ui算法3：SS-PUSH输入：二分图G，目标节点u，重新开始概率α和ws（vj） ←−←−aner rorth reshold.近似HPPπui，u（第5-7行）。当u i的邻居都被处理时，残差ruui被设置为0（第8行）。随后，算法2将V中节点的剩余推回到U中的节点。 更具体地，如果V中的任何节点vi具有非零残基（行9），则对于vi的每个邻居uj，算法2将uj的残基增加（1−α） ·w（uj，vi）·←r−u（vi）（第10-11行）。之后，算法2重新设置输出：<$π−ui，uuiU，<$r−u。第1-2行与算法2中的第1-2行相同3np←0;/* 选择性推送 */4 而true确实第5-9行与算法2中的第4-8行相同←−ws（uj）10N n+N（n）;ru（vi）到0（第12行）。SelectI vePUSH重复上述过程p p i直到U中的节点的残基都小于100b，并且V中的节点都没有正残基（第13行）。 注意，算法2不同于用于PPR计算的原始SelectIVEPUSH。特别地，在算法2中，我们交替地在U和V之间推进剩余，从而避免了矩阵P的物化。引理图3.2展示了算法2的一个关键性质。让我们来看看3.2. 考虑算法2中的任何迭代（第4-13行）。 在迭代结束时，以下等式成立。π（ui，u）=<$π−（ui，u）+uj∈Uπ（ui，uj）·<$r−u（uj）.（八）由于算法2在针对U中的每个节点ui的剩余量<$r−uui<$b时终止，因此引理3.2暗示由算法2返回的每个HPP值πui，u满足第11-14行与算法2中的第9-12行相同15np←np+N（vi）;16如果ui∈Us. t. ←r−u（ui）≤nb或则17转{←π−（ui，u）|ui∈U}，<$r−u;18如果不等式（10）成立，则破;/* 顺序推送 */19whileuiUs.t. ←r−uui>b和←r−uui>bdouiUs. t. ←r−uui>0do第21-28行与算法2中的第5-12行相同29转{←π−（ui，u）|ui∈U}，<$r−u;（3）如何将上述两种算法以优化的方式以提高效率？|B.|<ϵb.（九）4近似BHPP算法让我们来看看3.3.算法2运行在Ovi∈Vd（vi）2|U|·α·βb摊销时间为了规避这些挑战，我们首先提出了一个优化的SelectIVEPUSH的版本，称为Selective和SsequentialPush引理3.3提供了选择购买的摊销成本。Selec-TIVEPUSH算法由于自适应地考虑了每个节点的剩余，在实际中运行速度很快。然而，它不能有效地计算高精度的HPP值的图与大的平均度。在最坏的情况下，时间复杂度为|E|，比BO（|E|·log（1/f））-P波函数的边界。（下文称为SS-PUSH）;之后，我们在第4.2节中提出PI-PUSH（基于功率迭代的推送的缩写）以减轻并行迭代的效率问题，然后详细说明SS-PUSH和PI-PUSH的集成以获得我们的主要建议解决方案App R ox-BHPP，用于回答近似BHPP查询。4.1SS-PU sh3.3.4基线和挑战。节点u的近似BHPP查询（参见定义3.1）要求对U中的每个节点ui的精确BHPP值βu，ui=πu，ui+πui，u的近似，其中最大绝对误差为π。以概率方式回答节点u的近似BHPP查询的一种直接方式是计算π′（u，ui）， =在MonteCAR lo andget←π−（ui，u）通过SelectIvePUSH，其中对于U中的每个n odeui，一个c-根据Eq. （6）Eq. （9），和d值π′u，ui +←π−ui，u满足Eq.（8）概率大类似地，用于近似BHPP查询的另一种方法选择I veP USH，t= log 12−1和b=。在深入研究SS-Push的算法细节之前，我们给出了SS-P USH的高级概念。 SS-Push在某些情况下会遇到严重的效率问题。为了解释，考虑输入二分图G的节点vV，其连接到节点集合U中的100个邻居u1-u100。根据算法2中的第4-12行，在每次迭代中，v首先（i）接收来自所选邻居的残差，然后（ii）对u1-u100进行100次推送操作。在几次迭代之后，只有少数v的邻居会被选择，因为大多数节点的残差略小于10b。因此，为了消耗一定量的v的残留物，选择性1−αϵ2迭代，每个迭代涉及至少100个推送操作，然而，由于MonteC AR lo和MONTER It-e RA t I on方法的低效率，以及Select I veP USH的不足，用于近似BHPP查询的上述两种解决方案都招致巨大的成本，特别是对于大型图。为此，我们需要解决三个技术挑战：(1) 如何克服Select I ve PUSH的固有缺陷，将其成本降低到OE log 1？(2) 如何设计一个算法，提高了在传统的迭代-在不降低其理论保证的情况下，如何提高实际效率随机访问相邻节点。缓解这个问题的一个有希望的选择是在每次迭代中利用顺序推送，其在推回到u 1 - u 100之前在一个批次中聚合来自v的邻居的残差。然而，顺序策略执行推操作，而不管每个节点处的剩余，导致大量冗余的推操作。 为了克服这两种策略的局限性，我们采取了贪婪和自适应的方式将它们结合起来。具体来说，我们执行选择性推送，同时记录其实际成本，一旦前者的记录成本超过估计的计算成本，则切换到顺序推送。Σ二部图上的高效相似搜索WWW312{（）| ∈}.Σ∈∈（）∈ui∈U=ws（ui）←π−（ui，u）+u∈Uπ（uj，ui）ws（uj）<$r−u（uj）.（绝对的er r或在每个应用程序中的最大值HPP<$π−（ui，u）。（11）be来π（u，u）≤ws（ui）·<$π−（u，u）+<$f·uj∈Uπ（uj，ui），其中ui∈Uu我Bu我它导出t= log 1ui ∈U− 1。每次迭代（行pushes olvesG使用后者的成本开关由精心设计的阈值动态控制下面我们介绍细节。4.1.1续费 算法3显示SS-Push的伪代码。给定二分图G、目标节点u、重新开始概率α和绝对错误阈值αb作为输入，SS-PUSH开始于初始化剩余向量<$r−u并应用最优化HPP<$π−（ui，u），算法4：PI-PUSH输入：二分图G，源节点u，重新开始概率α，参数λ，er r或thresholdf，{<$π−（ui，u）|ui∈U}，<$r−u.输出：→−πu，uiuiU。/* 选择性推送 */1通过等式计算γ（14）;ui∈U，如算法2中的行1-2，并且执行的第2-14行与算法3中的第3-15行相同，由ws（u）·dsp表示的dsp;push操作np=0（第1-3行）。之后，算法3开始ws（ui） λ- 如算法2中的行4-12的选择性推送的迭代过程，在此期间，选择性推送的记录成本np增加N（ui）（分别地，N（vi）），如果ui∈U（resp.vi∈V）的值（第5-14行）。算法3终止iterati v e p rocessandre turns{←π−（ui，u）|ui∈U}，其中有←r−ueve ryresidue<$r−u（ui）不大于b（第16-17行）。115如果Ine质量（12）保持ui∈U，则返回{→−π（u，ui）|ui∈U}表示方程（15）;16如果不等式（13）成立，则破;/* 幂迭代 */17 对于ui∈U，18计算→−ru（ui），代入等式（16）;19计算→−π（u，ui），代入等式（15）;n p≥ 2 |E|· log11−α.ui∈U<$r−u（ui）（十）20根据等式计算t。（17）;21pu←PoweRIteRAtIon（U，V，→−ru（U），α，t）;另外，在第18行，如果算法3耗尽其用于选择性推送的计算预算（即，，方程式在满足第16-17行的终止条件之前，它明智地切换到迭代顺序推送（第19-28行）。在顺序推送的每次迭代中，SS-PUSH如算法2中的第4-12行那样对具有正残基的所有节点u i U和v i V执行推送操作，除了第4行处的push b被0替换（第20-28行）。迭代p rocessstopsand returns{←π−（ui，u）|ui∈U}，带<$r−u（第29行）u我B22对ui∈Udo→−π（u，ui）<$→−π（u，ui）+pu（ui）;23转{→−π（u，ui）|i∈U};PI-PUSH利用了由以下观察所激发的想法具体地说，将引理4.2插入引理3.2，π（u，ui）=ws（ui）<$π−（ui，u）+.u∈Uπ（ui，uj）<$r−u（uj）ws（ui）J当<$r−（u）≤<$<$u∈U或。←r−（u）≤（第19行）。在ws（u）ws（u）特别地，算法3重新估计剩余向量←r−u，以便于其与PI-PUSH的组合，如后续章节所述ws（u）jws（u）给出一个err或thr-holdf，如果我们假设rews（uj）·<$r−u（uj）≤holdf，则方程：4.1.2分析. 定理4.1表明算法3确保λws（.u）λbiws（u）iλ第4.1条（SS-Push的相关性）。给定目标节点u，这意味着ws（ui）·<$π−（ui，u）可以作为欠估计为每个节点关于π（u，u）ws（u）ui∈U使得π（ui，u）π（ui，u）− π ′（ui，u）≤πb。I. 在这方面，与其雇用一名律师，计算HPP值w.r.t.从头开始计算源节点u，我们可以将SS-Push返回的残差和近似HPP值进行变换，以获得粗略的近似值，并在当Eq.（10）持有，则─PI-PUSH使用一些选择性的推送和功率迭代。沿着..1ΣΣui∈U 我 u本文总结了PI-PUSHin算法的伪代码因此，由该阶段产生的电流为O| ·|·log.←r−（u）. 在4并在续集中解释其细节。在顺序推送的过程中，每次迭代都将←r−uuiuiU进入HP P。迭代次数对于顺序推送是t。注意，在最坏的情况下，4.2.1细节。PI-Push的输入参数与那些SS-PUSH，除了它接受绝对误差阈值当推停止时。<$r−（t）（u）≤r，其中r e<$r−（t）（u）表示后的残渣用一个额外的参数λ和初始的应用最大HPP值{←π−（ui，u）|ui∈U}与剩余向量测试顺序推送的迭代。因此，我们有←r−ureturnedbySS-PUS H. 与SS-PUSH类似，PI-PUSH包括.u∈U<$r−（t）（ui）=.u∈U。1−。tα（1−α）<$r·<$r−u（uj）≤<$b，两个阶段：选择性推送（第1-16行）和幂迭代国际新闻报.=0←r−u（ui）（第17-22行），其中使用幂迭代来缓解当过多的推送操作20-28）的连续1−α投资银行的遍历;因此，选择性推送，如算法3中的第3-15行。与SS-PUSH不同，选择性阈值ω f被替换为ω s（u）·ωf。此外，本发明还提供了一种方法，时间开销由O（|E|）的。总的来说，bws（ui） λSS-Push的时间复杂度为O（np+|E|（1）A=O（|E|·log（1/logb））。4.2皮-普乌什最多.如第4.1节所述。首先，PI-PUSH迭代地执行se-二部图上的高效相似搜索WWW313算法4中的选择性推送的终止条件改变如下：（i）对于每个节点ui∈U，让我们来看看4.2. 对任意两个结点ui，uj ∈ U，π（u，ui）=π（ui，u）.←r−u（ui）≤ws（u）·f（十二）ws（ui）ws（u）ws（ui） λWWW杨仁池314.（）∈（）（）ws（u）（）（）−{（）| ∈}（）（）（）{（）| ∈}ws（u）ΣΣ..阿维尼翁|E|·≤（）u∈Uws（ui）·<$r−u（ui）ws（u）ui∈U√γ布拉夫ϵ应用程序ox-BHPP可以最小化，算法5：App rox-BHPP输入：二分图G，查询节点u，重启概率α，10。8Avito参数λ和误差阈值λ，λb。0。60。4DBLP输出：{β′（u，ui）|ui∈U}。1 {←π−（ui，u）|ui∈U}，<$r−u<$SS-PUSH（G，α，u，nb）;2f<$−b;0。2000.02 0.04 0.06 0.08 布KDDCup3 {→−π（u，ui）|ui∈U}<$PI-PUSH（G，α，u，λf，λ，{<$π−（ui，u））|ui∈图1：γvs.γb。U}，<$r−u）;→−←−4对ui∈U，doβ′（u，ui）<$π（u，ui）+π（ui，u）;5转{β′（u，ui）|i∈U};保持，或者（ii）由选择性推送np引起的实际成本超过预定义的计算预算，即，、.Σ1−α我4.3完整的算法和分析算法5总结了AppR ox-BHPP的伪代码，其将二分图G、查询节点u、重新开始概率α、两个错误阈值α、αb（αb）以及参数λ（参见等式1）作为输入。<（18））。特别地，λ可以在预处理步骤中基于等式（1）有效地估计。（19）并保证是一个紧n p≥2 |E|·log 1.、（十三）基于引理4.4的maxui ∈Uuj ∈U π（uj，ui）的上界。让我们来看看4.4. 假设ρ是幂运算其中，γ在第1行基于公式14计算。当。输入参数e=1和t=τ。然后，我们有λ≥γ←.u∈Uws（ui）·<$r−u（ui）.（十四）maxui∈Uuj∈Uπ（uj，ui）成立，其中iws（u）λ=min.max u∈Uρ（u i）+|U|·（1 − α）τ +1，maxui∈U ws（ui）.（十九）如果第一个条件成立，算法4返回imin uj∈U ws（uj）→−π（u，ui）=ws（ui）·<$π−（ui，u）（15）作为每个节点uiU的πu，ui的估计（第15行）。 另一方面，如果不等式（13）（即，第二个条件）被满足（第16行），则PI-Push继续以利用几次幂迭代来细化结果。更具体地说，我们首先将近似HPP值<$π−ui，u和剩余值<$r−uui到应用程序最佳HPP中values→−πu，ui 和剩余物→−ruui 这就是Eq。（15）Eq.（16），分别（行17-19）。在在线阶段，算法5首先调用具有绝对err或thr_holdb的SS-Push来计算←π−ui，uuiU和←r−u（第1行）。然后，这些中间结果与f=b一起为：传递给PI-PUSH。在调用PI-PUSH之后，我们得到→−πu，ui ui联合最后，可以通过β′u，ui计算出U中每个节点ui的最佳BHPP值 =→−πu，ui +←π−ui，u，它被保证是λ-近似的，如定理4.5所示。方法4.5（应用程序-BHPP的相关性）。算法5→−r u（ui）=ws（ui）·←r−u（ui）（十六）返回β ′（u，ui），对于每个ui ∈ U，满足等式（五）、随后，算法4计算pu（ui）作为附加估计。π（u，ui）的信息部分，通过使用输入调用函数IteRA tI on4.3.1选择时间复杂度和时间复杂度。在下文中，我们讨论如何合理地选取数据库b，使得App R ox-BHPP运行参数包括图G，长度-|U|剩余向量→−ru（U），在最佳时间。由于f+b=，App rox-BHPP可以被公式化为以下函数：重新开始概率α，以及等式中定义的迭代次数（17）（第21行）。.f（b）=O.|·| ·.log1+布logγ=−logγ。b·（t=log11−αui∈U→−ru（ui）−1（17）因此，AppR ox-BHPP.|· log 1|·log 1ΣEventually，PI-PUSHgiveseach→−π（u，ui）afinaltouchbyaddingpu（ui），并将其作为π（u，ui）的估计返回（第22-23行）。4.2.2分析。定理4.3建立了PI-PUSH的精度保证。第4.3条（PI-Push的相关性）。算法4返回一个近似HPPπ′（u，ui）对于每个节点ui∈U，使得π（u，ui）-由于γ 1.根据fb，随着fb的减少和SS-P的增加，随着时间的推移，γ单调减小，PI-PUSH的成本降低。为了在SS-PUSH和PI-P USH所产生的成本之间取得平衡，我们需要选择合适的成本。为此，我们首先根据以下经验发现量化γ和β b之间的关系。图1绘制了将γ b从10 −6变为0时的γ值。1在我们实验中使用的三个真实数据集上在第5节。 可以观察到，γ µ（0 <µ ≤ 1），其中µπ′（u，ui）≤πf，当输入参数λ满足大概是，b最大（十八）|·|V|/|E|.|. 因此，计算时间接下来，我们分析了PI-PUSH的时间复杂度。首先，协议-b=|E|−√|U|·|V|.（二对于算法4中的第16行，PI-PUSH中的选择性推送2−µ2 |E|−|·|V|V|γλ≥uj ∈U π（uj，ui）.WWW杨仁池315（||）布拉夫..ΣΣ以O.|·| ·.log.时间到了此外，ui∈U→−ru（ui）Ite RA t I on消耗OE时间，而PI-PUSH执行t（参见等式2）。（17））幂次迭代（算法4中的第21行）。康-因此，PI-Push算法的时间复杂度为O |E|·log γ。5实验本节在7个真实数据集上实验评估了BHPP和其他8种相似性度量在查询重写和项目推荐上的有效性，并比较了AppR ox-BHPP二部图上的高效相似搜索WWW316−.∈N（q）<$N（q）w（qj，qk）.为了评估效果-asdes（qi，qj）=L中的用户项对（v，u）然后通过Eq.（21）[66]。让.d（qj）J表1：点击图的统计BHPP HPP Pearson JaccardSimRank PPRCoSimRankSimRank++ P-SimRank表2：用户项图的统计0。850。830。810。790。770。75NDCG@k(a) Avito0.9980.9940.9900.986NDCG@k(b) KDDCup0.9960.9940.9920.99NDCG@k(c) AOL在效率方面，与用于近似BHPP查询的两个基线解决方案进行 为了进行公平的比较，所有算法都是用C++实现的，并由具有O3优化的g++7.5编译，并且所有实验都在具有Intel Xeon（R）E7-8880 v4@2.20GHzCPU和1 TB RAM的Linux机器上进行。5.1数据集我们使用7个在以前的工作中使用的真实二分图进行实验[17，19，23，29，31，53，60]，包括3个点击图和4个用户项图，它们将分别用于第5.2节和第5.3节中的查询重写和项推荐5.1.1单击图表。 表1列出了3个点击图的统计数据：Avito、KDDCup和AOL，每个点击图都是一个二分图，U中包含一组查询，V中包含一组广告/URL。当且仅当发出查询的用户至少点击了一次广告/URL时，其中的每条边 另外，每个边与两个数字相关联，即，、点击次数和展示次数，分别表示广告/URL收到的点击次数和广告/URL的显示次数每条边的权重是它的点击次数与展示次数的比率。5.1.2用户项图表。 包括DBLP、MovieLens、Last.fm和Amazon-Games在内的4个用户项图的统计数据在表2中报告，其中U（resp.V）包含项目（分别为用户），E是用户和项目