Parallel Five-cycle Counting Algorithms
Parallel Five-cycle Counting Algorithms
复制标题
DOI：
10.1145/3556541
复制
发表时间：
2022-08
期刊：
影响因子：
--
通讯作者：
Jessica Shi;Louisa Ruixue Huang;Julian Shun
中科院分区：
文献类型：
--
作者：
Jessica Shi;Louisa Ruixue Huang;Julian Shun
计算大型网络中子图的频率是一个经典的研究问题，它揭示了这些网络的底层子结构，可用于重要的应用。然而，子图计数是一个具有挑战性的问题，即使子图的大小为五个，由于组合爆炸的可能出现的数量。五圈是五顶点子图计数的一个重要特例，也是最难有效计数的一种。我们设计了两个新的并行五周期计数算法，并证明了它们是有效的，并实现了多对数跨度。这两种算法都是基于计算低出度方向，这使得有向两路径和三路径的有效计算，算法的不同之处在于它们使用这种方向来消除重复计算的方式。此外，我们提出了新的并行算法获得无偏估计的五个周期计数使用图稀疏化。我们开发快速多核实现的算法，并提出了一个工作调度优化，以提高其性能。我们使用具有双向超线程的36核机器对各种真实世界的图形进行的实验表明，我们最好的精确并行算法实现了10-46倍的自相关加速比，比我们的串行基准性能高10-32倍，比以前最先进的串行算法高818倍。对于合理的概率参数，我们的最佳近似算法实现了高达20倍的自相关加速比，并且能够比我们的最佳精确算法快9-189倍地近似五个周期计数，误差在0.52%和11.77%之间。
Counting the frequency of subgraphs in large networks is a classic research question that reveals the underlying substructures of these networks for important applications. However, subgraph counting is a challenging problem, even for subgraph sizes as small as five, due to the combinatorial explosion in the number of possible occurrences. This article focuses on the five-cycle, which is an important special case of five-vertex subgraph counting and one of the most difficult to count efficiently. We design two new parallel five-cycle counting algorithms and prove that they are work efficient and achieve polylogarithmic span. Both algorithms are based on computing low out-degree orientations, which enables the efficient computation of directed two-paths and three-paths, and the algorithms differ in the ways in which they use this orientation to eliminate double-counting. Additionally, we present new parallel algorithms for obtaining unbiased estimates of five-cycle counts using graph sparsification. We develop fast multicore implementations of the algorithms and propose a work scheduling optimization to improve their performance. Our experiments on a variety of real-world graphs using a 36-core machine with two-way hyper-threading show that our best exact parallel algorithm achieves 10–46× self-relative speedup, outperforms our serial benchmarks by 10–32×, and outperforms the previous state-of-the-art serial algorithm by up to 818×. Our best approximate algorithm, for a reasonable probability parameter, achieves up to 20× self-relative speedup and is able to approximate five-cycle counts 9–189× faster than our best exact algorithm, with between 0.52% and 11.77% error.