An Efficient Subgraph Isomorphism Solver for Large Graphs

doi:10.1109/ACCESS.2021.3073494

2021-01-01

Zubair Ali Ansari *

Jahiruddin

Muhammad Abulaish

DOI：10.1109/ACCESS.2021.3073494

原文链接

查看原文

摘要

En 中文

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 Turbo(ISO), Glasgow, and VF3 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, SubGlw, 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 SubGlw is empirically evaluated and compared with two state-of-the-art subgraph isomorphism solvers - SubISO and Glasgow over three benchmark datasets - Yeast, Human, and Hprd. The experimental findings reveal that SubGlw performs significantly better in terms of both embedding count and execution time. We have also presented an analysis for identifying saddle point, 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 SubGlw can be downloaded from https://github.com/ZubairAliIgraph/SubGlw-master.

Keyword:

Graph mining

subgraph isomorphism

subgraph isomorphism solver

eccentricity

embedding

graph decomposition

saddle point