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

arXiv: https://arxiv.org/abs/2604.21290 · HTML: https://mlsanity.com/paper/2604.21290/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 33 of its 51 references that are in the map.
- First posted on arXiv 23 Apr 2026.

## Builds on (most cited first, 30 of 33)

- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Vision Mamba: Efficient Visual Representation Learning with Bidirectional State Space Model](https://mlsanity.com/paper/2401.09417/) (2024)
- [Do Vision Transformers See Like Convolutional Neural Networks?](https://mlsanity.com/paper/2108.08810/) (2021)
- [DeepGCNs: Can GCNs Go as Deep as CNNs?](https://mlsanity.com/paper/1904.03751/) (2019)
- [Vision GNN: An Image is Worth Graph of Nodes](https://mlsanity.com/paper/2206.00272/) (2022)
- [HyGCN: A GCN Accelerator with Hybrid Architecture](https://mlsanity.com/paper/2001.02514/) (2020)
- [Accelerating Large Scale Real-Time GNN Inference using Channel Pruning](https://mlsanity.com/paper/2105.04528/) (2021)
- [MobileViG: Graph-Based Sparse Attention for Mobile Vision Applications](https://mlsanity.com/paper/2307.00395/) (2023)
- [Bi-GCN: Binary Graph Convolutional Network](https://mlsanity.com/paper/2010.07565/) (2020)
- [Early-Bird GCNs: Graph-Network Co-Optimization Towards More Efficient GCN Training and Inference via Drawing Early-Bird Lottery Tickets](https://mlsanity.com/paper/2103.00794/) (2021)
- [GreedyViG: Dynamic Axial Graph Construction for Efficient Vision GNNs](https://mlsanity.com/paper/2405.06849/) (2024)
- [A Survey on Graph Neural Network Acceleration: Algorithms, Systems, and Customized Hardware](https://mlsanity.com/paper/2306.14052/) (2023)
- [EvGNN: An Event-driven Graph Neural Network Accelerator for Edge Vision](https://mlsanity.com/paper/2404.19489/) (2024)
- [PEANO-ViT: Power-Efficient Approximations of Non-Linearities in Vision Transformers](https://mlsanity.com/paper/2406.14854/) (2024)
- [PVG: Progressive Vision Graph for Vision Recognition](https://mlsanity.com/paper/2308.00574/) (2023)
- [MaGNAS: A Mapping-Aware Graph Neural Architecture Search Framework for Heterogeneous MPSoC Deployment](https://mlsanity.com/paper/2307.08065/) (2023)
- [Scaling Graph Convolutions for Mobile Vision](https://mlsanity.com/paper/2406.05850/) (2024)
- [WiGNet: Windowed Vision Graph Neural Network](https://mlsanity.com/paper/2410.00807/) (2024)
- [GraphAGILE: An FPGA-based Overlay Accelerator for Low-latency GNN Inference](https://mlsanity.com/paper/2302.01769/) (2023)
- [A survey on FPGA-based accelerator for ML models](https://mlsanity.com/paper/2412.15666/) (2024)
- [ClusterViG: Efficient Globally Aware Vision GNNs via Image Partitioning](https://mlsanity.com/paper/2501.10640/) (2025)
- [DVHGNN: Multi-Scale Dilated Vision HGNN for Efficient Vision Recognition](https://mlsanity.com/paper/2503.14867/) (2025)
- [BitGNN: Unleashing the Performance Potential of Binary Graph Neural Networks on GPUs](https://mlsanity.com/paper/2305.02522/) (2023)
- [MEGA: A Memory-Efficient GNN Accelerator Exploiting Degree-Aware Mixed-Precision Quantization](https://mlsanity.com/paper/2311.09775/) (2023)
- [UbiMoE: A Ubiquitous Mixture-of-Experts Vision Transformer Accelerator With Hybrid Computation Pattern on FPGA](https://mlsanity.com/paper/2502.05602/) (2025)
- [AdaptViG: Adaptive Vision GNN with Exponential Decay Gating](https://mlsanity.com/paper/2511.09942/) (2025)

## Abstract (arXiv)

Vision Graph Neural Networks (ViGs) represent 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, scaling as O(N2) with the number of patches N, and creating a sequential dependency between graph construction and feature updates. We introduce GraphLeap, a simple reformulation that removes this dependency by decoupling graph construction from feature update across layers. GraphLeap performs the feature update at layer ℓ using a graph built 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 graph construction enables concurrent graph construction and message passing. Although using prior-layer features can introduce minor accuracy degradation, lightweight fine-tuning for a few epochs is sufficient to recover the original accuracy. Building on GraphLeap, we present the first end-to-end FPGA accelerator for Vision GNNs. Our streaming, layer-pipelined design 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 edge-feature materialization. Evaluated on isotropic and pyramidal ViG models on an Alveo U280 FPGA, GraphLeap achieves up to 95.7× speedup over CPU and 8.5× speedup over GPU baselines, demonstrating the feasibility of real-time Vision GNN inference.