Publica
Hier finden Sie wissenschaftliche Publikationen aus den FraunhoferInstituten. Mining Tree Patterns with Partially Injective Homomorphisms
:
Postprint urn:nbn:de:0011n5523328 (301 KByte PDF) MD5 Fingerprint: 24a15315aa453726d8837c63a5260cf8 Created on: 24.7.2019 
 Berlingerio, Michele: Machine learning and knowledge discovery in databases. European Conference, ECML PKDD 2018 : Dublin, Ireland, September 1014, 2018; Proceedings Cham: Springer Nature, 2019 (Lecture Notes in Artificial Intelligence 11052) ISBN: 9783030109271 (Print) ISBN: 9783030109288 (Online) ISBN: 9783030109295 (Print) pp.585601 
 European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD) <2018, Dublin> 

 English 
 Conference Paper, Electronic Publication 
 Fraunhofer IAIS () 
 frequent subgraph mining; graphs of bounded treewidth; graph homomorphisms 
Abstract
One of the main differences between inductive logic programming (ILP) and graph mining lies in the pattern matching operator applied: While it is mainly defined by relational homomorphism (i.e., subsumption) in ILP, subgraph isomorphism is the most common pattern matching operator in graph mining. Using the fact that subgraph isomorphisms are injective homomorphisms, we bridge the gap between ILP and graph mining by considering a natural transition from homomorphisms to subgraph isomorphisms that is defined by partially injective homomorphisms, i.e., which require injectivity only for subsets of the vertex pairs in the pattern. Utilizing positive complexity results on deciding homomorphisms from bounded treewidth graphs, we present an algorithm mining frequent trees from arbitrary graphs w.r.t. partially injective homomorphisms. Our experimental results show that the predictive performance of the patterns obtained is comparable to that of ordinary frequent subgraphs. Thus, by preserving much from the advantageous properties of homomorphisms and subgraph isomorphisms, our approach provides a tradeoff between efficiency and predictive power.