Visualization Tasks for Unlabeled Graphs
Matt I. B. Oddo, Ryan Smith, Stephen Kobourov, Tamara Munzner · 2025
Read Visualization Tasks for Unlabeled Graphs by Matt I. B. Oddo, Ryan Smith, Stephen Kobourov, Tamara Munzner (2025) 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-2504-14115.txt.
Introduction
Matt Oddo, Ryan Smith, Stephen Kobourov, and Tamara Munzner investigate what visualization tasks make sense for unlabeled graphs. Their 2025 paper deals with graphs whose nodes carry no persistent or meaningful labels.
New techniques can draw such graphs, but they cannot be judged well until the tasks are clear. Some network tasks apply to both labeled and unlabeled graphs, while many do not transfer. The authors propose a data abstraction model that sets the unlabeled context apart from labeled, attributed, and augmented ones. They filter tasks from the literature through that model. The result is a taxonomy of abstract tasks, organized by target, action, and scope.
Catalog record
| CREATOR | Matt I. B. Oddo, Ryan Smith, Stephen Kobourov, Tamara Munzner |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 71 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-14115
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Visualization Tasks for Unlabeled Graphs Matt I. B. Oddo, Ryan Smith, Stephen Kobourov, Tamara Munzner Abstract We investigate tasks that can be accomplished with unlabeled graphs, which are graphs with nodes that do not have persistent or semantically meaningful labels attached. New visualization techniques to represent unlabeled graphs have been proposed, but more understanding of unlabeled graph tasks is required before these techniques can be adequately evaluated. Some network visualization tasks apply to both labeled and unlabeled graphs, but many do not translate between these contexts. We propose a data abstraction model that distinguishes the Unlabeled context from the increasingly semantically rich Labeled, Attributed, and Augmented contexts. We filter tasks collected and gleaned from the literature according to our data abstraction and analyze the surfaced tasks, leading to a taxonomy of abstract tasks for unlabeled graphs. Our task taxonomy is organized according to the Target data under consideration, the Action intended by the user, and the Scope of the data at play. We show the descriptive power of this task abstraction by connecting to concrete examples from previous frameworks, and connecting these abstractions to real-world problems. To showcase the evaluative power of the taxonomy, we perform a preliminary assessment across 6 different network visualization idioms for each task. For each combination of task and visual encoding, we consider the effort required from viewers, the likelihood of task success, and how both factors vary between small-scale and large-scale graphs. Availability: Supplemental materials are available at osf.io/e23mr . I Introduction Task taxonomies support the analysis, design, and evaluation of visualization tools [ 1 ] . In the case of graph-structured data, where nodes are interconnected through edges, tasks may pertain to the topological structure of that connectivity, or attributes attached to nodes or edges [ 2 ] . In nearly all previous visualization contexts, graphs are assumed to be labeled graphs; that is, they have persistent unique identifiers for the nodes, even when the graph has no other attributes. However, there are network visualization approaches that do not make this assumption, and rely purely on topological information that is completely independent of node labels. These unlabeled graph methods emphasize properties of graph data structures that remain unchanged when node labels are locally reassigned, globally shuffled, or even ignored. These techniques have been called invariant descriptor visualization idioms [ 3 ] , which we shorten here to invariant plots . Examples include the Network Portrait [ 4 ] , GraphPrism [ 5 ] , Graph Thumbnails [ 6 ] , and Census plots [ 3 ] . A crucial property of invariant plots is that the visual patterns [ 7 ] they surface are always the same for structurally identical (isomorphic) graphs [ 3 ] . Researchers may find it difficult to persuasively evaluate the efficacy and utility of invariant plots until a task taxonomy that pertains to them is introduced. Enumerating and categorizing what tasks can be performed on unlabeled graph data is an open problem that needs addressing before human-subjects studies can be run. The type of tasks supported by these invariant plots are fundamentally different from those targeted by the traditional views dedicated to semantically meaningful and persistent labels: while some tasks apply to both labeled and unlabeled graphs, many tasks designed for the labeled context do not translate to the unlabeled context. For example, the task of following the spread of disease between people through a contagion network presupposes persistent node labels to identify those specific people [ 8 ] . Conversely, some tasks that are challenging with traditional graph visualization approaches become feasible with visual encodings of unlabeled graphs. For example, pairwise comparison between two graphs could be easier with invariant plots that exploit a shared absolute coordinate system, than with node-link layouts where the spatial position of node points is arbitrary and unconstrained [ 3 ] . We attack this problem through a combination of literature review and reflective synthesis (Sec. II ). We identify which of the many concrete tasks discussed in previous work are labels-not-required tasks ; that is, tasks for the unlabeled graph context. We consider both abstract tasks stated explicitly in the visualization literature and implicit tasks that we infer from theoretical works, practitioner surveys, and domain-specific literature. To make these choices, we create a data abstraction that assigns graphs into the categories of Augmented, Attributed, Labeled, and Unlabeled (Sec. III ), which allows us to filter tasks from existing literature (Sec. IV ). We then propose our task taxonomy, which is an abstraction that maps concrete labels-not-required tasks into Target + Action + Scope triplets (Sec. V ). We show the generative power of our taxonomy by proposing new concrete tasks from the combinatorial possibilities of these triplets (Sec. VI-B and VI-C ). We also validate our task taxonomy through consideration of its descriptive, generative, and evaluative power [ 9 ] . We demonstrate its descriptive power by mapping many previously proposed concrete tasks into these abstract triplets; and provide some preliminary evidence of the ecological validity of the concrete tasks by connecting them to real-world problems stated in domain literature (Sec. VI-D ). To showcase the descriptive and evaluative power of our taxonomy, we provide an extended example of its use in a preliminary assessment of 6 visual encodings, both traditional and invariant plot views, in relation to 17 concrete tasks (Sec. VII ). In this exercise, we made educated guesses about the effort demanded from viewers and the likelihood of success for both small and large graphs. This assessment is not intended to provide final answers to these questions, but rather to showcase the utility of the taxonomy for the design of future user studies. In summary, the primary contribution of this paper is our Target + Action + Scope taxonomy of abstract visualization tasks for unlabeled graphs (Sec. V ); the data abstraction model behind the construction of this task taxonomy is a secondary contribution (Sec. III ). First Author Title Tasks Taxonomy Year Ref Ghoniem A comparison of the readability of graphs using node-link and matrix-based representations Choose X 2004 [ 10 ] Lee Task taxonomy for graph visualization Choose X 2006 [ 2 ] Brehmer A multi-level typology of abstract visualization tasks Choose X 2013 [ 1 ] Munzner Visualization analysis and design Choose X 2014 [ 11 ] Pretorius Tasks for multivariate network analysis Choose X 2014 [ 12 ] Kerracher A task taxonomy for temporal graph visualisation Choose X 2015 [ 13 ] Murray A taxonomy of visualization tasks for the analysis of biological pathway data Choose X 2016 [ 14 ] Pandey A state-of-the-art survey of tasks for tree design and evaluation with a curated task dataset Choose X 2022 [ 15 ] Filipov Are we there yet? A roadmap of network visualization from surveys to task taxonomies Choose X 2023 [ 16 ] Bae Bridging network science and vision science: Mapping perceptual mechanisms to network visualization tasks Choose X 2025 [ 17 ] Bagrow Portraits of complex networks Choose 2008 [ 4 ] Kairam GraphPrism: Compact visualization of network structure Choose 2012 [ 5 ] Yoghourdjian Graph Thumbnails: Identifying and comparing multiple graphs at a glance Choose 2016 [ 6 ] Bagrow An