An Efficient Index-Based Algorithm for Exact Subgraph Isomorphism on Bipartite Graphs

Abstract

Graphs are widely used to represent various real-world networks, but their non-linear nature and size increase pose challenges for efficient analysis. The subgraph isomorphism problem, which involves identifying subgraphs that are isomorphic to a query graph, plays a crucial role in diverse domains. In this paper, we focus on the exact subgraph isomorphism problem in bipartite graphs and propose a novel index-based solution algorithm. Our algorithm leverages triplet structures for graph embedding and uses a multi-level hash map for efficient filtering. We also introduce an optimized solution building process. Experimental results on real-world datasets demonstrate the performance superiority of our algorithm compared to state-of-the-art algorithms, with 2 to 500 times shorter querying times. Our findings suggest that our algorithm is a powerful and efficient solution for exact subgraph isomorphism in bipartite graphs.