A survey on graph representation learning in computer vision: perspectives on the granularity of visual entities and tasks

Background Graph representation learning has become a powerful paradigm for modeling the relational structure of visual data in computer vision tasks. Unlike traditional grid-based representations, graph representation learning offers a flexible framework for modeling non-Euclidean structures, which can capture long-range dependencies while facilitating structured reasoning. While several recent surveys review general Graph neural networks (GNNs) architectures and applications across domains, existing literature reviews in computer vision are typically organized around tasks or data modalities. As a result, there remains a lack of a unified perspective for categorizing graph representations by the structural roles they play in visual reasoning. Methodology Following standard literature search guidelines, we collected studies published between 2017 and 2025 from major Computer Vision/Machine Learning conferences and journals using targeted keywords related to graph representation learning. From this corpus , we identified representative works covering seven graph schemas and extracted their graph designs, learning mechanisms, and task-level findings to build our taxonomy. Results Our analysis identifies seven fundamental graph schemas: pixel, point, skeleton, object, region, image, and label graphs, which can form a hierarchy ranging from low-level spatial detail to high-level semantic abstraction. For each schema, we review representative models, discuss graph construction strategies, and compare learning mechanisms, including graph convolutional networks (GCNs), graph attention networks (GATs), spatio-temporal (ST)-GNNs, and graph transformers. Common challenges across schemas include reliance on predefined topologies, uniform neighbor aggregation, difficulty modeling long-range dependencies, and scalability limitations in large graphs. Emerging solutions include graph structure learning, attention-based and adaptive message passing, hierarchical and multiscale graph designs, and integration of graph reasoning into transformer architectures. Conclusions This survey presents a unified taxonomy of graph representation learning in computer vision, synthesizing methodological trends across diverse graph schemas. By clarifying the structural roles of graphs from pixels to labels, we provide a coherent framework for understanding how graph-based reasoning advances visual recognition, geometric understanding, and scene-level interpretation. Traditional challenges, such as adaptive graph construction, efficient reasoning on large graphs, and standardized evaluation, highlight important directions for future research. The insights presented here aim to guide the development of more scalable, interpretable, and context-aware graph-based solutions.