> "I can compute PageRank on a directed graph with one billion edges (graph500-26 from the Graphalytics dataset) using 5 GB of memory. Alternatively, I can identify all the weakly connected components in a graph with two billion edges (twitter_mpi from the same dataset collection) using 10 GB of memory. Neither NetworkX nor Igraph can do this; most existing graph algorithms require the graph to fit into memory. Previously, I thought you needed Apache Spark and GraphFrames for billion-scale graph analytics. Now, however, I think all you need is a laptop. I have completely changed my old opinion about using Apache DataFusion for graph analytics."
33M vertices and 1B edges easily fits into memory, if you use 32 bit integers, it will require about 4 GiB of memory. Out of curiosity I just implemented generating a random graph of that size and calculating one page rank iteration on it in the most naive way (20 lines of C#) and it consumed 8.4 GiB of memory and got one iteration done in 4:20 minutes single threaded.
~10 years ago, we helped create apache arrow, helped create GPU data frames, and been running for the last decade the open source pygraphistry and now gfql cpu+gpu property graph engine for this. Likewise, Nvidia has been doing great with cuGraph (OSS) for GPU algs around this.
It is great you are finding success with this direction, but "shoulders of giants" merit credit - 100+ people.
Ofc. I'm not claiming credit for Apache Arrow. Lots of people contributed to it.
I didn't write the graph algorithms in networkit. Somebody else did.
But if you're looking for 100-200 graph algorithms running efficiently on columnar memory, I haven't found a working implementation that's permissively open source.
Happy to work with cugraph or anyone else who builds on top of Parquet/Arrow ecosystem.
cudf/cugraph is open source and helped fund the arrow ecosystem , I think it's good to give teams credit when they do work they didn't have to do and not misrepresent them. And yes, it works great, graph500 leaderboard level.
CUDA and the ecosystem around it is more complicated.
I'll use it. I agree that it advanced the state of the art and helped fund some of the truly OSS projects.
Don't feel the need to bring it up on a HN comment. Neither does the parent article by Sem.
In fact, it's in the vendor's interest to transparently route the algorithms in Icebug to the GPU in a compatible way instead of writing their own APIs.
They use networkx today: https://github.com/rapidsai/nx-cugraph/ because it's more popular than networkit or icebug. But its popularity is based on ease of use, not performance:
we use igraph cpu / cugraph gpu in pygraphistry/gfql projects, and our experience is cugraph is ~10X+ on tiny cheap GPUs over igraph. looking at that table, where all seem same magnitude as igraph, I'd therefore expect much better than all the options listed. And when things get bigger and it merits a bigger GPU, even better. The team has been doing a great job over the last decade, and all free.
cudf+cugraph are the table+graph algorithms that started around that same time to align with it, that's what helped get arrow funded from the nvidia side
can't reply on the below, but re:networkx, it was more of the reverse, they did a nice job of building a standalone embeddable table+graph arrow-friendly library over many years, and with networkx compatibility from the beginning. Later, they collaborated with the networkx team to eventually upstream it so networkx users can benefit more easily
as it is embeddable, you don't need to go through networkx to use it -- eg, we use it directly, as do various databases
and I'm not sure why you're saying people do not use networkx->cugraph because of performance, again, this is graph500 level performance that even graph database vendors now support because it is literally magnitudes faster than their cpu alternatives. We have had projects like court cases where the data science team switched to sitting on top of pygraphistry/gfql -> cudf/cugraph and using the GPU versions were the difference between hours and minutes, which for iterating over interactive analysis, is important. It's night and day going from CPU -> GPU, and a lot of butts were saved because of this.
We see the same thing with databricks+neo4j migrations.. most tools have their sweet spots, but also their comparative weak spots.
agreed. gfql already gives this best-of-both for oss cpu+gpu cypher as we've been steadily working through benchmarks like ldbc, pokec, etc.
The HPC lessons for graph algorithms is less obvious as the substrate the OP is working through is close but not quite what HPC folks figured out, so the trade-off of fast to write and maintainable (dataframe/db-based) vs at the achievable magnitude of performance is tricky. LLMs change the calculus here too IMO, so I've been thinking a lot about more NUMA-exposed ideas that before were relegated to PhD land.
Hello, I am new to hacker news and finding it really resourceful. I found this article interesting (having learnt KG and Map Reduce (spark) as part of my masters' course), appreciate the effort to post this.
I am here to seek guidance from the community. I want to refresh my memory on knowledge graphs and algorithms for Big Data Mining and Processing.
I believe KG can solve problems on Agent attacks (LLM agency) in real-time - so want to build knowledge around the topic.
Interested to join any interest/ discussion groups if any.
Thanks!
Love this Sem. Will provide a great alternative to the SQL based connected components algorithm we ship in Splink. Looking forward to testing how much faster it is. Thanks for your work on it!
It would be nice if OP noted what caused the change in their opinion?
did datafusion gain some feature that they noted was missing in the previous article, or did something in their understanding click so they could overcome the previous issues?
I thought of datafusion work and the rust implementation as a way to address the delta seen vs the Spark/JVM GraphFrames implementation (author is a major contributor).
Looking forward to more such innovations, which will benefit the ecosystem as a whole. Why would anyone want to use a pure python graph algorithm package unless they're dealing with toy graphs?
We shared with the author how databricks multi-node and single-node graphframes were wildly inefficient for this kind of thing: we were measuring doing billion-edge graph traversals & scans in single node in-memory in seconds with regular dataframe (cudf) libraries, so the core of pagerank, which is magnitudes more efficient than their original spark approach
So then the question became pandas/polars/datafusion/duckdb/etc, must of which are rust/native. I'm curious myself why datafusion vs others, it's an interesting project :)
It's hard to take the article seriously when it has quotes like this:
"The hardest part. 2B edges twitter graph is already huge (its edges are 30 GB in CSV !!!)."
Who cares how big the graph is in CSV? That's not the representation you operate over in big data.
All of this would have easily fit in memory on any reasonable modern system.
Related, we recently release the polars version of GFQL, the only oss cypher property graph query engine for CPU+GPU, and even better, no database nor outside process needed. We started doing LDBC benchmarks vs neo4j, memgraph, kuzu, etc, and are already starting to outperform them both on latency for small OLTP graph searches and $, speed for big graph OLAP ones, especially in GPU mode.
The cool in the original post was directly inspired by our work here, with our advocacy to the author of keeping their previous Spark work for initial data lake data extraction, and the actual graph work to be redone in our columnar in-memory optimized style for magnitudes of speedup , cost savings
Datafusion is undoubtedly one of the best open source projects of all time, it's so incredibly powerful and well designed.
The extensibility is insane, you can create your own query language that compiles to logical plans.
> "I can compute PageRank on a directed graph with one billion edges (graph500-26 from the Graphalytics dataset) using 5 GB of memory. Alternatively, I can identify all the weakly connected components in a graph with two billion edges (twitter_mpi from the same dataset collection) using 10 GB of memory. Neither NetworkX nor Igraph can do this; most existing graph algorithms require the graph to fit into memory. Previously, I thought you needed Apache Spark and GraphFrames for billion-scale graph analytics. Now, however, I think all you need is a laptop. I have completely changed my old opinion about using Apache DataFusion for graph analytics."
Impressive!
33M vertices and 1B edges easily fits into memory, if you use 32 bit integers, it will require about 4 GiB of memory. Out of curiosity I just implemented generating a random graph of that size and calculating one page rank iteration on it in the most naive way (20 lines of C#) and it consumed 8.4 GiB of memory and got one iteration done in 4:20 minutes single threaded.
It reminds me of that Frank MacSherry paper[1]...
[1] "Scalability! But at what COST?"
> most existing graph algorithms require the graph to fit into memory.
You can get pretty far with sparse graphs, which are just arrays, in combination with memory mapping.
cool! you might be interested in graphchi (2012), also designed to do large scale graph operations on a single machine
https://github.com/GraphChi/graphchi-cpp#performance
I got to use graphchi/graphlab back in the day (I think I still have the tshirt from the 2013 conference), wish it had caught on more.
It looks similar to networkit in that it represents graphs using row oriented memory layout.
I forked networkit for exactly this reason. Columnar memory is much more efficient.
The idea of graph algorithms on Apache arrow at scale originated here. 100+ graph algorithms running on columnar memory.
https://github.com/Ladybug-Memory/icebug
Out of core with datafusion is the main innovation here in graphframes-rs. But it has only 2 algorithms so far.
Icebug and LadybugDB can be tightly integrated to efficiently move tables encoded as compressed sparse row (CSR) into arrow memory.
Jupyter notebooks available.
https://github.com/LadybugDB/ladybug-icebug-notebooks/blob/m...
Trade-off: datafusion allows you to do fine grained storage integration (spill to disk as a part of the algorithm).
The icebug/ladybug way is coarse grained. But it allows you to run cypher instead of writing datafusion operators.
Not really ;-)
~10 years ago, we helped create apache arrow, helped create GPU data frames, and been running for the last decade the open source pygraphistry and now gfql cpu+gpu property graph engine for this. Likewise, Nvidia has been doing great with cuGraph (OSS) for GPU algs around this.
It is great you are finding success with this direction, but "shoulders of giants" merit credit - 100+ people.
Ofc. I'm not claiming credit for Apache Arrow. Lots of people contributed to it.
I didn't write the graph algorithms in networkit. Somebody else did.
But if you're looking for 100-200 graph algorithms running efficiently on columnar memory, I haven't found a working implementation that's permissively open source.
Happy to work with cugraph or anyone else who builds on top of Parquet/Arrow ecosystem.
cudf/cugraph is open source and helped fund the arrow ecosystem , I think it's good to give teams credit when they do work they didn't have to do and not misrepresent them. And yes, it works great, graph500 leaderboard level.
I'm happy to credit these people.
https://arrow.apache.org/docs/r/authors.html
CUDA and the ecosystem around it is more complicated.
I'll use it. I agree that it advanced the state of the art and helped fund some of the truly OSS projects.
Don't feel the need to bring it up on a HN comment. Neither does the parent article by Sem.
In fact, it's in the vendor's interest to transparently route the algorithms in Icebug to the GPU in a compatible way instead of writing their own APIs.
They use networkx today: https://github.com/rapidsai/nx-cugraph/ because it's more popular than networkit or icebug. But its popularity is based on ease of use, not performance:
https://github.com/timlrx/graph-benchmarks
Not clear if the author or anyone else has an updated version of these benchmarks. Opened an icebug issue on the repo.
see graph500
we use igraph cpu / cugraph gpu in pygraphistry/gfql projects, and our experience is cugraph is ~10X+ on tiny cheap GPUs over igraph. looking at that table, where all seem same magnitude as igraph, I'd therefore expect much better than all the options listed. And when things get bigger and it merits a bigger GPU, even better. The team has been doing a great job over the last decade, and all free.
cudf+cugraph are the table+graph algorithms that started around that same time to align with it, that's what helped get arrow funded from the nvidia side
can't reply on the below, but re:networkx, it was more of the reverse, they did a nice job of building a standalone embeddable table+graph arrow-friendly library over many years, and with networkx compatibility from the beginning. Later, they collaborated with the networkx team to eventually upstream it so networkx users can benefit more easily
as it is embeddable, you don't need to go through networkx to use it -- eg, we use it directly, as do various databases
and I'm not sure why you're saying people do not use networkx->cugraph because of performance, again, this is graph500 level performance that even graph database vendors now support because it is literally magnitudes faster than their cpu alternatives. We have had projects like court cases where the data science team switched to sitting on top of pygraphistry/gfql -> cudf/cugraph and using the GPU versions were the difference between hours and minutes, which for iterating over interactive analysis, is important. It's night and day going from CPU -> GPU, and a lot of butts were saved because of this.
We see the same thing with databricks+neo4j migrations.. most tools have their sweet spots, but also their comparative weak spots.
The reason for not recommending networkx is the choice it offers:
I'm looking to offer something that's best in class on both CPU and GPU, so people don't have to choose.Now that nvidia is becoming a major CPU vendor, they may like the idea too.
agreed. gfql already gives this best-of-both for oss cpu+gpu cypher as we've been steadily working through benchmarks like ldbc, pokec, etc.
The HPC lessons for graph algorithms is less obvious as the substrate the OP is working through is close but not quite what HPC folks figured out, so the trade-off of fast to write and maintainable (dataframe/db-based) vs at the achievable magnitude of performance is tricky. LLMs change the calculus here too IMO, so I've been thinking a lot about more NUMA-exposed ideas that before were relegated to PhD land.
Hello, I am new to hacker news and finding it really resourceful. I found this article interesting (having learnt KG and Map Reduce (spark) as part of my masters' course), appreciate the effort to post this.
I am here to seek guidance from the community. I want to refresh my memory on knowledge graphs and algorithms for Big Data Mining and Processing.
I believe KG can solve problems on Agent attacks (LLM agency) in real-time - so want to build knowledge around the topic.
Interested to join any interest/ discussion groups if any. Thanks!
Love this Sem. Will provide a great alternative to the SQL based connected components algorithm we ship in Splink. Looking forward to testing how much faster it is. Thanks for your work on it!
It would be nice if OP noted what caused the change in their opinion?
did datafusion gain some feature that they noted was missing in the previous article, or did something in their understanding click so they could overcome the previous issues?
There is a bit of healthy competition going on between graphframes and icebug. See:
https://github.com/Ladybug-Memory/icebug-graphframes-compari...
I thought of datafusion work and the rust implementation as a way to address the delta seen vs the Spark/JVM GraphFrames implementation (author is a major contributor).
Looking forward to more such innovations, which will benefit the ecosystem as a whole. Why would anyone want to use a pure python graph algorithm package unless they're dealing with toy graphs?
We shared with the author how databricks multi-node and single-node graphframes were wildly inefficient for this kind of thing: we were measuring doing billion-edge graph traversals & scans in single node in-memory in seconds with regular dataframe (cudf) libraries, so the core of pagerank, which is magnitudes more efficient than their original spark approach
So then the question became pandas/polars/datafusion/duckdb/etc, must of which are rust/native. I'm curious myself why datafusion vs others, it's an interesting project :)
3.4 gb dataset on 10gb ram
It's hard to take the article seriously when it has quotes like this: "The hardest part. 2B edges twitter graph is already huge (its edges are 30 GB in CSV !!!)."
Who cares how big the graph is in CSV? That's not the representation you operate over in big data.
All of this would have easily fit in memory on any reasonable modern system.
Here is a proposal built on parquet/arrow. What other alternatives exist that can be queried by a database without ingest?
https://github.com/Ladybug-Memory/icebug-format
DataFusion is really cool, it's kind of like the LLVM of the OLAP world.
Really cool visualization, amazing how it resembles a neural network.
I'm pretty sure that's some stock output from CAIDA, looks like a traceroute graph from the inset
Does it support out-of-core or multi-processor processing?
Related, we recently release the polars version of GFQL, the only oss cypher property graph query engine for CPU+GPU, and even better, no database nor outside process needed. We started doing LDBC benchmarks vs neo4j, memgraph, kuzu, etc, and are already starting to outperform them both on latency for small OLTP graph searches and $, speed for big graph OLAP ones, especially in GPU mode.
The cool in the original post was directly inspired by our work here, with our advocacy to the author of keeping their previous Spark work for initial data lake data extraction, and the actual graph work to be redone in our columnar in-memory optimized style for magnitudes of speedup , cost savings
Pip install, benchmarks : https://pygraphistry.readthedocs.io/en/latest/gfql/benchmark...