大图上跳数受限的可达查询算法研究与优化①

邢耕源,徐 云

1（中国科学技术大学 大数据学院,合肥 230026）

2（安徽省高性能计算重点实验室,合肥 230026）

图网络能够有效表达不同类型事物之间复杂的关系,在现实生活不同领域中有着广泛的应用[1].随着信息技术的不断发展和互联网不断渗入生活,各类图数据规模发生爆炸式增长,以社交网络为例,2011年微信月活跃用户数有0.5亿人,而2019年微信月活跃用户数达到了11亿,是中国用户量最大的APP.面对如此大规模的数据量,传统的图搜索方案已经无法胜任.

图可达查询是图数据管理领域的研究热点问题,然而在现实生活中还需要对可达顶点间的距离加以限制[2].例如在社交网络中,根据小世界理论[3],任意两个人之间总存在着6跳的通路,单纯的可达性查询失去了意义.用户节点间的距离反映着用户之间联系的紧密程度,限定距离下的可达性查询可以帮助分析用户社区间的关系或搜索与自身相近的其他用户[4]; 在数据中心网络中,设计部署整体网络结构时,网络图中服务器间的距离信息反映着信息传递的时效性[5].对于限定距离下的可达性查询,在学术界被称为k跳可达问题[6].

大图上各类算法,都会通过构建索引信息,帮助在查询时快速求解.大图索引的建立和利用索引的查询策略,是算法设计的关键.索引的构建是为了根据图局部结构归纳信息,进行状态压缩; 查询策略需要在快速求解的同时保证问题的完备性,大图上现有的查询算法,都需要对时间效率和空间效率进行平衡[7].现有的2-hop类算法通过构建由中介顶点构成的2-hop类索引,加速搜索.该算法查询时间虽然迅速,但是受限于存储空间,不适合更大规模的图上运算.

为此本文提出了一种基于部分索引与局部搜索结合的跳数受限可达查询算法.通过改变原索引结构,提高索引利用率,从而在减少空间占用同时保持查询时间尽量低.本方法首先构建了基础的2-hop可达索引;然后采用了近邻节点和大度数热点顶点对索引进行约简; 最后采用索引表和局部搜索结合的方法进行可达性查询,能够节省更多的索引空间,从而适用于解决更大规模的图可达查询问题.

1 已有大图查询类算法分析

目前,已有的图查询算法包括一般可达性查询、最短路径查询、k跳可达性查询等.

1.1 一般可达性查询算法

大图上的可达性查询算法可以根据索引完整的程度和对在线搜索的依赖性,分为传递闭包类[8]、hop索引类[9]、索引+类算法[10].

（1）传递闭包类算法

该类算法利用设计的索引结构对大图可达性信息进行预计录,利用自身设计的各类索引结构能够快速查找顶点间的可达性关系.在索引设计上,这类算法利用了图上局部结构（如树[11]、链[12]）的拓扑性进行剪枝并记录,这一类算法在响应时间上是最快的,如图1所示.但是其自身的索引结构会随着图规模的增大而快速增大,因此存储空间是这类问题的桎梏.随着图规模达到百万甚至千万顶点级别,这类算法已经不能完成求解.

图1 简单图网络

（2）hop索引类算法

该类算法利用一些选定的中继节点作为中介,进而考虑目标顶点与中继顶点间的可达性.随着研究的不断深入,该类算法利用的中继结构不再限于单顶点,开始利用链路、树等图结构作为中间结构; 演化出了2-hop[13]类,演化成3-hop[14]、path-hop[15]类算法,如图2所示,为简单图网络对应的2-hop索引.

图2 2-hop索引结构

这一类算法在回答可达性查询时,只需要在对应行索引上进行搜索,寻找公共中介顶点的表项.该类方法的关键是hop索引的建立,即选取合适的中介结构辅助索引建立.

（3）索引+类算法

该类算法发现在实际搜索中,有向图点对间的不可达查询占了绝大多数[16]; 相比于发现可达性,他们更期望快速发现点对间的不可达关系,因此他们利用自身索引对可达性进行快速筛选.

如果凭借索引不足以证明点对间的不可达关系,这类算法利用在线搜索用于判定顶点间的可达性.这类算法的空间占用是最小的,但相应其查询时间最长.

1.2 路径查询算法

路径查询算法按照索引规模、索引种类可以分为在线搜索[17]、地标算法[18]、树分解算法[19]等.

