一种基于单向游走的高可扩展性SimRank计算方法

摘要

本发明涉及一种基于单向游走的高可扩展性SimRank计算方法。该方法包括：1)提交二部图和目标节点u到图计算平台，并初始化相关参数；2)从节点u产生R条初始随机路径；3)针对每一条随机路径，每隔偶数步执行下面操作：检查节点u到当前节点v的子路径是否满足初次相遇约束；若满足初次相遇约束，则计算节点u与节点v的增量相似度；然后累加节点u与节点v的增量相似度，得到更新后的u与v的相似度；4)重复步骤3)，直到R条路径消息处理完毕，输出节点u与其它节点的相似度。本发明针对单源SimRank top‑k任务优化了存储空间，并提出了计算全部或部分节点的top‑k相似度的路径共享优化策略，能够加快计算速度。

权利要求

1.一种基于单向游走的高可扩展性SimRank计算和查询的top-k相似商品推荐方法，其特征在于，包括以下步骤：

1)提交“用户-商品”二部图和目标节点u到图计算平台，并初始化相关参数；其中目标节点u为目标商品；

2)从节点u产生R条初始随机路径；

3)针对每一条随机路径，每隔偶数步执行下面操作：

3.1)检查阶段：检查节点u到当前节点v的子路径是否满足初次相遇约束；其中当前节点v表示当前商品；

对于两条随机路径p1＝和p2＝，令若m＝L，则称p1和p2满足初次相遇约束；

3.2)计算阶段：若满足初次相遇约束，则计算节点u与节点v的增量相似度；设路径p(u,v)＝，其中u2L＝v，路径中间节点为uL，则所述增量相似度采用下式计算：其中，|N(v)|是节点v的度数，|N(uL)|是节点uL的度数，C是衰减因子；

3.3)更新阶段：累加节点u与节点v的增量相似度，得到更新后的u与v的相似度；

4)重复步骤3)，直到R条路径消息处理完毕，输出节点u与其它节点的相似度；

5)根据步骤4)得到的相似度，进行“用户-商品”二部图的SimRank top-k相似度查询，得到top-k相似的商品；

在计算全部或部分节点的top-k相似度时，采用路径共享优化策略：将所有节点划分为多个块，依次计算每个块内节点的top-k；块之间进行路径共享，后续块内节点所需实际取样数少于R，且计算任务越靠后的块所需取样数越小，从而达到加速计算的目的；

所述路径共享优化策略包括如下操作：

(1)用户提交二部图到图计算平台，将节点划分为一系列逻辑块B0,B1…Bn，设定初始参数C,R,T；

(2)按照下述过程，依次计算B0,B1…Bn里所有节点的top-k相似；

(3)对于B0，每个节点产生R条随机路径，路径长度为3T，表示为p＝：(3.1)检查及计算u2,u4...u2T与u0的相似度，并累加和更新u0与节点u2,u4...u2T的相似度；

(3.2)对于i＝1,2...T：检查及计算ui+2,ui+4...ui+2T与ui的相似度，并累加和更新ui与节点ui+2,ui+4...ui+2T的相似度，且更新节点ui的实际取样总数R*；

(4)对于Bh的每个节点u，0

(4.2)若R*

(5)输出所有节点的top-k相似的节点。

2.如权利要求1所述的方法，其特征在于，步骤1)所述图计算平台是单机图处理平台或者分布式图处理平台；所述参数包括C,R,T，其中C是衰减因子，R是初始随机路径数量，T是路径的步长因子。

3.如权利要求1所述的方法，其特征在于，采用基于二叉堆的数据结构对单源SimRank top-k的存储空间进行优化，通过存储部分计算结果来节省存储空间。

4.如权利要求3所述的方法，其特征在于，所述基于二叉堆的数据结构具有固定容量Mk，其中k是需要返回的结果数量，M是一个整数乘法因子，根据值而不是缓存时间来选择牺牲项；所述对单源SimRank top-k的存储空间进行优化的方法如下：(1)对于目标节点u，分配用于存储相似度的二叉堆对象slot；

(2)对于键值对：

(2.1)若k属于slot，则累加v；

(2.2)若k不属于slot：

(2.2.1)若slot有剩余空间，则新分配空间存储；

(2.2.2)若slot没有剩余空间，且v大于slot的最小值，则回收最小值占用的空间，分配空间存储；

(2.2.3)若slot没有剩余空间，且v不大于slot的最小值，则忽略。

说明书

一种基于单向游走的高可扩展性SimRank计算方法

