Set Visualization and Uncertainty

In this talk, I first give a brief overview of hypergraph visualization, which is closely related to set visualization. Following the recent survey of Fischer et al. [1], hypergraph visualization techniques could be classified as node-link-based, matrix-based, and timeline-based approaches. During the overview, I ask the following questions with respect to uncertainty visualization: Where are the uncertainties? And how to encode uncertainties? I then discuss the current and future directions on hypergraph visualization. Specifically, from existing perspectives:

• $\mathrm{■}$

  Scalability;

• $\mathrm{■}$

  Aggregating and subsetting;

• $\mathrm{■}$

  Providing support for dynamic hypergraphs with a large number of time steps;

• $\mathrm{■}$

  Benchmark dataset for hypergraph visualizations;

• $\mathrm{■}$

  Performance metrics.

And from my own perspectives:

• $\mathrm{■}$

  Hypergraph simplification using topological approaches;

• $\mathrm{■}$

  Transforming hypergraphs to graphs while preserving metric structures;

• $\mathrm{■}$

  Hypergraph matching using measure theory and optimal transport;

• $\mathrm{■}$

  Uncertainty visualization for hypergraph ensembles.

The genomes in our cells naturally vary between individuals. These changes are mostly differences (mutations) at single base pair positions — two random individuals vary at about 3,000,000 locations (1 in 1,000). An individual may have an inherited mutation that predisposes them to disease (e.g. cancer) or have accumulated unrepaired DNA damage from environmental exposure (e.g. sunlight) that equally raises their risk. A mutation that triggers the onset of a disease is called a “driver mutation”. Such mutations typically dysregulate the repair systems of the genome and lead to an accumulation of errors – the genome becomes fragile and the cell may begin to divide without limitation imposed by checkpoints. As this cell divides, mutations accumulate and now the tumor becomes a collection of groups of cells (clones), each with a slightly different genome. This process leads to a “family tree”, in which nodes are groups of cells.

Thus, cancers can be thought of as sets (individuals with a tumor) of sets (tumors composed of cell groups) of sets (cell groups composed of cells). Visualizing this complexity is challenging for the researcher (tools are only now appearing) and reader (the researcher typically lacks design and visualization experience). Good practices in the use of color, symbol and encoding, which are well known in the visualisation community, have not penetrated the cancer research community — which has only a vague (or no) awareness of best practices. The biologists are not versed in breaking down and addressing the challenges in creating complex visualisations.

I present case studies from the field of genomics and cancer research that illustrate common errors in visualisations in that field, show how I address them (on an individual basis) and identify areas in which visualisation and set community can contribute.

Visualizing sets of elements and their relations is an important research area in information visualization. In this presentation, we present MosaicSets: a novel approach to create Euler-like diagrams from non-spatial set systems such that each element occupies one cell of a regular hexagonal or square grid. The main challenge is to find an assignment of the elements to the grid cells such that each set constitutes a contiguous region. As use case, we consider the research groups of a university faculty as elements, and the departments and joint research projects as sets. We aim at finding a suitable mapping between the research groups and the grid cells such that the department structure forms a base map layout. Our objectives are to optimize both the compactness of the entirety of all cells and of each set by itself. We show that computing the mapping is NP-hard. However, using integer linear programming we can solve real-world instances optimally within a few seconds. Moreover, we propose a relaxation of the contiguity requirement to visualize otherwise non-embeddable set systems. We present and discuss different rendering styles for the set overlays. Based on a case study with real-world data, our evaluation comprises quantitative measures as well as expert interviews.

The brief presentation introduced the interdisciplinary audience to the empirical research frontier in how to visualize uncertainty, inherent to any collected, analyzed, and visualized data. I reviewed empirically evaluated visual variables that are intuitively understood by target users of uncertainty visualizations (e.g., [1, 2]). I also reported on past and ongoing empirical geovisualization research with colleagues that investigates how data uncertainty visualized on maps might influence the process and outcomes of spatial decision-making, especially when made under time pressure, and in risky situations. Based on our collected empirical evidence to date, we argue that spatial data uncertainties should be communicated to space-time decision-makers, especially when decisions need to be made with limited time resources and when decision outcomes can have dramatic consequences.

Visualizing temporal uncertainty is still an open research challenge because the special characteristics of time require special visual encodings and may provoke different interpretations. Thus, we have conducted a comprehensive study comparing alternative visual encodings of intervals with uncertain start and end times: gradient plots, violin plots, accumulated probability plots, error bars, centered error bars, and ambiguation. Our results reveal significant differences in error rates and completion time for these different visualization types and different tasks. We recommend using ambiguation – using a lighter color value to represent uncertain regions – or error bars for judging durations and temporal bounds, and gradient plots – using fading color or transparency – for judging probability values.

