Simple Pattern-only Heuristics Lead To Fast Subgraph Matching Strategies on Very Large Networks

A wide range of biomedical applications entails solving the subgraph isomorphism problem, i.e. nding all the possible subgraphs of a target graph that are structurally equivalent to an input pattern graph. Targets may be very large and complex structures compared to patterns. Methods that address this NP-complete problem use heuristics. Their performance in both time and quality depends on a few subtleties of those heuristics. This paper compares the performance of state-of-theart algorithms for subgraph isomorphism on small, medium and very large graphs. Results show that heuristics based on pattern graphs alone prove to be the most ecient, an unexpected result.