Fast Subgraph Matching Strategies Based on Pattern-Only Heuristics

Antonino Aparo; Vincenzo Bonnici; Giovanni Micale; Alfredo Ferro; Dennis Shasha; Alfredo Pulvirenti; Rosalba Giugno

doi:10.1007/s12539-019-00323-0

Fast Subgraph Matching Strategies Based on Pattern-Only Heuristics

Antonino Aparo, Vincenzo Bonnici, Giovanni Micale, Alfredo Ferro, Dennis Shasha, Alfredo Pulvirenti, Rosalba Giugno

Computer Science

Research output: Contribution to journal › Article

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.

Original language	English (US)
Pages (from-to)	21-32
Number of pages	12
Journal	Interdisciplinary Sciences: Computational Life Sciences
Volume	11
Issue number	1
DOIs	https://doi.org/10.1007/s12539-019-00323-0
State	Published - Mar 1 2019

Keywords

Networks biology
Search strategy
Subgraph isomorphism

ASJC Scopus subject areas

Biochemistry, Genetics and Molecular Biology(all)
Computer Science Applications
Health Informatics

Access to Document

10.1007/s12539-019-00323-0

Fingerprint Dive into the research topics of 'Fast Subgraph Matching Strategies Based on Pattern-Only Heuristics'. Together they form a unique fingerprint.

Cite this

Aparo, A., Bonnici, V., Micale, G., Ferro, A., Shasha, D., Pulvirenti, A., & Giugno, R. (2019). Fast Subgraph Matching Strategies Based on Pattern-Only Heuristics. Interdisciplinary Sciences: Computational Life Sciences, 11(1), 21-32. https://doi.org/10.1007/s12539-019-00323-0

@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",

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",

}

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

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 -