Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

Probabilistic frequent subtrees for efficient graph classification and retrieval

: Welke, Pascal; Horvath, Tamas; Wrobel, Stefan

Postprint urn:nbn:de:0011-n-5030432 (764 KByte PDF)
MD5 Fingerprint: ca0f3194c243fdfb1d9ba77b5a337a5a
Created on: 24.7.2019

Machine learning 107 (2018), No.11, pp.1847-1873
ISSN: 0885-6125
Journal Article, Electronic Publication
Fraunhofer IAIS ()
pattern mining; frequent subgraph mining; Frequent subtree mining; probabilistic subtrees; efficient embedding computation; Min-hashing

Frequent subgraphs proved to be powerful features for graph classification and prediction tasks. Their practical use is, however, limited by the computational intractability of pattern enumeration and that of graph embedding into frequent subgraph feature spaces. We propose a simple probabilistic technique that resolves both limitations. In particular, we restrict the pattern language to trees and relax the demand on the completeness of the mining algorithm, as well as on the correctness of the pattern matching operator by replacing transaction and query graphs with small random samples of their spanning trees. In this way we consider only a random subset of frequent subtrees, called probabilistic frequent subtrees, that can be enumerated efficiently. Our extensive empirical evaluation on artificial and benchmark molecular graph datasets shows that probabilistic frequent subtrees can be listed in practically feasible time and that their predictive and retrieval performance is very close even to those of complete sets of frequent subgraphs. We also present different fast techniques for computing the embedding of unseen graphs into (probabilistic frequent) subtree feature spaces. These algorithms utilize the partial order on tree patterns induced by subgraph isomorphism and, as we show empirically, require much less evaluations of subtree isomorphism than the standard brute-force algorithm. We also consider partial embeddings, i.e., when only a part of the feature vector has to be calculated. In particular, we propose a highly effective practical algorithm that significantly reduces the number of pattern matching evaluations required by the classical min-hashing algorithm approximating Jaccard-similarities.