122 — HOLA: Human-like Orthogonal Network Layout

HOLA is an automated orthogonal graph layout engine that is design to mimic the complex high-level choices made by humans when organizing diagrams of charts with right-angle edges.

It’s interesting to mimic human-driven layout of graphs because of the informed decisions humans make when designing these visualizations: Relationships between nodes — dependencies, ownerships, predecessors — can be very complex, and the visualization of the graph can be crucial to parsing the meaning of its contents.

Kieffer et al here propose a Human-like Orthogonal Network Layout engine, or HOLA, which is designed to make graphs more human-interpretable by making them more “human-designed” even when laid out by a machine.

They accomplish this by first considering what humans like about human-designed graphs. This includes features like non-crossing edges (maximizing “planarity”, first done in the 80’s by an algorithm called Topology-Shape-Metrics (TSM), still used today), as well as proximity of neighbors and distance of less related nodes.

Using a variety of human designs as a basis for training, the HOLA system makes a few improvements over existing systems: First, it decomposes a graph into “core” and “tree” subcomponents. Then it lays out the core, using a stress-minimization function. Then trees are added, preferring “tree outsideness” as much as possible (trees should be inside loops as rarely as possible). Then the full network is balanced again using stress-minimization and “opportunistic alignment” to optimize for readability and human preference.

The authors found that human subjects, when asked to perform tasks like “shortest-path,” performed better with HOLA-designed graphs than other existing state-of-the-art layout engines’. HOLA has a comparable runtime to other state-of-the-art layout engines.