Publica
Hier finden Sie wissenschaftliche Publikationen aus den FraunhoferInstituten. HOPS: Probabilistic Subtree Mining for Small and Large Graphs
 Gupta, R. ; Association for Computing Machinery ACM, Special Interest Group on Knowledge Discovery and Data Mining SIGKDD: 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2020 : Virtual Event,CA, USA, July, 2020 New York: ACM, 2020 ISBN: 9781450379984 pp.12751284 
 International Conference on Knowledge Discovery and Data Mining (KDD) <26, 2020, Online> 

 English 
 Conference Paper 
 Fraunhofer IAIS () 
Abstract
Frequent subgraph mining, i.e., the identification of relevant patterns in graph databases, is a wellknown data mining problem with high practical relevance, since next to summarizing the data, the resulting patterns can also be used to define powerful domainspecific similarity functions for prediction. In recent years, significant progress has been made towards subgraph mining algorithms that scale to complex graphs by focusing on tree patterns and probabilistically allowing a small amount of incompleteness in the result. Nonetheless, the complexity of the pattern matching component used for deciding subtree isomorphism on arbitrary graphs has significantly limited the scalability of existing approaches. In this paper, we adapt sampling techniques from mathematical combinatorics to the problem of probabilistic subtree mining in arbitrary databases of many small to mediumsize graphs or a single large graph. By restricting on tree patterns, we provide an algorithm tha t approximately counts or decides subtree isomorphism for arbitrary transaction graphs in sublinear time with onesided error. Our empirical evaluation on a range of benchmark graph datasets shows that the novel algorithm substantially outperforms stateoftheart approaches both in the task of approximate counting of embeddings in single large graphs and in probabilistic frequent subtree mining in large databases of small to medium sized graphs.