@article{wang2024vldbj,
author = {Wang, Zhibin and Lai, Longbin and Liu, Yixue and Shui, Bing and Tian, Chen and Zhong, Sheng},
title = {Parallelization of butterfly counting on hierarchical memory},
year = {2024},
issue_date = {Sep 2024},
publisher = {Springer-Verlag},
address = {Berlin, Heidelberg},
volume = {33},
number = {5},
issn = {1066-8888},
url = {https://doi.org/10.1007/s00778-024-00856-x},
doi = {10.1007/s00778-024-00856-x},
abstract = {Butterfly (a cyclic graph motif) counting is a fundamental task with many applications in graph analysis, which aims at computing the number of butterflies in a large graph. With the rapid growth of graph data, it is more and more challenging to do butterfly counting due to the super-linear time complexity and large memory consumption. In this paper, we study I/O-efficient algorithms for doing butterfly counting on hierarchical memory. Existing algorithms of this kind cannot guarantee I/O optimality. Observing that in order to count butterflies, it suffices to “witness” a subgraph instead of the whole structure, a new class of algorithms called semi-witnessing algorithm is proposed. We prove that a semi-witnessing algorithm is not restricted by the lower bound Ω(|E|2MB) of a witnessing algorithm, and give a new bound of Ω(min(|E|2MB,|E||V|MB)). Subsequently, we develop the IOBufs algorithm that manages to approach the I/O lower bound, and thus claim its optimality. Finally, we investigate the parallelization of IOBufs to improve its performance and scalability. To support various hardware configurations, we introduce a general parallel framework, PIOBufs. Our analysis indicates that the key to implementing PIOBufs on multi-core CPUs lies in the fine-grained task division. Furthermore, we extend the CPU-tailored PIOBufs to harness the extensive parallelism that GPUs provide. Our experimental results show that IOBufs performs better than established algorithms such as EMRC, BFC-EM and G-BFC. Thanks to its I/O-efficient design, IOBufs can handle large graphs that exceed the main memory capacity on both CPUs and GPUs. A significant result is that IOBufs can manage butterfly counting on the Clueweb graph, which has 37 billion edges and quintillions (1018) of butterflies.},
journal = {The VLDB Journal},
month = jun,
pages = {1453–1484},
numpages = {32},
keywords = {Graph, Butterfly counting, Hierarchical memory, Parallel algorithm, GPGPU}
}