Coherent Closed Quasi-Clique Discovery from Large Dense Graph Databases

Zhiping Zeng, Jianyong Wang, Lizhu Zhou, and George Karypis
12th International Conference on Knowledge and Data Discovery (KDD), 2006
Download Paper
Frequent coherent subgraphs can provide valuable knowledge about the
underlying internal structure of a graph database, and mining
frequently occurring coherent subgraphs from large dense graph
databases has been witnessed several applications and received
considerable attention in the graph mining community recently. In
this paper, we study how to efficiently mine the complete set of
coherent closed quasi-cliques from large dense graph databases,
which is an especially challenging task due to the downward-closure
property no longer holds. By fully exploring some properties of
quasi-cliques, we propose several novel optimization techniques,
which can prune the unpromising and redundant sub-search spaces
effectively. Meanwhile, we devise an efficient closure checking
scheme to facilitate the discovery of only closed quasi-cliques. We
also develop a coherent closed quasi-clique mining algorithm,
COCAIN. Thorough performance study shows that COCAIN is very efficient
and scalable for large dense graph databases.
Research topics: Data mining | Graph mining