Graph Recognition via Subgraph Prediction
André Eberhard, Gerhard Neumann, Pascal Friederich · 2026
Read Graph Recognition via Subgraph Prediction by André Eberhard, Gerhard Neumann, Pascal Friederich (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-15133.txt.
Introduction
André Eberhard, Gerhard Neumann, and Pascal Friederich teach machines to read a graph out of a picture. Their 2026 arXiv paper deals with visual graph recognition. Tasks such as image classification and object detection have leapt ahead, but pulling a relationship graph from an image lags behind.
The authors blame the lack of a canonical way to frame the task. Their approach turns recognition into subgraph prediction. The model predicts the pieces of the graph rather than the whole structure at once. That split gives the learner a cleaner target to aim at.
Catalog record
| CREATOR | André Eberhard, Gerhard Neumann, Pascal Friederich |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 45 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-15133
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Graph Recognition via Subgraph Prediction André Eberhard, Gerhard Neumann, Pascal Friederich Abstract Despite tremendous improvements in tasks such as image classification, object detection, and segmentation, the recognition of visual relationships, commonly modeled as the extraction of a graph from an image, remains a challenging task. We believe that this mainly stems from the fact that there is no canonical way to approach the visual graph recognition task. Most existing solutions are specific to a problem and cannot be transferred between different contexts out-of-the box, even though the conceptual problem remains the same. With broad applicability and simplicity in mind, in this paper we develop a method, Gra ph Recognition via S ubgraph P rediction ( GraSP ), for recognizing graphs in images. We show across several synthetic benchmarks and one real-world application that our method works with a set of diverse types of graphs and their drawings, and can be transferred between tasks without task-specific modifications, paving the way to a more unified framework for visual graph recognition. I Introduction One picture says more than a thousand words. Looking at pictures, humans can tell which entities are present and how they interact. Based on the identified entities and their relationships, we can understand complex scenes simply by looking at one frame. For computers, digital images are merely arrays of pixels, and their raw representation does not lend itself well to describe or understand the actual content of an image. Although the artificial intelligence community has made significant progress in identification [ 18 , 11 ] and localization [ 10 , 31 , 29 ] of objects, the extraction of visual entities and their relationships remains a difficult problem. It has been formulated, among many distinct applications, as the extraction of a graph given an image, where the graph’s nodes describe the entities and edges their relationships. The applications range from early approaches of reversing graph drawings [ 2 ] to music recognition [ 8 ] , medical image analysis [ 1 ] , pose estimation [ 5 ] , the recognition of road segments [ 3 ] , molecules [ 25 , 24 ] and scene graphs [ 39 , 23 , 34 , 36 , 38 , 6 , 14 ] . Conceptually, all these domains operate on a common ground: Given an image, the objective is to generate a graph representing the entities and relationships of interest. Technically, the solutions differ significantly from task to task and do not share any design principles, for which the reason is two-fold. First, different fields operate independently and propose independent solutions to domain-specific problems. Although all solutions aim to extract a graph from an image, due to the generality and expressivity of graphs, the resulting techniques do not share many common traits, as the underlying problems themselves do not. Second, within the same task, especially if the task is new or difficult, many independent solutions are proposed for the same problem, each having its unique characteristics. We believe that this primarily stems from the fact that there is no canonical way to approach the image to graph translation conceptually, and each new method has to solve a common set of subproblems such as image processing, graph generation and optimization for the desired outcome. The major obstacle is how to model an expressive, discrete, compositional, and set-like structure with the currently available deep learning tools. Efforts to solve some of these subproblems are made within the field of graph generative models [ 37 , 20 , 19 ] . While they aim to model distributions of graphs, they do not have any connections to image processing. To the best of our knowledge, there exists no general method for extracting graphs from images yet. Most works, such as those for recognizing molecules or scene graphs, either rely on complex pipelines involving multiple components or domain- or application-specific encodings [ 27 , 37 ] , which avoid working with an explicit graph representation altogether. The complexity and specificity of these methods limits their applicability and transferability to other contexts. As learned from the bitter lesson [ 33 ] , methods built this way will not stand the test of time. Therefore, we believe that there should be a conceptual solution for recognizing graphs in images, rather than a collection of individual solutions to individual problems. This has the potential to unify many efforts across different tasks and domains by providing a unified framework. Ultimately, this will result in more general and powerful methods since efforts can be concentrated and improvements in one context may directly be transferred to others, as they share the underlying framework. In this paper, we present the first steps towards a more unified framework for visual graph recognition, termed Gra ph Recognition via S ubgraph P rediction, or GraSP . II Graphs as model outputs Working with graphs as outputs of neural networks is not as straightforward as it is with other modalities such as images or text, primarily for two reasons. Graphs as compositional objects. While images and text can be modeled as single units, graphs have a more compositional nature, which introduces additional challenges when using them as neural network outputs. When the task is, for example, to learn how to generate images, regardless of whether we use models such as Variational Autoencoders [ 16 ] or Diffusion Models [ 13 ] , remarkable results can be achieved simply by applying some kind of pixel-wise loss, without taking the interaction of those pixels into account. In a similar vein, one can learn fascinating generative models of text by simply predicting which token would have appeared next in a large corpus of text, e.g., in GPT-style models [ 4 ] , also not taking into account the interaction with other tokens for optimization. For graphs, this does not apply. When working with graphs as outputs of neural networks, we must make several predictions at once in order to arrive at a valid graph representation consisting of node and edge features as well as the edges themselves. This is further complicated by the edges being discrete and by variable-sized output graphs, i.e., graph sizes and connectivities. This introduces a source of methodological variability in the generation procedure, which we can highlight by looking at the methods proposed in the realm of graph generative modelling, a field also concerned with generating graphs but for modeling their distributions rather than image processing. In [ 19 ] , for example, the authors propose to generate a graph sequentially by introducing several stages of decision-making such as whether and where to add nodes and edges. Other methods, such as Graph Variational Autoencoders [ 17 ] or generative diffusion models for graphs [ 15 ] , generate the output representation in one shot. Methods such as [ 20 ] propose to generate blocks of the adjacency matrix one block at a time, operating somewhere in between. Both paradigms, sequential and one-shot generation, have their strengths and weaknesses. Sequential generation is flexible in how the graph is constructed and naturally handles variable-sized outputs and their orderings, but introduces additional latency during inference. One-shot generation is desirable in general as it is conceptually simpler and computationally more