（1）在线搜索算法

在线搜索算法不利用索引信息,在图上直接搜索两点之间的路径信息,在线搜索包括经典的Dijkstra算法和Floyd-Warshall算法等.在后续发展中有了A*算法、蚁群算法等改进的算法,该类算法在图顶点规模达到百万及以上时,即使在并行下,算法时间效率仍旧较为低下.

（2）地标算法

地标搜索是搜索最短路径的一类近似算法.这类算法事先选定一些地标点,以地标点作为中介,依次计算所有经过地标下的最短路径信息; 将其中最短的路径作为备选路径[20].这类算法的效果取决于最短路径是否经过一个真实的地标点,因此合适的地标点选取策略是这类算法的关键.目前常见的地标选取策略通常是基于平均顶点度数和中心距离的启发式算法.

树分解类算法构建了一棵新的索引树[21],利用构建的索引树,树分解算法可以按级对小规模节点团进行搜索,最终构建出最短路径.该类算法将原图中的一团临近节点缩为索引树中的一个节点,真实图中的一条路径对应团内路径和团间路径,利用搜索节点对的最小共同祖先和局部最短路径搜索算法可以分别解决两个子问题,该类策略的关键是在树高和团内节点数间平衡,并构建出一棵合适的搜索树.

1.3 k跳可达性查询

关于k跳可达算法,学术界已有算法相对较少,已有的k跳可达算法大多是有向图上算法.基于顶点覆盖集的k跳可达查询算法通过求解原图上的一个顶点覆盖集,然后在顶点覆盖集之上根据顶点之间的距离关系构建关系闭包作为图索引,在查询时可以通过查询顶点所在闭包索引,直接得到顶点间k跳可达关系.但是这个方法的空间复杂度较高,因为顶点覆盖集中的顶点之间的关系越稠密,带来的索引开销越大,k-reach 的索引空间和索引时间都随着图规模的增长呈指数上涨.

为了改善k跳可达性的扩展性问题,Cheng等给出了一种基于控制集的索引方法[22],并且将索引组织成两级索引的结构,一定程度上提高了算法的扩展性,但在扩展性得到了提高的同时,却牺牲了查询的时间效率.

近年国内也有k跳可达查询相关研究,基于双向搜索的k跳查询算法通过优化双向搜索过程提高了k跳可达性查询的时间效率[23].基于图压缩的 k跳可达性查询方法[24],通过对原图进行等价类的压缩来降低图的规模,提高算法的可拓展性.基于BFS树的k跳查询算法通过计算索引交集的计算方法,提高了算法的时间效率.

2 基于hop索引的k跳可达算法

k跳可达性查询相较于一般的可达性查询约束更为严格,因为一般可达性查询可以视为k=∞下的情况;k跳可达相较于最短路径查询约束较为宽松,因为k跳可达在求解到一条跳数不大于k的路径后,不关心点对间的最短路径.

我们解决索引空间和查询时间之间平衡的主要方法是:首先对于原索引中不常被利用缺占据大量空间的小度数顶点索引项,按一定比率选取其中部分进行“约简”操作.“约简”操作指:保留其近邻顶点索引和经过的大度数顶点索引,剔除其他索引项.对于优化后的索引表无法确定的查询,转用使用与索引表相结合使用LRU策略的局部搜索进行补充搜索.

为了求解k跳可达问题并优化原索引结构,设计了算法1.

2.1 图索引的建立

为了求解距离限制的可达查询问题,选用带有距离信息的2-hop类索引,2-hop类索引维护着所有顶点对应的2-hop表.当两个不同的顶点存在着一个公共的中介节点时,说明两者可达.此时查询两者对应的距离标签,如果所有距离标签中最小的在限制范围内,则说明这两个顶点是在限制范围内可达的.

构建完整表的方法,依赖于顶点对间的距离信息.算法最开始将每个顶点距自身距离为0的顶点加入自己对应的表单中（自身）; 然后检索所有的边,构建距离为1的项,按照优先度,将每条边加入优先度较高的顶点表单中,然后依照距离信息,递归的依次构建基于距离的索引,直到构建到距离为k的索引.

2.2 索引结构的约简

