R&D: Service map graph visualization

[jasonrhodes]

We need to test drive a few graph visualization options with a small proof-of-concept to determine what will work the best for the Service Maps UI.

We should start by considering React Vis force-graph (https://github.com/uber/react-vis-force) because it is the same chart library family we are currently using.

We should also loop in @markov00 to see what he's building for the visualization group and if there is any overlap we should be aware of. Basic design direction below:

[elasticmachine]

Pinging @elastic/apm-ui

[markov00]

@jasonrhodes can you describe me a bit better what type of graph you are looking to draw and what kind of relationships and layout you are going to draw?

I've done in the past a lot of work with various graph libraries, from a plain d3 force layout to cytoscape.js, sigmajs. If you can detail me the constraints and the idea of layout I can suggest you some ways to go.

The new EUIChart implementation is a reimplementation from scratch of the xy charts and doesn't use any existing vis library.

Here maybe also @monfera can support you on a graph library to choose.

So to recap, it will be great to have the following specification:

• layout: is a force layout required? can the node positioning predetermined? do you need to display the graph always with the same node positions?
• how many nodes and edges you will need to handle?
• what kind of interaction you need for each node? click, hover, drag? what about edges?
• animations?

[jasonrhodes]

@markov00 sure! I'll try to answer your questions below:

layout: is a force layout required? can the node positioning predetermined? do you need to display the graph always with the same node positions?

I think force layout or similar is going to be required to show nodes in the least confusing way possible. There will be a concept of a "primary node" for the first iteration of this feature, which would be the service you are looking at, and it should probably look like the rest of the nodes proceed from that primary one in some way, if possible. Where the others go after that is less important, but having them deterministically go to the same place on refresh or subsequent visits to the same map (with the same nodes) would probably be a good thing if possible.

how many nodes and edges you will need to handle?

/shrug! Probably need to make sure it works with a lot, but as usual, we aren't sure how many services a user might have. I think by far the most common case will be only a few nodes at a time, though (less than 10, possibly less than 5).

what kind of interaction you need for each node? click, hover, drag? what about edges?

Some kind of mobile-friendly hover/click hybrid on nodes and edges is probably enough for us for now. We plan to have data about the node and the edge that we'd like to display tooltips for in each case.

animations?

Not strictly necessary. :)

[ycombinator]

Hi, weighing in here per @snide's suggestion because we've tackled a similar "possibly unbounded DAG visualization" problem in the Logstash Pipeline Monitoring UI in Kibana and wanted to share some lessons we learnt.

In the first version of this UI, we used the webcola library to layout the Logstash pipeline DAG, giving the library certain constraints to come up with a force-directed layout.

This worked well for small DAGs, particularly ones with few edges (since one of the constraints was to try and minimize edge overlaps or crossings). But when users tried to visualize more complex DAGs, things got messy fast.

Eventually we realized that we could get away with a simpler layout that was more representative of a Logstash pipeline configuration anyway. So we ended up removing the original DAG layout implementation and introducing a simpler layout instead.

However, before we had the epiphany that we could get away with a simpler layout, we tried to think of how we could scale up the original DAG layout visualization. I'll share some of our thoughts as best as I can recall now (@andrewvc, @justinkambic please feel free to chime in and help me out if I missed anything):

• We gave the webcola layout algorithm a relatively generous — but ultimately fixed — amount of time to let the forces in the layout "settle". The resulting visualization could sometimes still be ugly but at least it wouldn't crash the browser :)

• We tried tweaking the various constraints to try and make the visualiations prettier but eventually we'd always find some DAG or another that would cause things to get laid out in an "ugly" fashion.

• We considered rendering only parts of the DAG up front and letting the user choose to render other parts if they wanted to explore further. An obvious boundary for us here was branches (ifs) in Logstash pipelines: we could render all nodes and edges leading up to and around branches and show a + sign or similar next to the if node in the visualization. The user could then expand that node if they wanted to explore that branch further. This could still result in a messy visualization but at least the user would've got there interactively and would've had the opportunity to close/minimize branches to keep the visualization tidy as they went about their journey.

Hope some of the above lessons are helpful to you. Happy to answer follow up questions as well!

[andrewvc]

Excellent writeup @ycombinator .

The key takeaway I have is that rendering arbitrary topologies quickly and beautifully is very hard. The usual advice of making it work for the simple case then expending effort to make the complex case work doesn't really apply.

Our initial progress on simple small graphs was deceptive. Once the graphs increased in complexity rendering them in a way that was actually useful to anyone became impossible. This isn't just about the mathematical complexity of determining these layouts. At a certain size a graph is just a hard to trace visually for a human (though they look cool).

I'm not familiar with the domain here, but if you think it will be at all common for there to be larger graphs I'd strongly recommend having a large test case as a part of early experiments.

[justinkambic]

Echoing what others have said - it's worth defining the maximum level of complexity you're prepared to handle and the contingency you'll display in that case as an early part of the design.

Based on what I've read here it sounds like the structures we're talking about don't have the same complexity concerns as Logstash pipelines, but it's still valuable to be cognizant of the issues @ycombinator and @andrewvc mentioned.

[andrewvc]

Oh, one note about cytoscape. It's pretty limited in terms of rendering. IIRC they've moved away from SVG to canvas, which is faster to render, but often yields blurry results for custom elements (and has obvious accessibility issues)

[monfera]

Interesting discussion folks! Minor addition:

@jasonrhodes you mentioned determinism, it's likely not news that as of v4.* d3-force is deterministic and its perf has increased tremendously over v3.* although d3 is but one of the many options.

@markov00 I haven't done much graph visualization other than tampering with Sankey internals, which is in theory adequate for DAG visualization as basically d3-sankey is expressly about DAGs, though it'd need a lot of work on styling the nodes and links appropriately, here's some farcical attempt (eg. links are just constant width lines, rather than full height as usual with Sankey). The bigger problem is that d3-sankey or similar approaches are not doing optimization, just follow some flakey heuristics, it'd need eg. integer programming.

I agree with the sentiment here that it's next to impossible to meaningfully visualize large graphs, maybe the trick is to somehow have ways for aggregating less interesting areas of the graph, and/or filtering non-relevant parts, or adaptively emphasizing the part in focus (eg. via node size and opacity, link saliency, drawing these on top) and perhaps providing navigation analogous to panning, zooming, drill-down, filtering etc.

[markov00]

I want to share this repo that can be maybe useful to compute a bit faster a graph force layout:
https://github.com/twosixlabs/d3-force-reuse

[dio]

@jasonrhodes the design is pretty!

[sorenlouv]

@katrin-freihofner We might not need this issue since the POC implementation has started here: #42120. Either way, this looks like a design issue, so I've moved it to the Design board.

[katrin-freihofner]

Closing this in favor of: #42120