Differentiating Set Intersections in Maximal Clique Enumeration by Function and Subproblem Size
Hans Vandierendonck · 2024
Clique finding problems such as maximal clique enumeration are computationally challenging due to the combinatorial number of vertex sets that need to be evaluated. Despite prior advances, the majority of execution time is still spent in set intersections, which limits the speed of the algorithms and their application to increasingly larger graphs. To address this issue, we propose to differentiate the set intersection algorithm to its function and the problem size, leading to several innovations: (i) a new primitive “intersect-size-exceeds” which short-cuts the calculation of the size of an intersection if it does not exceed a pre-determined threshold; (ii) a new data structure that supports efficient hash-based intersection on constantly evolving sets; and (iii) efficient specialized variants of clique search and intersection for “small” and “tiny” subproblems. Compared to the state-of-the-art maximal clique search algorithms by Blanusa et al (VLDB 2020) and Besta et al (MICRO 2021), a median speedup is observed of 4.14 × and 10.91 × on AMD Zen Version 2, and a median speedup of 3.44 × and 8.26 × on Intel Sapphire Rapids over 14 challenging graph datasets.