Efficient Enumeration of Large Maximal k-Plexes

Finding cohesive subgraphs in a large graph has many important applications, such as community detection and biological network analysis. Clique is often a too strict cohesive structure since communities or biological modules rarely form as cliques for various reasons such as data noise. Therefore, k-plex is introduced as a popular clique relaxation, which is a graph where every vertex is adjacent to all but at most k vertices. In this paper, we propose an efficient branch-and-bound algorithm as well as its task-based parallel version to enumerate all maximal k-plexes with at least q vertices. Our algorithm adopts an effective search space partitioning approach that provides a good time complexity, a new pivot vertex selection method that reduces candidate vertex size, an effective upper-bounding technique to prune useless branches, and three novel pruning techniques by vertex pairs. Our parallel algorithm uses a timeout mechanism to eliminate straggler tasks, and maximizes cache locality while ensuring load balancing. Extensive experiments show that compared with the state-of-the-art algorithms, our sequential and parallel algorithms enumerate large maximal k-plexes with up to 5 × and 18.9 × speedup, respectively. Ablation results also demonstrate that our pruning techniques bring up to 7 × speedup compared with our basic algorithm.