Multi-way set enumeration in real-valued tensors

ABSTRACT

The analysis of n-ary relations receives attention in many different fields, for instance biology, web mining, and social studies. In the basic setting, there are n sets of instances, and each observation associates n instances, one from each set. A common approach to explore these n-way data is the search for n-set patterns. An n-set pattern consists of specific subsets of the n instance sets such that all possible n- ary associations between the corresponding instances are observed. This provides a higher-level view of the data, revealing associative relationships between groups of instances. Here, we generalize this approach in two respects. First, we tolerate missing observations to a certain degree, that means we are also interested in n-sets where most (although not all) of the possible combinations have been recorded in the data. Second, we take association weights into account. More precisely, we propose a method to enumerate all n- sets that satisfy a minimum threshold with respect to the average association weight. Non-observed associations obtain by default a weight of zero. Technically, we solve the enumeration task using a reverse search strategy, which allows for effective pruning of the search space. In addition, our algorithm provides a ranking of the solutions and can consider further constraints. We show experimental results on artificial and real-world data sets from different domains.

REFERENCES

• 1: M. Ashburner, C. A. Ball, J. A. Blake, D. Botstein et al. Gene ontology: tool for the unification of biology. the gene ontology consortium. Nat Genet, 25(1):25--29, 2000.
• 2: David Avis , Komei Fukuda, Reverse search for enumeration, Discrete Applied Mathematics, v.65 n.1-3, p.21-46, March 7, 1996 [doi>10.1016/0166-218X(95)00026-N]
• 3: G. Bejerano, N. Friedman, and N. Tishby. Efficient exact p-value computation for small sample, sparse, and surprising categorical data. J Comput Biol, 11(5):867--86, 2004.
• 4: J. Besson, C. Robardet, L. D. Raedt, and J.-F. Boulicaut. Mining bi-sets in numerical data. In S. Dzeroski and J. Struyf, editors, KDID, volume 4747 of Lecture Notes in Computer Science, pages 11--23. Springer, 2006
• 5: Karsten M. Borgwardt , Hans-Peter Kriegel , Peter Wackersreuther, Pattern Mining in Frequent Dynamic Subgraphs, Proceedings of the Sixth International Conference on Data Mining, p.818-822, December 18-22, 2006 [doi>10.1109/ICDM.2006.124]
• 6: L. Cerf, J. Besson, C. Robardet, and J.-F. Boulicaut. Data peeler: Contraint-based closed pattern mining in n-ary relations. In SDM, pages 37--48, 2008.
• 7: A. P. Gasch, P. T. Spellman, C. M. Kao, O. Carmel-Harel, M. B. Eisen, G. Storz, D. Botstein, and P. O. Brown. Genomic Expression Programs in the Response of Yeast Cells to Environmental Changes. Mol. Biol. Cell, 11(12):4241--4257, 2000.
• 8: Elisabeth Georgii , Sabine Dietmann , Takeaki Uno , Philipp Pagel , Koji Tsuda, Enumeration of condition-dependent dense modules in protein interaction networks, Bioinformatics, v.25 n.7, p.933-940, April 2009 [doi>10.1093/bioinformatics/btp080]
• 9: Jiawei Han, Data Mining: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2005
• 10: Haiyan Hu , Xifeng Yan , Yu Huang , Jiawei Han , Xianghong Jasmine Zhou, Mining coherent dense subgraphs across massive biological networks for functional discovery, Bioinformatics, v.21 n.1, p.213-221, January 2005 [doi>10.1093/bioinformatics/bti1049]
• 11: Robert Jaschke , Andreas Hotho , Christoph Schmitz , Bernhard Ganter , Gerd Stumme, TRIAS--An Algorithm for Mining Iceberg Tri-Lattices, Proceedings of the Sixth International Conference on Data Mining, p.907-911, December 18-22, 2006 [doi>10.1109/ICDM.2006.162]
• 12: Liping Ji , Kian-Lee Tan , Anthony K. H. Tung, Mining frequent closed cubes in 3D datasets, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 13: Daxin Jiang , Jian Pei, Mining frequent cross-graph quasi-cliques, ACM Transactions on Knowledge Discovery from Data (TKDD), v.2 n.4, p.1-42, January 2009 [doi>10.1145/1460797.1460799]
• 14: B. Klimt and Y. Yang. The enron corpus: A new dataset for email classification research. In Machine Learning: ECML 2004, pages 217--226. Springer, 2004.
• 15: T. G. Kolda and B. W. Bader. Tensor decompositions and applications. Technical Report SAND 2007-6702, Sandia National Laboratories, Albuquerque, NM and Livermore, CA, 2007.
• 16: Tamara G. Kolda , Jimeng Sun, Scalable Tensor Decompositions for Multi-aspect Data Mining, Proceedings of the 2008 Eighth IEEE International Conference on Data Mining, p.363-372, December 15-19, 2008 [doi>10.1109/ICDM.2008.89]
• 17: M. Koyuturk, W. Szpankowski, and A. Grama. Assessing significance of connectivity and conservation in protein interaction networks. J Comput Biol, 14(6):747--64, 2007.
• 18: Sara C. Madeira , Arlindo L. Oliveira, Biclustering Algorithms for Biological Data Analysis: A Survey, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.1 n.1, p.24-45, January 2004 [doi>10.1109/TCBB.2004.2]
• 19: R. Shamir, A. Maron-Katz, A. Tanay, C. Linhart et al. Expander - an integrative program suite for microarray data analysis. BMC Bioinformatics, 6(1):232, 2005.
• 20: Jimeng Sun , Dacheng Tao , Christos Faloutsos, Beyond streams and graphs: dynamic tensor analysis, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150445]
• 21: T. Uno. An efficient algorithm for enumerating pseudo cliques. In Proceedings of ISAAC 2007, pages 402--414, 2007.
• 22: Xifeng Yan , X. Jasmine Zhou , Jiawei Han, Mining closed relational graphs with connectivity constraints, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081908]
• 23: Zhiping Zeng , Jianyong Wang , Lizhu Zhou , George Karypis, Coherent closed quasi-clique discovery from large dense graph databases, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150506]
• 24: Lizhuang Zhao , Mohammed J. Zaki, TRICLUSTER: an effective algorithm for mining coherent clusters in 3D microarray data, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066236]

INDEX TERMS

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

General Terms:
Algorithms