@article{6fd006bc36e14228b63befdb748062e4,
title = "Fast Subgraph Matching Strategies Based on Pattern-Only Heuristics",
abstract = "Many scientific applications entail solving the subgraph isomorphism problem, i.e., given an input pattern graph, find all the subgraphs of a (usually much larger) target graph that are structurally equivalent to that input. Because subgraph isomorphism is NP-complete, methods to solve it have to use heuristics. This work evaluates subgraph isomorphism methods to assess their computational behavior on a wide range of synthetic and real graphs. Surprisingly, our experiments show that, among the leading algorithms, certain heuristics based only on pattern graphs are the most efficient.",
keywords = "Networks biology, Search strategy, Subgraph isomorphism",
author = "Antonino Aparo and Vincenzo Bonnici and Giovanni Micale and Alfredo Ferro and Dennis Shasha and Alfredo Pulvirenti and Rosalba Giugno",
note = "Funding Information: Fig. 5 Number of instances, expressed as percentages with respect to the total amount of tests, that one algorithm performed as the fastest approach over all benchmarks: Erd{\"o}s–R{\'e}nyi (a), Barab{\'a}si–Albert (b), Forest-Fire (c), and PPI (d). The cases in which the execution times of RI and RI-DS are comparable are reported as RI/RI-DS. RI in red, Fig. 6 Number of instances, expressed as percentages with respect to the total amount of tests, that one algorithm performed as the fastest approach over the PPI benchmark. The cases in which the execution times of RI and RI-DS are equal are reported as RI/RI-DS. RI in red, RI-DS in green, RI/RI-DS in blue, and VF3 in purple. Results are grouped by number of distinct target labels (a) and by number of pattern vertices (b). RI is best when there are many vertices in the pattern graph Acknowledgements We would like to thank the authors of algorithm VF3 to have provided the software and for all your support on testing it. R. G., V. B., and A. A. would like to acknowledge the support of the Italian Ministry of Education, Universities and Research RI-DS in green, RI/RI-DS in blue, and VF3 in purple. The results are grouped by number of vertices in the target graph. RI or RI/RI-DS tends to be the best when there are many vertices. For few vertices, RI-DS is best (MIUR) “Dipartimenti di Eccellenza 2018-2022”, and Regione del Veneto, Regione del Veneto (IT) (Grants 2016-JPVR16FNCL, 2017-B33C17000440003, GNCS-INDAM). A. P., G. M., and A. F. acknowledge the support of Italian Ministry of Education, Universities and Funding Information: We would like to thank the authors of algorithm VF3 to have provided the software and for all your support on testing it. R. G., V. B., and A. A. would like to acknowledge the support of the Italian Ministry of Education, Universities and Research (MIUR) “Dipartimenti di Eccellenza 2018-2022”, and Regione del Veneto, Regione del Veneto (IT) (Grants 2016-JPVR16FNCL, 2017-B33C17000440003, GNCS-INDAM). A. P., G. M., and A. F. acknowledge the support of Italian Ministry of Education, Universities and Research (Ministero dell{\textquoteright}Istruzione, dell{\textquoteright}Universit{\`a} e della Ricerca, MIUR) Grant SCN_00451. D. S. would like to acknowledge the support of the U.S. National Science Foundation Grants MCB-1158273, IOS-1339362, and MCB-1412232. Funding Information: Research (Ministero dell{\textquoteright}Istruzione, dell{\textquoteright}Universit{\`a} e della Ricerca, MIUR) Grant SCN_00451. D. S. would like to acknowledge the support of the U.S. National Science Foundation Grants MCB-1158273, IOS-1339362, and MCB-1412232. Publisher Copyright: {\textcopyright} 2019, International Association of Scientists in the Interdisciplinary Areas.",
year = "2019",
month = mar,
day = "1",
doi = "10.1007/s12539-019-00323-0",
language = "English (US)",
volume = "11",
pages = "21--32",
journal = "Interdisciplinary Sciences - Computational Life Sciences",
issn = "1913-2751",
publisher = "Springer Verlag",
number = "1",
}