Perception in Network Visualization

Visualization has a long tradition of drawing on insights from human perception to inform effective design. In this talk, we review basic perceptual phenomena, including visual attention, visual search, and grouping, to highlight their basic mechanics and how they have been applied in past visualization design guidelines and experiments. We connect each phenomenon to past studies in network visualization to highlight key potential crossover between the fields and scaffold workshop discussion.

The term “perception” is used broadly in computer science, and can refer to a broad range of human behaviors. This talk painted an overview of the many, often parallel, processes involved when we interact with network representations, and with the world in general. Low level visual perception focuses on retinal processes such as sensing luminance and color variations, and the impact of differences in foveal and peripheral resolution. Early cortical processes provide binocular vision and enable low-level feature perception. The organization of these features into a unified whole is managed by processes of perceptual organization and attention. And cognitive processes imbue them with semantic meaning, enable memory, and support decision making. Emotion and aesthetic perception, often shaped by culture and experience, also contribute to our visual experience. Moreover, vision does not operate in a vacuum. We are simultaneously hearing, smelling, touching and moving through our world, guided by our intentions, tasks and desires. This is a “food chain,” in the sense that projections feed from sensors to cortex to higher centers, often called “bottom -up,” but it is really more of a network, with important “top down” feedback and modulation.

In this presentation, we reviewed key topics in early vision. The human visual system is designed to register variations in sensory stimuli. The absolute luminance is less important perceptually than the contrast, the difference between the highest and lowest luminance values, and our sensitivity to contrast depends on the way those luminance variations play out over space. In network visualization, there needs to be sufficient luminance contrast to make out nodes, edges, arrows and annotations, and the finer the spatial detail, the higher the required luminance contrast. Even for colored visualization features, like yellow or red edges on a gray background, legibility depends on luminance contrast.

Moving up the food chain, we can ask how visual information is organized perceptually. In the 1920, researchers from the Berlin School of Experimental Psychology developed a paradigm-shifting approach to studying perception. They focused not on bottom-up constructionist ideas of perception, but instead introduced the idea that top-down processes organized individual elements into Gestalts. The visual system actively constructs visual impression, causing us to perceive sets of elements as wholes. Principles such as proximity, continuity, symmetry and closure can be seen working when we extract perceive structures embedded in graphs. For small graphs, it may be easy to identify clusters or pick out embedded structures. But, how robust are these organizational forces when graphs become very large?

Humans are not passive recipients of visual information. We active move our bodies and our eyes to make sure that we can register important features. Some of these processes are bottom up. An object that has a different color from its surroundings or a different movement or orientation will attract our attention. Some types of low-level patterns are perceived instantly, no matter how many objects there are in the background. Others take time to suss out, and the more objects, the longer it takes to scrutinize the field to find them. In visualization, we can use these bottom-up cues to attract attention to features of interest. For example, marking a critical edge red will draw our attention to it automatically, marking all the nodes belonging to a class red will automatically group them together perceptually, even if they are not near each other spatially. There are so many visual cues bombarding our senses all the time that our perceptual system need mechanisms to segregate them into categories, and we can make use of these capabilities in network visualization to, for example, segregate sets of nodes by assigning them to a common color. We can even use hue to interactively “paint” a set of nodes in one network, and if that color is “brushed” onto corresponding nodes in another network, we see the correspondence immediately.

As we move up the food chain, we are struck by the powerful forces of top-down perception. As we said, we direct not only to low-level features that attract our attention, but to those objects that will give us information about the world. What we are trying to learn about the visual scene guides our gaze and our attention. This is especially important for high-level tasks like pattern recognition and decision-making. The layout of the graph will afford different types of visual observations, and different tasks will drive how we explore a visualization visually. Creating visualizations, thus, requires thinking about the intended audience, the task, and the multitude ways of representing data and relationships.

As we move up the food chain, individual differences play an increasing part in perception. The ability to detect and identify luminance, color, spatial, and movement is similar for everyone. However, where and how you look at a visualization, and what meaning you extract, depends on your training and experience. Some judgments, like naming colors, can depend on your cultural and linguistic background. The ability to perceive hidden shapes in a complex environment may not only reflect your spatial intelligence, but may even be tied to your personality. And at the top of the food chain, aesthetic judgments vary wildly from person to person, encompassing emotional and societal factors.

In network visualization, thus, we are not simply mapping data and relationships onto visual marks. These renderings are processed by the same mechanisms that have evolved to help us perceive and act in all the environments we encounter. Understanding how these mechanisms work, independently and together, can help guide the design of visualizations, and studying how human observers perceive and explore different visual metaphors can, likewise, help advance our understanding of visual perception.

