CoViG: Coarsened Vision GNN for Image Classification

Martial Guidez; Stefan Duffner; Christophe Garcia

cs.CVOct 15, 2026

CoViG: Coarsened Vision GNN for Image Classification

Authors: Martial Guidez, Stefan Duffner, Christophe Garcia

Organizations: INSA Lyon, CNRS, Universit´e Claude Bernard Lyon 1, LIRIS, UMR5205, 69621 Villeurbanne, France

Abstract

Although Graph Neural Networks are widely used in various domains, they remained mostly unexplored in computer vision. Convolutional Neural Networks and Vision Transformers were leading the field, until the quite recent introduction of Vision Graphs (ViG) that treat images as a set of nodes and apply graph convolution on their k-NN graphs. ViGs show impressive accuracy on image classification but their computational cost remains relatively high. Inspired by optimization methods for GNNs, we present CoViG, a novel approach combining graph coarsening and ViGs. Our method introduces an additional MinCUT pooling step within the Grapher component of intermediate ViG blocks. By simplifying the intermediate graphs and thus decreasing the number of nodes of specific blocks, our approach considerably reduces the computational cost of ViG during inference. We evaluated our approach on ImageNet with several ViG architectures, and we obtained accuracies equivalent to the original ViG models with only about 51% of FLOPs.

Figures & tables

Figure 1: Overview of the CoViG architecture: graph coarsening reduces the node set from $l$ nodes to $j$ super-nodes between two stages of ViG blocks. In this illustration, only a single coarsening step is applied.

Panel of Figure 2 — Figure 2: Comparison of the baseline Grapher block (a) and the proposed coarsened Grapher block (b).

Figure 3: Overview of the Vision Graph Neural Network (ViG) architecture.

Panel of Figure 4 — Figure 4: Visualization of the graph representation learned by the ViG [ 14 ] . From left to right: the input image overlaid with the 14×14 graph nodes, the dynamically constructed k-NN graph based on feature similarity, and a PCA projection of the learned node features into RGB space. Subfigures a) and b) correspond to different backbone blocks, illustrating the evolution of graph connectivity and feature representations throughout the network.

Model	$C_{start}$	$C_{r}$	Params (M)	FLOPs (G)	Latency (ms)	Acc (%)
ViG-Ti	-	-	7.18	1.31	15.22	74.4
CoViG-Ti	6	0.5	7.21	1.03	15.19	75.5
	3	0.5	7.21	0.88	14.64	75.0
	6	0.25	7.21	0.89	15.18	75.1
	5	0.25	7.21	0.82	15.23	74.9
	4	0.25	7.21	0.74	15.08	74.9

Table 1: CoViG-Ti performances under different single coarsening configurations

Panel of Figure 5 — Figure 5: Effect of coarsening depth on MinCUT assignment quality: near-hard spatial assignments at block 0 vs. soft semantic aggregation at block 6.

Model	$C_{start}$	$C_{r}$	$C_{step}$	$N_{T}$	Params (M)	FLOPs (G)	Acc (%)
ViG-Ti	-	-	-	-	7.18	1.31	74.4
CoViG-Ti	3	0.9	1	49	7.45	1.03	7.0
	6	0.9	1	49	7.38	1.19	32.5
	4	0.5	4	49	7.24	0.84	69.7
	6	0.5	3	49	7.24	0.96	71.7

Table 2: CoViG-Ti performances under different multiple coarsening configurations

Model	$C_{start}$	$C_{r}$	Params (M)	FLOPs (G)	Latency (ms)	Acc (%)
ViG-S	-	-	22.7	4.54	20.31	80.6
CoViG-S	8	0.5	22.81	3.52	19.93	78.7
	6	0.5	22.81	3.26	20.65	78.3
	4	0.5	22.81	3.0	20.37	77.8

Table 3: CoViG-S performances under different single coarsening configurations

Model	Params (M)	FLOPs (G)	Acc (%)
ViG-Ti [ 14 ]	7.18	1.31	74.4
SVIG-Ti [ 8 ]	7.2	1.3	74.6
ViHGNN-Ti [ 16 ]	8.2	1.8	74.3
Isotropic ViDR-GNN-Ti [ 49 ]	7.3	1.4	74.6
ViG-LRGC [ 9 ]	8.1	1.5	74.3
CoViG-Ti-6-0.5 (ours)	7.21	1.03	75.5

Table 4: Comparison of our CoViG method with different isotropic ViG-based models.

Graph Neural Networks

Graph Neural Networks learn from graph-structured data by combining information across connected nodes, edges, and larger structures.

See all 714 papers

GraphLeap: Decoupling Graph Construction and Convolution for Vision GNN Acceleration on FPGA
Apr 23, 2026Anvitha Ramachandran, Dhruv Parikh, Viktor PrasannaEfficient Neural Network Inference Dynamic Graph Learning
University of Southern California, Los Angeles, California, USA
AttentionViG: Cross-Attention-Based Dynamic Neighbor Aggregation in Vision GNNs
Sep 29, 2025Hakan Emre Gedik, Andrew Martin, Mustafa Munir +4Graph Attention Networks Cross-Attention
The University of Texas at Austin
Hierarchical Vision Transformer Enhanced by Graph Convolutional Network for Image Classification
Apr 18, 2026Haibin JiaoVision Transformer Hierarchical Representation Learning
Independent Researcher

Apr 23, 2026J/K move · Enter open · S save

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

Anvitha Ramachandran, Dhruv Parikh, Viktor Prasanna

University of Southern California, Los Angeles, California, USA

Efficient Neural Network Inference Dynamic Graph Learning FPGA Acceleration

Open paper AskPDF 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(N^2)

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

\ell

using a graph built from the previous layer's features, while simultaneously using the current layer's features to construct the graph for layer

\ell+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\times

speedup over CPU and

8.5\times

speedup over GPU baselines, demonstrating the feasibility of real-time Vision GNN inference.

Abstract

Graph Neural Networks

Explore similar work

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

AttentionViG: Cross-Attention-Based Dynamic Neighbor Aggregation in Vision GNNs

Hierarchical Vision Transformer Enhanced by Graph Convolutional Network for Image Classification