Faster Subgraph Isomorphism Detection by Well-Founded Total Order Indexing

Markus Weber; Marcus Liwicki; Andreas Dengel

In: Pattern Recognition Letters (PRL), Vol. Special Issue on Graph based Representations, Elsevier, 2012.


In this paper an extension to index-based subgraph matching is proposed. This extension significantly speeds up the indexing time for graphs where the nodes are labeled with a rather small amount of different classes. Furthermore, the needed storage amount is significantly reduced. In order to reduce the complexity, we introduce a weight function for labeled graphs. Using this weight function, a well-founded total order is defined on the weights of the labels. Inversions which violate the order are not allowed. A computational complexity analysis of the new preprocessing is given and its completeness is proven. Furthermore, in a number of practical experiments with randomly generated graphs the improvement of the new approach is shown. In experiments performed on random sample graphs, and on real-world datasets. The number of permutations for the real-world datasets have been decreased to a fraction of 10^−5 and 10^−8 in average compared to the original approach by Messmer. The novel indexing strategy makes indexing of larger graphs feasible, allowing for fast detection of subgraphs.

Weitere Links

PRL-2012-Faster_Subgraph_Isomorphism_Detection_by_Well-Founded_Total_Order_Indexing-Weber_et_al.pdf (pdf, 215 KB )

Deutsches Forschungszentrum für Künstliche Intelligenz
German Research Center for Artificial Intelligence