PaperlayerView exact revision on arXiv

Source-linked AI summary

CoViG: Coarsened Vision GNN for Image Classification

Martial Guidez, Stefan Duffner, Christophe Garcia

arXiv:2610.21321v1cs.CV

TL;DR

ViGs model image patches and their relationships with graphs, but repeated graph construction and convolution remain computationally costly. CoViG adds MinCUT-based graph coarsening at selected blocks; on ViG-Ti, it can halve computational cost while maintaining baseline accuracy, and one configuration improves accuracy as it reduces FLOPs.

  • Problem

    ViG computation remains costly because every block constructs a k-NN graph and applies a graph convolutional network.

    Source: §1 · p. 1

  • Method

    CoViG integrates MinCUT Pooling into selected ViG blocks to reduce the number of nodes processed by subsequent graph-convolutional blocks.

    Source: §1 · p. 1, §6 · p. 7

  • Results

    74.4% to 75.5% accuracy while FLOPs fall from 1.31G to 1.03G in one ViG-Ti configuration; CoViG also reduces computational cost by approximately half while maintaining baseline accuracy.

    Source: §6 · p. 7

  • Takeaways & Limitations

    Carefully positioned graph coarsening can control graph-reasoning cost while preserving, and in some configurations improving, recognition accuracy.

    Source: §6 · p. 7

Abstract

from arXiv · show

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.

1. Introduction

Vision Graphs model image patches and their relationships with graph neural networks, but graph construction and convolution remain computationally costly. CoViG addresses this with MinCUT-based graph coarsening at selected model blocks.

1. Introduction

  • ViG computation remains costly because each block constructs a k-nearest-neighbor graph by comparing patch embeddings and applies a graph convolutional network.The paper identifies graph construction as the main computational bottleneck.Source: §1 · p. 1
  • CoViG inserts graph coarsening at predetermined blocks, reducing the graph to fewer nodes and lowering the computational cost of subsequent blocks.MinCUT Pooling learns the clustering jointly with the model and task-specific loss.Source: §1 · p. 1
  • The approach adds a differentiable MinCUT-based Coarsened Grapher that can be configured for different pretrained ViG models.Users choose which blocks to reduce and the compression rate for each coarsening step.Source: §1 · p. 2

2. Related Work

This related-work section reviews CNN and ViT compression, graph neural networks for vision, and graph-compression approaches. It positions ViG graph construction and node reduction among these prior methods.

2. Related Work

  • The section frames its review around image-classification architectures and compression methods applied to them.Source: §2 · p. 2

2.1. CNN and ViT

  • CNN compression methods include pruning, knowledge distillation, early exit, and quantization, while ViT-specific approaches include distillation, quantization, reduced-complexity attention, token pruning, and token merging.ViTs’ self-attention scales quadratically with the number of image patches.Source: §2.1 · p. 2

2.2. From GNN to Vision GNN

  • ViGs represent image patches as graph nodes and use a GCN-based backbone, while later methods target graph construction or attention efficiency.ClusterViG partitions the patch grid for parallel local k-NN construction, without changing the node count.Source: §2.2 · pp. 2–3

2.3. Graph compression

  • Graph compression includes sparsification, which removes existing nodes or edges; coarsening, which aggregates nodes into super-nodes; and condensation, which creates a smaller synthetic graph.These approaches aim to make graphs easier to manipulate computationally.Source: §2.3 · p. 3
  • Coarsening methods differ in how they select or group nodes: DiffPool learns soft assignments, Top-K retains selected nodes, SAGPool scores nodes using a GCN, and Graclus matches neighboring nodes.DiffPool’s assignment matrix costs O(N^2) memory; Top-K can create coverage gaps on dense ViG graphs.Source: §2.3 · p. 3

3. Method

CoViG inserts learned MinCUT pooling into ViG blocks to reduce the nodes processed by later graph convolutions. The method builds on ViG’s feature-similarity k-NN graphs and MinCUT’s differentiable soft assignments.

3.1. Vision GNN

  • ViG repeatedly builds feature-similarity k-NN graphs, applies graph convolution and an FFN, then globally pools nodes for classification.The graph is based on feature similarity rather than spatial adjacency.Source: §3.1 · p. 3

3.2. MinCUT Pooling

  • MinCUT learns a soft node-to-cluster assignment using task loss and an unsupervised loss composed of cut and orthogonality terms.The cut term encourages connected nodes to merge, while the orthogonality term discourages assigning all nodes to all clusters.Source: §3.2 · p. 4

3. Method

  • CoViG replaces selected Grapher components with coarsened Graphers that reduce node counts, lowering the computation passed to subsequent blocks.The approach keeps ViG’s depth and feature dimensionality unchanged.Source: §3.3 · p. 4

