Outline

1. The problem: visualizing large node-weighted trees

2. Our solution: Maximum entropy summary trees

3. Going from “code that works for me” to an R package

4. Miscellaneous thoughts

• This is joint work with Howard Karloff.
• The summarytrees R package is hosted at https://www.github.com/kshirley/summarytrees.

Motivating Example: DMOZ (the Open Directory Project)

• DMOZ is one of the largest directories of websites in the world (although it may be a bit dated…)

Motivating Example: DMOZ (the Open Directory Project)

• Data is available for download at http://www.dmoz.org/rdf.html.

• As of April, 2015, there were about 3.7 million unique URLs listed in the directory, belonging to about 595,000 unique topics (excluding the Kids and Teens branch).

• The topics are organized into a hierarchy.

• Question: What is the distribution of URLs over this topic hierarchy?

Some Summary Statistics

                                                                                                                              Topic Frequency
1                                    Top/Arts/Animation         6
2                   Top/Arts/Animation/Anime/Characters         6
3      Top/Arts/Animation/Anime/Clubs_and_Organizations        31
4                 Top/Arts/Animation/Anime/Collectibles        10
5            Top/Arts/Animation/Anime/Collectibles/Cels        12
...                                                 ...       ...
595001             Top/World/Uyghurche/Rayonluq/Yawropa         3
595002                     Top/World/Uyghurche/Référans         5
595003                   Top/World/Uyghurche/Salametlik         1
595004                        Top/World/Uyghurche/Sport         1
595005                        Top/World/Uyghurche/Xewer         5

• Representing this data as a node-weighted tree, we have \(n = 635,855\) total nodes in the tree (40,000 internal nodes with weight = 0 were added to the 595,000 nodes with weight > 0).

