Human Similarity Notion of Graphs for Visual Comparison

The question of similarity, commonalities or differences of two objects to be compared seems so simple. We humans just do it every day. At the bakery, we decide we’d rather have that bread and not the other one because the other one is baked darker (baked darker = difference). While shopping, we decide against a t-shirt because it has too much in common with the one we already have in our closet. When analyzing the route for the travel to the vacation destination, we decide that a short visit of a friend is possible, because the routes with and without the detour are very similar to each other (= analysis of a graph with geo-location). Due to the fact that we are confronted with these judgments every day and in the most diverse situations, we are not aware of the complex processes that take place for answering the question of commonalities and differences and finally for the similarity, and which versatile influencing factors have an effect on these processes. This complexity and versatility makes answering these questions, which actually seem so simple, so challenging – both from the mathematical, theoretical perspective and from the perspective of a person who compares. For graphs and their similarity, this can be seen in the variety of different similarity measures that exist. Furthermore, an edge added to a tree consisting of five nodes – i.e., a graph consisting of five nodes in which each node has only one parent node – can be interpreted graph theoretically in a variety of ways: The change can be seen as an added edge. All parts of the graph have remained the same – only the one edge is new and thus a difference. Similarly, the change can be seen as a node getting another parent node. This means that it is no longer just the added edge that is different, but also the node that got another parent node. Another possible interpretation of the change is that the tree has now become a directed, acyclic graph – that is, the whole graph has changed. In summary, the resulting commonalities and differences depend on the level of abstraction chosen. When asked to make a similarity judgment, people judge the similarity of small pairs of graphs that have the same change (an added node and an edge at the first hierarchy level), that are comparable in structure, and that are only approximately doubled in number of nodes, strikingly different. This is remarkable because, from a graph-theoretic point of view, both pairs of graphs are more similar – for example, both changed graphs remain a tree, the out-degree of each root node increases by one, and the number of nodes at the first hierarchical level of each changed graph increases by one. Consequently, it appears that the human similarity notion (HSN) diverges from the mathematical one. This divergence has been found for other types of data as well. For differences and commonalities, humans give comparably diverse answers as graph theory. For human judgments of commonalities and differences, or of similarity, the differences are not yet as well explained as for graph theory, because foundational knowledge about visual comparisons, such as the factors that influence human notions of graph similarity, is still missing. Therefore, my dissertation aims to understand the human similarity notion of graphs. This includes, among other things, identifying the influencing factors and proceeds to improve node-link graph visualizations based on the newly gained knowledge about, for example, the influencing factors. Addressing my research goals for a broader range of graph, comparison, or visualization types would have been too broad. So I narrowed down the field using the principle of “strongest prevalence” – that is, I researched the current body of work to determine which graph, comparison, and visualization types were most common. With this I came to the following delimitation:
• Graph type → directed acyclic graph (DAG)
• Comparison type → pairwise → juxtaposed
• Visualization type → node-link diagrams
The central contributions of my research to understanding the HSN of directed acyclic graphs are the identification of factors influencing the HSN, the improvements of pairwise node-link visualizations with a graph layout specifically for comparisons, and a neural network that learns which differences in DAGs are recognized by humans. Used in a visual comparison system, this neural network can help to bring together the mathematical and human notions of similarity. Likewise, the network can help bring to the human’s attention what has actually changed in the DAGs and what the human has recognized as a difference (keyword: mitigating human biases). The layout helps differences in visual comparisons to be more easily recognized – thus facilitating the overall visual comparison and formation of the similarity judgment for humans. Knowing the influencing factors clarifies how optimized a comparative visualization needs to be. When people consider more factors, the visualization designer must also consider and optimize more factors in the overall visualization design than when fewer factors have an impact on the human notion of similarity. Understanding the specifics of the factors helps us learn the details of the similarity notion; for example, the average number of factors used across all participants gives us an estimate of the limit of influencing factors that people consider for their similarity judgments in the context of visual pairwise comparison. Detailed knowledge of the human similarity notion is valuable for future HSN-aware, mathematical similarity functions because, among other things, it tells us how many factors such a function should consider. As for my work on advances in measuring human similarity judgment, replicability and creation of experimental datasets, the visual-interactive system SampleSelector is to be mentioned. SampleSelector supports the entire sample selection process and is able to uncover white spots – i.e., missing combinations of properties relevant to the experiment – in the selected data that are obfuscated when the examiner uses only data-only tables and visualizations of the selected data items themselves.

