Simple pattern-only heuristics lead to fast subgraph matching strategies on very large networks

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

doi:10.1007/978-3-319-98702-6_16

Simple pattern-only heuristics lead to fast subgraph matching strategies on very large networks

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

A wide range of biomedical applications entails solving the subgraph isomorphism problem, i.e. finding 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-the-art 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 efficient, an unexpected result.

Original language	English (US)
Title of host publication	Practical Applications of Computational Biology and Bioinformatics, 12th International Conference
Editors	Miguel Rocha, Mohd Saberi Mohamad, Juan F. De Paz, Florentino Fdez-Riverola, Pascual Gonzalez
Publisher	Springer Verlag
Pages	131-138
Number of pages	8
ISBN (Print)	9783319987019
DOIs	https://doi.org/10.1007/978-3-319-98702-6_16
State	Published - 2019
Event	12th International Conference on Practical Applications of Computational Biology and Bioinformatics, PACBB 2018 - Toledo, Spain Duration: Jun 20 2018 → Jun 22 2018

Publication series

Name	Advances in Intelligent Systems and Computing
Volume	803
ISSN (Print)	2194-5357

Other

Other	12th International Conference on Practical Applications of Computational Biology and Bioinformatics, PACBB 2018
Country/Territory	Spain
City	Toledo
Period	6/20/18 → 6/22/18

Keywords

Networks biology
Search strategy
Subgraph isomorphism

ASJC Scopus subject areas

Control and Systems Engineering
General Computer Science

Access to Document

10.1007/978-3-319-98702-6_16

Cite this

Aparo, A., Bonnici, V., Micale, G., Ferro, A., Shasha, D., Pulvirenti, A., & Giugno, R. (2019). Simple pattern-only heuristics lead to fast subgraph matching strategies on very large networks. In M. Rocha, M. S. Mohamad, J. F. De Paz, F. Fdez-Riverola, & P. Gonzalez (Eds.), Practical Applications of Computational Biology and Bioinformatics, 12th International Conference (pp. 131-138). (Advances in Intelligent Systems and Computing; Vol. 803). Springer Verlag. https://doi.org/10.1007/978-3-319-98702-6_16

Simple pattern-only heuristics lead to fast subgraph matching strategies on very large networks. / Aparo, Antonino; Bonnici, Vincenzo; Micale, Giovanni et al.
Practical Applications of Computational Biology and Bioinformatics, 12th International Conference. ed. / Miguel Rocha; Mohd Saberi Mohamad; Juan F. De Paz; Florentino Fdez-Riverola; Pascual Gonzalez. Springer Verlag, 2019. p. 131-138 (Advances in Intelligent Systems and Computing; Vol. 803).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Aparo, A, Bonnici, V, Micale, G, Ferro, A, Shasha, D, Pulvirenti, A & Giugno, R 2019, Simple pattern-only heuristics lead to fast subgraph matching strategies on very large networks. in M Rocha, MS Mohamad, JF De Paz, F Fdez-Riverola & P Gonzalez (eds), Practical Applications of Computational Biology and Bioinformatics, 12th International Conference. Advances in Intelligent Systems and Computing, vol. 803, Springer Verlag, pp. 131-138, 12th International Conference on Practical Applications of Computational Biology and Bioinformatics, PACBB 2018, Toledo, Spain, 6/20/18. https://doi.org/10.1007/978-3-319-98702-6_16

Aparo A, Bonnici V, Micale G, Ferro A, Shasha D, Pulvirenti A et al. Simple pattern-only heuristics lead to fast subgraph matching strategies on very large networks. In Rocha M, Mohamad MS, De Paz JF, Fdez-Riverola F, Gonzalez P, editors, Practical Applications of Computational Biology and Bioinformatics, 12th International Conference. Springer Verlag. 2019. p. 131-138. (Advances in Intelligent Systems and Computing). doi: 10.1007/978-3-319-98702-6_16

Aparo, Antonino ; Bonnici, Vincenzo ; Micale, Giovanni et al. / Simple pattern-only heuristics lead to fast subgraph matching strategies on very large networks. Practical Applications of Computational Biology and Bioinformatics, 12th International Conference. editor / Miguel Rocha ; Mohd Saberi Mohamad ; Juan F. De Paz ; Florentino Fdez-Riverola ; Pascual Gonzalez. Springer Verlag, 2019. pp. 131-138 (Advances in Intelligent Systems and Computing).

@inproceedings{762d456b522a4784b29d03b2910477cf,

title = "Simple pattern-only heuristics lead to fast subgraph matching strategies on very large networks",

abstract = "A wide range of biomedical applications entails solving the subgraph isomorphism problem, i.e. finding 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-the-art 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 efficient, an unexpected result.",

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

doi = "10.1007/978-3-319-98702-6_16",

language = "English (US)",

isbn = "9783319987019",

series = "Advances in Intelligent Systems and Computing",

publisher = "Springer Verlag",

pages = "131--138",

editor = "Miguel Rocha and Mohamad, {Mohd Saberi} and {De Paz}, {Juan F.} and Florentino Fdez-Riverola and Pascual Gonzalez",

booktitle = "Practical Applications of Computational Biology and Bioinformatics, 12th International Conference",

note = "12th International Conference on Practical Applications of Computational Biology and Bioinformatics, PACBB 2018 ; Conference date: 20-06-2018 Through 22-06-2018",

}

TY - GEN

T1 - Simple pattern-only heuristics lead to fast subgraph matching strategies on very large networks

AU - Aparo, Antonino

AU - Bonnici, Vincenzo

AU - Micale, Giovanni

AU - Ferro, Alfredo

AU - Shasha, Dennis

AU - Pulvirenti, Alfredo

AU - Giugno, Rosalba

PY - 2019

Y1 - 2019

N2 - A wide range of biomedical applications entails solving the subgraph isomorphism problem, i.e. finding 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-the-art 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 efficient, an unexpected result.

AB - A wide range of biomedical applications entails solving the subgraph isomorphism problem, i.e. finding 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-the-art 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 efficient, an unexpected result.

KW - Networks biology

KW - Search strategy

KW - Subgraph isomorphism

UR - http://www.scopus.com/inward/record.url?scp=85052968753&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85052968753&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-98702-6_16

DO - 10.1007/978-3-319-98702-6_16

M3 - Conference contribution

AN - SCOPUS:85052968753

SN - 9783319987019

T3 - Advances in Intelligent Systems and Computing

SP - 131

EP - 138

BT - Practical Applications of Computational Biology and Bioinformatics, 12th International Conference

A2 - Rocha, Miguel

A2 - Mohamad, Mohd Saberi

A2 - De Paz, Juan F.

A2 - Fdez-Riverola, Florentino

A2 - Gonzalez, Pascual

PB - Springer Verlag

T2 - 12th International Conference on Practical Applications of Computational Biology and Bioinformatics, PACBB 2018

Y2 - 20 June 2018 through 22 June 2018

ER -

Simple pattern-only heuristics lead to fast subgraph matching strategies on very large networks

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this