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

Abstract

Graph Neural Networks (GNNs) and Graph Transformers have emerged as powerful tools for representation learning, particularly in domains where data is inherently relational or irregular. This survey provides a comprehensive review of these technologies within computer vision, adopting a task-oriented perspective. By categorizing applications across five modalities—2D images, videos, 3D data, vision+language, and medical imaging—the authors examine how graph-based approaches overcome the limitations of traditional grid-based processing and boost the state of the art in complex reasoning tasks.

The Shift from Grids to Graphs

For the past decade, Convolutional Neural Networks (CNNs) have been the standard for computer vision. However, CNNs are fundamentally constrained to regular grid structures like pixel arrays. Much of the visual world is irregular: 3D point clouds lack a fixed grid, and complex scenes are defined by the relationships between objects rather than just their spatial coordinates.

GNNs address this by treating visual elements as nodes in a graph, allowing for arbitrary connectivity. This "relational inductive bias" enables models to reason about high-level semantics, such as a "person" "holding" a "glass," which is difficult for standard convolutions to capture in isolation.

A Task-Oriented Taxonomy

The authors organize the vast landscape of GNN research into a structured taxonomy based on the input data modality, allowing for a clear comparison of how different tasks are tackled.

A comprehensive taxonomy of GNN and Graph Transformer applications in computer vision, categorized by data modality and specific vision tasks.
  1. 2D Natural Images: Beyond simple classification, GNNs are used for multi-label recognition, object detection, and scene graph generation.
  2. Videos: GNNs model temporal dependencies and human skeletal structures for action recognition and trajectory prediction.
  3. 3D Data: Point clouds and meshes are naturally represented as graphs, making GNNs the state-of-the-art choice for 3D segmentation and reconstruction.
  4. Vision + Language: GNNs serve as a bridge between modalities, representing images and text as graphs to facilitate complex reasoning in Visual Question Answering (VQA).
  5. Medical Images: Applications include analyzing brain activity networks and segmenting complex anatomical structures.

Architectural Evolution: From GCNs to Transformers

The survey traces the development of graph-based architectures from early Spectral GNNs (like GCN), which use graph Fourier transforms, to Spatial GNNs (like GraphSAGE and GAT) that aggregate local neighborhood information.

More recently, Graph Transformers have gained traction. By adapting the self-attention mechanism to graph structures, they allow for global relational modeling without the strict neighborhood constraints of traditional GNNs. A notable innovation is the Vision GNN (ViG), which treats standard images as graphs by connecting image patches based on feature similarity rather than just spatial proximity, outperforming popular Transformer models like DeiT on ImageNet classification.

Key Insights: Relational Reasoning

One of the most significant advantages of GNNs is their ability to perform explicit relational reasoning. In tasks like Scene Graph Generation, the model must not only identify objects but also the semantic links between them.

An example of Scene Graph Generation using attentional GCNs to map visual features to semantic relationships.

Furthermore, GNNs are uniquely suited for 3D data. Unlike voxel-based methods that introduce quantization errors, GNNs process point clouds in their raw, irregular form. In cross-modal tasks, GNNs act as a "unified language," allowing visual and textual graphs to be matched and aligned more effectively than traditional vector-based approaches.

Performance and Future Directions

Empirical results across standard benchmarks demonstrate the superiority of graph-based methods:

  • 3D Segmentation: PTv2 achieves 72.6% mIoU on S3DIS, setting the current state-of-the-art.
  • Action Recognition: Skeleton-based models like MS-G3D Net reach 91.5% accuracy on NTU-RGB+D by modeling the body as a graph of joints.
  • Multi-label Classification: TDRG achieves 86.0 mAP on MS-COCO by explicitly modeling label dependencies.

Despite these successes, challenges remain. Most models rely on handcrafted rules for graph construction (e.g., k-nearest neighbors), and scaling GNNs to high-resolution images remains computationally expensive. Future research is expected to focus on automated graph topology learning, improved efficiency, and better explainability of the message-passing process.

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