I am pleased to announce d3-force-reuse, a new D3.js plugin for computing faster force-directed graph layouts. This new library reduces graph layout computation time by 10% to 90% depending on the graph. The best part is that it is able to accomplish this without decreasing layout quality!
How It works
This library is based on my new research on speeding up the Barnes-Hut approximation. It does this by reusing approximations instead of computing new ones at each iteration of the layout algorithm. The standard Barnes-Hut approximation computes a quadtree at the beginning of each iteration. It then uses this quadtree to approximate repulsive forces for distant nodes by aggregating groups of nodes and treating them as one large node. This reduces the force calculation from quadratic running time down to O(n log n), which greatly improves runtime. If you’re interested in learning more about Barnes-Hut, Jeff Heer has a wonderful in-depth explanation.
My new research experiments with reusing the quadtree from one iteration to the next. This reduces the overall runtime by creating fewer trees, which saves several O(n log n) runtime operations. The d3-force-reuse library does this by only computing a new quadtree once every 13 iterations. In between, it reuses the most recently created quadtree. This is what I call the “uniform schedule”, which is in contrast to the “standard schedule” that Barnes-Hut normally uses. One alternative is a logarithmic schedule, which creates a new quadtree more often earlier in the simulation and less often later. I also tested a dynamic schedule that dynamically looks at node movement to decide when to create a new quadtree.
Fast, Good Quality Graph Layouts
My experiments show that creating a new quadtree once every 13-14 iterations using the uniform schedule decreases the runtime by 10% to 90%. This is a bigger improvement than the logarithmic schedule, but sometimes the dynamic schedule is a little faster.
Furthermore, the uniform schedule’s graph layout quality is at least as good as the standard Barnes-Hut algorithm, and sometimes a little better (on average)! We can measure the graph layout quality with Greadability.js by measuring the number of edge crossings, edge crossing angle, and the angle of incident edges. The uniform schedule always performs at least as well as the standard Barnes-Hut algorithm, and sometimes it even performs a little better! The logarithmic schedule sometimes performs a little worse, and the dynamic schedule performs the worst of them, but not by a lot.
Interestingly, these methods for reusing approximations also work with other approximation methods like the fast multipole method and the well-separated pair decomposition. We could also these methods on algorithms like t-SNE to reduce its runtime while still finding good embeddings. More details on the experiments are available in my research paper, and the code to run the experiments is available open access.
Try It Out Yourself!
You can start using the uniform schedule for your own graph layouts. It’s available in d3-force-reuse, a plugin for D3.js version 4 or higher.
- Git repo: d3-force-reuse
- NPM package: d3-force-reuse
- Open access experiment code
- PDF paper preprint
This research is being published in Forum Media Technology. The citation is below:
Robert Gove. “It Pays to Be Lazy: Reusing Force Approximations to Compute Better Graph Layouts Faster.” Proceedings of Forum Media Technology, 2018.
Bridging the gap between the impossible and the practical with innovative technology solutions in cyber, data science, mobile, microelectronics and information operations and a full spectrum of products and capabilities to advance national security missions.