Connected-Components

In a previous post, I was sceptical about using Apache DataFusion for graph analytics. However, after some thought and experimentation, I changed my mind. I have reconsidered my approach and now have a working implementation of basic graph algorithms, such as WCC, PageRank and MSSP. For example, I can identify weakly connected components in a graph with two billion edges using just 10 GB of RAM and two cores. This is one of the most widely used graph algorithms and lies behind most entity resolution. The pure CSR of this graph requires over 15 GB of raw memory (or 30 GB if it is treated as undirected, as WCC requires). The hard limit was 10 GB of RAM when using systemd-run -p MemoryMax=10G, and the process was successful. Not Vibe-coded.

I don’t think anyone besides me has considered using Apache DataFusion to write graph algorithms. I still don’t fully understand DataFusion’s place in the world of graphs, but I’d like to share my initial experience with it. Spoiler alert: It’s surprisingly good! In this post, I will explain the weakly connected components problem and its close relationship to the common problem of modern data warehouses (DWHs), namely, identity resolution. I will also describe an algorithm for connected components in a MapReduce paradigm. I consider this to be the algorithm that strikes the best balance between performance and simplicity. Finally, I’ll present my DataFusion-based implementation of the algorithm and the results of toy benchmarks on a graph containing four million nodes and 129 million edges. As always, keep in mind that this post is very opinionated!