What is graph uncertainty and how can analysts visualize probabilistic graphs?
This post describes our recent work titled “Visualizing Uncertainty in Probabilistic Graphs with Network Hypothetical Outcome Plots (NetHOPs)” by Dongping Zhang, Eytan Adar, and Jessica Hullman, to be presented at IEEE VIS 2021.
1. Graph Uncertainty
Node-link diagrams are a pervasive way to visualize networks. Typically, when we see an edge connecting two vertices in a node-link diagram, we assume the relation (e.g., friendship or advice-seeking) it represents exists. However, this assumption can be problematic because it neglects the uncertainty that often affects our measurements of edge occurrence.
So what is graph uncertainty? This uncertainty arises from network data collection. Networks are typically constructed using data from surveys, field observations, archival records, or digital traces. Even when we think we are capturing deterministic relationships, we can rarely assume this. For example, the collected data often comes in the form of interaction frequencies, meaning analysts can record the number of actors who think or claim an edge to occur. Nevertheless, how can we differentiate a tie reported by 10 actors versus another tie reported by 5 actors? Should we treat them equally or differently?
In the network analysis pipeline, analysts can use different statistical models to impute or infer dependent or independent edge probabilities (so-called “the link prediction problem”). But once edges become probabilistic, how can an analyst use common representations like node-link diagrams to conduct exploratory network analysis?
One might argue we can still communicate edge uncertainty through the use of different visual encodings (e.g., width, fuzziness, or grain). The truth is the rendered graph is often difficult to visually assess for practical use.
For example, try using the figure above to do some basic graph analysis tasks, like determining “What is the in-degree of node 9?” or “What is the shortest path between node 9 and 16?”. It’s not so easy. This is because probabilistic graphs tend to be maximally connected: all edges with non-zero weights need to be present in the graph. This can create tremendous visual clutter, such as overlapping edges. Analysts must also rely on the visual channel not only to gain probability information about a single edge (e.g., “Is there a tie connecting 9 and 16?”) but also to simultaneously integrate and process the joint probability from multiple edges (e.g., “Can you estimate the overall graph density?”). Finally, certain common network analysis tasks, like identifying community structure, are subject to uncertainty with probabilistic graphs but pose additional challenges for visual analysis. For instance, how can the node-link diagram support cluster detection when clusters are determined by edges that are uncertain?
2. Uncertainty Visualization
When thinking about different approaches to address the challenges with exploratory visual analysis of probabilistic graphs, we considered alternatives to static ways of encoding probability like edge stroke width. One such alternative is the frequency-based uncertainty visualization technique called Hypothetical Outcome Plots (HOPs), shown applied to a simple 2D visualization above. HOPs dynamically visualize a set of draws sampled from a distribution, making them useful for communicating uncertainty in cases where the visualization is already complex (e.g., many of the preferred visual channels like position are already used to show the data). Perceptual research has also found that temporal frequency encoding can help viewers to extract frequency information automatically and unintentionally, and it can also support intuitive estimations of event probabilities or even joint probabilities.
3. Network Hypothetical Outcome Plots (NetHOPs)
We developed Network Hypothetical Outcome Plots to address some of the challenges with visualizing probabilistic graphs. As illustrated below, there are four main steps to construct NetHOPs.
Step 1: Construct Probabilistic Graph
We start with a probabilistic graph as input. The first step is to infer or approximate the probability of each edge occurrence within a network. After assigning probabilities as an edge attribute, the input graph has a fixed node-set and probabilistically weighted edges.
Step 2: Sample Network Realizations
The probabilistic edges allow us to create a random graph model, which creates a data generating process enabling us to sample network realizations. However, we cannot just animate these realizations off the bat. The dynamic layout algorithms (e.g., the force-directed layout and stress minimization) are designed to optimize aesthetic constraints, like minimizing edge crossings and overlapping vertices, to generate a meaningful layout for a single static graph.
However, when applied directly to sampled realizations, this can result in very different layouts each time. As shown above, the animation will likely be ineffective because layout differences would distort the viewer’s mental map when they tried to estimate network properties under uncertainty.
Step 3: Layout engineering to preserve analyst’s mental map
To help an analyst preserve a mental map of how nodes are arranged across realizations, we need to engineer the layouts. After sampling a sufficient set of N samples, we can compute a reference layout through an offline drawing approach called aggregation. The reference layout determines each node position by the mean theoretical distance of the corresponding node pairs summarized from all sampled realizations of the set, which produces the most stable layout since it places all nodes in fixed positions throughout the animation.
However, if we animate all realizations using the reference layout shown above, viewers would lose some visual information of some structural configurations that are crucial to better grasp the uncertainty of targeted network statistics. Hence, we need to navigate the trade-off between layout stability and layout readability to find an appropriate balance that allows mental map preservation while still conveying useful information about how the graph structure changes across frames.
Therefore, we can use the reference layout as a baseline to adjust individual layout differences through a technique called anchoring. The trade-off between layout stability and readability can be parametrized by an anchoring parameter, ɑ. As shown below, setting ɑ = 0 emphasizes individual layout differences with no mental map preservation. On the other hand, setting ɑ = 1 produces the most stable reference layout. When setting alpha between 0 and 1, as alpha increases, layouts tend to become more stable because the reference layout is weighted more when computing individual layouts.
Step 4: Match Clusters
Graph clustering is an important topic but is challenging for probabilistic graphs. It is similar to the thought experiment called “the Ship of Theseus” because it is difficult to identify communities when vertices change partially or entirely in sampled network realizations, as illustrated in row (A) of the figure below. If communities are unstable, we cannot assign consistent visual attributes like colors or convex hulls.
To address this challenge, we developed an instant-optimal cluster matching algorithm, which is a two-step process to analyze node stability in community structures and to assign stable community colors.
The algorithm first searches communities for each realization in the set. We then create a weighted full graph, which we call the “co-community graph.” Edge weights record the number of times a node pair has the same community membership. By thresholding edge weights, this co-community graph will decompose from a giant component, and isolate will emerge. Whenever a node becomes an isolate, we assign the threshold to the node as a “stability score” attribute. The larger the stability score, the more stable the node is across realizations. So we can prioritize color assignment to the more stable nodes. Lastly, we match the same color to the other vertices that belong to the same community in each network realizations.
Row (B) of the figure above presents the end result of our cluster matching algorithm. This algorithm is our solution to the “Ship of Theseus” problem, which enables NetHOPs to support topology-based tasks such as cluster detection.
4. NetHOPs User Study
While NetHOPs can technically solve the challenging problems of visualizing uncertainty in graphs, we weren’t sure how well NetHOPs would allow analysts to complete basic exploratory network analysis tasks. To answer this question, we conducted a user study and recruited 51 network experts to complete a set of common graph analysis tasks using NetHOPs.
We created two NetHOPs using David Krackhardt’s Cognitive Social Structure data shown left, which describe the advice-seeking and friendship relations among 21 managers in a high-tech firm. Both NetHOPs consist of 150 sampled realizations, and between the 2 networks, we can see the advice-seeking network has a higher density than that of the friendship.
Tasks
As shown in the table below, we develop six categories of tasks based on network task taxonomies.
Types of Responses
For attribute-based tasks, we asked for point estimates of the probability of certain network structures because they are either present or absent similar to a Bernoulli random variable. For topology, overview, and browsing tasks, we elicited user-perceived distributions using a frequency-based distribution sketching tool called the distribution builder, shown below.
We compared participants’ probability estimations and elicited distributions with the ground truth summarized from the 150 network realizations that comprised our NetHOPs. (After checking that the 150 network realizations we used were representative. Nevertheless, sampling error can still affect the ground truth, and we discuss this further in our paper).
Evaluation
We used Earth Mover’s Distance (EMD), which represents two distributions discretely and calculates the average distance points in the user distribution need to move to match the target distribution (ground truth), illustrated below.
Preset Visualization Parameters
To render NetHOPs, we experimented with what combination of visualization parameters (i.e., anchoring ɑ and frame rate) and graphical elements (e.g., edge opacity, convex hulls) seemed reasonable for the tasks with the goal of not adding any special visual features to support different tasks unless totally necessary.
Tuning Visualization Parameters
We had our participants complete all tasks twice: once with the presets and then again with the freedom to control NetHOPs rendering by tuning visualization parameters and graphical elements through sliders and buttons.
5. Results
Here briefly summarize our findings. You’ll find a more detailed discussion in our paper.
Performance on Distribution Elicitation Tasks
From (A) and (B) of the figure above, we can see the distributions of the EMD measures for each distribution elicitation task.
We noticed participants performed consistently well when tracking path lengths between selected vertices on both NetHOPs, despite the differences in the ground truth distributions between the two networks.
Participants were good at identifying isolates, perhaps because people tend to be visually sensitive to a lack of continuity between vertices.
Participants were able to perceive the distribution of distinct communities more accurately for the advice-seeking network. This result is not surprising because the ground truth distribution for the advice-seeking networks has a smaller variance. We also speculate another important reason is that realizations of the friendship NetHOPs have more overlapping communities, which makes the task more difficult.
Density estimation was one of the most difficult tasks for our participants. The averaged EMD measures for the two density tasks are much higher than the rest. But we found participants were able to estimate the density for the sparse friendship network better.
Performance on Probability Estimation Tasks
From (C) and (D) of the same figure above presents participants’ probability estimation error with 95% confidence intervals. We can see participants are more likely to underestimate probabilities for node-attribute tasks and overestimate for edge-attribute tasks. Participants’ probability estimates are not too far from the ground truth, with average performance within about 10% of the ground truth for many tasks.
Does Tuning Help?
We found tuning could slightly improve participants’ EMD measure, by 4% on average but not reliably. By inspecting the distributions of the performance metrics in the figure below, we can see that tuning did help some participants. To take a closer look, we identified top-performers and bottom-performers by ranking them by quartiles.
After pooling performance evaluation metrics by task types, we found top-performers, on average, were able to sketch more accurate distributions with a mean EMD score of 3.1 comparing with 7.8 of the bottom-performers. Top-performers estimated probabilities more accurately with a low error rate of 1.9%, comparing with the error amount of 14.3% by the bottom-performers. So we are interested to see how did these two groups of participants tuned visualization parameters and used graphical elements differently.
Starting with the layout stability, as shown in the top row of the figure below, we found stability seemed generally beneficial, even for tasks like density estimation that do not require stability. We think stability is likely related to density; the denser the network, the more stable layout was preferred. At the same time, participants almost never preferred maximal stability and can tolerate more node movements, especially for sparse networks.
For animation speed shown in the second row of the figure above, we found a consistent pattern that top-performers preferred on average 23% slower animation speed than bottom performers. This is intuitive because slower speed allowed participants to review each network realization more thoroughly and detect changes with greater accuracy. However, participants from both groups preferred faster animation speed on average when viewing the denser advice-seeking networks.
For visual aids, we computed the percentage of users who used each graphical element by task for both groups. We found top-performers tend to accentuate the salience of relevant network objects and chose to deactivate irrelevant visual features, likely, to prevent distractions. We have also observed some creative use of visual aids and think these add-ons can greatly reduce the risk of change-blindness and suggest any practical implementation of NetHOPs would allow for such visual tunings.
5. What’s next?
Our study involved two relatively small networks. Many questions and challenges remain unaddressed for network uncertainty visualization. Beyond testing larger networks, future work might pursue perceptual studies that compare NetHOPs users’ accuracy to that of using static node-link diagrams, and explore how animated or static adjacency matrices can be used to show graph uncertainty. The utility of NetHOPs for bipartite or multiplex networks, or even hyper-graphs, could be explored, as well as network models with edge dependencies, which NetHOPs are well suited to address.
