Abstract
Hypergraph Vision Transformers (HgVT) introduce a hierarchical bipartite hypergraph structure to vision transformers, enabling the capture of complex, higher-order relationships between image patches. Unlike traditional Vision Transformers (ViTs) or Graph Neural Networks (ViGs) that rely on pairwise relationships or expensive clustering, HgVT utilizes dynamic adjacency formation and virtual hyperedges to facilitate efficient global context communication. By replacing slow K-Nearest Neighbors (KNN) algorithms with a differentiable cosine similarity mechanism and introducing novel regularization techniques, HgVT achieves superior accuracy and significant speedups. Experimental results on ImageNet-1k show that HgVT-Ti achieves 76.2% top-1 accuracy, outperforming existing hypergraph models by 1.9% while maintaining a 1.4x speedup over ViG models.
Introduction
Vision Transformers (ViTs) have become the standard for computer vision, yet they often struggle to balance computational efficiency with a deep semantic understanding of image components. Existing alternatives, such as Vision Graph Neural Networks (ViGs), attempt to model these relationships by treating image patches as nodes in a graph. However, ViGs face significant hurdles, including computational bottlenecks from expensive clustering algorithms and the failure to carry forward learned edge information across network layers.
HgVT addresses these challenges by reimagining the image as a bipartite hypergraph. In this setup, "image vertices" (patches) connect to "virtual hyperedges" (latent groups) that act as communication pools. This allows information to flow efficiently between distant but semantically related patches, capturing global context more effectively than standard grid-based or pairwise node-based methods.
Methodology
The HgVT architecture is built around the concept of dynamic hypergraph construction and message passing. Key technical innovations include:
- Dynamic Adjacency Formation: Instead of iterative clustering like KNN, HgVT uses a differentiable cosine similarity mechanism to determine patch-to-hyperedge membership. This approach is approximately 10x faster than traditional methods.
- Structured Multi-Head Attention: The model employs three specialized attention layers within each block: vertex self-attention, edge aggregate attention (vertex to edge), and edge distribution attention (edge to vertex).
- Regularization and Pooling: To prevent hyperedge collapse and maintain optimal connection density, the model uses Diversity and Population Regularization. For final classification, "Expert Edge Pooling" treats each hyperedge as a specialized expert, generating confidence scores for a more robust prediction.
Experiments and Results
The model was evaluated on standard benchmarks including ImageNet-1k, ImageNet-100, CIFAR-100, and image retrieval datasets (ROxford & RParis).
- Superior Accuracy: The HgVT-Ti (Tiny) model achieved a 76.2% Top-1 accuracy on ImageNet-1k, outperforming the previous state-of-the-art hypergraph model (ViHGNN) by 1.9% while using fewer parameters.
- Efficiency Gains: HgVT demonstrated a speedup of at least 1.4x over ViG models. The adjacency computation alone is an order of magnitude faster than KNN-based methods.
- Retrieval Performance: In image retrieval tasks, HgVT-Ti outperformed strong baselines like MRL by over 8% in mean Average Precision (mAP), demonstrating the effectiveness of learned hypergraph structures for semantic search.
Discussion and Conclusion
HgVT proves that images are effectively modeled as more than just grids or simple graphs. By leveraging hyperedges, the model can represent abstract concepts (like "Plant" or "Fish") spanning multiple non-contiguous patches. While currently limited to isotropic architectures, future work will focus on extending HgVT to pyramidal structures and exploring self-supervised learning paradigms. The emergent specialization of hyperedges through expert pooling suggests a promising path toward more interpretable and robust vision models.
Summary updated