4 ms·
I don't know much about graph neural networks although it is a topic that I want to study in the next few months. But what bothered me in your article is what
by sischoel 6y ago
I don't know much about graph neural networks although it is a topic that I want to study in the next few months.
But what bothered me in your article is what you wrote about graph data structures.
NetworkX is indeed very slow, this is due to two facts:
- NetworkX is a pure Python implementation and does not relay on some methods written in a faster language like C.
- They use dictionaries to represent the graphs, which may have some advantages when mutating graphs, but of course have much worse locality than an adjacency list or a some sparse matrix format.
But even for python there are much faster libraries such as igraph. The data structure in igraph is an edge list.
A lot of single core graph libraries use an adjacency list internally, and while it is true that the index list for each vertex can be somewhere arbitrary in memory, they usually do not behave like a linked list, unless you graph is really sparse.
One of the most used operations in graph algorithms is to iterate over the neighbors of a vertex, and for this, adjacency lists are very good.
They also have a small advantage over CSR matrices for adding or removing edges, and they might use slightly less memory, as their index type only needs to be able to index all vertices and not all edges, so they need half of the space, which is better for caches.
- tehjoker 6y agoThere's graph-tool but it is annoying to compile sometimes: https://graph-tool.skewed.de/ https://graph-tool.skewed.de/
- enriquto 6y agoIndeed, the best support for large graphs in Python is found inside scipy.sparse
- jim22k 6y agoAnyone who is serious about graph analysis in Python using linear algebra should check out GraphBLAS (graphblas.org). The inclusion of semirings makes things like SSSP and BFS extremely elegant on sparse adjacency matrices. The main implementation is SuiteSparse::GraphBLAS, a C library which has two Python bindings (search for grblas or pygraphblas). Disclosure: I'm the author of grblas. Both are available on conda-forge for easy installation. If you want to try it out without installing, here is a binder link: https://mybinder.org/v2/gh/metagraph-dev/grblas/HEAD?filepath=notebooks%2FIntro%20to%20GraphBLAS%20%2B%20SSSP%20example.ipynb https://mybinder.org/v2/gh/metagraph-dev/grblas/HEAD?filepat...
- VHRanger 6y agoThanks! What's the underlying data structure of the graph?
- lmeyerov 6y agoI've found sparse good for many-columns (10K+). However, for graphistry's graph workloads, we do most scipy-size graphs at much higher speeds via cudf + cugraph. Similar apis, more speed. Ex: Preprocess many cols with scikit sparse (genomes, many-featured fraud, ...) -> cudf (= gpu dataframes) for most of workload -> infer relationships with gpu UMAP then gpu k-nn -> graphistry for visual analysis. We're starting to experiment with bigger-than-memory (TB etc) scale via the gpu-enabled dask libs. I definitely recommend trying. If interested in adding visual analytics here, these'll be hitting our free + self-hosted layers soon, and drop a contact method if you'd like early access. Exciting times!
- VHRanger 6y agoRight, the data structure depends on the tradeoff being made. Do you add or remove nodes as often as you traverse the graph? Then a dictionary/network-of-pointers make sense. But generally, if you're doing that a lot, a database also makes sense which is why I don't like the tradeoff NetworkX made at all. If you don't add nodes often at all, but traverse from edge-to-edge a lot, a CSR representation makes sense. Adjacency array representations have other tradeoffs vis-a-vis CSR representaitons and are kind of an in-between solution.
- jedbrown 6y agoThe index type for CSR need only index nodes. It's the offsets (one per row) that need to index edges. The blog's portrayal of NVMe vs distributed memory is a bit off: > With modern NVMe drives random seeks aren’t slow anymore, much faster than distributed network calls like you do when scaling the linked list-based graph. Distributed memory machines has 1 microsecond off-node latency and 15-20 microsecond reductions (with thousands of nodes). These latencies have been pretty flat for the past 20 years in supercomputing, and have been widely available at cloud providers for the past few years. NVMe is not as fast as it's made out to be. https://twitter.com/SwiftOnSecurity/status/990797948354211840 https://twitter.com/SwiftOnSecurity/status/99079794835421184... The other issue is that NVMe is more expensive than DRAM or HBM when you care about bandwidth (and graph/network analysis is almost always memory bandwidth limited, even on HBM). Suppose you need to do 1000 traversals of a 1 TB data structure. This takes about 10 seconds with 100 HBM devices ($1 at on-demand pricing, assuming amortized startup), but days of saturating NVMe bandwidth.
- sischoel 6y agoYes, I had something mixed up here - you are completely right about CSR matrices, they should not use more memory than an adjacency list.
- VHRanger 6y agoThanks for the correction. I was aware of the speed of distributed cluster reads, but I might be overestimating the speed of NVMe random seeks. > The other issue is that NVMe is more expensive than DRAM How are you calculating that? When I upgraded my home server the other week, 16GB of DDR3-1600 cost nearly as much as 1TB of decently fast NVMe (HP SX920). Would you still think an on-disk mmap'ed CSR graph library be useful for medium-scale usecases given modern SSDs? Or do you think such latencies kill any use
- jedbrown 6y agoUnless your data is at rest, you're paying for bandwidth, not capacity. SRAM > HBM > DRAM > NVMe when you're buying bandwidth. Seriously, when we have a low-latency network, the most cost-effective way to run some simulations and graph algorithms is out of L3 on EPYC (where mid-tier parts have over 1 TB/s at a fraction of the energy and cost of an A100/MI100). Your NVMe quotes 3.2 GB/s, versus 25 GB/s (theoretical) for a stick of DDR4-3200 (which is in the same price range). A standard 2-socket EPYC server can give you 300 GB/s from DRAM, but you'd need several servers servers packed with NVMe to provide that bandwidth. The rationale for persistent storage (like NVMe) as an algorithmic device is either (a) you need it to be persistent or (b) you have physical or algorithmic constraints that prevent you from using more parallelism and you're willing to pay 5-10x for the privilege of executing from NVMe.