The quality of a graph drawing can be measured in terms of its (1) faithfulness and (2) readability. There have been three kinds of algorithms proposed and deployed for graph drawing – planarity-based methods, force-directed methods, and layered drawing. The performance of these methods against faithfulness and readability requirements varies, especially with respect to scale – performance on large graphs differs from performance on small graphs. For large graphs, finding visual proofs of assertions seems to be a promising research direction.

In our daily life, to perceive and correctly recognize objects is key. We have to quickly process food, have to decide whether it’s good or bad, healthy or lethal. We have to tell partners, friends and enemies apart. But looking behind the scenes of everyday perception we have to realize that the percept of an object is a mental construction. We cannot perceive the object, our cognitive apparatus makes believe we perceive a certain very determined object. Consequently we have to understand perception to understand how we perceive, asses and understand the object. Perception-based analysis will also help to understand emotional and personal reactions triggered by objects.

When visualizing a high-dimensional dataset, dimension reduction techniques are commonly employed which provide a single 2 dimensional view of the data. We describe ENS-t-SNE: an algorithm for Embedding Neighborhoods Simultaneously that generalizes the t-Stochastic Neighborhood Embedding approach. By using different viewpoints in ENS-t-SNE’s 3D embedding, one can visualize different types of clusters within the same high-dimensional dataset. This enables the viewer to see and keep track of the different types of clusters, which is harder to do when providing multiple 2D embeddings, where corresponding points cannot be easily identified. We illustrate the utility of ENS-t-SNE with real-world applications and provide an extensive quantitative evaluation with datasets of different types and sizes.

Working group members: Tim Dwyer, Peter Eades, Henry Förster, Seok-Hee Hong, Felix Klesen, Stephen Kobourov, Giuseppe Liotta, Kazuo Misue, Fabrizio Montecchiani, Alexander Pastukhov, and Falk Schreiber

The working group discussed scenarios where it is necessary to convince an audience that a particular graph has some structural property. We assume that a prover already knows that the assertion is true. A visual proof is a visual representation used to convince a third party who does not know the proof. Visual proofs are commonly used in different areas of science to show the truth of a statement or to support an argument. Figure 1 provides on overview of our concept for visually proving an assertion about a given graph. The prosecution lawyer (prover) shows evidence for the assertion in a visual certificate drawing of the graph. In order to convince the judge (third party who does not know the proof), the visual proof must guide the judge’s perception to form a mental model that makes the assertion easy to understand and validate. In addition, the visual proof needs to be entirely trustworthy as otherwise a defense lawyer may raise doubts about the validity of the prosecution lawyer’s claims.

Visual proofs have some key differences to the standard motivations for network visualization. While typical network visualization approaches often seek a representation which shows as many graph properties as possible simultaneously, a visual proof may focus on showing optimally just one specific property. Also, common aesthetic criteria for network layout may not hold for specific visual proofs. A simple examples of a visual proof is proving that there is a cut vertex (i. e. that the graph is not biconnected). This is trivial: put the cut vertex in the middle and show that after removing there are two or more components. Figure 2 shows visual proofs for this property, the right drawing is better than the left drawing as it is clear there is no edge bypassing the cut vertex. We found a number of other easy examples initially, however, the problem turned out much more challenging quite quickly.

After initial discussions about the idea of visual proofs for network properties, the working group focused on two major areas: developing and formalizing the general concept of visual proofs for graph properties (see also Figure 1), and discussing and structuring examples for properties and related proofs. Research questions discussed included

• $\mathrm{■}$

  How can we visually prove properties of graphs?

• $\mathrm{■}$

  What does it mean to visually prove a property?

• $\mathrm{■}$

  What makes a good visual proof?

• $\mathrm{■}$

  What is a good formalization?

• $\mathrm{■}$

  What layout (or other graphical representation) is optimal with respect to proving a particular property?

• $\mathrm{■}$

  What is the relationship between visual complexity and complexity theory?

• $\mathrm{■}$

  What classes of properties are visually provable?

• $\mathrm{■}$

  When is the opposite of a property easy, when difficult to prove visually?

The working group continued after the Dagstuhl Seminar to further develop ideas, concept and examples, and recently submitted a paper describing the concept and applications of visual proofs of network properties.

Working group members: Carsten Görg, Cindy Xiong, Danielle Szafir, and Paul Rosen

Working group members: Tamara Mchedlidze, Alexandru C. Telea, Marius H. Raab, Christophe Hurter, Natalia Melnik, Martin Nöllenburg, and Bernice E. Rogowitz

The quality of data visualizations is typically assessed through their conformance to drawing styles and conventions and by measuring quality metrics. Drawing styles and conventions aim to provide a certain quality standard of a graph drawing, but do not explicitly measure it, while quality metrics measure the quality aspect of a graph drawing without an algorithmic way to optimize it. Drawing styles and conventions and quality metrics originating from a variety of perspectives, are complementary tools, but are rarely systematic. Our working group discussed approaches to systematize and unify currently existing metrics and conventions in a single framework for assessing graph visualization quality. During this Dagstuhl Seminar, we discussed the possibilities of integrating the abilities and peculiarities of the human perceptual system (what we here refer to as “perceptual principles”) into a unified visualization pipeline (Figure 3).