技术领域

[0001] 本发明属于信息技术领域，涉及大规模二部图上的SimRank计算，具体涉及一种基于单向游走的蒙特卡洛方法，可应用在分布式环境下计算大规模二部图的SimRank top-k相似度；无需维护索引，支持在线查询，具有高可扩展性。

背景技术

[0002] 现实生活中，基于二部图的推荐场景非常常见，例如“用户-商品”二部图，用于向用户推荐已购买过的top-k相似的商品。在计算相似度的各种方案中，SimRank是非常重要的一种基于图结构的度量方法。它基于“相似物品所指向的物品也是相似的”这一原则，在广告推荐、商品推荐等领域有着广泛应用。在大数据时代，二部图会达到上亿节点规模，且图的结构往往会随着时间动态改变；另一方面，推荐系统需要实时快速的返回计算结果。在这样的场景下，SimRank需要做到高可扩展性，高可维护性，以及实时快速计算。

[0003] SimRank原始迭代公式的计算复杂度很高，难以满足海量规模图下的计算要求。在4
最坏情况下，它的时间复杂度为O(|V|T)，且很难用于计算给定节点或部分节点集合的top-k相似。

[0004] 目前，针对SimRank的优化路径分为两种：一种是基于矩阵迭代的优化方法，一种是采用随机游走模型。前者沿用SimRank原始迭代公式，在计算过程中，通过一系列的优化措施来加快计算。比如，重用中间值，利用距离剪枝，利用图结构剪枝等等。但是这一种方式仍然具有较高的时间和空间复杂度，很难用于大规模图的SimRank top-k相似计算。

[0005] 采用随机游走模型是一种可行方案。早在2002年Wisdom等人已经提出SimRank的双向随机游走模型；基于此模型，后续研究者提出各式计算框架。相较于基于矩阵迭代的优化方法，现有双向随机游模型能够在合理的时间内返回给定点对的SimRank值，但仍然存在一些不足。它需要建立和维护较大的索引，产生较大的时间和空间开销。一方面，当动态图结构快速变化的时候，索引无法及时反映图的结构；另一方面，大规模图的索引会给系统内存带来很大负担。另外，现有双向随机游走模型无法支持在线top-k查询。当图规模较大时，单点top-k相似度计算的响应时间往往会达到数十到数百秒，无法满足实时查询的要求。最后，现有双向随机游走模型均建立在单机之上。当图的规模大到单机无法处理时，有的计算框架会借助磁盘的支持，但磁盘IO的性能远远不及内存。实现分布式SimRank计算框架，借助分布式集群的高扩展能力应该是处理大规模图的有效手段和发展方向。

[0006] 专利申请CN104933312A公开了一种基于SimRank的结点相似度计算方法，其是一套基于邻接矩阵计算SimRank的节点相似度的方法，重点在于将原始的SimRank公式改写成非迭代模型，以此来计算相似度的值；同时根据Eigen-SimRank算法动态维护矩阵信息，满足动态网络的节点相似度计算。但是，该非迭代模型是理论上并不与原始SimRank等价，且当图的规模巨大的时候，该方法存储邻接矩阵会产生巨大的内存压力，可扩展性较差。而本发明提出的方法理论上与原始SimRank公式等价，不需要存储索引，内存开销小，采用单向随机游走模型，具有高可扩展性。

发明内容

[0007] 本发明提出了一种在大规模二部图上基于单向游走模型的SimRank top-k相似度计算方法，该方法无需建立和维护索引，支持在线查询，可适用于各种分布式图计算框架，具有高可扩展性。

[0008] 本发明提出的一种基于单向游走的高可扩展性SimRank计算方法，包括以下步骤：

[0009] 1)提交二部图和目标节点u到图计算平台，并初始化相关参数；

[0010] 2)从节点u产生R条初始随机路径；

[0011] 3)针对每一条随机路径，每隔偶数步执行下面操作：

[0012] 3.1)检查阶段：检查节点u到当前节点v的子路径是否满足初次相遇约束；

[0013] 3.2)计算阶段：若满足初次相遇约束，则计算节点u与节点v的增量相似度；

[0014] 3.3)更新阶段：累加节点u与节点v的增量相似度，得到更新后的u与v的相似度；

[0015] 4)重复步骤3)，直到R条路径消息处理完毕，输出节点u与其它节点的相似度。

[0016] 进一步地，所述图计算平台包括是单机图处理平台或者分布式图处理平台。

