Multi-Scale High-Resolution Logarithmic Grapher Module for Efficient Vision GNNs

AI summary

Overview

• Research area: Efficient computer vision architectures, specifically Vision Graph Neural Networks (ViGs) and hybrid CNN-GNN models for image classification and semantic segmentation.
• Technical level: Advanced. The paper assumes familiarity with CNNs, Vision Transformers, graph neural networks, graph construction via k-nearest neighbors, over-squashing, and efficiency metrics such as GMACs and parameter counts.
• Scope: The paper introduces Logarithmic Scalable Graph Construction (LSGC) and LogViG, a hybrid CNN-GNN architecture that applies LSGC together with a multi-scale high-resolution branch, and evaluates it against CNN, ViT, and ViG baselines on ImageNet-1K classification and ADE20K semantic segmentation.

What This Paper Is About

Vision GNNs represent an image as a graph of patches rather than as a grid of pixels (CNNs) or a sequence of patches (ViTs), but building that graph is expensive. The standard approach, k-nearest neighbor (KNN), is costly on larger images, while the cheaper static alternative, Sparse Vision Graph Attention (SVGA), grows connections linearly and causes over-squashing, where too much information is compressed into one vector. This paper proposes a graph construction rule that grows connections logarithmically with image size, then embeds it in a new hybrid CNN-GNN network that also fuses high-resolution and low-resolution features.

Key Contributions

1. Logarithmic Scalable Graph Construction (LSGC): A graph construction method that scales connections based on the bit-depth of the input image's height and width rather than statically, generating fewer connections than SVGA on high-resolution images while still establishing global links and preserving locality by prioritizing nearby connections.
2. LogViG architecture: A hybrid CNN-GNN model for image classification and semantic segmentation that uses convolutional and grapher layers in all four stages, performing local and global processing at every stage, and that employs a high-resolution skip connection inspired by HRNet, Lite-HRNet, and HRViT.
3. Empirical comparison against CNN, ViT, and ViG architectures: Demonstrates that LogViG outperforms these alternatives in accuracy for comparable or lower parameter counts and GMACs, and that LSGC broadly outperforms SVGA on both image classification and semantic segmentation.
4. Ablation studies: Isolates the contributions of LSGC versus SVGA, the high-resolution shortcut, the placement of graph convolutions across stages, and the choice of a deeper-and-narrower versus shallower-and-wider network.

Main Findings

• Shortest path lengths are substantially reduced by LSGC: On a 56 × 56 resolution, a regular square lattice has an average shortest path length of 37.333, which LSGC reduces to 4.359 and SVGA reduces to 2.895. At 28 × 28 the values are 18.667 (lattice), 3.719 (LSGC), and 2.794 (SVGA); at 14 × 14 they are 9.333, 3.303, and 2.605; at 7 × 7 they are 4.667, 2.334, and 1.750. The paper notes SVGA has a shorter average path length than LSGC because it makes significantly more connections, which the authors link to SVGA's over-squashing.
• Ti-LogViG efficiency and accuracy: Ti-LogViG achieves 79.9% ± 0.2% average top-1 accuracy on ImageNet-1K with 8.1 M parameters and 1.1 GMACs over 300 epochs. The abstract states this is 1.7% higher average accuracy than Vision GNN with a 24.3% reduction in parameters and 35.3% reduction in GMACs.
• Comparison with PViG and PViHGNN at the smallest scale: PViG-Ti reaches 78.2% top-1 at 10.7 M parameters and 1.7 GMACs, and PViHGNN-Ti reaches 78.9% at 12.3 M parameters and 2.3 GMACs. The paper describes Ti-LogViG as 1.0% more accurate than PViHGNN-Ti for 4.3 M fewer parameters and 1.1 fewer GMACs, and 1.7% more accurate than PViG-Ti for fewer parameters and GMACs.
• Larger LogViG variants: S-LogViG achieves 81.5% ± 0.1% top-1 at 13.9 M parameters and 1.9 GMACs. B-LogViG achieves 83.6% ± 0.1% at 30.5 M parameters and 4.6 GMACs. The paper compares B-LogViG against HRViT-b3, which it reports at 82.8% with 37.9 M parameters and 5.7 GMACs, a 0.8% accuracy difference at higher cost.
• Comparisons against non-graph architectures: Ti-LogViG exceeds PoolFormer-S12 (77.2%) by 2.7% top-1 accuracy with 3.9 M fewer parameters and 0.9 fewer GMACs. S-LogViG exceeds DeiT-S (81.2%, 22.5 M parameters, 4.5 GMACs) by 0.3% top-1 accuracy with 8.6 M fewer parameters and 2.6 fewer GMACs. B-LogViG is reported to beat the EfficientFormer family with significantly fewer parameters.
• Semantic segmentation on ADE20K: The dataset contains 20K training images and 2K validation images across 150 semantic categories. S-LogViG with 13.9 M parameters achieves 44.1 ± 0.6 mIoU, and B-LogViG with 30.5 M parameters achieves 46.8 ± 0.4 mIoU.
• Segmentation gains over specific backbones: S-LogViG outperforms PoolFormer-S12, FastViT-SA12, EfficientFormer-L1, and MobileViG-M by 6.9, 6.1, 5.2, and 2.3 mIoU respectively. B-LogViG outperforms FastViT-SA36 by 3.9 mIoU with only 0.1 M more parameters, and EfficientFormer-L3 by 3.3 mIoU with 0.8 M fewer parameters.
• Ablation: LSGC versus SVGA and the high-resolution shortcut: Ti-LogViG with SVGA and without the high-resolution shortcut reaches 79.4% top-1. Adding LSGC raises it to 79.8% with no additional parameters. Adding the high-resolution shortcut raises it to 79.9% with 0.1 M additional parameters.
• Ablation: where graph convolutions are placed: Using a MobileViG-S baseline (7.2 M parameters, 78.2%), the authors first apply LSGC with a deeper and narrower network to reach 78.8% with 7.0 M parameters, which the paper reports as 0.6% higher accuracy with 0.2 M fewer parameters. Using graph convolutions in stages 2, 3, and 4 yields 79.8% at 8.0 M parameters, described as 1.0% higher than using graph convolutions only in stage 4. Using graph convolutions in all four stages yields 79.9% at 8.1 M parameters when combined with the deep network, and 79.6% at 8.0 M parameters without it.
• Ablation: deeper versus wider: In Section 3.3 the deeper LogViG-Ti is reported to achieve a 0.4% accuracy increase with only a 0.1 M increase in parameters relative to the wider variant. In the Section 4.3 discussion of the same comparison, the wider network is reported to show a 0.3% decrease in accuracy with only 0.1 M fewer parameters. The wider variant cuts depth by 33% and increases channel width by 50% for stages 1 to 3, with stage 4 width increased to 384 from 224.

