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. |
A blog that covers only failures of large SVG viewers having 10,000+ of nodes.
https://egbert.net/blog/articles/comparison-svg-viewers-larg...
From there I could write better visualizations. I got laid off before the project was completed, though.
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?
Neo4j, cytoscape, etc will not work.
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...
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.
It used to be thought that visualizing super large graphs would reveal some kind of macro-scale structural insight, but it turns out that the visual structure ends up becoming dominated by the graph layout algorithm and the need to squash often inherently high-dimensional structures into 2 or 3 dimensions. You end up basically seeing patterns in the artifacts of the algorithm instead of any real structure.
There's a similar, but unrelated desire to overlay sequenced transaction data (like transportation logs) on a geographical map as a kind of visualization, which also almost never reveals any interesting insights. The better technique is almost always a different abstraction like a sequence diagram with the lanes being aggregated locations.
There's a bunch of these kinds of pitfalls in visualization that people who work in the space inevitably end up grinding against for a while before realizing it's pointless or there's a better abstraction.
(source: I used to run an infoviz startup for a few years that dealt with this exact topic)
I want to stress this point and go a bit further. It can be worse as people have pareidolia[0], a tendency to see order in disorder. Like how you see familiar shapes in the clouds. There is a danger in that with large visualizations such as these that instead of conveying useful information, you counterproductively convince someone that something that isn't true is! Here's a relevant 3B1B video where this is kinda discussed. There is real meaning but the point is that it is also easy to be convinced of things that aren't true[1]. In fact, Grant's teaching style is so good you might even convince yourself of the thing he is disproving as he is revealing how we are tricked by the visualization. Remember what the original SO person latched onto.
I think it's important to recognize that visualization is a nontrivial exercise. Grant makes an important point at the end, restating how the visualization was an artifact and how if you dig deep enough into an arbitrary question, you _can_ find value. Because at the end of the day, there are rules to these things. The same is true about graphs. There will always be value in the graph, but the point of graphing is to highlight the concepts that we want to convey. In a way, many people interpret what graphs are doing and why we use them backwards. You don't create visualizations to then draw value from them, but rather your plots are a mathematical analysis that is in a more natural language for humans. This is subtle and might be confusing because people often are able to intuit what kind of graph should be used to convey data but are not thinking about what the process is doing. So what I'm saying is that you don't want to use arbitrary graphs, but there's the right graph for the job. You can find a lot of blogs on graph sins[2] and this point will become clearer.
At the heart, this is not so different than "lies, damned lies, and statistics." People often lie with data without stating anything that is untrue. With graphs, you can lie without stating a word, despite being worth a thousand. So the most important part of being a data scientist is not lying to yourself (which sounds harder than it is).
[0] https://en.wikipedia.org/wiki/Pareidolia
[1] https://www.youtube.com/watch?v=EK32jo7i5LQ
[2] Except this might be hard because if you Google this you'll have a hard time convincing google that you don't mean "sine". So instead search "graph deadly sins", "data visualization sins", "data is ugly", and so on. I'll pass you specifically the blog of "Dr. Moron" (Kennith Moreland) and one discussion of bad plots https://www.drmoron.org/posts/better-plots/ (Ken is a data visualization expert and both his blogs have a lot on vis). There's also vislies: https://www.vislies.org/2021/
(Source: started my PhD in viz and still have close friends in infoviz and sciviz who I get to hear their rants about their research, and occasionally I contribute)
It sounds like perhaps what you are trying to do is something more like this?
check out the visual simulations of the
http://visual6502.org/sim/varm/armgl.html
http://visual6502.org/JSSim/index.html
http://visual6502.org/JSSim/expert-6800.html
I will say (and please forgive that digital circuits are not my field), there are almost certainly better techniques and approaches in the field to accomplish what you are trying to do. I would personally move away from what you are trying and seek insight in the domain that's able to produce multi-billion transistor microprocessors.
Perhaps there are tools for large-scale logic circuit simulation?
https://old.reddit.com/r/computerscience/comments/uhappo/bes...
0 - https://www.cs.purdue.edu/homes/xmt/classes/slides/CS530/Inf...
- https://en.wikipedia.org/wiki/Data_and_information_visualiza...
There used to be a lively research field for information visualization that studied current visualization techniques and proposed new ones to solve specific challenges -- I remember when treemaps were first introduced for example [1]. Large networks were a pretty big area of research at the time with all kinds of centrality clustering, and edge minimization techniques.
1 - https://www.google.com/search?q=treemap+visualization&tbs=im...
A few teams even tried various kind of hyperbolic representations [2,3] so that areas under local inspection were magnified under your cursor, and the rest of the hairball was pushed off to the edges of the display. But with big graphs you run into quite a few big problems very quickly like local vs. global visibility, layout challenges, etc.
2 - https://graphics.stanford.edu/papers/webviz/webviz/node2.htm...
3 - https://www.caida.org/catalog/software/walrus/
Not specifically graph related, but the best critical thinker I know of in the space is probably Edward Tufte [4]. I have some problems with a few bits of his thinking, and other than sparklines his contributions are mostly in terms of critically challenging what should be represented, why, how, and methods of interaction, his critical analysis has stayed up there as some of the best. He has a book set that's a really great collection of his thoughts.
4 - https://www.edwardtufte.com/tufte/
If you approach this problem critically, you end up at the inevitable conclusion that trying to globally visualize a massive graph in general is basically useless. Sure there are specific topologies that can be abstracted into easier to display graphs, but the general case is not conducive. It's also somewhat surprising at how small a graph can be before visualizing it gets out of hand -- maybe a few dozen nodes and edges.
I remember the U.S. DoE did some really pioneering studies in the field and produced some underappreciated experts like Thomas, Cook and Risch [5,6]. I like Risch's concepts around visualizations as formal metaphors of data. I think he's successful in defining the rigorous atomic components of visualization that you can build up from. Considering OP's request in view of Tufte and Risch, I think that they really need to think about the potential for different metaphors at different levels of detail (since they specify zooming in and out). There may not exist a single metaphor that can visualize certain data at every conceivable scope and detail!
5 - https://ils.unc.edu/courses/2017_fall/inls641_001/books/RD_A...
6 - https://arxiv.org/pdf/0809.0884v1
One interesting artifact from all of this is that most of the research has long ago been captured and commoditized or made open source. There really isn't a market anymore for commercial visualization companies, or grant money for visualization research. D3.js [7] (and the derivatives) more or less took millions upon millions of dollars in R&D and commercial research and boiled it down into a free, open source, library that captured pretty much all of the major findings in one place. It's objectively better than anything that was on the market or in labs at the time I was in the space and it's free.
Hairballs are not interesting, but the shapes that show up in a graph once you make a few cuts can be fascinating.
I think there is a need for a tool that can extract and tell an interesting story based on a subgraph of a huge graph, but that takes thinking unlike hairball plotting, ai image generation and other seductive scourges.
I went to an posthumous art show based on this guy
https://www.amazon.com/Interlock-Conspiracy-Shadow-Worlds-Lo...
where they showed how he drew 40 drafts with pencil of one of his graphs and went from a senseless hairball to something that seems immediately meaningful. Funny that might have something to do with his mysterous death... Maybe a tool that would help you do that is too dangerous for "them" to let you have!
I doubt we'd see such a tool anytime soon. It takes expert experience and skill to make good visualizations and there are no well defined rules. If you see such a tool, I'd be wary of promises that are too big to be kept.
[0] Sometimes people complain about how something has a difficult/steep learning curve. It is important to note that while frustrating, this does not always make the learning curve a bad thing. Often a shallow learning curve can be bad because it convinces one that they have far greater ability than they actually do. We could argue that this is in part due to the improper way we visualize learning curves.
This may be one of the most rediculous conspiracy theories i have ever heard. Big data (heh) had him killed... ok.
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.
Context: I’m the CTO of a GraphViz company, I’ve been doing this for 10+ years.
Here are my recommendations:
- if you can generate a projection of your graph into millions of nodes, you might be able to get somewhere with Three.js, which is a JS library to generate WebGL graphics. The library is close enough to the metal to allow you to build something large and fast.
- if you can get the data below 1M nodes, your best shot is Ogma (spoiler: my company made it). It scales well thanks to WebGL and allows for complex interactions. It can run a graph layout on the GPU in your browser. See https://doc.linkurious.com/ogma/latest/examples/layout-force...
- If you want to keep your billions of nodes but are OK with not seeing the whole graph at once, my company builds Linkurious. It is an advanced exploration interface for a graph stored in Neo4j (or Amazon Neptune). We believe that local exploration up to 10k nodes on screen is enough, as long as you can run graph queries and full-text search queries against the whole graph with little friction. See https://doc.linkurious.com/user-manual/latest/running-querie...
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.
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
is 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.
If you want other resources, I also have a GitHub list of Graph-related libraries (visualizations etc.) on GitHub[3].
[1]: https://js.cytoscape.org/ [2]: https://github.com/anvaka/VivaGraphJS [3]: https://github.com/stars/AlexW00/lists/graph-stuff
It does tend to “hairball” (technical term) at about 500+ nodes. That’s not the tools fault, just large graphs tend to be difficult.
It’s just hard to imagine visualizing a million plus nodes without doing some clustering first.
Note that visualizations are limited by human perception to ~10000 elements, more usefully 1000 elements. You might try a force directed graph, perhaps a hierarchical variant wherein nodes can contain sub-graphs. Unless you have obvious root nodes, this variant would be interesting in that the user could start from an arbitrary set of nodes, giving different insights depending on their starting point.
1 - An excerpt from "Harder Drive", a rather silly implementation of a unix block device using ping latency with any host that will let him. He visualizes the full ipv4 address space in a hilbert curve at this offset: https://youtu.be/JcJSW7Rprio?si=0AlyMgaZjH7dmh5y&t=363
It visualizes the IPv4 space based on reverse DNS responses.
There's almost never a use case where a customer wants to see a gigantic graph. Or researchers. Or family members for that matter. People's brains just don't seem to mesh with giant graphs. Tiny graphs, sure. Sub-graphs that display relevant information, sure. The whole thing? Nah. Unless it's for an art project, in which case giant graphs can be pretty cool looking.
In moments like these your job is to not be the monkey's paw. Don't just blithely give them what they asked for. Ask more questions to find out what they're actually trying to accomplish, and help them compose a more specific request that's closer to what they actually want.
https://gephi.wordpress.com/2024/06/13/gephi-week-2024-peek-...
- Deal with 100k node graphs, preferably larger
- Interactive filtering tools, e.g. filtering by node or edge data, transitive closures, highlighting paths matching a condition. Preferably filtering would result in minimally re-layouting the graph.
- Does not need an very sophisticated layout algorithms, if hiding or unranking nodes interactively is easy. E.g. centering on a node could layout other nodes using the selected node as the root.
- Ability to feed live data externally, add/remove nodes and edges programmatically
- Clusters (nodes would tell which clusters they belong in)
I'm actually thinking of writing that tool some day, but it would of course be nicer if it already existed ;). I'm thinking applications like studying TLA+ state traces, visualizing messaging graphs or debug data in real time, visualizing the dynamic state of a network.
Also if you have tips on applicable Rust crates to help creating that, those are appreciated!
So I gave it a try and it seems quite a capable tool. It doesn't check all my boxes and is more cumbersome to use than I'd wish, e.g. it is able to find shortest path between nodes, but activating that needs finding and entering the node ids manually.
However, this still seems the best tool I've ever seen for this purpose and it's also highly general. Thanks!
Tested it up to 5M nodes, renders above 60fps on my laptop's iGPU and on my Pixel 7 Pro. Turns out, drawing lots of points using shaders is fast.
Though like everybody else here said you probably don't want to draw that many nodes. Create a lower LoD version of the graph and render it instead
Visualizations are great at helping humans parse data, but usually they work best at human scales. A billion nodes is at best looking at clouds, rather than nodes, which can be represented otherwise.
You could copy their design, if you know how you want to project your nodes into 2D. Essentially dividing the visualisation into a very large number of tiles, generated at 18 different zoom levels, then the 'slippy map' viewer loads the tiles corresponding to the chosen field of view.
Then a PostGIS database alongside, letting you run a query to get all the nodes in a given rectangle - such as if you want to find the ID number of a given node.
Of course, they do get to dodge a major problem: That high-dimensional data is hard to visualise in an understandable way. Everyone knows what a map looks like, nobody knows what a clear visualisation of a set of 100-dimensional vectors looks like.
I created an HTML page that used vis-network to created a force-directed nodegraph. I'd then just open it up and wait for it to settle.
The initial code is here, you should be able to dump it into an LLM to explain: https://github.com/HebeHH/skyrim-alchemy/blob/master/HTMLGra...
I later used d3 to do pretty much the same thing, but with a much larger graph (still only 100,000 nodes). That was pretty fragile though, so I added an `export to svg` button so you could load the graph, wait for it to settle, and then download the full thing. This kept good quality for zooming in and out.
However my nodegraphs were both incredibly messy, with many many connections going everywhere. That meant that I couldn't find a library that could work out how to lay it out properly first time, and needed the force-directed nature to spread them out. For your case of 1 billion nodes, force-directed may not be the way to go.
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
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.
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.
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.
Even 8k-screens have not enough pixel to show that many nodes at the same time. So some visual optimization has to happen anyway.
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.
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.
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.
4,294,967,296^2,073,600 is very large but 2^(10^22) is much much larger
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.
It's only 24-bits of visible colours.