[0017] 进一步地，采用基于二叉堆的数据结构对单源SimRank top-k的存储空间进行优化，通过存储部分计算结果来节省存储空间。

[0018] 进一步地，在计算全部或部分节点的top-k相似度时，采用路径共享优化策略：将所有节点划分为多个块，依次计算每个块内节点的top-k；块之间进行路径共享，后续块内节点所需实际取样数少于R，且计算任务越靠后的块所需取样数越小，从而达到加速计算的目的。

[0019] 本发明针对现有双向游走模型的不足，提出了二部图上的单向游走模型。相较于现有双向游走模型，本发明具有以下优势：

[0020] 1)本发明无需建立和维护索引。当图规模巨大或图结构动态变化时，便会体现无索引方案的优势。一方面，构建大规模图的索引需要大量时间(如有的文献会超过10小时)，当动态图的结构快速变化的时候，索引无法真实反应当前图结构；另一方面，大规模图的索引往往会消耗大量的内存空间。

[0021] 2)本发明计算单源SimRank top-k无需计算候选点集。现有双向随机游走模型需要先计算目标节点的候选点集，然后计算该目标节点与每一个候选节点的SimRank值，计算效率受限于候选点生成算法的质量。路径相关的时间复杂度为O(|H|RT)，其中H是候选点集，R是计算每个点对的游走路径数量，T是路径最大长度；而本发明无需计算候选节点，时间复杂为O(RT)。另外，针对单源top-k问题，本发明设计了具有较高存储性能的数据结构，不需要存储该节点与所有其它节点的相似度值，大大节省存储空间。

[0022] 3)本发明支持在线top-k相似度查询。在线top-k相似查询要求对于给定节点，能够在数毫米到数十毫米之间返回该节点的top-k相似度。当图规模很小的时候(几万节点规模)，已有双向随机游走模型能够在数毫米级别返回结果；但是随着图规模的增大，单点top-k相似度的计算会随之急剧增大，当图规模达到千万节点时，现有双向随机游走模型往往需要数十秒到数百秒的计算时间。与之相反，本发明对于单源top-k相似度查询时间稳定在数毫秒到数十毫米之间，与图规模无关。

[0023] 4)本发明适用于分布式图计算框架，具有高可扩展性。目前，双向随机游走模型的计算框架均建立在单机之上。尽管部分计算框架借助磁盘的支持，能够在单机上处理较大规模的图(千万节点级别)，但是当图的规模进一步增大时，磁盘IO会产生较大代价。本发明已经在分布式图计算框架giraph上实现，能够支持任意规模二部图的SimRank top-k相似度查询。需要说明的是，本发明采用的图计算平台不局限于giraph平台，可以灵活的在诸多分布式平台如spark上实现，并且也可以在单机图处理平台上实现。

附图说明

[0024] 图1：单源SimRank计算示例图。

[0025] 图2：SimRank top-k空间存储策略示意图。

[0026] 图3：路径共享优化策略示意图。

具体实施方式

[0027] 下文通过具体实施例并配合附图，对本发明方法的计算框架以及优化措施作出说明。

[0028] 首先，我们描述单源SimRank的计算流程，其次针对单源SimRank top-k任务优化存储空间，最后针对全部或部分节点集合的top-k任务，进行路径共享优化，加快计算速度。

[0029] 首先，介绍本发明关于单源SimRank的计算流程，给出示例图。

[0030] 1.用户提交二部图和目标节点u到giraph平台，初始化参数C,R,T等。其中，参数C是衰减因子，R是初始随机路径数量，T是路径的步长因子。

[0031] 2.从节点u产生R条初始随机路径。

[0032] 3.针对每一条随机路径，每隔偶数步(不超过2T)执行下面操作：

[0033] 3.1检查阶段：检查节点u到当前节点v的子路径是否满足“初次相遇约束”。

[0034] 对于两条随机路径p1＝和p2＝ ，令若m＝L，则称p1和p2满足初次相遇约束。

[0035] 3.2计算阶段：若上述检查合法(即满足初次相遇约束)，则计算该节点v与节点u的增量相似度。不失一般性地，设路径p(u,v)＝，其中u2L＝v，路径中间节点为uL，则所述增量相似度采用下式计算：

[0036]

[0037] 其中，|N(v)|是节点v的度数，|N(uL)|是节点uL的度数。

[0038] 3.2更新阶段：累加节点u与节点v的增量相似度，得到更新后的u与v的相似度。

[0039] 4.重复步骤3，直到R条路径消息处理完毕，输出节点u与其它节点的相似度。