3.3. CoViG architecture

  • CoViG sets coarsening positions with Cstart and Cstep, and coarsening strength with Cr and a minimum node threshold, NT.At each coarsened Grapher, MinCUT pools node features using Xcoarse = XS before graph convolutions; the residual connection is removed in that block.Source: §3.3 · pp. 4–5

4. Experiments

Experiments use ImageNet and pretrained ViG models to assess coarsened variants. The setup measures classification accuracy, computational cost, and latency, while varying coarsening configurations and auxiliary-loss weight.

Dataset and metrics

  • Experiments use ImageNet’s 1.2M training and 50K validation images across 1,000 classes.Top-1 accuracy is the primary evaluation metric.Source: §4 · p. 5

Training and ablations

  • Coarsened models are trained for 150 epochs from pretrained models, using batch size 128, AdamW, and a 10^-4 learning rate.The experiments vary coarsening position, ratio, repetition spacing, and ωu; most settings use ωu = 0.1.Source: §4 · p. 5

Computational evaluation

  • FLOPs are reported using a 1 FLOP = 1 MAC conversion, and latency is averaged over 200 images on one NVIDIA A100 GPU.Latency measurements use batch size 1 after a 20-image warm-up.Source: §4 · p. 5

5. Results

Coarsening improves the compute–accuracy trade-off in ViG-Ti, while repeated reductions hurt accuracy and larger ViG-S models show greater sensitivity. The results also suggest that delaying coarsening allows more meaningful graph aggregation.

Single coarsening configurations

  • Cstart = 6 with Cr = 0.5 gains one accuracy point at 78% of the reference computational cost, while Cstart = 3 with Cr = 0.25 halves cost at baseline accuracy.Most tested single-coarsening configurations match or outperform baseline accuracy; MinCUT Pooling adds 0.5% parameters.Source: §5 · p. 5, Table 1 · p. 5

Assignment quality by coarsening depth

  • Block 0 produces near-hard assignments with confidence up to 0.9, whereas block 6 assignments are softer, peaking at 0.35, and aggregate patches across clusters.The authors interpret later coarsening as aggregating nodes after more meaningful global relationships develop, consistent with its better accuracy–efficiency trade-off.Source: §5 · p. 6, Figure 5 · p. 6

Multiple coarsening configurations

  • Repeated coarsening reduces node count and computational cost but degrades accuracy; at the same cost, the first Table 2 model achieves only 7% accuracy versus 75.5% for CoViG-Ti-6-0.5.A single reduction retains full-resolution graph reasoning in earlier layers before reducing graph size.Source: §5 · pp. 6–7, Table 2 · p. 6

Larger ViG-S model

  • For ViG-S, tested configurations reduce FLOPs by 22.5 to 33.9% while lowering accuracy by 1.9 to 2.8 accuracy points.The reported trade-off is less favorable than for ViG-Ti, though computational reduction remains meaningful.Source: §5 · p. 7, Table 3 · p. 7

Comparison with other isotropic ViG methods

  • CoViG-Ti-6-0.5 achieves the best accuracy among the compared isotropic ViG models with less computation, while CoViG-3-0.25 is half their size at the same accuracy.The authors report that a less aggressive setting can even improve classification performance.Source: §5 · p. 7, Table 4 · p. 7

6. Conclusion

CoViG uses graph coarsening to reduce the computational cost of ViG while preserving classification performance. On ImageNet, carefully positioned coarsening can cut cost substantially, though repeated or aggressive reduction can hurt accuracy.

6. Conclusion

  • CoViG progressively reduces visual tokens for later graph-convolution blocks while retaining the ViG architecture's original depth and feature dimensionality.The authors suggest future work on adaptive coarsening and extension to other graph-based vision architectures, including pyramid ViG.Source: §6 · p. 7
  • For ViG-Ti, a less aggressive CoViG configuration raises accuracy from 74.4% to 75.5% while reducing FLOPs from 1.31G to 1.03G.The experiments also report approximately halved computational cost while maintaining baseline accuracy.Source: §6 · p. 7
  • Coarsening effectiveness depends strongly on Grapher position: applying it too early can discard spatial information before high-level representations form.Delaying coarsening lets the network perform graph reasoning at full resolution before aggregating visual tokens.Source: §6 · p. 7
  • Repeated coarsening is less effective than one appropriately placed operation, as multiple stages can discard discriminative information and substantially degrade accuracy.The larger ViG-S experiments support generality but also show greater sensitivity to aggressive node reduction in larger models.Source: §6 · p. 7

Related papers

Loading 2610.21321v1…