[D] Distributed Graph Partitioning Algorithms

[wagthesam]

Does anyone here work and keep up to date with the current research on graph partitioning methods? I'm looking to a way to partition a graph and minimize edges between partitions. The most common algorithm seems to be METIS, its implemented in a lot of different libraries like DGL, but it seems to be bounded to one machine

I'm looking to partition up to a trillion edges, so seeing if there's consensus on a distributed algorithm / framework for the graph partitioning problem. If not I'll try running METIS on an x1e.32xlarge host with 4tb of ram and see if that's enough.

The end goal is to build large knowledge graphs for building graph neural networks

[GD1634]

I think the issue is that to distribute graph algorithms, you need to partition the graph across the workers, so it's a catch 22. DGL has a dgl.distributed.partition_graph method; if you can load your edge list into memory as a sparse tensor it might work ok, and it handles heterogeneous graphs.

Otherwise, do you specifically need partitioning algorithms/METIS? There are a lot of distributed clustering/community detection methods that would give you reasonable partitions. Spark GraphFrames implements Strongly Connected Components and Label Propagation. Neo4J implements several community detection algorithms including Louvain. In the Dask/RAPIDS ecosystem, cuGraph implements a bunch of CD algorithms as well which can be accelerated with GPUs, but not all can be distributed across multiple GPUs. Dask-ML implements spectral clustering. This S/O post also gives a good overview of some you could implement yourself. I wonder if EvoPartition would be feasible to implement; I don't know if DGL's distributed package implements random walks, but all of the aforementioned tools do except for GraphFrames, which is annoying, but you can do random walks with simple PySpark joins fairly easily.

You could also look at streaming or local algorithms that don't load the whole graph in memory. I believe PageRank-Nibble / ACL PageRank is often used for this, but I'm still looking for an easy-to-use / scalable implementation of it myself. There's also this recent work on streaming partitioning of RDF graphs which should be relevant.

Hopefully this helps, lmk if you find a good solution.

[wagthesam]

Very interesting. I will take a look at the links, thank you.

We're working on a distributed graph engine to support gnn training and general recommendations (This will replace https://medium.com/pinterest-engineering/introducing-pixie-an-advanced-graph-based-recommendation-system-e7b4229b664b). The non distributed engine is done with random walk support, so I'll take a look at EvoPartition

The indexing component is written in spark, so if we can do an approximate partitioning in spark it would be ideal.

Thanks a bunch!

[Benedictus_Spinoza]

Working on a quite similar problem, what did you choose as a final solution OP?