[0040] 图1是上述流程的简化示例，计算节点1的top-2相似，这里C＝0.6，R＝100，T＝3。以两条随机路径为例。从节点1出发，产生两条随机路径path1＝<1,2,3,6,5,8,7>和path2＝<1,2,3,4,1,2,3>，分别如图1中(a)图和(b)图所示；在随机游走过程中，每隔偶数步执行上述步骤3的计算。在计算过程中，路径需要满足“初次相遇约束”，超级步superstep＝2时，<1,2,3>满足约束；当superstep＝6时，<1,2,3,4,1,2,3>不满足，因为从1，3出发的随机游走会在2初次相遇，而不是中点4。对于不满足“初次相遇约束”的节点对，不需要计算相似度。图1中Sd表示增量相似度。

[0041] 其次，介绍本发明关于单源SimRank top-k的存储空间优化措施。

[0042] 对于大规模图上单源SimRank来说，存储目标节点与所有其它节点的相似度没有必要，非常浪费存储空间。本文采用一种基于二叉堆的数据结构，用于存储部分计算结果。它具有固定容量Mk(k是需要返回的结果数量，M是一个整数乘法因子)，根据值而不是缓存时间来选择牺牲项。得益于本发明的游走策略，即使只存储和更新部分结果，得到的top-k结果也具有较高的精度。

[0043] 具体操作如下：

[0044] 1.对于目标节点u，分配用于存储相似度的二叉堆对象slot；

[0045] 2.对于键值对：

[0046] 2.1若k属于slot，则累加v；

[0047] 2.2若k不属于slot：

[0048] 2.2.1若slot有剩余空间，则新分配空间存储；

[0049] 2.2.2若slot没有剩余空间，且v大于slot的最小值，则回收最小值占用的空间，分配空间存储；

[0050] 2.2.3若slot没有剩余空间，且v不大于slot的最小值，则忽略。

[0051] 图2是存储相似度的数据结构使用示例。这里有2条随机路径，分别在游走2步，4步，6步之后更新相应的存储结果。

[0052] 最后，介绍本发明在计算全部或部分节点的top-k相似度的路径共享优化策略。

[0053] 当图的规模为|V|时，计算全部节点的top-k相似度复杂度为O(|V|RT)；当使用路径共享技术时，所有节点划分为多个块，依次计算每个块内节点的top-k；块之间进行路径共享，后续块内节点所需实际取样数少于R，且计算任务越靠后的块所需取样数越小，从而达到加速计算的目的。具体操作如下：

[0054] 1.用户提交二部图到giraph平台，将节点划分为一系列逻辑块B0,B1...Bn，设定初始参数C,R,T。

[0055] 2.按照下述过程，依次计算B0,B1...Bn里所有节点的top-k相似度。

[0056] 3.对于B0，每个节点产生R条随机路径，路径长度为3T，如

[0057] p＝：

[0058] 3.1检查及计算u2,u4...u2T与u0的相似度，并累加和更新u0与节点u2,u4...u2T的相似度；

[0059] 3.2对于i＝1,2...T：检查及计算ui+2,ui+4...ui+2T与ui的相似度，并累加和更新ui与节点ui+2,ui+4...ui+2T的相似度，且更新节点ui的实际取样总数R*。

[0060] 4.对于Bh(0

[0061] 4.1若R*≥R，则该节点已经计算完毕。

[0062] 4.2若R*

[0063] 5.输出所有节点的top-k相似度。

[0064] 图3是上述优化措施的一个简单示例，T＝2。当产生一条随机路径p＝<1,4,3,6,5,7,8>时，事实上相当于产生了三条随机路径：

[0065] p1＝<1,4,3,6,5>；p2＝<4,3,6,5,7>；p3＝<3,6,5,7,8>

[0066] 那么，当计算节点4和节点3的top-k相似时，可以分别少取样1条；同理，当其他随机游走路径产生大量可重用路径时，后续的取样数目会越来越少，从而加快整个计算过程。理想情况下，当逻辑块B0,B1...Bn划分和调度合理，随机游走路径足够长的时候，每游走1步，可以产生1条有效路径；计算全部节点的top-k相似的时间复杂度为O(|V|R)。

[0067] 以上实施例仅用以说明本发明的技术方案而非对其进行限制，本领域的普通技术人员可以对本发明的技术方案进行修改或者等同替换，而不脱离本发明的精神和范围，本发明的保护范围应以权利要求书所述为准。