Methodology in Plain English

The authors start from the observation that KNN graph construction in Vision GNNs requires computing nearest neighbors for every image, which is expensive, and that the cheaper static alternative, SVGA, connects every patch to every K-th patch in its row and column, which grows connections quadratically with resolution and causes over-squashing. They argue that a fixed number of connections per token, as in MGC, loses global context on high-resolution images.

Their replacement, LSGC, begins by computing the "bit-depth" of the image height H and width W — the number of bits needed to represent those dimensions in binary. For example, an 8 × 8 input has a bit-depth of four for both width and height. This bit-depth determines how far the graph expands. Starting from each pixel, the method performs a forward expansion downward and to the right, creating connections at offsets of 2^n − 1 for n from 1 up to the bit-depth, with an expansion rate K (K = 2 in the illustrative figure). It then performs a backward expansion upward and to the left, the reverse of the forward pass. If there is no room to expand — for instance at the image edge — the expansion wraps around to the opposite side of the image.

After each directional expansion, the method performs max-relative graph convolution (MRConv): it computes an element-wise max over the difference between the original image X and the expanded version, accumulating the result. Finally, it concatenates the accumulated result with the original image and applies a Conv2d over the full matrix. This is intended to give a global receptive field while using fewer links than SVGA and avoiding the two reshape operations that KNN-based ViGs require to move between 4D image tensors and 3D graph tensors.

For the network itself, LogViG first passes the input through a convolutional stem that downsamples by 4× using convolutions with stride 2. The stem output splits into two branches. The low-resolution branch processes features through four stages, each alternating MBConv blocks and LSGC blocks, with convolution-based downsampling between stages. The high-resolution branch consists of a single High-Resolution Shortcut (HRS) block containing two 3 × 3 convolutions — one with stride 2 and one with stride 1 — each followed by batch normalization and GeLU. To fuse the two branches, the low-resolution features are upsampled with bilinear interpolation, passed through a pointwise convolution to match channel dimensions, summed with the high-resolution features, and passed through another pointwise convolution followed by batch normalization and GeLU. The merged output goes through average pooling and a feed-forward network to produce the class prediction.

Training used PyTorch 1.12 and the Timm library. Models were trained from scratch for 300 epochs on ImageNet-1K with the AdamW optimizer, a learning rate of 2e-3 and a cosine annealing schedule, at a standard 224 × 224 resolution for training and testing. Following prior work, knowledge distillation used RegNetY-16GF (reported at 82.9% top-1 accuracy). Data augmentation included RandAugment, Mixup, Cutmix, random erasing, and repeated augment. For segmentation, LogViG was built with Semantic FPN as the decoder, initialized with ImageNet-1K pretrained weights, and trained for 40K iterations on 8 NVIDIA RTX 6000 Ada generation GPUs with the AdamW optimizer, a learning rate of 2 × 10⁻⁴ with poly decay by the power of 0.9, and a training resolution of 512 × 512. LogViG's top-1 accuracy results are averaged over four experiments and reported as mean ± standard deviation; the mIoU results are likewise averaged over four experiments.

