Maximal Defective Clique Enumeration

Abstract

Maximal clique enumeration is a fundamental operator in graph analysis. The model of clique, however, is typically too restrictive for real-world applications as it requires an edge for every pair of vertices. To remedy this restriction, practical graph analysis applications often resort to find relaxed cliques as alternatives. In this work, we investigate a notable relaxed clique model, called s-defective clique, which allows at most s edges to be missing. Similar to the complexity of maximal clique enumeration, the problem of enumerating all maximal s-defective cliques is also NP-hard. To solve this problem, we first develop a new polynomial-delay algorithm based on a carefully-designed reverse search technique, which can output two consecutive results within polynomial time. To achieve better practical efficiency, we propose a branch-and-bound algorithm with a novel pivoting technique. We prove that the time complexity of this algorithm depends only on O(α_sn) or O(αsδ) when using a degeneracy ordering optimization, where αs is a positive real number strictly less than 2, and δ (δ <n) is the degeneracy of the graph. To our knowledge, this is the first algorithm that can break the O(2n) time complexity to enumerate all maximal s-defective cliques (s>0). We also develop several new pruning techniques to further improve the efficiency of our branch-and-bound algorithm to enumerate all relatively-large maximal s-defective cliques. In addition, we further generalize our pivot-based branch-and-bound algorithm to enumerate all maximal subgraphs satisfying a hereditary property. Here we call a graph meeting the hereditary property if all its subgraphs have the same property as itself. Finally, extensive experiments on 11 datasets demonstrate the efficiency, effectiveness, and scalability of the proposed solutions.