{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:31:55Z","timestamp":1740123115262,"version":"3.37.3"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2019,2,15]],"date-time":"2019-02-15T00:00:00Z","timestamp":1550188800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[2019,7]]},"DOI":"10.1007\/s10994-019-05779-1","type":"journal-article","created":{"date-parts":[[2019,2,15]],"date-time":"2019-02-15T17:26:21Z","timestamp":1550251581000},"page":"1137-1164","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Probabilistic and exact frequent subtree mining in graphs beyond forests"],"prefix":"10.1007","volume":"108","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2123-3781","authenticated-orcid":false,"given":"Pascal","family":"Welke","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6852-6939","authenticated-orcid":false,"given":"Tam\u00e1s","family":"Horv\u00e1th","sequence":"additional","affiliation":[]},{"given":"Stefan","family":"Wrobel","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,2,15]]},"reference":[{"key":"5779_CR1","unstructured":"Agrawal, R., Mannila, H., Srikant, R., Toivonen, H., & Verkamo, A.I. (1996). Fast discovery of association rules. In Advances in Knowledge Discovery and Data Mining (pp. 307\u2013328). AAAI\/MIT Press."},{"issue":"9","key":"5779_CR2","first-page":"1488","volume":"76","author":"T Akutsu","year":"1993","unstructured":"Akutsu, T. (1993). A polynomial time algorithm for finding a largest common subgraph of almost trees of bounded degree. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 76(9), 1488\u20131493.","journal-title":"IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences"},{"issue":"2","key":"5779_CR3","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S Arnborg","year":"1987","unstructured":"Arnborg, S., Corneil, D. G., & Proskurowski, A. (1987). Complexity of finding embeddings in a k-tree. SIAM Journal on Algebraic Discrete Methods, 8(2), 277\u2013284. https:\/\/doi.org\/10.1137\/0608024 .","journal-title":"SIAM Journal on Algebraic Discrete Methods"},{"key":"5779_CR4","doi-asserted-by":"publisher","unstructured":"Bringmann, B., Zimmermann, A., De Raedt, L., & Nijssen, S. (2006). Don\u2019t be afraid of simpler patterns. In J. F\u00fcrnkranz, T. Scheffer, & M. Spiliopoulou (Eds.), European Conference on Principles and Practice of Knowledge Discovery in Databases (PKDD) Proceedings, Lecture Notes in Computer Science (Vol. 4213, pp. 55\u201366). Springer. https:\/\/doi.org\/10.1007\/11871637_10 .","DOI":"10.1007\/11871637_10"},{"issue":"1\u20132","key":"5779_CR5","first-page":"161","volume":"66","author":"Y Chi","year":"2005","unstructured":"Chi, Y., Muntz, R. R., Nijssen, S., & Kok, J. N. (2005). Frequent subtree mining\u2014An overview. Fundamenta Informaticae, 66(1\u20132), 161\u2013198.","journal-title":"Fundamenta Informaticae"},{"issue":"1","key":"5779_CR6","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1016\/0196-6774(87)90030-7","volume":"8","author":"MJ Chung","year":"1987","unstructured":"Chung, M. J. (1987). $$O(n^{2.5})$$ O ( n 2.5 ) time algorithms for the subgraph homeomorphism problem on trees. Journal of Algorithms, 8(1), 106\u2013112. https:\/\/doi.org\/10.1016\/0196-6774(87)90030-7 .","journal-title":"Journal of Algorithms"},{"key":"5779_CR7","doi-asserted-by":"publisher","unstructured":"Cordella, L. P., Foggia, P., Sansone, C., & Vento, M. (1999). Performance evaluation of the VF graph matching algorithm. In International Conference on Image Analysis and Processing (ICIAP) (pp. 1172\u20131177). IEEE Computer Society. https:\/\/doi.org\/10.1109\/ICIAP.1999.797762 .","DOI":"10.1109\/ICIAP.1999.797762"},{"issue":"8","key":"5779_CR8","doi-asserted-by":"publisher","first-page":"1036","DOI":"10.1109\/tkde.2005.127","volume":"17","author":"M Deshpande","year":"2005","unstructured":"Deshpande, M., Kuramochi, M., Wale, N., & Karypis, G. (2005). Frequent substructure-based approaches for classifying chemical compounds. Transactions on Knowledge and Data Engineering, 17(8), 1036\u20131050. https:\/\/doi.org\/10.1109\/tkde.2005.127 .","journal-title":"Transactions on Knowledge and Data Engineering"},{"key":"5779_CR9","volume-title":"Graph theory, Graduate texts in mathematics","author":"R Diestel","year":"2012","unstructured":"Diestel, R. (2012). Graph theory, Graduate texts in mathematics (4th ed., Vol. 173). Berlin: Springer.","edition":"4"},{"key":"5779_CR10","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","volume":"6","author":"P Erd\u0151s","year":"1959","unstructured":"Erd\u0151s, P., & R\u00e9nyi, A. (1959). On random graphs I. Publicationes Mathematicae, 6, 290\u2013297.","journal-title":"Publicationes Mathematicae"},{"key":"5779_CR11","volume-title":"Computers and intractability: A guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness. New York: W. H. Freeman."},{"issue":"5","key":"5779_CR12","doi-asserted-by":"publisher","first-page":"755","DOI":"10.1016\/j.jcss.2007.01.003","volume":"73","author":"M Hajiaghayi","year":"2007","unstructured":"Hajiaghayi, M., & Nishimura, N. (2007). Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth. Journal of Computer and System Sciences, 73(5), 755\u2013768. https:\/\/doi.org\/10.1016\/j.jcss.2007.01.003 .","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"5779_CR13","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1023\/b:dami.0000005258.31418.83","volume":"8","author":"J Han","year":"2004","unstructured":"Han, J., Pei, J., Yin, Y., & Mao, R. (2004). Mining frequent patterns without candidate generation: A frequent-pattern tree approach. Data Mining and Knowledge Discovery, 8(1), 53\u201387. https:\/\/doi.org\/10.1023\/b:dami.0000005258.31418.83 .","journal-title":"Data Mining and Knowledge Discovery"},{"issue":"4","key":"5779_CR14","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"JE Hopcroft","year":"1973","unstructured":"Hopcroft, J. E., & Karp, R. M. (1973). An n $$^{\\wedge }$$ \u2227 5\/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing, 2(4), 225\u2013231. https:\/\/doi.org\/10.1137\/0202019 .","journal-title":"SIAM Journal on Computing"},{"key":"5779_CR15","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1007\/978-3-540-73847-3_26","volume-title":"Inductive Logic Programming (ILP) Revised Selected Papers, Lecture Notes in Computer Science","author":"T Horv\u00e1th","year":"2007","unstructured":"Horv\u00e1th, T., Bringmann, B., & Raedt, L. D. (2007). Frequent hypergraph mining. In S. Muggleton, R. P. Otero, & A. Tamaddoni-Nezhad (Eds.), Inductive Logic Programming (ILP) Revised Selected Papers, Lecture Notes in Computer Science (Vol. 4455, pp. 244\u2013259). Berlin: Springer. https:\/\/doi.org\/10.1007\/978-3-540-73847-3_26 ."},{"issue":"31\u201333","key":"5779_CR16","doi-asserted-by":"publisher","first-page":"2784","DOI":"10.1016\/j.tcs.2010.03.030","volume":"411","author":"T Horv\u00e1th","year":"2010","unstructured":"Horv\u00e1th, T., & Ramon, J. (2010). Efficient frequent connected subgraph mining in graphs of bounded tree-width. Theoretical Computer Science, 411(31\u201333), 2784\u20132797. https:\/\/doi.org\/10.1016\/j.tcs.2010.03.030 .","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"5779_CR17","doi-asserted-by":"publisher","first-page":"472","DOI":"10.1007\/s10618-009-0162-1","volume":"21","author":"T Horv\u00e1th","year":"2010","unstructured":"Horv\u00e1th, T., Ramon, J., & Wrobel, S. (2010). Frequent subgraph mining in outerplanar graphs. Data Mining and Knowledge Discovery, 21(3), 472\u2013508. https:\/\/doi.org\/10.1007\/s10618-009-0162-1 .","journal-title":"Data Mining and Knowledge Discovery"},{"issue":"3","key":"5779_CR18","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0020-0190(88)90065-8","volume":"27","author":"DS Johnson","year":"1988","unstructured":"Johnson, D. S., Papadimitriou, C. H., & Yannakakis, M. (1988). On generating all maximal independent sets. Information Processing Letters, 27(3), 119\u2013123. https:\/\/doi.org\/10.1016\/0020-0190(88)90065-8 .","journal-title":"Information Processing Letters"},{"key":"5779_CR19","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1007\/978-3-662-04599-2_11","volume-title":"Relational data mining","author":"S Kramer","year":"2001","unstructured":"Kramer, S., Lavra\u010d, N., & Flach, P. (2001). Propositionalization approaches to relational data mining. In S. D\u017eeroski & N. Lavra\u010d (Eds.), Relational data mining (pp. 262\u2013291). Berlin: Springer. https:\/\/doi.org\/10.1007\/978-3-662-04599-2_11 ."},{"issue":"9","key":"5779_CR20","doi-asserted-by":"publisher","first-page":"1038","DOI":"10.1109\/TKDE.2004.33","volume":"16","author":"M Kuramochi","year":"2004","unstructured":"Kuramochi, M., & Karypis, G. (2004). An efficient algorithm for discovering frequent subgraphs. Transactions on Knowledge and Data Engineering, 16(9), 1038\u20131051. https:\/\/doi.org\/10.1109\/TKDE.2004.33 .","journal-title":"Transactions on Knowledge and Data Engineering"},{"issue":"3","key":"5779_CR21","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1023\/a:1009796218281","volume":"1","author":"H Mannila","year":"1997","unstructured":"Mannila, H., & Toivonen, H. (1997). Levelwise search and borders of theories in knowledge discovery. Data Mining and Knowledge Discovery, 1(3), 241\u2013258. https:\/\/doi.org\/10.1023\/a:1009796218281 .","journal-title":"Data Mining and Knowledge Discovery"},{"key":"5779_CR22","doi-asserted-by":"publisher","unstructured":"Marx, D., & Pilipczuk, M. (2014). Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but wereafraid to ask). In E. W. Mayr & N. Portier (Eds.), International Symposium on Theoretical Aspects of Computer Science (STACS), Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, LIPIcs (Vol. 25, pp. 542\u2013553). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2014.542 .","DOI":"10.4230\/LIPIcs.STACS.2014.542"},{"issue":"1\u20133","key":"5779_CR23","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/0012-365x(92)90687-b","volume":"108","author":"J Matou\u0161ek","year":"1992","unstructured":"Matou\u0161ek, J., & Thomas, R. (1992). On the complexity of finding iso-and other morphisms for partial $$k$$ k -trees. Discrete Mathematics, 108(1\u20133), 343\u2013364. https:\/\/doi.org\/10.1016\/0012-365x(92)90687-b .","journal-title":"Discrete Mathematics"},{"key":"5779_CR24","first-page":"273","volume":"10","author":"DW Matula","year":"1968","unstructured":"Matula, D. W. (1968). An algorithm for subtree identification. Siam Review, 10, 273\u2013274.","journal-title":"Siam Review"},{"issue":"1","key":"5779_CR25","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/j.entcs.2004.12.039","volume":"127","author":"S Nijssen","year":"2005","unstructured":"Nijssen, S., & Kok, J. N. (2005). The gaston tool for frequent subgraph mining. Electronic Notes in Theoretical Computer Science, 127(1), 77\u201387. https:\/\/doi.org\/10.1016\/j.entcs.2004.12.039 .","journal-title":"Electronic Notes in Theoretical Computer Science"},{"key":"5779_CR26","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1002\/net.1975.5.3.237","volume":"5","author":"RC Read","year":"1975","unstructured":"Read, R. C., & Tarjan, R. (1975). Bound on backtrack algorithms for listing cycles, paths, and spanning trees. Networks, 5, 237\u2013252.","journal-title":"Networks"},{"issue":"3","key":"5779_CR27","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N Robertson","year":"1986","unstructured":"Robertson, N., & Seymour, P. D. (1986). Graph minors. II. Algorithmic aspects of tree-width. Journal of Algorithms, 7(3), 309\u2013322. https:\/\/doi.org\/10.1016\/0196-6774(86)90023-4 .","journal-title":"Journal of Algorithms"},{"issue":"2","key":"5779_CR28","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1006\/jagm.1999.1044","volume":"33","author":"R Shamir","year":"1999","unstructured":"Shamir, R., & Tsur, D. (1999). Faster subtree isomorphism. Journal of Algorithms, 33(2), 267\u2013280. https:\/\/doi.org\/10.1006\/jagm.1999.1044 .","journal-title":"Journal of Algorithms"},{"key":"5779_CR29","unstructured":"Sloane, N. J. A. (2016). The online encyclopedia of integer sequences. A000055: Number of trees with n unlabeled nodes. http:\/\/oeis.org\/A000055 . Accessed 18 November 2016."},{"key":"5779_CR30","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511609589","volume-title":"Enumerative combinatorics, Cambridge Studies in Advanced Mathematics","author":"RP Stanley","year":"1999","unstructured":"Stanley, R. P., & Fomin, S. (1999). Enumerative combinatorics, Cambridge Studies in Advanced Mathematics (Vol. 2). Cambridge: Cambridge University Press. https:\/\/doi.org\/10.1017\/CBO9780511609589 ."},{"issue":"2","key":"5779_CR31","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"R Tarjan","year":"1972","unstructured":"Tarjan, R. (1972). Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1(2), 146\u2013160.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"5779_CR32","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/321921.321925","volume":"23","author":"JR Ullmann","year":"1976","unstructured":"Ullmann, J. R. (1976). An algorithm for subgraph isomorphism. Journal of the ACM, 23(1), 31\u201342. https:\/\/doi.org\/10.1145\/321921.321925 .","journal-title":"Journal of the ACM"},{"issue":"4","key":"5779_CR33","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/s11222-007-9033-z","volume":"17","author":"U Luxburg von","year":"2007","unstructured":"von Luxburg, U. (2007). A tutorial on spectral clustering. Statistics and Computing, 17(4), 395\u2013416. https:\/\/doi.org\/10.1007\/s11222-007-9033-z .","journal-title":"Statistics and Computing"},{"key":"5779_CR34","unstructured":"Welke, P. (2019). Efficient frequent subtree mining beyond forests. Ph.D. thesis, University of Bonn."},{"key":"5779_CR35","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1007\/978-3-319-23708-4_14","volume-title":"Inductive Logic Programming (ILP) Revised Selected Papers, Lecture Notes in Computer Science","author":"P Welke","year":"2015","unstructured":"Welke, P., Horv\u00e1th, T., & Wrobel, S. (2015). On the complexity of frequent subtree mining in very simple structures. In J. Davis & J. Ramon (Eds.), Inductive Logic Programming (ILP) Revised Selected Papers, Lecture Notes in Computer Science (Vol. 9046, pp. 194\u2013209). Berlin: Springer. https:\/\/doi.org\/10.1007\/978-3-319-23708-4_14 ."},{"issue":"11","key":"5779_CR36","doi-asserted-by":"publisher","first-page":"1847","DOI":"10.1007\/s10994-017-5688-7","volume":"107","author":"P Welke","year":"2018","unstructured":"Welke, P., Horv\u00e1th, T., & Wrobel, S. (2018). Probabilistic frequent subtrees for efficient graph classification and retrieval. Machine Learning, 107(11), 1847\u20131873. https:\/\/doi.org\/10.1007\/s10994-017-5688-7 .","journal-title":"Machine Learning"},{"key":"5779_CR37","doi-asserted-by":"publisher","unstructured":"Wilson, D.B. (1996). Generating random spanning trees more quickly than the cover time. In: G.L. Miller (Ed.) ACM Symposium on the Theory of Computing (STOC) Proceedings (pp. 296\u2013303). ACM. https:\/\/doi.org\/10.1145\/237814.237880 .","DOI":"10.1145\/237814.237880"},{"issue":"1","key":"5779_CR38","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/s11280-007-0031-z","volume":"11","author":"P Zhao","year":"2008","unstructured":"Zhao, P., & Yu, J. X. (2008). Fast frequent free tree mining in graph databases. World Wide Web, 11(1), 71\u201392. https:\/\/doi.org\/10.1007\/s11280-007-0031-z .","journal-title":"World Wide Web"}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10994-019-05779-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-019-05779-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-019-05779-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,13]],"date-time":"2023-09-13T17:48:40Z","timestamp":1694627320000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10994-019-05779-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,2,15]]},"references-count":38,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2019,7]]}},"alternative-id":["5779"],"URL":"https:\/\/doi.org\/10.1007\/s10994-019-05779-1","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"type":"print","value":"0885-6125"},{"type":"electronic","value":"1573-0565"}],"subject":[],"published":{"date-parts":[[2019,2,15]]},"assertion":[{"value":"14 December 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 January 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 February 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}