Max k-Cut

Overview

The Max k-Cut algorithm partitions the nodes of a graph into k groups such that the number of edges between different groups is maximized. It uses a greedy local search approach: starting from a random partition, it iteratively moves each node to the partition that maximizes the cut size.

Unlike community detection algorithms that maximize intra-group connectivity, Max k-Cut maximizes inter-group edges. It has applications in network design, VLSI layout, and frequency assignment.

Concepts

Maximum k-Cut

Given a graph and an integer k, the maximum k-cut problem seeks to partition the nodes into k disjoint sets such that the total number of edges crossing between sets is maximized. When k = 2, this is the classic maximum cut problem.

In this example with k = 2, the optimal cut places nodes {A, D} in one partition and {B, C, E} in the other, cutting 5 of the 6 edges.

The Max k-Cut problem is NP-hard, so the algorithm uses an approximation via local search that converges to a locally optimal solution.

Considerations

• The algorithm treats all edges as undirected.
• Results may vary between runs due to random initialization.

Example Graph

GQL
INSERT (A:default {_id: "A"}), (B:default {_id: "B"}),
       (C:default {_id: "C"}), (D:default {_id: "D"}),
       (E:default {_id: "E"}), (F:default {_id: "F"}),
       (G:default {_id: "G"}), (H:default {_id: "H"}),
       (A)-[:default]->(B), (A)-[:default]->(C),
       (A)-[:default]->(D), (A)-[:default]->(E),
       (A)-[:default]->(G), (D)-[:default]->(E),
       (D)-[:default]->(F), (E)-[:default]->(F),
       (G)-[:default]->(D), (G)-[:default]->(H)

Parameters

Run Mode

Returns:

GQL
CALL algo.maxkcut({
  k: 3
}) YIELD nodeId, partition, cutSize

Result:

Stream Mode

Returns the same columns as run mode, streamed for memory efficiency.

GQL
CALL algo.maxkcut.stream({
  k: 2
}) YIELD nodeId, partition
RETURN partition, COLLECT(nodeId) AS members
GROUP BY partition

Result:

Stats Mode

Returns:

GQL
CALL algo.maxkcut.stats({
  k: 2
}) YIELD nodeCount, partitionCount, cutSize

Result:

Write Mode

Computes results and writes them back to node properties. The write configuration is passed as a second argument map.

Write parameters:

Writable columns:

Returns:

GQL
CALL algo.maxkcut.write({k: 3}, {
  db: {
    property: "cut_group"
  }
}) YIELD task_id, nodesWritten, computeTimeMs, writeTimeMs