A Grammar-Based Approach
for Applying Visualization Taxonomies to Interaction Logs

Researchers generally view user interactions with visualization systems as a hierarchical construct with multiple levels of granularity, as shown in Figure 1. These granularities are often derived in a bottom-up manner and categorized into four levels, as summarized by Gotz & Zhou [GZ09]: individual user interactions (e.g., [SMG*20]), sequences of user interactions (e.g., [GGZL15]), user tasks (e.g., [BH19]), and high-level reasoning constructs or goals (e.g., [BOZ*14, LTM17]). There exist many visualization taxonomies and applications of these taxonomies at each of these four levels of granularity, which we describe below.

Individual Interactions. Taxonomies at the lowest-level categorize the user’s most primitive interactions. Example taxonomies include those proposed by Amar et al. [AES05], Yi et al. [YaKSJ07] and Brehmer & Munzner [BM13]. Amar et al. proposed ten categories of interactions derived from explicit questions asked by students as they visually explored various datasets [AES05]. Yi et al. clustered the interaction capabilities of visualization tools into seven categories of interaction [YaKSJ07]. Brehmer & Munzner used a similar approach to derive a multi-level typology for user interaction [BM13], categorizing not only low-level interactions, but also the user’s motivations for performing these interactions, such as to present information or to discover new hypotheses.

Sequences of Interactions. Low-level interactions are often chained together into sequences or patterns and examples of such taxonomies include ones proposed by Shneiderman [Shn96], Grammel et al. [GTS10], and Guo et al. [GGZL15]. Shneiderman’s information-seeking mantra: “overview first, zoom and filter, then details on demand” describes an explicit progression of interactions performed when visually exploring data [Shn96]. Grammel et al. conducted a user study to understand how novices construct visualizations in Tableau [GTS10] and used their collected data to tabulate transitions made between attribute and encoding selection interactions. Guo et al. build on their analysis to identify sequences of interactions that frequently lead to insights in systems  [GGZL15].

Tasks. Related interaction sequences can be clustered together to infer the intent of a user’s analysis, often referred to as tasks. Notable examples at the task level include the taxonomies proposed by Pirolli and Card [PC05], Battle and Heer [BH19], Kang et al. [KGS09], Sedig and Parsons [SP13], and Alspaugh et al. [AZL*18]. Pirolli and Card propose a pipeline of data analysis tasks encompassed within two high-level loops, foraging and sensemaking [PC05]. Battle and Heer [BH19] survey the literature to identify common tasks completed during visual exploration. Kang et al. [KS11], Kandel et al. [KPHH12], and Alspaugh et al. [AZL*18] interview industry professionals to summarize common steps and challenges in the data analysis process. Sedig and Parsons [SP13] use a set of tasks which are broader patterns to characterize user’s mental cognitive process. Yan et al. segment sequential event logs which combines data, interaction, and user features into high-level user tasks [YGR21]. Other works such as  [Hib99] characterize specific non-exploration tasks for information visualization of real-world data. Further, [SNHS13] characterize broad visualization tasks based on their roles such as developers, authors and end users. However, although tasks are richer semantically, they often require in-depth and arguably laborious analysis of the underlying log data to extract meaningful user activities [YGR21].

Goals and Reasoning. At the highest-level of the hierarchy, taxonomies aim to capture how the users organize their analysis process into tasks and broader analysis goals. For example, Karer et al. build a formal rule-based model to reason about creation of a visualization and represent the analyst’s information and knowledge flow graphically [KSHL20]. Lam et al. [LTM17] survey design study papers to understand how user’s goals are broken down into actionable analysis tasks within visualization tools. Gotz et al. [GZA06] and Shrivnivasan et al. [SvW08] represent analyst’s mental models as links or cycles between insight discovery and knowledge understanding when tracking a user’s interactions with their tools. Sedig and Parsons [SP13] aim to speak to the user’s cognitive processes via the use a patterns characterizing patterns in their analysis with visualization tools. However, we observe very few works that develop models of the user’s high-level analysis intents. We believe this stems from the challenge of modeling high-level constructs in general. Tasks and analytic reasoning structures at the highest level are difficult to capture but semantically rich as they give insight into human analytic process, while primitive interactions captured at the lowest level of the hierarchy are easier to capture but semantically poor as they provide few details about the human analytic process.

