Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

Mining Tree Patterns with Partially Injective Homomorphisms

: Schulz, Till Hendrik; Horvath, Tamas; Welke, Pascal; Wrobel, Stefan

Postprint urn:nbn:de:0011-n-5523328 (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 10-14, 2018; Proceedings
Cham: Springer Nature, 2019 (Lecture Notes in Artificial Intelligence 11052)
ISBN: 978-3-030-10927-1 (Print)
ISBN: 978-3-030-10928-8 (Online)
ISBN: 978-3-030-10929-5 (Print)
European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD) <2018, Dublin>
Conference Paper, Electronic Publication
Fraunhofer IAIS ()
frequent subgraph mining; graphs of bounded tree-width; graph homomorphisms

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 tree-width 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 trade-off between efficiency and predictive power.