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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

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

  • Vincenzo Carletti,
  • Pasquale Foggia,
  • Francesco Rosa,
  • Mario Vento

摘要

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.