An Efficient Subgraph Isomorphism Solver for Large Graphs
oleh: Zubair Ali Ansari, Jahiruddin, Muhammad Abulaish
| Format: | Article |
|---|---|
| Diterbitkan: | IEEE 2021-01-01 |
Deskripsi
For a given pair of pattern and data graphs, the subgraph isomorphism finding problem locates all instances of the pattern graph into the data graph. For a given subgraph isomorphic image of the pattern graph in a data graph, the set of all ordered pairs of the pattern graph’s vertices and their respective images data graph is called an embedding. Many solvers, such as <inline-formula> <tex-math notation="LaTeX">$\mathrm {Turbo_{ISO}}$ </tex-math></inline-formula>, <monospace>Glasgow</monospace>, and <monospace>VF3</monospace> exist in the literature for subgraph isomorphism finding problem. Though each solver aims to minimize computing costs in its own way, computational efficiency is still a central issue for the subgraph isomorphism finding problem. In this paper, we present the development of an efficient solver, <monospace>SubGlw</monospace>, for subgraph isomorphism finding which first decomposes data graph into small-size candidate subgraphs using a ranking function and then searches the embeddings of the pattern graph in each of them separately. The ranking function is designed in such a way that it minimizes both number and size of the candidate subgraphs. The performance of <monospace>SubGlw</monospace> is empirically evaluated and compared with two state-of-the-art subgraph isomorphism solvers – <monospace>SubISO</monospace> and <monospace>Glasgow</monospace> over three benchmark datasets – <monospace>Yeast</monospace>, <monospace>Human</monospace>, and <monospace>Hprd</monospace>. The experimental findings reveal that <monospace>SubGlw</monospace> performs significantly better in terms of both <italic>embedding count</italic> and <italic>execution time</italic>. We have also presented an analysis for identifying <italic>saddle point</italic>, which is a timeout at which our solver achieves maximum embeddings in least execution time. This analysis provides a better understanding for parameter settings. The source codes of <monospace>SubGlw</monospace> can be downloaded from <uri>https://github.com/ZubairAliIgraph/SubGlw-master</uri>.