Accelerating Biclique Counting on GPU

Linshan Qiu, Zhonggen Li, Xiangyu Ke, Lu Chen, Yunjun Gao

Abstract

Biclique counting is a fundamental task in bipartite graph analysis, essential for applications ranging from community detection to recommendation systems. However, the combinatorial nature of $(p, q)$-bicliques makes counting them computationally expensive, particularly as graph sizes and clique parameters scale. This paper presents GBC (GPU-based Biclique Counting), a novel framework designed to accelerate this process by leveraging the massive parallelism of GPUs. By introducing a Hierarchical Truncated Bitmap (HTB) for efficient set intersection, a hybrid DFS-BFS search strategy, and a communication-free partitioning scheme, GBC achieves an average speedup of 497.8× over state-of-the-art CPU algorithms.

Introduction

In the era of big data, bipartite graphs serve as a critical model for representing relationships between two distinct sets of entities, such as users and products, authors and papers, or genes and diseases. Within these graphs, a $(p, q)$-biclique is defined as a complete subgraph where $p$ vertices from the first set are connected to all $q$ vertices in the second set. Identifying and counting these structures is vital for uncovering dense communities and patterns in complex networks.

Despite its importance, biclique counting is a "combinatorial nightmare." As the size of the graph or the parameters $p$ and $q$ increase, the search space grows exponentially. Existing state-of-the-art algorithms, such as BCL, primarily rely on recursive backtracking on CPUs. Analysis reveals that these algorithms spend approximately 97% of their execution time on a single operation: set intersection. While GPUs offer a potential solution through massive parallelism, a naive porting of CPU-based algorithms often fails due to memory bottlenecks and thread divergence. GBC addresses these challenges through a series of GPU-specific optimizations.

The GBC Framework

To overcome the limitations of traditional CPU-based approaches, GBC introduces four key technical innovations designed to align with the GPU's architecture.

1. Hierarchical Truncated Bitmap (HTB)

The primary bottleneck in biclique counting is finding common neighbors between vertices. Traditional methods use list-based intersections or binary searches, which are inefficient for GPU memory access patterns. GBC replaces these with the Hierarchical Truncated Bitmap. By hashing adjacency lists into 32-bit truncated bitmaps, the framework enables the GPU to perform intersections using high-speed bit-wise AND operations. This significantly reduces memory transactions and accelerates the core computational task.

2. Border Vertex Reordering

To further enhance the efficiency of the HTB, GBC employs a strategy called "Border" reordering. This method groups vertices to maximize the density of the resulting bitmaps. By increasing data locality and density, the reordering strategy effectively compresses the data and improves the cache hit rate during bit-wise operations.

3. Hybrid DFS-BFS Exploration

Standard counting algorithms utilize Depth-First Search (DFS) for its memory efficiency. However, DFS often leads to thread starvation on GPUs, where many cores sit idle while a few process deep branches. Conversely, Breadth-First Search (BFS) offers high parallelism but can lead to memory exhaustion. GBC adopts a hybrid approach: it uses BFS locally to generate a sufficient workload for a warp of threads, then transitions to DFS to maintain a manageable memory footprint.

4. Load Balancing and Partitioning

Real-world graphs are often highly skewed, with a small number of vertices possessing a disproportionately large number of neighbors. GBC manages this imbalance through a joint load-balancing mechanism that combines static task allocation with runtime work-stealing. For graphs that exceed the physical memory of a single GPU, the framework utilizes BCPar, a communication-free partitioning method. BCPar exploits the fact that biclique computation only requires knowledge of 2-hop neighbors, allowing for independent processing of graph segments.

Experimental Evaluation

The performance of GBC was evaluated across 11 diverse datasets, including real-world networks (Youtube, Yelp, IMDB, and StackOverflow) and large-scale datasets (Orkut). To test the limits of the framework, synthetic datasets (S1, S2) with high 2-hop neighbor density were also utilized.

Performance Results

Compared to the state-of-the-art CPU algorithm (BCL), GBC demonstrated transformative performance gains:

  • Average Speedup: GBC outperformed BCL by an average of 497.8×.
  • Peak Performance: On the synthetic S2 dataset with $p=q=8$, GBC achieved a peak speedup of 1217.7×.
  • Comparison with Parallel CPU: Even when compared against BCLP (a version of BCL utilizing 16 CPU threads), GBC remained 146.7× faster on average.
  • Scalability: The BCPar partitioning method allowed GBC to process the Orkut dataset (327 million edges), demonstrating its capability to handle massive graphs that typically exceed consumer GPU memory.

Conclusion

GBC represents a significant advancement in graph mining, proving that specialized data structures like HTB and hybrid search strategies can unlock the full potential of GPUs for combinatorial problems. While the current framework is optimized for bipartite structures, its success suggests a roadmap for accelerating other complex graph algorithms. Future research will explore extending these techniques to general unipartite graphs and dynamic temporal networks where connections evolve over time.

Summary updated

BibTeX
@inproceedings{qiu2024accelerating,
  author = {Linshan Qiu and Zhonggen Li and Xiangyu Ke and Lu Chen and Yunjun Gao},
  title = {{Accelerating Biclique Counting on GPU}},
  booktitle = {ICDE},
  year = {2024},
  url = {https://openreview.net/forum?id=7szVGIKWxd},
}
Figure