The literature shows that many works have used taxonomies to analyze interaction logs. For example, Guo et al. manually apply the taxonomy proposed by Yi et al. [YaKSJ07] to analyze user interaction logs from a text document exploration tool [GGZL15]. Similarly, Satyanarayan et al. [SMWH17] also use Yi et al. [YaKSJ07] to define interaction categories to evaluate Vega-Lite. Battle and Heer [BH19] use a similar approach to map analyst’s interactions with Tableau to the Tableau-focused taxonomy of Heer et al. [HMSA08]. Likewise, Gotz & Wen use the interaction taxonomy proposed by Gotz & Zhou [GZ09] as a means for extracting common sequences of visualization interactions [GW09]. Battle and Scheidegger [BS21] use Brehmer & Munzner [BM13] to guide literature review on capturing distinctions in how data management technology can be applied in interactive analysis systems. Further, Battle et al. use Pirolli and Card’s sensemaking loop taxonomy [PC05] and Shneiderman’s information-seeking mantra [Shn96] to distinguish common interaction sequences as users visually explore massive array data [BCS16]. In all cases, these applications focus less on using taxonomies for their intended use as design guidelines and more on the unintended use of evaluation. Only a few interaction-focused taxonomies are designed to accommodate the complex tasks observed in visual analytics [LFB*14]. Further, all these taxonomies still need to be manually applied to individual log records, which can be a tedious process. Our goal is to work towards automation by formalizing the process of applying taxonomies to interaction logs.

Although few, there have been some interesting works in the visualization community that have taken a language-based or grammar-based perspective to understand user behavior and analytic activity. For instance, several works use Markov models [OGW19, BCS16, RJPL16] and finite automata [DC16] to infer user’s common analysis and exploration behaviors. Dabek et al. in particular derive a grammar-based model to learn user interactions and determine common patterns for guiding new users for their visual analytic process [DC16]. Expressing taxonomies as formal grammars can enable researchers to express theories of user analytic activity using a single, consistent language thereby encouraging a formal means to analyze taxonomies, compare them, and either refine existing taxonomies or derive new ones. Our goal is to bridge the gap between theoretical taxonomies and data-driven analysis of visualization tools. In addition to formalizing the process of mapping taxonomies to interaction logs, we aim to enable the generation of data-driven guidelines for the design of future taxonomies and visualization tools.

We define a taxonomy $t$ as being at either the low level, i.e., terminal level ($T$), or high level, i.e., non-terminal level ($NT$): $t\in\{T,NT\}$. We use $t$ to define a regular grammar, which consists of three parts:

• –

  a set of terminal symbols $\Sigma$,

• –

  a set of non-terminal symbols $N$, and

• –

  a set of production rules

  • –

    Each production rule $f$ is a function over terminal and/or non-terminal symbols $f:N\rightarrow\{\Sigma\cup N\}^{*}$, where $\cup$ denotes the union of two symbol sets and ^∗ denotes repetition of items.

The terminal symbols, $\Sigma$, are the most primitive building blocks in a grammar, i.e., the lowest level of the visualization taxonomy hierarchy in Figure 1. Therefore, the taxonomies at the lowest level ($T$) can be seen as $\Sigma$. In the context of interaction log data, the set of distinct user interactions captured represent the primitives to be mapped to a target set of terminal symbols, similar to mapping observed words to a target dictionary.

The non-terminal symbols, $N$, capture the syntax of a grammar. These symbols resemble more complex user analysis behavior captured at higher levels of the visualization hierarchy. For example, recurring patterns or sequences of user interactions within log data can be represented as functions over terminal and non-terminal symbols, akin to deriving common sentence structures from observed word sequences. Thus taxonomies at the higher levels ($NT$) can be represented as $N$. Note that non-terminals are not limited to expressing sequences of terminals and in fact can express all levels of the hierarchy, which we modulate through production rules. In the simplest case, non-terminals can be defined as a mapping to a single terminal, i.e., mapping a single log record to a taxonomy category. In the most complex case, non-terminals can be defined as a function of other non-terminal symbols, i.e., a function of functions. In this way, we can leverage the recursive power of regular grammars to express user analysis behavior at multiple levels of granularity.

Here we walk through our approach of generating a regular grammar for two well-known visualization taxonomies: Brehmer & Munzner’s multi-level typology  [BM13] ($BM$) and Shneiderman’s information-seeking mantra [Shn96] ($S$). Note that we focus on the how level of BM. We also demonstrate its application on an interaction log dataset collected by Wall [Wal20]. This dataset captures user interactions from a visualization system intended to select a committee of politicians, enabling further study of the user’s potential biases in decision making. We represent our approach in Figure 2.

Brehmer & Munzner classify individual interactions into 11 categories, which we represent as a set of terminal symbols $\Sigma_{BM}$:

Note that we can represent any low-level visualization taxonomy as a set of terminal symbols in a similar fashion.

