GraphLeap: Decoupling Graph Construction and Convolution for Vision GNN Acceleration on FPGA
Anvitha Ramachandran, Dhruv Parikh, Viktor Prasanna · 2026
Read GraphLeap: Decoupling Graph Construction and Convolution for Vision GNN Acceleration on FPGA by Anvitha Ramachandran, Dhruv Parikh, Viktor Prasanna (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-21290.txt.
Introduction
Anvitha Ramachandran, Dhruv Parikh, and Viktor Prasanna remove the main bottleneck in vision graph networks. Rebuilding the patch graph each layer eats 50 to 95 percent of convolution time on CPUs and GPUs. Their GraphLeap reformulation updates features with the previous layer's graph while building the next layer's graph at the same time, enabling concurrent construction and message passing. Light fine-tuning recovers any lost accuracy. A streaming FPGA design then hits up to 95.7 times CPU speed and more than 8 times GPU speed.
Catalog record
| CREATOR | Anvitha Ramachandran, Dhruv Parikh, Viktor Prasanna |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 41069 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.21290
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
GraphLeap: Decoupling Graph Construction and Convolution for Vision GNN Acceleration on FPGA Anvitha Ramachandran, Dhruv Parikh, Viktor Prasanna Abstract 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 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 ( N 2 ) O(N^{2}) where N 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 ℓ \ell 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 \ell{+}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 × 95.7\times speedup over CPU and 8.5 × 8.5\times 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 . I Introduction Modern computer vision backbones span Convolutional Neural Networks (CNNs), Vision Transformers (ViTs), state-space based vision models, and Vision Graph Neural Networks (ViGs). CNNs apply convolutional filters on grid-structured feature maps to exploit locality [ 19 , 17 ] . ViTs treat image patches as tokens and use self-attention to capture long-range interactions, at the cost of quadratic complexity in the number of tokens [ 5 , 33 ] . More recently, state-space based vision models (e.g., Vision Mamba) trade explicit pairwise attention for selective scan style sequence modeling [ 9 , 49 ] . ViGs depart from grids and sequences by representing an image as a graph of patch tokens whose edges encode feature-driven patch relationships; critically, this graph is reconstructed across layers to adapt neighborhoods to evolving features [ 11 ] . This flexibility allows ViGs to achieve competitive accuracy with favorable compute efficiency compared to similarly sized ViTs, making them suitable for resource-constrained settings [ 27 , 12 ] . Dynamic graph construction remains a major bottleneck for real-time ViG deployment. Prior methods reduce its cost via clustering, windowing, or approximate neighborhoods [ 32 , 37 , 1 , 29 , 6 , 30 , 27 , 12 , 20 , 41 , 45 , 28 ] , but still enforce per-layer dependencies and often compromise the dynamic, feature-driven graphs central to ViGs. Most GNN accelerators target large static graphs, while vision accelerators focus on CNN/ViT/state-space operators, leaving dynamic image graph construction and full ViG pipelines largely unsupported. Motivated by these limitations, we ask: can dynamic graph construction be decoupled from graph convolution in ViGs? We introduce GraphLeap , which updates features at layer \ell using the previous layer’s graph while concurrently constructing the graph for layer \ell+1 from current features. This one-layer lookahead enables overlapping graph construction and convolution, reducing inference latency. We show that any minor accuracy loss from using prior-layer graphs can be recovered with lightweight fine-tuning. Building on GraphLeap, we present the first end-to-end FPGA accelerator for Vision GNN inference. Our design is a streaming, layer-pipelined architecture that overlaps a kNN-based graph construction engine with a feature update engine, exploits node- and channel-level parallelism, and supports ViG graph convolution efficiently in hardware. Our contributions are: • GraphLeap Vision GNNs. We propose GraphLeap, a general algorithmic reformulation that decouples dynamic graph construction from graph convolution by constructing the graph for layer \ell{+}1 while updating features for layer \ell , and we validate its effectiveness across standard isotropic and pyramidal ViG backbones. • End-to-end FPGA accelerator. We develop the first end-to-end FPGA accelerator for ViG inference based on GraphLeap, implementing a streaming pipeline that overlaps graph construction and feature update across layers to reduce end-to-end latency. • Streaming kNN graph construction. We design a high-throughput dynamic graph construction engine for dilated kNN image graphs that concurrently operates one layer ahead of feature update and streams neighbor indices to the compute pipeline. • Efficient feature-update pipeline. We design a hardware feature-update engine specialized for ViGs, including a shared systolic MLP compute fabric reused across graph convolution and Feed Forward Network (FFN) stages via streaming buffers. • Evaluation. We demonstrate the effectiveness of the GraphLeap architecture on an AMD-Xilinx Alveo U280 FPGA across various isotropic and pyramidal ViG variants. Our results show significant end-to-end performance gains, achieving up to 95.7 \times speedup over CPU and 8.5 \times over GPU. • Comparison to ViT Accelerators. We compare the latency of our accelerator with recent ViT accelerators. Compared to state-of-the-art ViT accelerators on similar FPGA platforms, our accelerator achieves an end-to-end latency that is 3\times faster with a comparable accuracy. II Challenges and Key Innovations II-A Preliminaries: Graph Neural Networks Graph Neural Networks A graph is denoted as \mathcal{G}=(\mathcal{V},\mathcal{E}) , where \mathcal{V} is the node set and \mathcal{E} is the edge set. Let N=|\mathcal{V}| and node features be stacked as \mathbf{X}\in\mathbb{R}^{N\times D} , where \mathbf{x}_{i}\in\mathbb{R}^{D} is the feature of node v_{i} . Most GNNs can be expressed in the message-passing form: each layer aggregates neighbor information and then updates node states (features) [ 8 , 36 , 7 , 16 , 10 ] . Concretely, with neighbor set \mathcal{N}(i) (induced by \mathcal{E} ), a generic layer is \mathbf{x}_{i}^{\prime}=\mathrm{Upd}\!\Big(\mathbf{x}_{i},\ \mathrm{Agg}\big(\{\mathbf{x}_{j}:j\in\mathcal{N}(i)\}\big)\Big), (1) where \mathrm{Agg}(\cdot) is a permutation-invariant operator (e.g., sum/mean/max), and \mathrm{Upd}(\cdot) is typically a linear layer or an MLP. Max-Relative Graph Convolution (MRConv) Following [ 21 , 11 ] , we focus on max-relative aggregation, which is simple and efficient: \displaystyle\mathbf{x}_{i}^{\prime\prime} \displaystyle=\Big[\,\mathbf{x}_{i},\ \max_{j\in\mathcal{N}(i)}(\mathbf{x}_{j}-\mathbf{x}_{i})\,\Big]\in\mathbb{R}^{2D}, (2) \displaystyle\mathbf{x}_{i}^{\prime} \displaystyle=\mathbf{x}_{i}^{\prime\prime}\mathbf{W}_{\mathrm{upd}}, (3) where \mathbf{W}_{\mathrm{upd}}\in\mathbb{R}^{2D\times D} (bias omitted). In practice, ViG further adopts a multi-head update: split \mathbf{x}_{i}^{\prime\prime} into h heads and apply per-head weights, then concatenate the results [ 11 ] . II-B ViG: Dynamic Graph Convolution over Image Patches Image-to-graph representation ViG represents an image as a graph over non-overlapping patches [ 11 ] . Let an image be divided into N patches, each mapped to a node feature, yielding \mathbf{X}\in\mathbb{R}^{N\times D} . A dynamic image graph is constructed by connecting each node to its K nearest neighbors in feature space: \mathcal{G}=G(\mathbf{X}),\qquad\mathcal{G}=(\mathcal{V},\mathcal{E}),\quad\mathcal{N}(i)\ \text{derived from}\ \mathcal{E}. (4) Unlike typical GNN settings with static graphs, ViG reconstructs the graph at each layer using the current