GraphLeap: Decoupling Graph Construction and Convolution for Vision GNN Acceleration on FPGA

Vision Graph Neural Networks (ViGs) model an image as a graph of patch tokens, enabling adaptive, feature-driven neighborhoods. Unlike CNNs with fixed grid biases or Vision Transformers with global token interactions, ViGs rely on dynamic graph convolution: at each layer, a feature-dependent graph is built via k-nearest neighbor (kNN) search on current patch features, followed by message passing. This per-layer graph construction is the main bottleneck—consuming 50–95% of graph convolution time on CPUs and GPUs—and scales by O(N2) where N is the number of patches, creating a sequential dependency between graph construction and feature updates.In this paper, we introduce GraphLeap, a simple yet novel reformulation that removes this dependency by decoupling graph construction from feature update across layers. GraphLeap performs the feature update at layer ℓ using a graph constructed from the previous layer’s features, while simultaneously using the current layer’s features to construct the graph for layer ℓ+1. This one-layer lookahead dynamic graph construction enables concurrent graph construction and GNN message passing, yielding a new class of ViGs, which we call GraphLeap. While using prior-layer features for graph construction can introduce minor accuracy degradation, we show that lightweight fine-tuning for a few epochs is sufficient to recover original accuracy. Building on GraphLeap, we present the first end-to-end FPGA accelerator for Vision GNNs. Our design is a streaming, layer-pipelined architecture that overlaps a kNN graph construction engine with a feature update engine, exploits node and channel-level parallelism, and enables efficient on-chip dataflow without explicit materialization of edge features. Evaluated on isotropic and pyramidal ViG models deployed on an Alveo U280 FPGA, our approach achieves up to 95.7× speedup over CPU and 8.5× speedup over GPU baselines, demonstrating the feasibility of real-time Vision GNN inference and motivating future hardware– algorithm co-design for graph-based vision models. Code is available at https://github.com/anvitha305/GraphLeap.