TY - JOUR
T1 - Fast Subgraph Matching Strategies Based on Pattern-Only Heuristics
AU - Aparo, Antonino
AU - Bonnici, Vincenzo
AU - Micale, Giovanni
AU - Ferro, Alfredo
AU - Shasha, Dennis
AU - Pulvirenti, Alfredo
AU - Giugno, Rosalba
N1 - 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ös–Rényi (a), Barabá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’Istruzione, dell’Università 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’Istruzione, dell’Università 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:
© 2019, International Association of Scientists in the Interdisciplinary Areas.
PY - 2019/3/1
Y1 - 2019/3/1
N2 - 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.
AB - 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.
KW - Networks biology
KW - Search strategy
KW - Subgraph isomorphism
UR - http://www.scopus.com/inward/record.url?scp=85062723243&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85062723243&partnerID=8YFLogxK
U2 - 10.1007/s12539-019-00323-0
DO - 10.1007/s12539-019-00323-0
M3 - Article
C2 - 30790228
AN - SCOPUS:85062723243
VL - 11
SP - 21
EP - 32
JO - Interdisciplinary sciences, computational life sciences
JF - Interdisciplinary sciences, computational life sciences
SN - 1913-2751
IS - 1
ER -