Approximate Maximum k-cut

Finding the maximum k-cut for a graph has several known applications, for example it is used to:

In practice, finding the best cut is not feasible for larger graphs and only an approximation can be computed in reasonable time.

The approximate heuristic algorithm implemented in GDS is a parallelized GRASP style algorithm optionally enhanced (via config) with variable neighborhood search (VNS).

For detailed information about a serial version of the algorithm, with a slightly different construction phase, when k = 2 see GRASP+VNR in the paper:

To see how the algorithm above performs in terms of solution quality compared to other algorithms when k = 2 see FES02GV in the paper:

GRASP style algorithms are iterative by nature. Every iteration they run the same well-defined steps to derive a solution, but each time with a different random seed yielding solutions that (highly likely) are different too. In the end the highest scoring solution is picked as the winner.

Variable neighborhood search (VNS) works by slightly perturbing a locally optimal solution derived from the previous steps in an iteration of the algorithm, followed by locally optimizing this perturbed solution. Perturb in this case means to randomly move some nodes from their current (locally optimal) community to another community.

VNS will in turn move 1,2,…​,vnsMaxNeighborhoodOrder random nodes and using each of the resulting solutions try to find a new locally optimal solution that’s better. This means that although potentially better solutions can be derived using VNS it will take more time, and additionally some more memory will be needed to temporarily store the perturbed solutions.

By default, VNS is not used (vnsMaxNeighborhoodOrder = 0). To use it, experimenting with a maximum order equal to 20 is a good place to start.

First off, we will estimate the cost of running the algorithm using the estimate procedure. This can be done with any execution mode. We will use the mutate mode in this example. Estimating the algorithm is useful to understand the memory impact that running the algorithm on your graph will have. When you later actually run the algorithm in one of the execution modes the system will perform an estimation. If the estimation shows that there is a very high probability of the execution going over its memory limitations, the execution is prohibited. To read more about this, see Automatic estimation and execution blocking.

For more details on estimate in general, see Memory Estimation.

The mutate execution mode extends the stats mode with an important side effect: updating the named graph with a new node property containing the approximate maximum k-cut for that node. The name of the new property is specified using the mandatory configuration parameter mutateProperty. The result is a single summary row, similar to stats, but with some additional metrics. The mutate mode is especially useful when multiple algorithms are used in conjunction.

For more details on the mutate mode in general, see Mutate.

We can see that when relationship weight is not taken into account we derive a cut into two (since we didn’t override the default k = 2) communities of cost 13.0. The total cost is represented by the cutCost column here. This is the value we want to be as high as possible. Additionally, the graph 'myGraph' now has a node property community which stores the community to which each node belongs.

To inspect which community each node belongs to we can stream node properties.

Looking at our graph topology we can see that there are no relationships between the nodes of community 1, and two relationships between the nodes of community 0, namely Alice → Bridget and Charles → Bridget. However, since there are a total of eight relationships between Bridget and nodes of community 1, and our graph is unweighted assigning Bridget to community 1 would not yield a cut of a higher total weight. Thus, since the number of relationships connecting nodes of different communities greatly outnumber the number of relationships connecting nodes of the same community it seems like a good solution. In fact, this is the maximum 2-cut for this graph.

In this example we will have a look at how adding relationship weight can affect our solution.

Since the value properties on our TRANSACTION relationships were all at least 1.0 and several of a larger value it’s not surprising that we obtain a cut with a larger cost in the weighted case.

Let us now stream node properties to once again inspect the node community distribution.

Comparing this result with that of unweighted case we can see that Bridget has moved to another community but the output is otherwise the same. Indeed, this makes sense by looking at our graph. Bridget is connected to nodes of community 1 by eight relationships, but these relationships all have weight 1.0. And although Bridget is only connected to two community 0 nodes, these relationships are of weight 81.0 and 45.0. Moving Bridget back to community 0 would lower the total cut cost of 81.0 + 45.0 - 8 * 1.0 = 118.0. Hence, it does make sense that Bridget is now in community 1. In fact, this is the maximum 2-cut in the weighted case.

In the stream execution mode, the algorithm returns the approximate maximum k-cut for each node. This allows us to inspect the results directly or post-process them in Cypher without any side effects.

For more details on the stream mode in general, see Stream.

We can see that the result is what we expect, namely the same as in the mutate unweighted example.