This survey provides a comprehensive roadmap for the integration of Graph Neural Networks (GNNs) and Graph Transformers into the computer vision (CV) pipeline. By categorizing research through a task-oriented lens—spanning 2D images, video, 3D data, multi-modal vision+language, and medical imaging—the authors illustrate how moving beyond regular grids to relational modeling is essential for achieving human-like visual reasoning.
TL;DR
While convolutional neural networks (CNNs) dominate grid-like data, GNNs and Graph Transformers are emerging as the go-to tools for modeling the complex, irregular relationships inherent in scene understanding and 3D analysis. This survey systematizes the field, showing how relational inductive biases are pushing the state-of-the-art across five major visual modalities.
What Problem Does This Paper Address?
Modern computer vision has been built on the back of CNNs, which excel at processing data defined on regular Cartesian grids (like pixels in an image). However, much of the visual world is inherently irregular or relational. For example, a 3D point cloud has no fixed grid, and understanding a complex scene requires reasoning about how a "person" interacts with a "baseball bat"—a task that requires more than just local pixel processing.
The authors argue that the next frontier in CV is combinatorial generalization: the ability to represent structures and reason about relations. GNNs and Graph Transformers address this by providing a flexible framework to model arbitrary dependencies (one-to-many, many-to-many) that vanilla CNNs and even standard Vision Transformers (ViTs) struggle to capture efficiently.
Methods
The paper recaps the evolution of graph-based learning, categorizing methods into three main buckets:
- Recurrent GNNs: The early iterations that used iterative weight sharing to extract node representations.
- Convolutional GNNs: Divided into Spectral approaches (which use the graph Laplacian and Fourier transform, like GCN) and Spatial approaches (which use message passing between neighbors, like GraphSAGE and GAT).
- Graph Transformers: A more recent development that adapts the self-attention mechanism to graph structures, allowing for long-range dependency modeling without the strict local biases of traditional GNNs.
A key methodological takeaway is the "Vision GNN" (ViG) concept, where an image is split into patches and treated as a graph of nodes, allowing the model to learn topological structures directly from 2D data.
Datasets
As a survey, the paper references a vast array of benchmarks used to validate these methods:
- 2D Natural Images: MS-COCO and VOC 2007 for multi-label classification and object detection.
- Video: Charades, NTU-RGB+D, and Kinetics for action recognition.
- 3D Data: ModelNet40 for classification and S3DIS for semantic segmentation.
- Vision + Language: VQA v2.0 and GQA for visual question answering.
- Medical Imaging: Various f-MRI and CT datasets for brain disorder recognition and anatomy segmentation.
Key Insights and Ideas
- Relational Inductive Bias: The core "superpower" of GNNs is their ability to use arbitrary connectivity. While ViTs are technically a special case of GNNs (operating on fully connected graphs), GNNs offer the flexibility to design specific, irregular connectivities that match the data's nature (e.g., scene graphs).
- Graph Construction is Critical: For regular grid data (images/video), how you build the graph—whether through K-Nearest Neighbors, semantic label correlations, or temporal overlapping—is often as important as the GNN architecture itself.
- Hybrid Backbones: Most successful applications don't throw away CNNs. Instead, they use CNNs as local feature extractors and GNNs as a "relational layer" to perform global reasoning.
Key Results
- ViG Performance: The Vision GNN (ViG) outperformed DeiT by 1.7% on ImageNet classification, proving that graph-based patch modeling is a viable alternative to standard Transformers.
- Multi-Label Gains: Models like ML-GCN (Fig. 3) significantly boosted mAP on MS-COCO (from 77.3 to 83.0) by explicitly modeling label dependencies.
- 3D SOTA: Point-transformer-based methods currently achieve state-of-the-art results on 3D semantic segmentation (S3DIS), handling the irregular nature of point clouds far better than voxel-based CNNs.
- Medical Impact: In population-based brain analysis, GNNs have shown a >5% improvement in identifying disorders like Autism Spectrum Disorder (ASD) compared to traditional classifiers.
Limitations and Future Work
The authors highlight several hurdles that remain:
- Heuristic Graph Construction: Many current methods rely on human priors to build graphs. Future work needs to focus on automatic graph construction that learns the optimal topology for a given task.
- Computational Efficiency: Dense graphs lead to quadratic complexity. Scaling GNNs to high-resolution images or long videos requires more efficient sampling and pooling strategies.
- Optimization Challenges: Training GNNs can be more unstable than training CNNs, particularly when trying to build "Deep GNNs" (e.g., 50+ layers) where over-smoothing becomes a major issue.
- Explainability: While GNNs are more "interpretable" in theory (you can see which nodes interact), extracting clear reasoning paths from complex message-passing iterations remains an open research question.
Summary updated