This is a variant of Rob's improvement heuristic. Assume the nodes are indexed $1,\dots,N.$
- Assign a color to each node randomly.
- Shuffle the list $1,\dots,N$ of node indices randomly.
- For each node in the shuffled list, compute the sum of edge weights to nodes in every color group and reassign the node to the "cheapest" color (which might be the current color of the node).
- After checking every node, repeat steps 2 and 3 until you make one full pass through the shuffled list without any nodes changing color.
Since this should be pretty fast computationally, you might want to do it multiple times and take the best solution.
For something more sophisticated, there are ways to attack the problem using genetic algorithms.
Addendum: I tried both the heuristic (with random restarts) and a GA on a 20 x 10 grid graph. Given equal run times, the heuristic seemed to outperform the GA. (I also tried solving the MIP model, with CPLEX, but gave up because the lower bound is too loose to reach proven optimality in the time I was willing to allocate.)