On mining cross-graph quasi-cliques

ABSTRACT

Joint mining of multiple data sets can often discover interesting, novel, and reliable patterns which cannot be obtained solely from any single source. For example, in cross-market customer segmentation, a group of customers who behave similarly in multiple markets should be considered as a more coherent and more reliable cluster than clusters found in a single market. As another example, in bioinformatics, by joint mining of gene expression data and protein interaction data, we can find clusters of genes which show coherent expression patterns and also produce interacting proteins. Such clusters may be potential pathways.In this paper, we investigate a novel data mining problem, mining cross-graph quasi-cliques, which is generalized from several interesting applications such as cross-market customer segmentation and joint mining of gene expression data and protein interaction data. We build a general model for mining cross-graph quasi-cliques, show why the complete set of cross-graph quasi-cliques cannot be found by previous data mining methods, and study the complexity of the problem. While the problem is difficult, we develop an efficient algorithm, Crochet, which exploits several interesting and effective techniques and heuristics to efficaciously mine cross-graph quasi-cliques. A systematic performance study is reported on both synthetic and real data sets. We demonstrate some interesting and meaningful cross-graph quasi-cliques in bioinformatics. The experimental results also show that algorithm Crochet is efficient and scalable.

REFERENCES

• 1: James Abello , Mauricio G. C. Resende , Sandra Sudarsky, Massive Quasi-Clique Detection, Proceedings of the 5th Latin American Symposium on Theoretical Informatics, p.598-612, April 03-06, 2002
• 2: Bader, G.D. and Hogue, C.W. An automated method for finding molecular complexes in large protein interaction networks. BMC Bioinformatics, 4(1)(2), Jan. 2003.
• 3: Barabási, A.L. and Albert, R. Emergence of scaling in random networks. Science, 286, Oct. 1999.
• 4: Bayada, D.M. et al. An algorithm for the nultiple common subgraph problem. J. of Chem Info & Comp Sci, pages 680--685, 1992.
• 5: Ben-Dor, A. et al. Clustering gene expression patterns. J. of Comp Biology, 6(3/4):281--297, 1999.
• 6: Bu, D. et al. Topological structure analysis of the protein-protein interaction network in budding yeast. Nucleic Acids Research, 31(9):2443--2450, 2003.
• 7: Yizong Cheng , George M. Church, Biclustering of Expression Data, Proceedings of the Eighth International Conference on Intelligent Systems for Molecular Biology, p.93-103, August 19-23, 2000
• 8: Cho, R.J. et al. A Genome-Wide Transcriptional Analysis of the Mitotic Cell Cycle. Molecular Cell, Vol. 2(1):65--73, July 1998.
• 9: Chris H. Q. Ding , Xiaofeng He , Hongyuan Zha , Ming Gu , Horst D. Simon, A Min-max Cut Algorithm for Graph Partitioning and Data Clustering, Proceedings of the 2001 IEEE International Conference on Data Mining, p.107-114, November 29-December 02, 2001
• 10: Dongen, S.V. Graph clustering by flow simulation. PhD Thesis, University of Utrecht, The Netherlands, 2000.
• 11: Sašo Džeroski, Multi-relational data mining: an introduction, ACM SIGKDD Explorations Newsletter, v.5 n.1, July 2003 [doi>10.1145/959242.959245]
• 12: Enright, A.J., Dongen, S.V. and Ouzounis, C.A. An efficient algorithm for large-scale detection of protein families. Nucleic Acids Reserach, 30(7):1575--1584, 2002.
• 13: Christos Faloutsos , Kevin S. McCurley , Andrew Tomkins, Fast discovery of connection subgraphs, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014068]
• 14: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 15: Erez Hartuv , Ron Shamir, A clustering algorithm based on graph connectivity, Information Processing Letters, v.76 n.4-6, p.175-181, Dec.31 2000 [doi>10.1016/S0020-0190(00)00142-3]
• 16: Holder, L.B. et al. Substructure discovery in the subdue system. In KDD'94.
• 17: Akihiro Inokuchi , Takashi Washio , Hiroshi Motoda, An Apriori-Based Algorithm for Mining Frequent Substructures from Graph Data, Proceedings of the 4th European Conference on Principles of Data Mining and Knowledge Discovery, p.13-23, September 13-16, 2000
• 18: Glen Jeh , Jennifer Widom, Mining the space of graph properties, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014075]
• 19: Kasturi, J. et al. An information theoretic approach for analyzing temporal patterns of gene expression. Bioinformatics, pages 449--458, 2003.
• 20: Michihiro Kuramochi , George Karypis, Frequent Subgraph Discovery, Proceedings of the 2001 IEEE International Conference on Data Mining, p.313-320, November 29-December 02, 2001
• 21: H. Matsuda , T. Ishihara , A. Hashimoto, Classifying molecular sequences using a linkage graph with their pairwise similarities, Theoretical Computer Science, v.210 n.2, p.305-325, Jan. 17, 1999 [doi>10.1016/S0304-3975(98)00091-7]
• 22: Ng, A.Y. et al. On spectral clustering: analysis and an algorithm. Advances in Neural Information Processing Systems, 14, 2001.
• 23: Christopher R. Palmer , Phillip B. Gibbons , Christos Faloutsos, ANF: a fast and scalable tool for data mining in massive graphs, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775059]
• 24: Rymon, R. Search through systematic set enumeration. In KR'92.
• 25: Segal, E. et al. Discovering molecular pathways from protein interaction and gene expression data. Bioinformatics, 19:i264--i272, 2003.
• 26: Roded Sharan , Ron Shamir, Center CLICK: A Clustering Algorithm with Applications to Gene Expression Analysis, Proceedings of the Eighth International Conference on Intelligent Systems for Molecular Biology, p.307-316, August 19-23, 2000
• 27: Takahashi, Y. et al. Recognition of largest common fragment among a variety of chemical structures. Analytical Sciences, pages 23--28, 1987.
• 28: Chen Wang , Wei Wang , Jian Pei , Yongtai Zhu , Baile Shi, Scalable mining of large disk-based graph databases, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014088]
• 29: Haixun Wang , Wei Wang , Jiong Yang , Philip S. Yu, Clustering by pattern similarity in large data sets, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564737]
• 30: Xu, Y. et al. Clustering gene expression data using a graph-theoretic approach: an application of minimum spanning trees. Bioinformatics, 18:536--545, 2002.
• 31: Xifeng Yan , Jiawei Han, CloseGraph: mining closed frequent graph patterns, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956784]
• 32: Xifeng Yan , Jiawei Han, gSpan: Graph-Based Substructure Pattern Mining, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.721, December 09-12, 2002
• 33: Xifeng Yan , Philip S. Yu , Jiawei Han, Graph indexing: a frequent structure-based approach, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007607]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Performance

Keywords:
bioinformatics, graph mining, patterns