Close

Presentation

Enumeration of Billions of Maximal Bicliques in Bipartite Graphs without Using GPUs
DescriptionMaximal biclique enumeration (MBE) is crucial in bipartite graph analysis. Recent studies rely on extensive set intersections on static bipartite graphs to solve the MBE problem. However, the computational subgraphs dynamically change during enumeration, leading to redundant memory accesses and degraded set intersection performance. To overcome this limitation, we propose an AdaMBE algorithm. First, we redesign its core operations using local neighborhood information derived from computational subgraphs to minimize redundant memory accesses. Second, we dynamically create computational subgraphs using bitmaps leveraging its fast bitwise operations to accelerate set intersections. Finally, we integrate them in AdaMBE. Our experimental results show that AdaMBE is 1.6×−49.7× faster than its closest CPU-based competitor and successfully enumerates all 19 billion maximal bicliques on the TVTropes dataset, a large task beyond the capabilities of existing algorithms. Notably, on certain datasets, our parallel version, ParAdaMBE, on CPUs even outperforms GMBE on GPUs by up to 5.07×.
Event Type
Paper
TimeThursday, 21 November 20243:30pm - 4pm EST
LocationB308
Tags
Accelerators
Algorithms
Data Movement and Memory
Graph Algorithms
Registration Categories
TP