Die Frage nach Ähnlichkeit, Gemeinsamkeiten oder Unterschieden von zwei zu vergleichenden Objekten wirkt so einfach. Wir Menschen machen das einfach jeden Tag. Beim Bäcker entscheiden wir uns dafür, dass wir lieber das Brot möchten und nicht das das andere, weil das andere dunkler gebacken ist (dunkler gebacken = Unterschied). Beim Einkaufen entscheiden wir uns gegen ein T-Shirt, da es mit dem, das wir bereits im Schrank haben, zu viele Gemeinsamkeiten hat. Bei der Routenanalyse für die Fahrt in den Urlaub entscheiden wir uns dafür, dass ein kurzer Besuch bei einem Freund möglich ist, da die Routen mit
und ohne den Abstecher einander sehr ähnlich sind (= Analyse eines Graph mit Geo-Position). Dadurch, dass wir jeden Tag und in den unterschiedlichsten Situationen mit diesen Beurteilungen konfrontiert sind, ist uns nicht bewusst welche komplexen Prozesse für die Beantwortung der Frage nach Gemeinsamkeiten und Unterscheiden und final nach der Ähnlichkeit ablaufen und welche vielseitigen Einflussfaktoren auf diese Prozesse einwirken. Diese Komplexität und Vielseitigkeit macht die Beantwortung dieser eigentlich so einfach erscheinden Fragen so herausfordernd – sowohl aus der mathematisch, theoretischen Perspektive als auch aus der Perspektive eines Menschen, der vergleicht. Für Graphen und deren Ähnlichkeit ist das daran zu erkennen, dass es eine Vielzahl unterschiedlicher Ähnlichkeitsmaße gibt. Des Weiteren ist eine Kante, die zu einem Baum bestehend aus fünf Knoten – d.h. ein Graph aus fünf Knoten in dem jeder Knoten nur einen Vaterknoten hat – graphtheoretisch auf unterschiedlichste Weisen interpretierbar: Die Änderung kann als hinzugefügte Kante gesehen werden. Alle Teile des Graphen sind gleich geblieben – nur die eine Kante ist neu und damit ein Unterschied. Ebenso kann die Änderung darin gesehen werden, dass ein Knoten einen weiteren Vaterknoten bekommen hat. Das bedeutet, dass nicht mehr nur die hinzugefügte Kante unterschiedlich ist, sondern auch der Knoten, der einen weiteren Vaterknoten bekommen hat. Eine weitere mögliche Interpretation der Änderung ist, dass aus dem Baum nun ein gerichteter, azyklischer Graph geworden ist – d.h. der ganze Graph hat sich verändert. Zusammenfassend lässt sich sagen, dass die resultierenden Gemeinsamkeiten und Unterschiede von der gewählten Abstraktionsebene abhängen. Bei der Frage nach einem Ähnlichkeitsurteil beurteilen Menschen die Ähnlichkeit von kleinen Graphenpaaren, die die gleiche Änderung – einen hinzugefügten Knoten und eine Kante auf der ersten Hierarchieebene aufweisen, in ihrer Struktur vergleichbar sind und nur in der Anzahl der Knoten ungefähr verdoppelt sind, auffallend unterschiedlich. Dies ist bemerkenswert, da aus graphentheoretischer Sicht beide Graphenpaare ähnlicher sind – z.B. bleiben beide veränderten Graphen ein Baum, der Ausgangsgrad jedes Wurzelknotens erhöht sich um eins, und die Anzahl der Knoten auf der ersten Hierarchieebene jedes veränderten Graphen erhöht sich um eins. Folglich scheint es, dass der menschliche Ähnlichkeitsbegriff" (HSN) von dem mathematischen abweicht. Diese Divergenz wurde auch für andere Datentypen festgestellt.
Für Unterschiede und Gemeinsamkeiten geben Menschen vergleichbar unterschiedliche Antworten wie die Graphentheorie. Für menschliche Einschätzungen von Gemeinsamkeiten und Unterschieden bzw. von Ähnlichkeit sind die Unterschiede noch nicht so gut erklärbar wie für die Graphentheorie, da grundlegendes Wissen über visuelle Vergleiche, wie zum Beispiel die Faktoren, die den menschlichen Ähnlichkeitsbegriff von Graphen beeinflussen, noch fehlt.
Daher hat meine Dissertation zum Ziel den menschlichen Ähnlichkeitsbegriff von Graphen zu verstehen. Das beinhaltet u.a. die Identifikation der Einflussfaktoren und geht dazu über Node-Link Diagramm Visualisierungen auf Basis des neu gewonnenen Wissen über zum Beispiel die Einflussfaktoren zu verbessern. Meine Forschungsziele für ein breiteres Spektrum an Graph-, Vergleichs- oder Visualisierungstypen anzugehen, wäre zu weit gefasst gewesen. Also habe ich den Bereich nach dem Prinzip der “häufigsten Vorkommen” eingegrenzt – d.h. ich habe in existierenden Arbeiten recherchiert, welche Graph-, Vergleichs und Visualisierungstypen am häufigsten vorkommen. Hiermit kam ich zu folgender Eingrenzung:
• Graphtyp → gerichteter, azyklischer Graph (DAG)
• Vergleichstyp → paarweise → nebeneinanderliegend (juxtaposed)
• Visualisierungstyp → Node-Link Diagramme
Die zentralen Beiträge meiner Forschung zum Verständnis des menschlichen Ähnlichkeitsbegriffs von gerichteten, azyklischen Graphen sind die Identifikation der Einflussfaktoren auf den menschlichen Ähnlichkeitsbegriff, die Verbesserungen von paarweisen Node-Link Vergleichsvisualisierungen mit einem Graphlayout speziell für Vergleiche und einem neuronalen Netz, das lernt welche Unterschiede in DAGs von Menschen erkannt werden. Eingesetzt in einem visuellen Vergleichssystem kann dieses neuronale Netz helfen den mathematischen und den menschlichen Ähnlichkeitsbegriff zusammenzuführen. Ebenso
kann das Netz helfen dem Menschen vor Augen zu führen was sich tatsächlich in den DAGs geändert hat und was der Mensch als Unterschied erkannt hat (Stichwort: Abmilderung menschlicher Bias). Das Layout hilft dabei, dass Unterschiede in visuellen Vergleichen leichter erkannt werden – somit wird der gesamte visuelle Vergleich und die Bildung des Ähnlichkeitsurteils für Menschen erleichtert. Das Wissen um die Einflussfaktoren stellt klar, wie optimiert eine vergleichende Visualisierung sein muss. Wenn Menschen mehr Faktoren berücksichtigen, muss der Visualisierungsdesigner auch mehr Faktoren im gesamten Visualisierungsdesign berücksichtigen und optimieren, als wenn weniger Faktoren einen Einfluss auf den menschlichen Ähnlichkeitsbegriff haben. Das Verständnis der Spezifika der Faktoren hilft uns, die Details des Ähnlichkeitsbegriffs zu lernen; zum Beispiel gibt uns die durchschnittliche Anzahl der
verwendeten Faktoren über alle Teilnehmer eine Schätzung der Grenze der Einflussfaktoren, die Menschen für ihre Ähnlichkeitsurteile im Kontext des visuellen Vergleichs berücksichtigen. Detailliertes Wissen über den Ähnlichkeitsbegriff ist wertvoll für zukünftige HSN-sensitive, mathematische Ähnlichkeitsfunktionen, da es uns u.a. sagt, wie viele Faktoren eine solche Funktion berücksichtigen sollte. Was meine Arbeiten zu Fortschritten bei der Messung menschlicher Ähnlichkeitsurteile, Replizierbarkeit und Erstellung von Versuchsdatensätzen angeht, ist das visuell-interaktive System SampleSelector zu nennen. SampleSelector unterstützt den gesamten Sample-Selection-Prozess und ist in der Lage, weiße Flecken – d.h. fehlende Kombinationen von Eigenschaften, die für das Experiment relevant sind – in den selektierten Daten aufzudecken, die verschleiert werden, wenn der Untersuchungsleiter nur reine Datentabellen und die Visualisierung der selektierten Datenelemente selbst verwendet.