A Survey on Graph Neural Networks and Graph Transformers in Computer Vision: A Task-Oriented Perspective

Chaoqi Chen, Yushuang Wu, Qiyuan Dai, Hong-Yu Zhou, Mutian Xu, Sibei Yang, Xiaoguang Han, Yizhou Yu

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:

  1. Recurrent GNNs: The early iterations that used iterative weight sharing to extract node representations.
  2. 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).
  3. 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.

Fig. 1: Overview of the landscape of GNNs and graph Transformers in computer vision.

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.
Fig. 2: Two types of graph convolutional operations.

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.
Fig. 3: ML-GCN (Figure used courtesy of [42]).

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

Abstract

Graph Neural Networks (GNNs) have gained momentum in graph representation learning and boosted the state of the art in a variety of areas, such as data mining (\emph{e.g.,} social network analysis and recommender systems), computer vision (\emph{e.g.,} object detection and point cloud learning), and natural language processing (\emph{e.g.,} relation extraction and sequence learning), to name a few. With the emergence of Transformers in natural language processing and computer vision, graph Transformers embed a graph structure into the Transformer architecture to overcome the limitations of local neighborhood aggregation while avoiding strict structural inductive biases. In this paper, we present a comprehensive review of GNNs and graph Transformers in computer vision from a task-oriented perspective. Specifically, we divide their applications in computer vision into five categories according to the modality of input data, \emph{i.e.,} 2D natural images, videos, 3D data, vision + language, and medical images. In each category, we further divide the applications according to a set of vision tasks. Such a task-oriented taxonomy allows us to examine how each task is tackled by different GNN-based approaches and how well these approaches perform. Based on the necessary preliminaries, we provide the definitions and challenges of the tasks, in-depth coverage of the representative approaches, as well as discussions regarding insights, limitations, and future directions.
BibTeX
@article{chen2024survey,
  author = {Chaoqi Chen and Yushuang Wu and Qiyuan Dai and Hong-Yu Zhou and Mutian Xu and Sibei Yang and Xiaoguang Han and Yizhou Yu},
  title = {{A Survey on Graph Neural Networks and Graph Transformers in Computer Vision: A Task-Oriented Perspective}},
  journal = {IEEE Trans. Pattern Anal. Mach. Intell.},
  year = {2024},
  url = {https://openreview.net/forum?id=EwnbnY8kRO},
}
Figure