How to partition 3d Voronoi graph into n-number of balanced cuts while minimizing the number of edges that go between the parts?

Question

I have a 3d Delaunay triangulation and I construct a Voronoi diagram from it. I have a computation algorithm: for each node of the Voronoi diagram compute a value based on values that neighbouring nodes have. I would like to run this algorithm in parallel in the public cloud. Unfortunately, I cannot find a way to split my graph for maximum computation efficiency. All of my workers end up hitting the network to access neighbouring nodes. I need a way to split my graph to minimise network I/O between workers.

Ideally I want to split my graph into (approximately) balanced parts and minimize the number of edges crossing the parts.

I thought that ordering all nodes in some kind of 'locality-preserving' order is an option since I might not know upfront how many workers I have.

Answer 1

One natural thing would be to try a separator kind of trick. If the Voronoi cells are fat, and of similar size then a randomly shifted grid of the right side would do reasonably well. in particular, there is a paper by Miller and Thurston (and some other people - their names escape me) about finding a separator if you have fat regions covering space, and every point is covered only a constant number of times. It is essentially an extension of their proof of the existence of a planar separator to these more general settings.

Answer 2

Non-optimal tricks I might use:

1) Use a force directed graph drawing program, then use the layout coordinates to generate a quadtree(z-curve).

2) Use k-means, with k= 3, and distance being the shortest path length. Then recursively apply the kmeans to each cluster. You will get something close to the notion of a space filling curve. When you subdivide one cell into three, use the distance between the generator for each of the three children and the two generators of the other two parent level cells to determine the ordering. For the highest level ordering just pick something.

Answer 3

I don't see how the fact that the graph results from a voronoi diagram substantially changes the problem. You have a graph and want to do a k-cut, where k is the number of your workers. Instead of minizing just the cut, you also want to make the partitions equal in size.

There is a ridiculously simple heuristic for k-kut. Pick an edge at random and merge the nodes at both endpoints. Repeat, until desired number of components is reached. Try again from the beginning, until bored. Output best result.

This works, because expensive cuts have lots of edges that could get picked, while cheap cuts have few and are therefore selected less often.

Normally, the problem is formulated with edge weights, and edges get picked at nonuniform probabilities, scaled by their weight. If you would instead pick edges with probabilities scaled in such a way, that it favors equally sized components, it should be possible to find a heuristic that gets good results for both minimizing cut size and spreading nodes equally.

I'd suggest to weight the edges according to the number of nodes in the original graph that the resulting node would represent. Edges which represent multiple edges in the original graph, should also get higher probability (their weights start at one, but must still be aggregated on a merge). The resulting probability to pick an edge would be: (number of edges in the original graph the edge represents) / (number of nodes both endpoints represent in the original graph, combined). Off course, this needs to be normalized to 1.

In this way the components would grow at roughly equal speeds, and components which are well connected are merged together with higher preference. I just tried this with a small pen and paper example, and it seems to actually work out just like that.

Depending on whether your problem suffers more from unequal work loads or too much network access, you can tune the probabilities to prefer merging due to high edge count over merging due to low node count or vice versa.