jmlr jmlr2009 jmlr2009-72 jmlr2009-72-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Jan Ramon, Siegfried Nijssen
Abstract: Algorithms that list graphs such that no two listed graphs are isomorphic, are important building blocks of systems for mining and learning in graphs. Algorithms are already known that solve this problem efficiently for many classes of graphs of restricted topology, such as trees. In this article we introduce the concept of a dense augmentation schema, and introduce an algorithm that can be used to enumerate any class of graphs with polynomial delay, as long as the class of graphs can be described using a monotonic predicate operating on a dense augmentation schema. In practice this means that this is the first enumeration algorithm that can be applied theoretically efficiently in any frequent subgraph mining algorithm, and that this algorithm generalizes to situations beyond the standard frequent subgraph mining setting. Keywords: graph mining, enumeration, monotonic graph classes
Rakesh Agrawal, Heikki Mannila, Ramakrishnan Srikant, Hannu Toivonen, and A. Inkeri Verkamo. Fast discovery of association rules. In Advances in Knowledge Discovery and Data Mining. AAAI/MIT Press, 1996. Christian Borgelt and Michael R. Berthold. Mining molecular fragments: Finding relevant substructures of molecules. In ICDM, pages 51–58, 2002. Gregory Butler. Fundamental algorithms for permutation groups, volume 559 of Lecture Notes in Computer Science. Springer-Verlag, 1991. Yun Chi, Richard R. Muntz, Siegfried Nijssen, and Joost N. Kok. Frequent subtree mining - an overview. Fundam. Inform., 66(1-2):161–198, 2005. Leslie A. Goldberg. Efficient algorithms for listing unlabeled graphs. Journal of Algorithms, 13(1): 128–143, 1992. Leslie A. Goldberg. Polynomial space polynomial delay algorithms for listing families of graphs. In Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing (STOC’93), pages 218–225, New York, NY, USA, 1993. ACM Press. Tam´ s Horv´ th, Jan Ramon, and Stefan Wrobel. Frequent subgraph mining in outerplanar graphs. a a In Proceedings of the Twelfth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 197–206, Philadelphia, PA, August 2006. Jun Huan, Wei Wang, and Jan Prins. Efficient mining of frequent subgraphs in the presence of isomorphism. In ICDM, pages 549–552. IEEE Computer Society, 2003. Akihiro Inokuchi. Mining generalized substructures from a set of labeled graphs. In ICDM, pages 415–418. IEEE Computer Society, 2004. Akihiro Inokuchi, Takashi Washio, and Hiroshi Motoda. Complete mining of frequent patterns from graphs: Mining graph data. Machine Learning, 50(3):321–354, 2003. Johannes K¨ bler, Uwe Sch¨ ning, and Jacobo Tor´ n. The Graph Isomorphism Problem: Its Struco o a tural Complexity. Birkh¨ user, 1993. a Michihiro Kuramochi and George Karypis. An efficient algorithm for discovering frequent subgraphs. IEEE Trans. Knowl. Data Eng., 16(9):1038–1051, 2004. 928 P OLYNOMIAL -D ELAY G RAPH E NUMERATION Jure Leskovec, Ajit Singh, and Jon M. Kleinberg. Patterns of influence in a recommendation network. In Advances in Knowledge Discovery and Data Mining, 10th Pacific-Asia Conference (PAKDD), pages 380–389, 2006. Brendan D. McKay. Isomorph-free exhaustive generation. Journal of Algorithms, 26:306–324, 1998. Shin-ichi Nakano and Takeaki Uno. Constant time generation of trees with specified diameter. In Juraj Hromkovic, Manfred Nagl, and Bernhard Westfechtel, editors, Proceedings of the 30th International Workshop on Graph Theoretical Concepts in Computer Science, volume 3353 of Lecture Notes in Computer Science, pages 33–45. Springer-Verlag, 2004. Siegfried Nijssen and Joost N. Kok. A quickstart in frequent structure mining can make a difference. In Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pages 647–652, 2004. Christophe Paul, Andrzej Proskurowski, and Jan A. Telle. Generating graphs of bounded branchwidth. In Proceedings of the 32nd International Workshop on Graph Theoretical Concepts in Computer Science, volume 4271 of Lecture Notes in Computer Science, pages 206–216, 2006. Jan Ramon and Siegfried Nijssen. General graph refinement with polynomial delay. In Proceedings of the Workshop on Mining and Learning with Graphs (MLG’07), 2007. Robert A. Wright, Bruce Richmond, Andrew Odlyzko, and Brendan D. McKay. Constant time generation of free trees. SIAM Journal on Computing, 15(2):540–548, 1986. Xifeng Yan and Jiawei Han. gSpan: Graph-based substructure pattern mining. In Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM 2002), pages 721–724, Japan, 2002. IEEE Computer Society. 929