Efficient Defective Clique Enumeration and Search with Worst-Case Optimal Search Space

A 𝑘-defective clique is a relaxation of the traditional clique definition, allowing up to 𝑘 missing edges. This relaxation is crucial in various real-world applications such as link prediction, community detection, and social network analysis. Although the problems of enumerating maximal 𝑘-defective cliques and searching a maximum 𝑘-defective clique have been extensively studied, existing algorithms suffer from limitations such as the combinatorial explosion of small partial solutions and sub-optimal search spaces. To address these limitations, we propose a novel clique-first branchand-bound framework that first generates cliques and then adds missing edges. Furthermore, we introduce a new pivoting technique that achieves a search space size of O (3 𝑛 3 • 𝑛 𝑘 ), where 𝑛 is the number of vertices in the input graph. We prove that the worstcase number of maximal 𝑘-defective cliques is Ω(3 𝑛 3 • 𝑛 𝑘 ) when 𝑘 is a constant, establishing that our algorithm's search space is worstcase optimal. Leveraging the diameter-two property of defective cliques, we further reduce the search space size to O (𝑛 • 3

where 𝛿 is the degeneracy and Δ is the maximum degree of the input graph. We also propose an efficient framework for maximum 𝑘-defective clique search based on our branch-and-bound, together with practical techniques to reduce the search space. Experiments on real-world benchmark datasets with more than 1 million edges demonstrate that each of our proposed algorithms for maximal 𝑘-defective clique enumeration and maximum 𝑘-defective clique search outperforms the respective state-of-the-art algorithms by up to four orders of magnitude in terms of processing time.

• Mathematics of computing → Graph algorithms.