2-hop类索引构建时,表单中索引项的选取都是单条最短路径上优先度最高的顶点; 因此大度数顶点的索引项会较短,而小度数顶点的完整索引项会较繁琐.回答完整性的可达性查询,因保存这些边缘顶点全部的信息牺牲掉了很大的存储空间; 而真正查询时针对这些边缘顶点的查询频度也较低.这也造成了因存储不能被及时利用的信息所造成的存储空间浪费,此需要调整存储空间和查询时间之间的平衡.

为了弥补保留部分索引造成的信息丢失,在查询时需要进行局部搜索,检测限制距离内两个目标顶点之间的可达性关系,在社交图中,除了边缘顶点临近的顶点外,利用其他高度数的顶点作为索引可以加速搜索.针对小度数边缘顶点采用保留近邻节点信息以及高度数代表顶点作为索引的策略,因社交图上的顶点倾向于发现与自身相近的顶点或与热点顶点间关系,所以保留两种不同类型的顶点作为部分索引,使其加速整体索引搜索过程.

2.3 基于约简后索引表的查询算法

2.3.1 可达性查询算法

针对社交图上2-hop索引信息不平衡的情况,本文通过保留近邻节点和大度数代表顶点的手段约简了索引结构,整体查询流程如图3所示.

图3 可达查询算法流程图

在查询点对间可达性时,首先在约简后的部分索引上进行查询,若查询顶点并非小度数顶点,则其对应的表项是完整的,基于索引表的可达性查询结果是完备的.若待查询的顶点是小度数顶点,则优先在其约简后的部分索引上进行2-hop索引查询; 若经过查询后存在着k跳关系,则可以直接回答可达性,若未搜索到k跳可达关系,则需在LRU索引上查询已有的可达性索引,查看是否近期已经补全过对应行索引.

若LRU索引上仍未有对应的结果,则需在索引表上进行对应行的局部搜索; 并将补全后的行索引存入LRU索引,并将LRU索引进行更新,在原索引表上的局部搜索过程与建立2-hop索引时的检索过程一致,依据距离信息从小到大依次检查约简的小度数顶点不同跳数下的2-hop关系,将其依次补全.

2.3.2 基于约简后索引表的查询算法优劣势分析

使用约简的2-hop索引可以有效地减小索引空间,并保持可达性查询时间与完备索引上的查询时间在同一数量级下,保持时间性能并优化空间性能的关键在于代表索引,即近邻顶点和高度数顶点的选取.但本文的约简方法对原图类型有较强要求,对于非社交图处理效果较差,因其不再具有选取近邻顶点和高度数顶点作为代表点的特征,同时对于待查询点对也有一定要求,对于完全随机的点对间查询效果也不明显.

3 实验结果与分析

实验分别测定了不同约简比率下、不同局部搜索方法、不同跳数下索引空间与查询时间之间的关系.

3.1 数据集介绍与实验配置

本文选用的数据集来自斯坦福网络分析项目提供的开源数据集,YouTube[25]和Orkut数据集均为社交网络数据集.其中YouTube数据集规模较小,该数据集顶点数为1134 890个,边数为2987 624条; Orkut数据集规模较大,该数据集顶点数为3072 441个,边数为117 185 083条,所有的实验都在单机Ubuntu 18.04.5 LTS环境下运行.内存为512 GB,实验环境的线程数最高为56个.

3.2 评估标准与结果分析

由于本文提出的基于方法是基于hop类算法的k跳可达查询算法,主要贡献在于优化hop类索引结构,能够胜任规模更大的图上快速查询的任务.因此在实验评估标准的选择上,本文主要选择索引空间、查询时间两个评估标准.同时在对比方法选取上,本文选择了2019年SIGMOD会议上提出的PSL索引算法[26],该算法已是最先进的hop类算法.

整体实验方法分为两部分:确定局部搜索策略和选用某一实验参数.其中,不同局部搜索算法实验部分用于确定局部搜索算法,优化比率实验部分用于确定实验的一个可变参数:低度数顶点索引优化比率.索引优化实验部分用于测定在选用参数下索引空间和查询时间之间的关系.

3.2.1 不同局部搜索算法实验

本文设计了多种不同的局部搜索算法,实验表中展示的是优化后的基于启发式搜索的双向局部搜索与基于索引表的搜索方法间对比,本实验数据集采用YouTube数据集,对比了不同跳数（k）下两种采纳不同局部搜索算法与原算法（PSL）间索引空间和查询时间的关系.