• The total weight (# of URLs) of the tree is \(W = 3,776,432\).

• The maximum depth of the tree is 15.

• The range of node weights is \([1, 1276]\).

Distribution of URLs aggregated to Level 2

• One solution is aggregating the nodes.

• Problem: the distribution of aggregated weights across the children of the root is heavily skewed.

• We’d naturally like to drill down into the largest nodes, and perhaps group the small ones into a cluster called “other”.

Drilling down into Top/World…

Drilling down into Top/World…

• … we see the same thing: a heavily skewed distribution with a long tail.

• The central problem (across many real-world trees): To visualize all the children of a node using a layered layout, we waste space on lots of inconsequential nodes.

• (Quick note on treemaps – yes, they are compact in space, but they don’t always do a good job of showing the hierarchy of a tree).

• The solution: aggregate nodes flexibly at different levels of the tree, and allow aggregation of a subset of children under each parent.

• This leads to our definition of a summary tree.

Preview of Solution

Outline

1. The problem: visualizing large node-weighted trees

2. Our solution: Maximum entropy summary trees

3. Going from “code that works for me” to an R package

4. Miscellaneous thoughts

The defintion of a summary tree

• Suppose this is the input tree, containing 9 nodes:

The defintion of a summary tree

• A node in a summary tree can represent an entire subtree of the original tree.

The defintion of a summary tree

• A node of a summary tree can represent at most one cluster of children under each parent (and all the descendants of those children).

The defintion of a summary tree

• A node of a summary tree can represent at most one cluster of children under each parent (and all the descendants of those children).

The defintion of a summary tree

• A node of a summary tree can represent at most one cluster of children under each parent.

• Not a summary tree!

Maximum entropy summary trees

• Among all summary trees with the same number of nodes, which is the best?
• Define the entropy of a node-weighted tree as the entropy of the discrete probability distribution defined by the normalized node weights.

• Both are 6-node summary trees of the DMOZ tree, but one has much higher entropy.
• If 6 nodes is your “budget”, the left summary tree is more informative.

Algorithms:

• Use dynamic programming to compute the maximum entropy summary tree with \(k\) nodes for all \(k = 1, 2, ..., K\), for some user-defined \(K\) (we often set \(50 \leq K \leq 200\)).
• Algorithm 1: “Optimal”
  • The exact solution runs in \(O(nK^2W)\), where \(n\) is the number of nodes and \(W\) is the sum of the weights, which must be integers.
  • The approximation algorithm gets within \(\epsilon\) of the maximum entropy by scaling down weights and rounding.
• Algorithm 2: “Greedy”
  • a greedy heuristic that searches only part of the solution space, but does very well in practice. Runs in \(O(nK^2)\).

Output:

• A series of \(K\) summary trees. We use a layered layout for plots but this isn’t required (computation is independent of vis layout).

• The entropy profile of the tree. Simply the plot of entropy as a function of the number of nodes in the maximum entropy summary tree:

• A key benefit: There are no tuning parameters here, making it a good default method. The vector of maximum entropies for \(k = 1, ..., K\) is essentially a summary statistic of the input tree.

The end of the project… or is it?

• Wrote a paper (Karloff and Shirley, EuroVis 2013)

• Wrote code to implement the algorithm on enough examples to support the paper

• Generated a few static plots (for the paper and associated website)

The end of the project… or is it?

• Wrote a paper (Karloff and Shirley, EuroVis 2013)

• Wrote code to implement the algorithm on enough examples to support the paper

• Generated a few static plots (for the paper and associated website)

The end of the project… or is it?

• Wrote a paper (Karloff and Shirley, EuroVis 2013)

• Wrote code to implement the algorithm on enough examples to support the paper

• Generated a few static plots (for the paper and associated website)

• then…

• …

• …

• (crickets chirping)

• …

• nothing happened.

Outline

1. The problem: visualizing large node-weighted trees

2. Our solution: Maximum Entropy Summary Trees

3. Going from “code that works for me” to an R package

4. Miscellaneous thoughts

How to make this an R package

• Original workflow was:
  • R code to read, manipulate, prepare data
  • R code for computation (super slow)
  • R code to spit out Graphviz code
  • Graphviz to produce a series of (K = 100) pdf files.

How to make this an R package

• Original workflow was:
  • R code to read, manipulate, prepare data
  • R C code for computation (super slow 100x faster)
  • R code to spit out Graphviz code
  • Graphviz to produce a series of (K = 100) pdf files

How to make this an R package

• Original workflow was:
  • R code to read, manipulate, prepare data
  • R C code for computation (super slow 100x faster)
  • R code to spit out Graphviz code write JSON data to disk
  • Graphviz d3.js to produce a series of (K = 100) pdf files a single interactive web-based graphic.

How to make this an R package

• Original workflow was:
  • R code to read, manipulate, prepare data
  • R C code for computation (super slow 100x faster)
  • R code to spit out Graphviz code write JSON data to disk
  • Graphviz d3.js to produce a series of (K = 100) pdf files a single interactive web-based graphic.
  • Wrap this all up into an R package, summarytrees

Using the summarytrees package:

1. Read in your data as a “list of edges”:
   • 4 variables: node ID, parent ID, (non-negative) weight, and label.
   • To-do: accept nested JSON-formatted trees, other formats?
2. Do the computation (with K = 100 for example):
   • optimal(..., K = 100, epsilon = 0) for the exact algorithm
   • optimal(..., K = 100, epsilon > 0) for the approximation algorithm
   • greedy(..., K = 100) for the greedy algorithm
   • All of them return the list of K summary trees as output

3. Call prepare.vis() to set plotting options, such as node colors, the sizes of various plotting elements, etc.

4. Call draw.vis() to open a browser and locally serve the visualization from a temporary directory on your machine using the servr package.

The package has vignettes, and some of this will change over time, most likely.

Examples:

• DMOZ

• Math Genealogy

• R Source code

Comparison to Collapsible Tree

• Collapsible trees are a very nice d3.js example from Mike Bostock: http://bl.ocks.org/mbostock/4339083.

• The function d3.layout.tree() implements the Reingold-Tilform algorithm for a nice-looking layered layout of nodes and links of a tree.

• The collapsible tree allows for expanding/collapsing children of nodes.

• Maximum entropy summary trees are less flexible, but come with nice properties of their own.

• Think of them as a very strictly-guided tour of the structure of a node-weighted tree (rather than allowing one to explore with complete freedom).

Outline

1. The problem: visualizing large node-weighted trees

2. Our solution: Maximum Entropy Summary Trees

3. Going from “code that works for me” to an R package

4. Miscellaneous thoughts

The Good

• The algorithms work and d3.js is slick and fun!

• Take an R list, use toJSON(list), and scoop it up in javascript with d3.json().

• Interesting challenge with summary tree transitions:
  • Maximum entropy summary trees are not nested!
  • Example: The 34 and 35-node maximum entropy summary trees for the DMOZ data only share 32 nodes in common.
  • Solution: send the union of all tree nodes to the browser and look up most recent common ancestor between the \(k_\text{old}\)-node summary tree and the \(k_\text{new}\)-node summary tree to determine entry and exit locations for transitions.

The Bad

• Need better data input options (accept JSON, for example, rather than just list of edges)
• Need better error checking (make sure the input is a tree!) and testing
• Need to find a home for the entropy profile in the d3.js plot
• Most importantly: Need to leverage the R ecosystem and community!
  • Tree data manipulation: jsonlite, dendrogram() (h/t Tal Galili, author of dendextend), ape (focus on phylogenetic trees), others?
  • R-to-d3.js workflow: htmlwidgets, rCharts, networkD3
  • Data: rotl (R Open Tree of Life), others?

The Ugly

• Calling C from R using .C and capture.output()

  tmp <- capture.output(.C("Roptimal", R_K = as.integer(K), 
      R_n = as.integer(n), R_numparents = as.integer(numparents), 
      R_epsilon = as.double(epsilon), R_weight = as.double(data[, 
          "weight"]), R_childindex = as.integer(childindex), 
      R_childstart = as.integer(childstart), 
      R_childend = as.integer(childend), 
      PACKAGE = "summarytrees"))
  

  • Lesson: Don’t be macho with your co-developers about your data manipulation skills.

• Echoing similar statements from R community members Hilary Parker and Hadley Wickham, among others:
  
  

• If you decide to organize your code as an R package, the sooner you do it the better!

Thanks

Thanks!

Acknowledgements: Thanks to Carson Sievert and Carlos Scheidegger for tips and discussion on d3.js

kshirley@research.att.com

github.com/kshirley

twitter.com/kennyshirley

R summarytrees package at Github: kshirley/summarytrees