Abstract

In this paper, the problem of finding sequential patterns from graph databases is investigated. Two serious issues dealt in this paper are efficiency and effectiveness of mining algorithm. A huge volume of sequential patterns has been generated out of which most of them are uninteresting. The users have to go through a large number of patterns to find interesting results. In order to improve the efficiency and effectiveness of the mining process, constraints are more essential. Constraint-based mining is used in many fields of data mining such as frequent pattern mining, sequential pattern mining, and subgraph mining. A novel algorithm called CSGP (Constraint-based Sequential Graph Pattern mining) is proposed for mining interesting sequential patterns from graph databases. CSGP algorithm is revised to mine top-k closed patterns and named as TCSGP (Top-k Closed constraint-based Sequential Graph Pattern mining).

References

• Arnaud Soulet, and Bruno Cremilleux, “Optimizing Constraint-Based Mining by Automatically Relaxing Constraints”, Fifth IEEE International conference on Data mining, Nov 2005.
• Chen Wang, Yangtai Zhu, Tianyi Wu, Baileshi, “Constraint-Based Graph Mining in Large Database”, Web Technologies Research and Development-ApWeb 2005, Lecture Notes in Computer Science, Volume 3399, 2005, 133-144.
• Chuntao Jiang, Frans Coenen and Michele Zito, “A survey of Frequent Subgraph Mining Algorithms”, The Knowledge Engineering Review, Volume 28, Issue 01, Mar 2013, 75-105.
• F. Masseglia, P. Poncelet, and M. Teisseire, “Efficient mining of sequential patterns with time constraints: Reducing the combinations”, Expert Systems with Applications, Elsevier, Volume 36, Issue 02, Mar 2009, 2677-2690.
• Feida Zhu, Xifeng Yan, Jiawei Han, and Philip S. Yu, “gPrune: A Constraint Pushing Framework for Graph Pattern Mining”, Advances in Knowledge Discovery and Data Mining, Lecture notes in Computer Science, Springer, Volume 4426, 2007, 388-400.
• Francesco Bonchi, Claudio Lucchese, “Extending the state-of-the-art of Constraint-based pattern discovery”, Data and Knowledge Engineering, Elsevier, Volume 60, Issue 02, Feb 2007, 377-399.
• Francesco Bonchi, Fosca Giannotti, Claudio Lucchese, Salvatore Orlando, Raffaele Perego, Roberto Trasarti, “A constraint-based querying system for exploratory pattern discovery”, Information Systems, Elsevier, Volume 34, Issue 01, March 2009, 3-27.
• Gao Cong, and Bing Liu, “ Speed-up Iterative Frequent Itemset Mining with Constraint Changes”. In proceedings of 2002 IEEE International conference on Data mining, 2002, 107-114.
• Jean-Francois Boulicat and Baptiste Jeudy, “Constraint-Based Data Mining”. The Data mining and Knowledge Discovery Handbook, Springer, 2005, 399-416.
• Jian Pei and Jiawei Han, “Can We Push More Constraints into Frequent Pattern Mining?”. In Proceedings of the Sixth ACM SIGKDD international conference on knowledge discovery and data mining, 2000, 350-354.
• Jian Pei, Jiawei Han, and Laks V.S. Lakshmanan, “Mining Frequent Itemsets with Convertible Constraints”. In proceedings of 1th international conference on Data Engineering, IEEE, April 2001, 433-442.
• Jian Pei, Jiawei Han, and Wei Wang, “ Mining Sequential Patterns with Constraints in Large Databases”. In Proceedings of CIKM’02 Eleventh International conference on Information and knowledge management, ACM, Newyork, 2002, 18-25.
• Jian Pei, Jiawei Han, and Wei Wang, “Constraint-based sequential pattern mining: the pattern-growth methods”, Journal of Intelligent Information Systems, Springer, Volume 28, Issue 02, April 200, 133-160.
• Loic Cerf, Jeremy Besson, Celine Robardet, Jean-Francois Boulicaut, “DATA-PEELER: Constraint-Based Closed Pattern Mining in n-ary Relations”. In proceedings of the 2008 SIAM International conference on Data Mining, 2008, 37-48.
• Luc De Raedt, and Albrecht Zimmermann, “Constraint-Based Pattern Set Mining”. In proceedings of the 2007 SIAM International conference on Data Mining, 2007.
• Luc De Raedt, Tias Guns, Siegfried Nijssen, “Constraint Programming for Itemset Mining”. In Proceedings of KDD’08, ACM, Aug 2008, 204-212.
• Marek Wojciechowski and Maciej Zakrzewicz, “Dataset Filtering Techniques in Constraint-Based Frequent Pattern Mining”. In Proceedings of the ESF Exploratory workshop on Pattern Detection and Discovery, Springer, 2002, 77-91.
• Marion Leleu, Christophe Rigotti, Jean-Francois Boulicaut, and Guillaume Euvrard, “ Constraint-Based Mining of Sequential Patterns over Datasets with Consecutive Repetitions”, Knowledge Discovery in databases: PKDD 2003, Lecture notes in Computer Science, Springer, Volume 2838, 2003, 303-314.
• Mehdi Khiari, Patrice Boizumault, and Bruno Cremilleux, “Combining CSP and Constraint-Based Mining for Pattern Discovery”, Computational Science and its applications, ICCSA 2010 Lecture Notes in Computer science, Springer, Volume 601, Mar 2010, 432-447.
• Minos N. Garofalakis, Rajeev Rastogi, and Kyuseok Shim, “ SPIRIT: Sequential Pattern Mining with Regular Expression Constraints”. In Proceedings of VLDB’99 25th International conference on very large databases, Morgan Kaufmann publishers, San Francisco, 1999, 223-234.
• Siegfried Nijssen, TiasGuns, and Luc De Raedt, “Correlated Itemset Mining in ROC space : A Constraint Programming Approach”. In Proceedings of KDD’09, ACM, 2009, 647-656.
• Stefano Bistarelli, and Francesco Bonchi, “Soft constraint based pattern mining”, Data and Knowledge Engineering, Elsevier, Volume 62, Issue 01, July 2007, 118-137.
• Synthetic graph generated by IBM Quest Synthetic Data Generation Code for Associations and Sequential Patterns. [http://www.7.ust.hk/graphgen/].
• Unil Yun, “Mining lossless closed frequent patterns with weight constraints”, Knowledge-Based Systems, Elsevier, Volume 20, Issue 01, Feb 2007, 86-97.
• Wei Wang, Chen Wang, Yongtai Zhu, Baile Shi, Jian Pei, Xifeng Yan, and Jiawei Han, “ GraphMiner: A Structural Pattern-Mining System for Large Disk-based Graph Databases and Its Applications”. In proceedings of the 2005 ACM SIGMOD international conference on Management of data, ACM, Newyork, 2005, 89-881.
• Xifeng Yan, X.Jasmine Zhou, and Jiawei Han, “Mining Closed Relational Graphs with Connectivity Constraints. In proceedings of KDD’05, ACM, Newyork, 2005, 324-333.
• Yen-Liang Chen, Ya-Han Hu, “Constraint-based sequential pattern mining: The consideration of recency and compactness”, Decision Support Systems, Elsevier, Volume 42, Issue 02, Nov 2006, 1203-1215.