A collection of Force-directed Graph demonstrations.
I need to render a big network (~10k Nodes, ~10k Links) in Javascript. The simplest case performs pretty poorly (~3fps on my machine). There are a bunch of ways we could improve performance–so this is a collection of those approaches. If you find yourself in a similar situation (needing to render a huge interactive network in the browser), perhaps these can save you some time.
In general, these should all possess node dragging and panning/zooming functionality, though it’s buggy in many cases. I’ll try to note the implementation issues in the documentation below.
I don’t have a complex benchmarking architecture, just a count of the number of ticks that resets every second, visible on the bottom-right corner of every visualization. The numbers given in the table below show the median observed FPS for that graph type (higher is better).
| Index | Strategy | SVG | Canvas |
|---|---|---|---|
| 01 | Basic | 3 | 14 |
| 02 | Increased Theta | 4 | 29 |
| 03 | Finite Max-Distance | 3 | 10 |
| 04 | Force-Reuse | 4 | 15 |
| 05 | Force-Sampled | 4 | 24 |
| 06 | requestAnimationFrame | ||
| 07 | WASM | 3 | 2 |
| 08 | Webworker | ||
| 09 | WebGL (Pixi) | (NA) | 13 |
| 10 | GPUjs | ||
| 11 | Pre-warmed |
(Note that the indices are essentially arbitrary, and just for managing ordering in Finder/File Explorer.)
There are a lot of variables that go into making a visualization like these smooth. Some notable ones that I’m simply taking as constant on my own machine are: the machine (Apple Macbook Pro 2020 w/ i7, 32GB Ram), Browser (Chrome 86), number of nodes in the network (10,000) number of links in the network (10,000), and lots of configurations in the network. I can’t possibly test all of them, so what ends up being best for my use case may not be best for yours. Basically, take the above numbers as an approximation of the order of efficiency of the associated approach when this document was last updated (presently December 2020).
Approximately the simplest D3 Force Directed Graph with Zooming and Dragging. Nothing has been attempted to optimize these, making them optimal boilerplates for the others.
Here we see the first stark contrast between SVG and Canvas Performance. Canvas outperforms SVG by a factor of between 4x and 5x, though the canvas version is still unacceptably choppy.
A lot of the annoyance from watching these networks comes from waiting for the network to cool down. Perhaps we can improve the experience of using these networks by computing the state of the network in the distant future before the first time we draw it. This is achieved by simply calling simulation.tick(n); where n is the number of ticks you wish to advance, before you first update the visual.
Once the network is rendered, the FPS is the same as 01 - Basic Version. The salient benchmark here is the time between starting computation and first rendering the network. Because this computation does not include rendering, the results are essentailly the same for both SVG and Canvas–around 19. This, in conjunction with 02 - Increased Theta gives us an important hint: The simulation is at least as big a bottleneck as rendering on a canvas.
d3-force leverages quadtrees and the Barnes-Hut approximation to simplify node trajectory computations. Essentially, when a bunch of nodes are far away from a node, d3 just treats all those far away nodes as one big heavy node located in the middle, meaning it only needs to compute the effect of the forces once, rather than as many times as there are far-away nodes. But the definition of “far away” is related to this theta parameter. Set theta small, and you make “far away” mean farther away. Increase it and we can perform the approximation more aggressively, meaning the browser can pump up the frame rate.
However, it comes with some problems as well: once the Network reaches a reasonably stable equilibrium, this approach exhibit a minor-but-noticeable juddering effect on nodes that are otherwise well-placed. For most applications, this is probably an acceptable tradeoff.
In the description of 02 - Increased Theta, I provide a brief non-technical description of the Barnes-Hut approximation algorithm leveraged by D3-Force to make real-time force-directed layouts possible. In addition to setting a threshold for consolidating nodes (theta), you can set a threshold for evaluating if a charge or gravitational tug should affect a node at all. This is the maxDistance threshold. By default, it’s Infinite–that is, there’s no distance at which one node will no longer affect the trajectory of another. By setting this value lower, we can reduce the computational burden of evaluating these relationships.
Unfortunately, this one turn out to be obviously non-useful in multiple respects. First and foremost, it doesn’t provide a meaningful improvement in performance for our class of graphs. Second, it tends to self-organizes into a pattern of overlapping circles of radius equal to the given maximum value. While beautiful and rather interesting, these patterns hide the analytical utility of the network structure. Accordingly I recommend you should always leave the maxDistance set to Infinity.
Robert Gove of TwoSix Labs produced an alternative version of d3-forceManyBody called d3-force-reuse which purports to improve the performance of the base d3 implementation by recomputing the quadtree only every 13 ticks, instead of on every tick. (Read the paper for technical details.)
While this does improve performance slightly, it does so while adding a distracting propensity for the graph to expand and contract periodically. Moreover, for the class of graphs I’m evaluating here, performance gains from this strategy were minimal. I believe this may be an effective approach for other graph types, but I can’t definitively make this claim based on these data.
In addition to Force-Reuse (see above), Robert Gove of TwoSix Labs produced a second d3 forceManyBody alternative which achieves better performance by sampling nodes instead of leveraging quadtrees. This reduces the theoretical computational cost from O(n log n) to O(n). (See the associated Research Paper.)
These performance gains were definitively observable for our graphs, but at a significant readability cost. Furthermore, Force-Sampled exhibited the odd property that it would periodically “fling” nodes far outside the body of the graph. For smaller graphs, I can definitely see applications, but don’t recommend it for graphs in our class of use cases.
Please note that this one isn’t correctly implemented yet.
Performance-tuning D3 isn’t an especially untrodden path. One suggestion for improving visual performance is to leverage requestAnimationFrame to break updates into multiple steps.
If Javascript is too slow for your application, one perrennial option is to recode your algorithm in C or Rust and then use emscripten to compile to Web ASseMbly (WASM). Fortunately for us, Colin Eberhardt of Scott Logic already did this using AssemblyScript (a subset of Typescript).
Personally, I found this one most disappointing. There are two reasons for this: first, it’s the only case in which the Canvas implementation actually underperformed the equivalent SVG implementation. Second, it appears not to improve performance even in the better SVG case.
There are a few sources of possible explanations for this curiously poor performance. First and foremost, I may have implemented the use of the library inefficiently or otherwise incorrectly. If not this, it’s worth noting that this is a two-year-old project that never got much beyond the level of a proof-of-concept. It could be the case that the core d3-force implementation has been improved in the intemediate timespan. Alternately, it may be that the d3-wasm implementation was incomplete, or encumbered in some other way. Whatever the case, I do not presently recommend this approach for any applications.
OK, this is one of the odder suggestions. Instead of computing the effects of the force-directed layout on the main thread, we move that computation into a WebWorker thread. That shouldn’t improve the performance meaningfully–after all, the WebWorker certainly doesn’t get resources the main thread doesn’t. What it does offer is the ability to perform those computation without blocking the main thread, so you could use this architecture in an environment where you needed the browser to remain snappy no matter how slowly your network was running.
Mike Bostock himself wrote a demo doing this …for a static layout. Whether it can be leveraged effectively for an interactive, animated layout remains to be seen.
It’s worth remarking that the Canvas version has access to support that the SVG version does not. Specifically, the canvas offers the OffscreenCanvas API, for which this sort of thing is precisely the use case. Essentially, the canvas gets to listen to a special memory channel while the SVG has to rely on a data transfer that’s little better than an AJAX request. (OK, It’s a lot better than that, but still way worse than the Offscreen Canvas API.)
However, this comes with some important tradeoffs in code complexity. Current issues in our implementation include:
Note that there’s no SVG version of this one, since there isn’t really a logical mapping from the output of WebGL (which is essentially a canvas) to SVG.
Just a concept for now. One additional way we might be able to speed up computation
None of these strategies offers a slam-dunk performance improvement that will enable a seamless network of 20,000+ elements. However, the difference between rendering a network on SVG and on Canvas is consistent and tremendous. If possible, you should definitely use a canvas-based approach. It is also likely that for large networks, you’ll benefit from increasing the default theta value somewhat.
D3 and its plugins are hardly the only available option for rendering networks in the browser.
We can use this the pre-set the layout, sort of like pre-warmed.
We can also use this to pre-set the layout, and then switch to the d3-force simulation. While this doesn’t directly improve performance, it does give us
force-graph is a little library to package up an easy-to-use d3-force graph widget. It comes to my attention now because of this demo, which purports to render 75,000 elements (and looks pretty crisp).