Undirected graphs are frequently used to model phenomena that deal with interacting objects, such as social networks, brain activity and communication networks. The topology of an undirected graph $G$ can be captured by an adjacency matrix; this matrix in turn can be visualized directly to give insight into the graph structure. Which visual patterns appear in such a matrix visualization crucially depends on the ordering of its rows and columns. Formally defining the quality of an ordering and then automatically computing a high-quality ordering are both challenging problems; however, effective heuristics exist and are used in practice.

Often, graphs do not exist in isolation but as part of a collection of graphs on the same set of vertices, for example, brain scans over time or of different people. To visualize such graph collections, we need a single ordering that works well for all matrices simultaneously. The current state-of-the-art solves this problem by taking a (weighted) union over all graphs and applying existing heuristics. However, this union leads to a loss of information, specifically in those parts of the graphs which are different. We propose a collection-aware approach to avoid this loss of information and apply it to two popular heuristic methods: leaf order and barycenter.

The de-facto standard computational quality metrics for matrix ordering capture only block-diagonal patterns (cliques). Instead, we propose to use Moran’s $I$, a spatial auto-correlation metric, which captures the full range of established patterns. Moran’s $I$ refines previously proposed stress measures. Furthermore, the popular leaf order method heuristically optimizes a similar measure which further supports the use of Moran’s $I$ in this context. An ordering that maximizes Moran’s $I$ can be computed via solutions to the Traveling Salesperson Problem (TSP); orderings that approximate the optimal ordering can be computed more efficiently, using any of the approximation algorithms for metric TSP.

We evaluated our methods for simultaneous orderings on real-world datasets using Moran’s $I$ as the quality metric. Our results show that our collection-aware approach matches or improves performance compared to the union approach, depending on the similarity of the graphs in the collection. Specifically, our Moran’s $I$-based collection-aware leaf order implementation consistently outperforms other implementations. Our collection-aware implementations carry no significant additional computational costs.

In a metric space we have objects and a way to measure distances between pairs of objects. In a bounded metric space, there is an upper bound on the maximum distance.

We define full diversity of a subset of a metric space as a subset where all pairs of objects are approximately as far apart as the diameter, up to a constant factor.

We examine how large fully diverse subsets can be in several cases of metric spaces, like bit strings with Hamming distance, graphs with edit distance, simple polygons inside a unit square with area-of-symmetric difference or Hausdorff distance, or Frechet distance of the boundary. We give upper and lower bounds in these cases and others.

This research is joint work with Fabian Klute and it appeared in WG 2022.

Set visualization deals with visual methods to support people understand and make sense of sets, their elements, and relations thereof. Existing methods such as Euler diagrams, Venn diagrams, and bi-partite node-link representations focus on communicating set memberships, their cardinality, and their possible intersections. However, designing visual representations of uncertain sets appears to be challenging. This is mainly due to the fact that not only the data $D$ themselves need to be encoded visually, but also the information about their uncertainty $U$ needs to be communicated to a reader. Above all, set visualization users must be able to extract all the encoded information (about the data and their uncertainty) from the visualization, which can be formulated abstractly as a pipeline:

The visualization designer defines a mapping $m$ of data $D$ and uncertainty $U$ to create a visual representation $V$. Through an interpretation $i$ of the visual representation $V$, human observers extract their own versions of data $D^{\prime }$ and uncertainty information $U^{\prime }$. The scientific challenge is to understand the cognitive process of $i$ and to devise mappings $m$ so that ideally $D=D^{\prime }$ and $U=U^{\prime }$ for all human observers. The congruence of $D$ and $D^{\prime }$, as well as $U$ and $U^{\prime }$, can serve as a guiding principle for the visualization of uncertain data.

While set visualizations themselves are an active research frontier there are far fewer research activities in the understanding of the implications of uncertainty for set visualization. In the first place, it is still unclear how uncertainty is defined in the context of set-type data. Only if we know what types of uncertainty are relevant for set type data can we design expressive visual representations of uncertain sets. Therefore, we conceptualized uncertainty in the context of set visualization by examining (a) which aspects of set-type data might be affected by uncertainty, and (b) which characteristics of uncertainty might influence the visualization design.

Undeniably, uncertainty bears the notion of something being known, unknown, vague, and/or containing varying accuracy. So, the starting point of our discussion centered around specifying what is known and what is unknown. In a perfect world, we know the data and we assume that they are accurate. For set-type data this means that we know for certain all elements, all existing sets, and the set membership of each element. There are also associated data attributes we know with certainty, for example, set size as an important derived set attribute. There may be further data attributes given for elements or sets for which we know their data values with certainty (e.g., the number of female members of a team). Given these data characteristics ($D$), the visualization of set-type data is primarily concerned with communicating (i) set membership, (ii) set properties, and (iii) associated data attributes. An overview of suitable visualization methods for the cases where set characteristics are certain is available in [1].