The Wall dataset has 11 distinct log record categories representing individual interaction types, all of which can be represented using an equivalent terminal from $\Sigma_{BM}$. As shown in Figure 2(1), examples of these log records include mouseover_from_list, change_attribute_distribution, filter_changed, etc., which allow users to retrieve details for specific politicians within the current committee list, change the rendered distribution measures computed over the politician attributes, and change the politician filtering criteria, respectively. These distinct log records can be mapped to corresponding terminals in $\Sigma_{BM}$ using production rules defined over the Wall dataset $D_{W}\mapsto\Sigma_{BM}$, which we label as wall2020-brehmermunzner2013-mapping (Figure 2(2)). For example, we can use these functions to map the individual log records listed earlier to select, aggregate, and filter terminals respectively in $\Sigma_{BM}$ (Figure 2(3)).

High-level taxonomies such as Shneiderman’s information-seeking mantra (“overview first, zoom and filter, then details-on-demand” [Shn96]) express common sequences of user interactions observed during visual exploration. The components of this mantra (“overview”, “zoom”, “filter” and “details-on-demand”) can together be represented as a set of non-terminal symbols $N_{S}$ (see Figure 2(4)):

Other high-level taxonomies can also be represented using non-terminal symbols in a similar fashion.

Each non-terminal in $N_{S}$ can be defined as a function of one or more Brehmer & Munzner terminals: $N_{S}\mapsto\Sigma_{BM}$ (Figure 2(5)), with left-hand side showing non-terminal symbol and right-hand side showing regular expression of possible terminal symbols. For example, the overview non-terminal symbol occurs when users transform the data, arrange the data differently or visualize the data in various ways. These transformations can be represented using the aggregate, arrange or encode terminals in $\Sigma_{BM}$. The corresponding production rule is as follows, defined as a regular expression:

Similarly, the zoom, filter and details-on-demand non-terminal symbols can be defined as regular expressions over $\Sigma_{BM}$:

We label these production rules as brehmermunzner2013-shneiderman1996-mapping. Similar production rules can be generated for the same non-terminal using different underlying terminals, e.g., terminals defined by Yi et al. [YaKSJ07] instead of Brehmer & Munzner [BM13].

Since production rules can be represented as regular expressions, we can easily apply them to user interaction sequences within logged analysis sessions to determine whether relevant patters arise within this data. For example, Figure 2(6) shows one occurrence of the information-seeking mantra in the user session data. Similarly, other non-terminals represented by their corresponding production rules can be used to examine patterns in user interaction log data.

We select seven taxonomies: four taxonomies occurring at the lower granularity of the hierarchical structure and three taxonomies occurring at the higher granularity as representative taxonomies on which we demonstrate the generation of regular grammar. Although we select only a subset of taxonomies here, we note that the same process can be applied directly to other taxonomies. The representative taxonomies are selected based on two factors. First, we look for the implementation and application of the taxonomies in application systems to demonstrate their empirical use. We use the number of citations measure, with a minimum threshold of 300 as a quantitative measure of the widespreadness of the taxonomies. Second, we examine the feasibility of taxonomies such that they have enough detail to be mapped to interaction log data in order to successfully generate a regular grammar for it. We observe the number of systems that apply or use these taxonomies for either their design, analysis (e.g., GAN Lab [KC20]) or evaluation (e.g., Sliceplorer [TSM17]) as a measure of feasibility of the taxonomies. In accordance to these factors, the four representative low-level taxonomies selected are:

• [T1] Amar et al.’s [AES05] analytic task taxonomy.

• [T2] Brehmer & Munzner’s [BM13] multi-level typology of visualization tasks.

• [T3] Gotz & Zhou’s [GZ09] characterization of visual activity.

• [T4] Yi et al.’s [YaKSJ07] interaction technique category.

• [NT1] Shneiderman’s [Shn96] information-seeking mantra.

• [NT2] Gotz & Wen’s [GW09] behavior patterns to infer user’s intended visual task.

• [NT3] Guo et al.’s [GGZL15] common analysis patterns.

We performed a search for available and pre-collected interaction log datasets online as well as reached out to our network. Following the retrieval of interaction log datasets, we specified three criteria to short-list usable datasets. First, the interaction log datasets captured needed to be of visualization-based systems. Second, the interaction log datasets needed to capture the lowest level of user interactions with visualization systems and last, the systems needed to have features that led to interaction log records mapping to at least 60% distinct categories of the representative taxonomies. Some interaction log datasets that were ruled out due to either their unavailability or limited functionalities of the tools were Patterns and Pace dataset [FPH18], HindSight dataset [FDPH16], Anchoring Effect dataset [CWK*17], etc. We found three interaction log datasets that matched our criteria, encouraging us to apply our regular grammar’s approach to them. However, our process can also be applied to other interaction log datasets as well. We list our representative datasets here, describe their tasks and provide statistics about them in Table 1.

