Technical Papers Archive

Efficient Maximal Biclique Enumeration on GPUs

Authors: Zhe Pan, Shuibing He, and Xu Li (Zhejiang University); Xuechen Zhang (Washington State University, Vancouver); and Rui Wang and Gang Chen (Zhejiang University)

Abstract: Maximal biclique enumeration (MBE) in bipartite graphs is an important problem in data mining with many real-world applications. All existing solutions for MBE are designed for CPUs. Parallel MBE algorithms for GPUs are needed for MBE acceleration leveraging its many computing cores. However, enumerating maximal bicliques using GPUs has three main challenges including large memory requirement, thread divergence, and load imbalance. In this paper, we propose GMBE, the first highly-efficient GPU solution for the MBE problem. To overcome the challenges, we design a stack-based iteration approach to reduce GPU memory usage, a pro-active pruning method using the vertex’s local neighborhood size to alleviate thread divergence, and a load-aware task scheduling framework to achieve load balance among threads within GPU warps and blocks. Our experimental results show that GMBE on an NVIDIA A100 GPU can achieve 70.6× speedup over the state-of-the-art parallel MBE algorithm ParMBE on a 96-core CPU machine.




Back to Technical Papers Archive Listing