While we might believe to know things accurately in a perfect world, in the real world, however, there is certainty about uncertainty ($U$) surrounding us. Just take the weather predictions, for example, and the often heard statement “There is a 70% chance of rain tomorrow” on your favorite weather app. We thus asked ourselves, how much do we actually know about data uncertainty? In a perfect world, we know that there exists no uncertainty at all, which we denote as $U=0$. In the real world, however, one can distinguish two scenarios. First, we know that there is uncertainty, but we cannot tell accurately where it is, what it is, or how much of it exists. In other words, we know for a fact that uncertainty is present in our data, but no further details. We denote this as $U>0$. In the second scenario, we not only know that uncertainty exists in our data, but we also know with certainty where, what, and how much of it exists in our data. For the sake of simplicity, we denote this as $U=p$. The letter $p$ is a strong simplification of what could be known about the uncertainty in our dataset. Depending on the given data characteristics we are interested in, $p$ can take different forms. When set membership of an element $a$ and a set $X$ is certain, one can say either $a\in X$ or $a\notin X$. Under uncertainty, $p$ might denote a probability of $a$ being a member of $X$, $P(a,X)=p$, which is a notation known from fuzzy sets. In this case, $p$ can be understood as a plain probability value. Yet, we could also say that $p$ denotes a more complex probability distribution (e.g., $p=𝒩(\mu ,{\sigma }^2)$) based on which set membership is decided. Also, in relation to the data attributes of elements or sets, we may understand $p$ as the probability value of an attribute taking a particular data value. The same holds for the notion of $p$ being a probability distribution. Additionally, it is common for uncertain attribute values to specify them via a range of possible values, in which case $p=[l,u]$ is some interval with a lower and upper bound of $l$ and $u$.

Overall, the discussion of the characteristics of set data $D$ and the types of uncertainty $U$ led us to a conceptual framework of uncertainty in set visualization. In terms of $D$, the framework distinguishes: set membership, set attributes, and element attributes. Related to $U$, we use the different plausible types of (un)certainty: certainty ($U=0$), uncertainty as a binary fact ($U>0$), and uncertainty as quantifiable measure ($U=p$). We captured the framework in a table whose columns and rows respectively represent $D$ and $U$, as shown in fig. 7.

Based on this conceptual framework, we then systematically discussed possible visualization designs to illustrate examples and highlight challenges of integrating uncertainty in set visualizations. Three subgroups were formed, each working on a selected data characteristic (i.e., table column). As a baseline, each subgroup used the simple case of a visual representation with zero uncertainty ($U=0$). The group that dealt with set membership worked with bi-partite node-link and matrix representations, which were gradually expanded to include unknown uncertainty ($U>0$) and known uncertainty ($U=p$) by varying the visual encoding of links and matrix cells as indicated in fig. 8.

Set attributes turned out to be particularly challenging to visualize when uncertainty is involved. The reason for this is that derived data attributes depend by definition on other data characteristics, which also can include varying levels of uncertainty. For example, set size depends on set memberships. Leaving this particular challenge for future work, the subgroup designed and discussed visual representations where set attributes do not depend on other factors. They came up with node-link-style representations as shown in fig. 9. Sets are represented as bigger nodes being linked to their belonging set elements, which are depicted as smaller nodes. The set attributes are shown as pie charts within the bigger nodes, where color hue indicates certain attribute values and hatching marks uncertain set elements. The same encoding is applied to the attributes of the individual set elements on the smaller nodes.

Finally, one subgroup worked on visualizing uncertain element attributes. Their focus was not so much on coming up with new designs, but to review the existing knowledge about general uncertainty visualization. For example, cartography has a long history in working with uncertain data, but also the visualization community studied this topic in detail. Particularly, the works by Alan MacEachren et al. [5, 6], Kristin Potter et al. [7, 8, 2], Amit Jena et al. [4], and Theresia Gschwandtner et al. [3] offer profound insight into how uncertain data values can be encoded visually, and to what degree humans can interpret and understand the depicted information. With these general considerations, the table of the developed conceptual framework could be filled completely. Based on the intense and productive discussions centered on the conceptual framework for set visualization and uncertainty, we drafted an outline for a journal article that will summarize key results of the research conducted at the Dagstuhl-Seminar. Our planned article will also include a synthesis of recommendations to be considered when designing visualizations for uncertain set data and an outline of future research directions.

This working group consisted of (in alphabetical order) Michael Behrisch, Susanne Bleisch, Sarah Fabrikant, Eva Mayr, Silvia Miksch, Helen Purchase, and Christian Tominski (see fig. 10). Helen Purchase headed the group. Christian Tominski drafted this report. All members of the team contributed significantly to the discussions, provided feedback and edited this report, and will be co-authors of the planned journal article.