Perception plays an important role in how humans judge and perceive visual information. One phenomenon that strongly affects one’s perception is grouping. Perceptual grouping refers to processes in which discrete elements (“parts”) are parsed into groups (“wholes”) by the visual system, following so-called Gestalt principles [7]. In a typical example, rows of dots positioned closer together are perceived as grouped together more than the rows of dots that are sparely positioned (i.e., proximity principle). Such grouping is, for instance, one of the targeted perception optimization for graph visualization [22]. However, some similarities between the graph drawing and perceptual grouping can be observed. For example, in graph drawing, in stress model [12], edges are shortened, so that the related nodes are placed closer together and thus appear as grouped together. While there are clear differences between the mechanisms behind Gestalt perception and graph drawings, the outcome product can be seen as analogous: the items appear as grouped.

From this starting point we made progress by analyzing specific drawing styles and conventions and quality metrics, relating them to a list of perception principles. Our initial focus included such Gestalt principles as proximity, symmetry, common fate, closure, similarity, common region, and good continuation, as well as such additional concepts as curvature, visual complexity and global aesthetics, and clutter. Our analysis revealed that drawing styles and conventions and quality metrics often rely on one or another perception principle, at least to some extent. For instance, global shape, bundling, and number of crossings reflect the Gestalt principle of similarity. We acknowledge that some of the metrics will reflect a complex combination of perception principles. However, we believe that they can nevertheless be formally described. After the description, the sample space of all possible variations of the metrics can be measured and new graph layouts can be computed. How to effectively measure the space and design quality metrics from the measured spaces, still remains an open question though. Our connecting of metrics with perceptual principles can help, e.g., people choosing sets of metrics to optimize simultaneously (because they relate to the same principle) or, alternatively, see which tasks will be helped when optimizing certain metrics.

We believe that quality metrics can be also ordered along a hierarchical spectrum (i.e., low, mid, and high), potentially adhering to the hierarchical spectrum of visual perception (low-, mid-, high-level vision). Generic attributes of the drawings, which are typically less data- and less task-specific (to give a few examples: number of bends, or number of crossings) and are easier to quantify and measure automatically, could correspond to low-level perception. Other quality measurements are more data- and task-specific, and can thus be seen as high(er) level. They are typically the ones quantified by user experiments. Interestingly, there is a problem: good low-level metrics values do not imply good high-level metric values, and conversely. For example, a drawing may have few crossings, but a path-following task might still be hard without monotonicity of the paths [15]. The other way round: A drawing might not be symmetric in a strictly mathematical sense, but might appear symmetric due to local regularities [9] or the global shape [8]. While the metrics near the endpoints of the spectrum are relatively easy to identify, how exactly to order the metrics at the mid-level (potentially symmetry, bundling quality, clutter, complexity) is an open question. Additionally, there is a need for ways to measure some higher-level quality properties, e.g., global aesthetics. The challenge is that it is unclear how to reduce these to easily measurable properties, e.g., curvature or shape. The end product could be to be able to derive an aesthetics function a(D, f(D)) from a good set of samples (D, f(D)) of graph drawings D and their corresponding lower-level metrics f(D).

To sum up, our working group proposed the first steps towards the creation of a framework that unifies quality metrics and drawing conventions based on human perception. We suggest that new metrics and drawing conventions can be developed for perceptual mechanisms which are not reflected by the current metrics or conventions. We hope that the connection between the perceptual principles and the metrics can aid in optimization of certain aspects that relate to the same perceptual principle or development of tasks in order to see which ones will be improved when optimizing certain metrics. We ended up the Dagstuhl week with the intention to further develop the framework and publish a paper related to it.

Working group members: Annika Bonerath, Claus-Christian Carbon, Silvia Miksch, Maurizio Patrignani, and Alessandra Tappini

Several user studies were performed to assess the ability of people to use maps, graphs, or other abstract representations of the relationship between objects in a spatial environment. In this report, we describe how a user study can be designed to address the complex scenario when the user has to cope with a network that is dynamic both with respect to nodes (that are “available” or “unavailable” in specific time windows) and with respect to edges (that change their congestion through time).

Working Group members: Carolina Nobre, Daniel Archambault, Rita Borgo, Andreas Kerren

Working group members: Michael Aichem, Mohammad Ghoniem, Christophe Hurter, Karsten Klein, Oliver Kohlbacher, Mauro Martino, Jacob Miller, Helen C. Purchase, Bernice Rogowitz, Markus Wallinger, and Hsiang-Yun Wu