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

Technical Summary: GraphLeap

Problem Statement
Vision Graph Neural Networks (ViGs) represent images as graphs of patch tokens, utilizing dynamic, feature-driven neighborhoods to achieve competitive accuracy with favorable compute efficiency compared to Vision Transformers (ViTs). However, the core mechanism of ViGs—reconstructing a $k$-nearest neighbor ($k$NN) graph at every layer based on current patch features—creates a severe performance bottleneck. This dynamic graph construction consumes 50–95% of the total inference time on CPUs and GPUs and scales quadratically ($O(N^2)$) with the number of patches. Crucially, this process enforces a strict sequential dependency: the graph for layer $\ell$ must be fully constructed before the feature update (convolution) for that layer can begin. This serialization prevents efficient parallelization and hinders real-time deployment. Furthermore, existing hardware accelerators largely target static graphs or regular grid operations (CNNs/ViTs), leaving the specific challenges of dynamic image graph construction and full ViG pipelines unsupported.

Methodology: GraphLeap Reformulation
The authors introduce GraphLeap, a novel algorithmic reformulation that decouples graph construction from feature updates across layers to break the sequential dependency.

• One-Layer Lookahead: Instead of constructing the graph for layer $\ell$ using features from layer $\ell$ (which must wait for the previous layer's update), GraphLeap constructs the graph for layer $\ell+1$ using the features of the current layer $\ell$, while simultaneously performing the feature update for layer $\ell$ using the graph constructed from the previous layer's features ($\ell-1$).
• Algorithmic Shift: In standard ViG, $G^{(\ell)} = G(U^{(\ell)})$. In GraphLeap, the message passing at block $\ell$ uses $\hat{G}^{(\ell)} = G(U^{(\ell-1)})$, while $U^{(\ell)}$ is concurrently used to build $\hat{G}^{(\ell+1)}$.
• Accuracy Recovery: The authors acknowledge that using "stale" graphs (from the previous layer) can introduce minor accuracy degradation. However, they demonstrate that lightweight fine-tuning (30 epochs) is sufficient to recover the original accuracy, often matching or exceeding the baseline ViG performance.

System Architecture: End-to-End FPGA Accelerator
Building on the GraphLeap algorithm, the paper presents the first end-to-end FPGA accelerator for Vision GNNs, implemented on an AMD-Xilinx Alveo U280. The design features a streaming, layer-pipelined architecture that overlaps two primary engines:

1. Graph Construction Engine (GCE): A high-throughput engine that computes dilated $k$NN graphs. It processes node features in tiles, uses a mesh of processing elements (PEs) for pairwise distance computation, and maintains min-heaps to extract neighbors. Crucially, it streams neighbor indices to the next stage without materializing full edge features in off-chip memory.
2. Feature Update Engine (FUE): This engine consumes the streamed graph data and performs the ViG Grapher and Feed-Forward Network (FFN) operations. It includes:
   • Gather Module (GM): Handles irregular memory access patterns via interleaved banking and prefetching to retrieve neighbor features.
   • Graph Convolution Module (GCM): Implements max-relative aggregation and linear transformations using a systolic array, avoiding explicit concatenation of node features and messages.
   • FFN Module (FM): A specialized MLP datapath for per-node updates.

• Dataflow Strategy: The GCE operates one layer ahead of the FUE. This allows the construction of the graph for layer $\ell+1$ to proceed in parallel with the feature update of layer $\ell$. The design avoids explicit materialization of $O(NK)$ edge features, keeping only node features and small line buffers on-chip.

Key Contributions

1. GraphLeap Algorithm: A general reformulation that decouples dynamic graph construction from graph convolution, enabling concurrent execution of graph building and feature updates.
2. First End-to-End ViG Accelerator: The development of a streaming, pipelined FPGA architecture specifically for Vision GNNs, featuring a dedicated $k$NN graph construction engine and a specialized feature update engine.
3. Streaming $k$NN Construction: A high-throughput hardware design for dilated $k$NN image graphs that operates one layer ahead of feature updates, streaming neighbor indices directly to the compute pipeline.
4. Efficient Feature-Update Pipeline: A hardware engine utilizing shared systolic MLP fabrics for both Graph Convolution and FFN stages, connected via streaming buffers to handle mixed irregular and regular workloads.

Experimental Results
The authors evaluated GraphLeap on isotropic (Ti, S, B) and pyramidal (Py-Ti, Py-S, Py-M, Py-B) ViG models deployed on the Alveo U280 FPGA.

• Speedup: The approach achieves up to 95.7× speedup over a 64-core CPU baseline and 8.5× speedup over an NVIDIA RTX A5000 GPU baseline for end-to-end inference.
• Latency: For the ViG-B model at 224×224 resolution, the accelerator achieves an end-to-end latency of 2.77 ms.
• Comparison to SOTA: Compared to state-of-the-art ViT accelerators (DRViT, UbiMoE) on similar FPGA platforms, GraphLeap achieves 3× lower latency with comparable accuracy.
• Accuracy: After fine-tuning, GraphLeap models recover to within 1.4% of the original ViG Top-1 accuracy (e.g., ViG-Py-B reaches 82.34%).

Significance and Claims
The paper claims that GraphLeap demonstrates the feasibility of real-time Vision GNN inference by fundamentally addressing the sequential bottleneck of dynamic graph construction. The authors argue that while the algorithmic reformulation yields only modest gains on conventional CPU/GPU architectures (1.03–1.23×), it unlocks significant performance potential when co-designed with hardware that can exploit the resulting producer-consumer streaming relationship. The work motivates future hardware-algorithm co-design for graph-based vision models, showing that decoupling construction from convolution allows for efficient, low-latency inference without sacrificing the adaptive neighborhood benefits of ViGs.