图4和图5中PSL算法为对比算法,PSL_pru为双向启发式搜索算法,PSL*算法为索引表局部搜索算法.实验具体数据见表1,表2.由图可见,两种改进的索引优化算法均在索引空间上效率超过了原算法,而在查询时间上高于原算法.其中基于索引的局部搜索算法,由于采用了LRU机制,因此其索引空间略高于双向搜索查询算法; 但其对应的查询时间则大大减少,与未经优化的PSL算法更为相近.保证了查询时间在同一数量级下,同时索引空间得到了优化.

表1 不同跳数下搜索策略的索引空间和跳数间关系（B）

表2 不同跳数下搜索策略的查询时间和跳数间关系（ms）

图4 不同搜索算法空间性能比较

图5 不同搜索算法时间性能比较

3.2.2 优化比率实验

在确定了局部搜索算法的种类后,为了得到更好的空间优化效果,同时保证时间性能在同一数量级下我们测试了不同优化比率下查询时间和索引空间的关系.优化比率作为平衡索引时的一个重要参数,影响的是约简小度数顶点的比例,优化比率越低,被选中修改的小度数顶点项越少,实验测试数据集为YouTube数据集,测试了不同跳数下,不同优化比率下的索引空间和查询时间.

此处的优化比率作为实验的一个参数,可以根据实际需求人工配置.该比率越高保留的顶点数目越少,算法空间优化比率越高; 比率越低,保留的原索引项越多,算法查询时间消耗越低.本实验为了突出空间优化效果,选用了查询时间不发生显著改变下的并有着较优空间优化效果的比率进行测定.实际应用时,可以根据需求选取适当的参数配置.

由表3可见,30%至70%的比率下,索引空间减小的速度较为均匀,但查询时间方面,50%至60%的优化比率出现了较为明显的查询时间上升.60%至70%的优化比率下出现了更为剧烈的时间上升,因此考虑到使查询时间保持在原数量级,本文后续实验选用50%下的约简比率进行实验.

表3 不同优化比率下查询时间与索引空间关系

3.2.3 索引优化实验

确定了局部搜索算法和优化比率后,我们在规模更大的社交网络数据集下进行了与原算法相比较新的对比实验,实验的性能评估指标,我们仍旧选定为索引空间和查询时间.测定了不同跳数变化下,我们的算法与原算法相比性能的优劣,

通过实验结果,由图6和图7可见,从跳数为4开始,本文的算法空间性能开始逐步优化,同时保证了时间效率上略高于原算法.具体实验数据见表4,表5.其中索引空间可以优化为原算法的68.18%,同时保证查询时间为原算法1.38倍,保证了时间性能在原算法同一数量级下.

图6 索引优化前后空间性能比较

图7 索引优化前后时间性能比较

表4 索引优化前后空间性能比较（B）

表5 索引优化前后时间性能比较（ms）

该实验结果中,可见空间性能随跳数k有明显的变化,但查询时间上出现了PSL*整体查询时间先上升后下降的现象.引发这样的现象的原因是:当限制的跳数k较小时,顶点间的k跳关系较难达成,因此需要借助除原索引外的局部搜索进行测定; 而当跳数k上升至一定程度后,顶点间的k跳约束得到了松弛,此时仅凭借索引表可以得到肯定结果的顶点对比率得到了上升.得到肯定查询后的顶点对不再需要借助局部搜索进一步查询,因此算法的查询时间得到了下降.

4 结论与展望

本文针对2-hop类索引在k跳可达问题上出现的因索引分布不均匀造成的空间浪费的现象,提出了人工可控的平衡索引空间与查询时间的优化算法.该算法首先构筑一般的2-hop类索引表,再根据约简比率对原索引表进行平衡处理,并记录下被处理过的小度数顶点标号.同时,我们设计了与约简算法相应的查询算法,保证查询的完备性,同时利用LRU机制加速查询阶段.在查询可达性关系时,首先在约简后的索引表上进行查找,若查询不到对应顶点信息,则转入LRU索引上查询,若仍得不到肯定结果,再转入局部搜索,并将结果更新至LRU索引上.

实验表明,我们的方法相比于已有的最先进的索引方法,能够有效地减小索引占用的空间,同时保证查询时间增加的幅度可控.下一步的工作重点,是设计针对不同图类型和图半径等信息的参数自动优化算法,增强算法对不同类型的图网络的适应性,同时设计新的机制,在优化查询时间上得到进一步的发展.