Quick Mining of Isomorphic Exact Large Patterns from Large Graphs

Islam Almasri, Xin Gao, Nina V. Fedoroff

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations

Abstract

The applications of the sub graph isomorphism search are growing with the growing number of areas that model their systems using graphs or networks. Specifically, many biological systems, such as protein interaction networks, molecular structures and protein contact maps, are modeled as graphs. The sub graph isomorphism search is concerned with finding all sub graphs that are isomorphic to a relevant query graph, the existence of such sub graphs can reflect on the characteristics of the modeled system. The most computationally expensive step in the search for isomorphic sub graphs is the backtracking algorithm that traverses the nodes of the target graph. In this paper, we propose a pruning approach that is inspired by the minimum remaining value heuristic that achieves greater scalability over large query and target graphs. Our testing on various biological networks shows that performance enhancement of our approach over existing state-of-the-art approaches varies between 6x and 53x. © 2014 IEEE.
Original languageEnglish (US)
Title of host publication2014 IEEE International Conference on Data Mining Workshop
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages517-524
Number of pages8
ISBN (Print)9781479942749
DOIs
StatePublished - Dec 2014

Fingerprint

Dive into the research topics of 'Quick Mining of Isomorphic Exact Large Patterns from Large Graphs'. Together they form a unique fingerprint.

Cite this