VF-GPU: Exploiting Parallel GPU Architectures to Solve Subgraph Isomorphism

Subgraph isomorphism is a challenging problem involving the search for structural patterns in graphs. It has numerous applications across various fields, and many specialized algorithms have been proposed. However, existing sequential algorithms struggle with extremely large and sparse graphs, particularly when the pattern size is very small with respect to the target graph. Recently, GPU-based approaches have been introduced to address this issue; but, while they are highly effective at exploiting GPU parallelism, these methods are also memory-intensive. In this paper, we present VF-GPU, a novel hybrid algorithm that leverages both CPU and GPU architectures to efficiently solve the subgraph isomorphism problem. Our approach is based on a state space representation (SSR) and employs a limited breadth-first search (BFS) strategy to constrain state generation during exploration. This enables efficient parallelism while controlling memory usage. We evaluated VF-GPU against VF3, VF3-L, and the GPU-based GSI algorithm. The experiments, conducted on a large sparse graph with over 300,000 nodes, demonstrate the effectiveness of our method across different query sizes and label distributions.