Abstract  We propose a new heuristic for the graph partitioning problem. Based on the traditional iterative improvement framework, the heuristic uses a new type of gain in selecting vertices to move between partitions. The new type of gain provides a good explanation for the performance difference of tie-breaking strategies in KL-based iterative improvement graph partitioning algorithms. The new heuristic performed excellently. Theoretical arguments supporting its efficacy are also provided. As the proposed heuristic is considered a good candidate for local optimization engines in metaheuristics, we combined it with a genetic algorithm as a sample case and obtained a surprising result that even the average results over 1,000 runs equalled the best known for most graphs.