A k -defective clique is a relaxation of the traditional clique definition, allowing up to k 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 k -defective cliques and searching a maximum k -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 branch-and-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 n/3 • n k ), where n is the number of vertices in the input graph. We prove that the worst-case number of maximal k -defective cliques is Ω(3 n/3 • n k ) when k is a constant, establishing that our algorithm's search space is worst-case optimal. Leveraging the diameter-two property of defective cliques, we further reduce the search space size to O (n • 3 δ/3 • (δ Δ) k ), where δ is the degeneracy and Δ is the maximum degree of the input graph. We also propose an efficient framework for maximum k -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 k -defective clique enumeration and maximum k -defective clique search outperforms the respective state-of-the-art algorithms by up to four orders of magnitude in terms of processing time.

Given a set of data graphs and a query graph, graph isomorphism query processing is the problem of finding all the data graphs that are isomorphic to the query graph. Graph isomorphism query processing is a core problem in graph analysis of various application domains. In existing approaches, index construction or query processing takes much time as the graph sizes increase. In this paper, we propose an efficient algorithm for graph isomorphism query processing. We introduce the color-label distribution which represents the canonical coloring of a vertex-labeled graph. Based on degree sequences and color-label distributions, we introduce a two-level index, which helps us efficiently solve graph isomorphism query processing. Experimental results on real datasets show that the proposed algorithm is orders of magnitude faster than the state-of-the-art algorithms in terms of index construction time, and it runs faster than existing algorithms in terms of query processing time as the graph sizes increase.

Graph isomorphism is a core problem in graph analysis of various application domains. Given two graphs, the graph isomorphism problem is to determine whether there exists an isomorphism between them. As real-world graphs are getting bigger and bigger, applications demand practically fast algorithms that can run on large-scale graphs. However, existing approaches such as graph canonization and subgraph isomorphism show limited performances on large-scale graphs either in time or space. In this paper, we propose a new approach to graph isomorphism, which is the framework of pairwise color refinement and efficient backtracking. The main features of our approach are: (1) pairwise color refinement and binary cell mapping (2) compressed CS (candidate space), and (3) partial failing set, which together lead to a much faster and scalable algorithm for graph isomorphism. Extensive experiments with real-world datasets show that our approach outperforms state-of-the-art algorithms by up to orders of magnitude in terms of running time.