• [D1] Battle & Heer: Data exploration using Tableau [BH19].

• [D2] Liu & Heer: Big data exploration using imMens [LH14].

• [D3] Wall: Visual analytics for decision making [Wal20].

The individual user interactions in an interaction log dataset can be synonymous to low-level taxonomy categories, that is terminal symbols ($\Sigma$).

Overview. Therefore, for a given interaction log dataset $D$ and terminal symbol $\Sigma$, we can translate each log record $d\in D$ to its corresponding terminal symbol $i\in\Sigma$, producing the mapping $f:D\mapsto\Sigma$. For example, suppose the dragging of a slider is being mapped to the Brehmer & Munzner terminal, represented by $\Sigma_{BM}$ (see subsection 3.2), $f$ may map this recorded event to the $\mathtt{filter}$ terminal $\in\Sigma_{BM}$. We develop functions over $\Sigma$ and the interaction log dataset $D$ which we call mappings. These mappings are formulated as JSON objects, one for every interaction log dataset and low-level taxonomy that is a terminal symbol pair. Therefore, we develop a total of 12 unique mappings = 3 sets of interaction log datasets ($D$) $\times$ 4 sets of terminal taxonomies ($\Sigma_{T}$).

Process. We follow best practices in qualitative coding to derive our mappings. Similar to prior work [GTS10, LTM17], we used an iterative approach to establish a code-book of the mappings for all the terminal taxonomy and interaction log dataset pairs. To measure agreement among authors in applying the code-book, we calculate inter-rater reliability scores [Wan09], and find that all coders were consistently in close agreement, i.e., achieved scores of 0.99 out of 1.0.

In the first iteration, for each interaction log dataset, two researchers on the project individually used the elimination approach [Smi43] to map each distinct log record $d\in D$ to a single terminal of the low-level taxonomy, that is $i\in\Sigma$. This was repeated for all four terminal symbol taxonomies. The two researchers mapped an interaction log record to a special null terminal if they found multiple or no terminals from the taxonomy that mapped to the log record. At the end of the first iteration, the mappings of both the researchers were aligned to calculate an inter-coder reliability score of 0.47. In order to reconcile on the code-book, the second iteration constituted of both the researchers discussing the conflicting mappings and reasoning on their choices. This discussion led to either a consensus on the mappings or finalizing the conflicts. The second iteration of forming the code-book resolved the majority of the conflicts and increased the inter-coder reliability score to 0.91. In the final round of iteration, the final conflicts were resolved by having the other two researchers on the project follow the same process which further raised the inter-coder reliability score to 0.99.

The special null terminal was used for interaction log records that could not be mapped to a single terminal even after discussions with all four researchers. Examples of such terminals are the log records for resetting of the interface, which are commonly observed in the Tableau tool and thus in Battle & Heer’s [BH19] interaction log dataset. The Gotz & Zhou [GZ09] taxonomy does not include an interaction category that resets interfaces. Therefore, we assignment null to reset actions when mapping to the Gotz & Zhou terminal symbol $\Sigma_{GZ}$.

We use this final iterated and established code-book of mappings (inter-coder reliability agreement = 0.99 out of 1.0) to perform further analysis. A justification for each mapping is provided as an additional nested description property in the JSON object mappings explaining our reasoning process. Along with the mappings, we provide a Python script that takes as input a interaction log dataset file ($D$) and the terminal symbol mapping ($\Sigma$) and outputs another file containing a list of corresponding terminal symbols, $i\in\Sigma$ of all log records of the interaction log dataset, $d\in D$.

The user patterns or sequences observed in interaction log datasets can be synonymous to high-level sequence taxonomy categories, that is non-terminal symbols ($N$). Therefore, we represent every high-level taxonomy describing user’s sequences ($NT$) as a distinct set of non-terminal symbols, $N_{NT}$.

Overview. Each pattern or sequence in a high-level taxonomy can be represented as consecutive interactions of simpler symbols, which are terminals ($\Sigma_{T}$). Therefore, we simply degenerate each pattern into simpler terminals and assign them to be included in the set of non-terminal symbols. These degenerations are either explicitly provided by the researchers who find these patterns or are described by them in words. Thus, based on these explicit representations or descriptions, we come up with a set of consecutive simpler terminals, $t\in NT$ that express the non-terminal sequence. Therefore, we develop a total of 3 sets of non-terminal symbols ($N_{NT}$) each consisting of one or multiple sequences or non-terminals which are represented using terminal symbols ($\Sigma_{t}$).

