Ask HN: What is the best software to visualize a graph with a billion nodes?
Currently I am using GraphViz. But I am not happy with the quality of output (It is writing a postscript file).
I want to be able to zoom in and zoom out. Graph has upto 100B nodes and is directed cyclic graph.
116 comments
[ 4.7 ms ] story [ 124 ms ] threadis there a way you can subsample or simplify or approximate the graph that'd be good enough?
in some domains, certain problems that are defined on graphs can be simplified by pre-processing the graph, to reduce the problem to a simpler problem. e.g. maybe trees can be contracted to points, or chains can be replaced with a single edge, or so on. these tricks are sometimes necessary to get scalable solution approaches in industrial applications of optimisation / OR methods to solve problems defined on graphs. a solution recovered on the simplified graph can be "trivially" extended back to the full original graph, given enough post-processing logic. if such graph simplifications make sense for your domain, can you preprocess and simplify your input graph until you hit a fixed point, then visualise the simplified result? (maybe it contracts to 1 node!)
Just to be clear, the OP already has a graph. There are nodes and relationships. The graph can be queried for understanding.
Rendering the graph is tractable for a small graph or a portion of the graph.
Trying to render all the nodes in an enormous graph is almost always an expensive quixotic adventure.
Perhaps that is the experience he was after for his billion node graph.
I'm finding even 10's of thousands can be difficult.
Just generally, is there a list of visualization products that is broken down by how many nodes they can handle?
While you can envision ways of laying out and rendering such large graphs (force-directed layout is frequent, as are hardware-accelerated rendering methods that typically only show nodes with size and color, but little more complex than that), you don't just want to stare at a pretty hairball. Graphs have structure, which the correct layout will emphasize or even make visible. And you want to be able to explore or interact with the data. And there's where this often breaks down.
If you're just interested in part of the data, reduce the graph to that part. Makes layout, rendering, and interaction way easier.
If you have ways of grouping or clustering the data beforehand, reduce the graph to the clusters and then drill down into them.
You might get lucky and your data already has a structure that's well suited for fast layout algorithms and the same structure makes it easy to figure out which part you want to look at more closely. But in my experience that's rare. Most requests for large graphs from customers come from requirements of the software (e.g. “should be able to handle 100k nodes and as many edges at 60 fps with a load time of no more than 2 seconds”) written by someone who pulled more or less reasonable maximum numbers from thin air, or from just looking at the amount of data without really having an idea of how to work with it and just wondering whether all that can somehow be turned into pixels. Dedicating less than a pixel on the screen to each node is very frequently not helpful, even though a visualization product may very well advertise that they can handle it. It may make for pretty pictures, but often not very useful ones.
There are a number of posts on the topic, e.g.
• https://cambridge-intelligence.com/how-to-fix-hairballs/
• https://www.yworks.com/pages/smooth-visualization-of-big-dat...
https://gephi.wordpress.com/2024/06/13/gephi-week-2024-peek-...
Thinking specifically about a graph of knowledge, so will be an iterative process.
Just looking for anything more than a text editor really!
Obsidian is PKM right? Does it have the idea of labels on the edges?
I'd look for Knowledge Graph editors then, for RDF or OWL knowledge bases, I don't have any specific recommendation, there are many but most are rather old.
Alternatively, go for a graph database like Neo4j, it's primarily designed as a database and not an editor, but it does have a nice UI visualize and change things by hand.
https://datashader.org/
But if you were my coworker I'd really press on why do you want the visualisation and if you can get your answers in some other way. And whether you can create aggregates of your data that reduces it to thousands of groups instead. Your data is a minimum of ~800GB if the graph is a single line (position + 64bit value encoding each edge, no labels), so you're not doing anything real-time with it anyway.
That being the case, I think you're suggesting that this high level summarisation happens as a separate preprocessing step (which I agree with FWIW) whereas I think they're imagining it happening dynamically as part of rendering.
Even 8k-screens have not enough pixel to show that many nodes at the same time. So some visual optimization has to happen anyway.
2) You may be interested in the large body of open source HPC visualization works. LLNL and ORNL are the two dominant labs in that space. Your issue might also be I/O since you can generate data faster than you can visualize it. One paradigm that HPC people utilize is "in situ" visualization. Where you visualize at runtime so that you do not hold back computation. At this scale, if you're not massively parallelizing your work, then it isn't the CPU that's the bottleneck, but the thing between the chair and keyboard. The downside of in situ is you have to hope you are visualizing the right data at the right time. But this paradigm includes pushing data to another machine that performs the processing/visualization or even storage (i.e. compute on the fast machine, push data to machine with lots of memory and that machine handles storage. Or more advanced, one stream to a visualization machine and another to storage). Checkout ADIOS2 for the I/O kind of stuff.
https://github.com/ornladios/ADIOS2
Comparing it to a rendering engine I think is a bit of a cheat unless the points do have some intrinsic 2-D spatial coordinates (and no edges beyond immediate adjacency). You're ultimately viewing a 2-D surface, your brain can kinda infer some 3-D ideas about it, but if the whole volume is filled with something more complex than fog, it gets tricky. 4-D, forget about it. 100-D as many datasets are? lol.
Having worked in a lab where we often wanted to visualize large graphs without them just devolving into a hairball, you'd need to apply some clustering, but the choice of clustering algorithm is extremely impactful to how the whole graph ends up looking, and in some cases it feels like straight deception.
I think the relationship to a 4k image is a great way to explain why you should never do this. Specifically because we can note how as resolution increases it gets difficult to distinguish the difference. Like the difference between 480p and 720p is quite large but 4k and 8k is... not. A big part of why the high res images even work is because the data being visualized is highly structured and neighboring data strongly relates. So maybe OP's graph contains highly structured graph cliques. But it is likely doubtful. Realistically, OP should be aiming for ways to convey their data with far less than 10k points. Maybe ask yourself a question: can you differentiate a picture of a thousand people from two thousand? Probably not.
Having the structure of the device available should also help with the layout - we know you can group the nodes logically into independent boxes instead of trying to auto-layout everything.
https://github.com/latentcat/graphpu
A 1080p monitor has:
1,920 × 1,080 = 2,073,600 pixels
Each pixel can display 32-bit color, which equates to:
2^32 = 4,294,967,296 colors
So, while each pixel can display one of 4.3 billion colors, the monitor can display combinations of those colors across its 2,073,600 pixels. The total number of possible color combinations on the screen is astronomical.
The actual number of possible combinations is:
4,294,967,296^2,073,600
You do something similar with 100B data points since you're not literally looking at the relation between individual nodes when all 100B are on screen at once.
4,294,967,296^2,073,600 is very large but 2^(10^22) is much much larger
It's only 24-bits of visible colours.
If you want it to be interactive, you will need to figure out a few things:
1.) how to format the data so it can be streamed off disk. 2.) how to cull the offscreen bounding boxes quickly. 3.) how to cull tiny bounding boxes quickly.
The central problem is finding a way to group the nodes efficiently into chunks. A 2D approach is probably best. You would then have something that could be rendered efficiently.
Other than that, maybe a point cloud renderer? There might be one you can buy off the shelf, or something open source.
You can do the hierarchical clustering using HDBScan probably in reasonable time, it's a fast algorithm.
To have any sort of 2d display you need to project the nodes, which might require some form of PCA given the data set size. UMAP might also work.
From there, you can use an R* tree in conjunction with "cut-depth" cluster segmentation tied to zoom level with additional entity selection based on count and centrality. If you load it in postgres PostGIS can do this in one query.
All pretty straightforward stuff.
If you're fully "zoomed out", is seeing 1B individual nodes the most useful representation? Wouldn't some form of clustering be more useful? Same at intermediate levels.
D3 has all sorts of graphing tooling and is very powerful. It likely wouldn't handle 1B nodes (even if it did, your browser can't) but it has primitives to build graphs
https://tulip.labri.fr/site/