Low-Power Subgraph Isomorphism at the Edge Using FPGAs

Subgraph matching is a significant problem in several fields, including like social network analysis, chemical compound search, and fraud detection. While current solutions using CPU, graphics processing units (GPUs), and data center field-programmable gate arrays (FPGAs) deliver high performance, they consume significant power, making them unsuitable for resource-constrained edge environments. This article introduces a novel low-power FPGA accelerator that enables efficient subgraph matching using a small FPGA-based accelerator through three main innovations: a flexible two-level hash table architecture that minimizes memory accesses, a caching mechanism that reduces on-chip memory requirements, and a dynamic first-in first-out (FIFO) queue that efficiently buffers partial results. Experimental results on five real-world graphs show that the accelerator reduces energy consumption by an average of 75× compared to state-of-the-art CPU solutions, and 107× compared to GPU solutions, demonstrating that complex graph operations can be performed efficiently using even a small accelerator implemented on a reconfigurable platform.