Why This Matters

• Impact on research: The paper reframes graph construction in Vision GNNs as a scaling problem rather than a nearest-neighbor search problem, and provides evidence that deliberately limiting long-range links can improve accuracy while cutting parameters and GMACs. It also extends multi-scale high-resolution feature fusion — a technique established in CNN and ViT families such as HRNet, Lite-HRNet, and HRViT — into the Vision GNN setting, and quantifies the over-squashing tradeoff using average shortest path length measurements across resolutions.
• Real-world applications:
  • Mobile and edge image classification, where the reported parameter and GMAC reductions at 79.9% top-1 accuracy (8.1 M parameters, 1.1 GMACs) matter for on-device deployment.
  • Scene parsing and semantic segmentation for autonomous systems, given the ADE20K results of 44.1 mIoU (S-LogViG) and 46.8 mIoU (B-LogViG) across 150 semantic categories.
  • High-resolution image understanding tasks, the setting the paper identifies as the weakness of both ViTs and existing ViG graph construction methods.
  • Robotics and embedded vision pipelines that operate on higher-resolution inputs and are constrained by latency and compute.
• Industry relevance: Efficiency measured jointly in parameters and GMACs is a primary constraint for shipping vision models on devices and in latency-sensitive services. A method whose accuracy advantage holds at matched or lower cost, and which avoids the KNN graph construction bottleneck on larger images, is directly relevant to teams optimizing vision backbones. The code is released at https://github.com/mmunir127/LogViG-Official.

Future Directions

• Testing LSGC in other graph-based vision architectures: The paper applies LSGC within a hybrid CNN-GNN design; whether the logarithmic construction transfers to other ViG variants is left open.
• Resolution scaling beyond the evaluated settings: LSGC is motivated by high-resolution behavior, but classification was trained and tested at 224 × 224 and segmentation at 512 × 512. Behavior at substantially higher resolutions is not reported.
• Reconciling the deeper-versus-wider ablation: Section 3.3 and Section 4.3 report the deeper-versus-wider comparison with different figures (a 0.4% accuracy increase for the deeper network versus a 0.3% decrease for the wider one), which would benefit from clarification or further study.
• Combining LSGC with alternative graph construction strategies: The paper compares LSGC mainly against SVGA and cites MGC as a fixed-connection alternative but does not report direct experiments against MGC.

Target Audience

Researchers and engineers working on efficient vision backbones, graph neural networks for computer vision, and on-device model deployment. It is most useful to readers already comfortable with CNN, ViT, and GNN design tradeoffs — including GMACs, parameter counts, over-squashing, and multi-scale feature fusion — and to practitioners looking for accuracy-per-compute improvements on ImageNet-1K classification and ADE20K semantic segmentation. Beginners will find the core ideas accessible at a high level, but the algorithmic details and efficiency comparisons require prior background.

Authors’ abstract

Vision graph neural networks (ViG) have demonstrated promise in vision tasks as a competitive alternative to conventional convolutional neural nets (CNN) and transformers (ViTs); however, common graph construction methods, such as k-nearest neighbor (KNN), can be expensive on larger images. While methods such as Sparse Vision Graph Attention (SVGA) have shown promise, SVGA's fixed step scale can lead to over-squashing and missing multiple connections to gain the same information that could be gained from a long-range link. Through this observation, we propose a new graph construction method, Logarithmic Scalable Graph Construction (LSGC) to enhance performance by limiting the number of long-range links. To this end, we propose LogViG, a novel hybrid CNN-GNN model that utilizes LSGC. Furthermore, inspired by the successes of multi-scale and high-resolution architectures, we introduce and apply a high-resolution branch and fuse features between our high-resolution and low-resolution branches for a multi-scale high-resolution Vision GNN network. Extensive experiments show that LogViG beats existing ViG, CNN, and ViT architectures in terms of accuracy, GMACs, and parameters on image classification and semantic segmentation tasks. Our smallest model, Ti-LogViG, achieves an average top-1 accuracy on ImageNet-1K of 79.9% with a standard deviation of 0.2%, 1.7% higher average accuracy than Vision GNN with a 24.3% reduction in parameters and 35.3% reduction in GMACs. Our work shows that leveraging long-range links in graph construction for ViGs through our proposed LSGC can exceed the performance of current state-of-the-art ViGs. Code is available at https://github.com/mmunir127/LogViG-Official.