Process. We follow the same iterative process to establish a code-book for the non-terminal symbols mappings as followed for the terminal symbols. In the first iteration, two researchers on the project understand the descriptions of the founder researchers coming up with the sequences to build the set of non-terminal symbols. This is repeated for all three sets of representative non-terminal taxonomies ($N_{NT}$). A full inter-coder reliability score of 1.0 was achieved after the first iteration, thereby, saving further discussion and iterations with the other two researchers. Once again, this iterated and established code-book of non-terminals mappings was used to perform further analysis.

Empirically in interaction log datasets, complex behaviors of users are perceived to be patterns of underlying simpler interactions. In regular grammar, this can be paralleled to forming sets of non-terminal symbols ($N$) using combinations of simpler sets of terminal symbols ($\Sigma$) put together. Even more complex sequences, which speak to the more abstract tasks of the user can be formulated as combinations of not only the sets of terminal symbols but also the sets of non-terminal symbols. Our approach adopts this approach by the ability to generate production rules over non-terminal symbols. Production rules can be functions or regular expressions of both terminal and non-terminal symbols to generate complex non-terminal symbols thus informing user’s common behaviors as sequences or tasks in interaction log datasets.

Overview. Each non-terminal can be represented as a function of terminal symbols, $\Sigma_{T}$. Because each low-level taxonomy or terminal symbol has a unique mapping represented by $\Sigma$, the same high-level taxonomy may be generated using different terminals, depending on which underlying low-level terminal is used. Thus, we develop functions or mappings of all possible pairings of low-level taxonomy (i.e., terminals) and high-level taxonomy (i.e., non-terminals) listed in section 3. These mappings too are formulated as a JSON object, one for every terminal and non-terminal pair. Therefore, we develop a total of 12 unique mappings = 4 sets of terminal symbols ($\Sigma_{T}$) $\times$ 3 sets of non-terminal symbols ($N_{NT}$).

Process. We follow a similar iterative and best qualitative process to establish the code-book for the production rule mappings as followed for the sets of terminal and non-terminal symbols. The mappings for non-terminal symbols are produced by building functions of mapping each individual non-terminal of the non-terminal sequence to its corresponding terminal mapping. This is repeated for all non-terminal taxonomy and terminal-taxonomy pairs. After the first iteration, where two researchers on the project individually produced the mappings for the non-terminals, a inter-coder reliability score of 0.73 was achieved. After a second iteration of discussion and resolving conflicts, a full inter-coder reliability score of 1 was achieved, thereby, saving a third iteration with the other two researchers. Once again, this final iterated and established code-book of regular expressions mappings was used to perform further analysis.

For some non-terminals, additional information was needed about the attributes and dimensions on which interactions were captured. For example, two non-terminals observed by Gotz & Wen [GW09]: scan and drill-down mean that users continuously perform the inspect iterations over a series of similar (i.e., on the same dimension or attribute) and different (i.e., on different dimensions or attributes) visual data objects respectively. To meet these needs, we modified the underlying terminal symbols to include inspectsame and inspectdifferent for scan and drill-down respectively.

Similar to the previous mappings, regular expressions also use the special null category if the non-terminals cannot be represented as regular expressions using underlying terminals. For instance, scan and drill-down Gotz & Wen non-terminals cannot be represented with Amar et al. [AES05] terminal, since there is no inspect-like interaction in Amar et al. taxonomy. We also provide another Python script that takes as input the terminal mappings file ($\Sigma$) and non-terminal mappings file ($N$), and outputs another file containing a list of sequences found.

Before we can extract patterns from log data, we first need to map it to a relevant set of terminals ($\Sigma$). However, the expressiveness of a terminal-level taxonomy can influence our ability to extract patterns, such as by having low coverage that causes us to lose data records, or by having low diversity that causes us to lose semantic meaning across interaction sequences. To evaluate the expressiveness of terminal-level taxonomies, we analyze the coverage they provide when mapped to each of our three datasets, as well as the diversity of terminals observed across the resulting mappings. We evaluate the four different representative terminal-level taxonomies in this analysis.

Similar to the analysis performed for terminal symbols, the coverage-based analysis of non-terminal symbols is analyzed by calculating the number of occurrences of established sequences or non-terminals in the interaction log datasets. And, the diversity-based analysis of non-terminal symbols is informed by finding new sequences or new non-terminals that are observed within and across interaction log datasets.