Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Ask HN: What is the best software to visualize a graph with a billion nodes?

news.ycombinator.com

Post reply on HN
Print view View original

71–80 of 117 posts

Re: Ask HN: What is the best software to visualize a graph with a billion nodes?

#71

Post by moshegramovsky »

infecto wrote: post #44
CuriouslyC wrote: post #21

You don't. generate a hierarchical clustering of the data, then collapse nodes into groups to get under a data set size threshold at any given view distance. That gives you full interaction and the ability to do mouseover info on groups, while being able to zoom in and interact with individual nodes if you want.

This is the way imo. Nobody is consuming 100b nodes in a chart.

This is mostly a data structure problem. I am certain this can be made interactive, but it will require some elbow grease.

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.

Re: Ask HN: What is the best software to visualize a graph with a billion nodes?

#72

Post by bee_rider »

tinsane wrote: post #60

Dude is casually asking about software to visualize a graph with size comparable to whole internet...

Maybe it represents the connection between transistors in a chip. Could easily be hundreds of billions of nodes, probably a lot of structure to the edges though.

Re: Ask HN: What is the best software to visualize a graph with a billion nodes?

#75

Post by zamalek »

Try collapsing cycles into single nodes. In my experience, cycles are extremely low entropy. Those cycle nodes can then be explored on separate diagrams/pages. Explore more dimensions that allow you to collapse nodes. You effectively want to turn you graph into a data cube.

Re: Ask HN: What is the best software to visualize a graph with a billion nodes?

#76

Post by david_p »

As many people already commented, no one actually visualizes graphs of that size at once.

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...

Re: Ask HN: What is the best software to visualize a graph with a billion nodes?

#77

Post by CuriouslyC »

moshegramovsky wrote: post #71
infecto wrote: post #44

Earlier quoted context omitted.

This is the way imo. Nobody is consuming 100b nodes in a chart.

This is mostly a data structure problem. I am certain this can be made interactive, but it will require some elbow grease. 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 efficie…

First step is to generate a graph distance matrix to use as features.

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.

Re: Ask HN: What is the best software to visualize a graph with a billion nodes?

#78

Post by nick238 »

viraptor wrote: post #16

It really feels like an under defined task. Do you actually need to see those nodes? At that scale, you never want to render 100B of them. Instead you would need some kind of density aggregation when zoomed out and moving to LoD style k-d tree partitioning when zoomed in. That's almost the area of rendering engines like Unreal's Nanite. You can create your own renderer for data like this, but game engines are likely…

What is the average degree of the 100B nodes in this graph? If it's anything north of like...2 (or maybe 1.0000001, or less, unsure), then this sounds about as intractable as "visualizing Facebook friends" (times 30)

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.

Re: Ask HN: What is the best software to visualize a graph with a billion nodes?

#79

Post by pfortuny »

exe34 wrote: post #63
bunderbunder wrote: post #62

Earlier quoted context omitted.

I'm reminded of the time back in the aughties when I was asked to help print a ~300,000 page PDF. That's about 30 boxes' worth of paper if you print double-sided. I spent an hour tracing the request back to its source and discovered that they really only wanted some specific pieces of information out of it. I extracted that information from the file and printed maybe 5 pages instead. In moments like these your job is…

> Don't just blithely give them what they asked for. Depends on how much they're paying you for it.

Just in case you are not being sarcastic: there is a thing called ethics, which is the basis of human relations.

Re: Ask HN: What is the best software to visualize a graph with a billion nodes?

#80

Post by PaulHoule »

bane wrote: post #67

Visualizing large graphs is a natural desire for people with lots of connected data. But after a fairly small size, there's almost no utility in visualizing graphs. It's much more useful to compute various measures on the graph, and then query the graph using some combination of node/edge values and these computed values. You might subset out the nodes and edges of particular interest if you really want to see them -…

I am pretty sour about it and will call out people who post "just another hairball" and act like they've done something special.

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!

Post reply on HN