Graph-Algorithms

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.

About a year ago, I got involved in reviving and maintaining GraphFrames, a 10-year-old OSS project with a lot of history and not enough active maintenance. I was doing it neither for money nor to sell anything, but out of a still old-fashioned belief in free software and in the idea that it is worth spending time on software that is genuinely useful to others. This post is a reflection on what that experience has actually looked like: a constant tension between building new features and doing unglamorous maintenance, inherited code and forgotten assumptions everywhere, and the persistent fear of breaking backward compatibility in a library that had long ago been wired into important production processes.

In this blog post, I will recount my experience working on the addition of the graph embeddings API to the GraphFrames library. I will start with a top-level overview of the vertex representation learning task and the existing approaches. Then, I will focus on generating embeddings from random walks. I will explain the intuition behind and the implementation details of Random Walks in GraphFrames, as well as the chosen trade-offs and limitations. Given a sequence of graph vertices, I will explain the possible ways to learn vertex representations from it. First, I will analyze the common approach of using the word2vec model and its limitations, especially the limitations of the Apache Spark ML Word2vec implementation. I will present the results of my analysis of alternative approaches and their respective advantages and disadvantages. Finally, I will explain the intuition behind the Hash2vec approach that I chose as a starting point for GraphFrames, as well as the details of its implementation in Scala and Spark. Finally, I will present an experimental comparison of Hash2vec and Word2vec embeddings and share my thoughts about future directions.

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!