Kernighan–Lin algorithm and multiple gain functions
Kim and Moon (2004) compare variants of Kernighan-Lin which combine the usual gain and a lock-based gain, which is relative to the locked vertices. You can combine two gain functions in the range $-n\ldots n$ using an implementation of Fiduccia-Matheyses with $O(n^2)$ buckets.

Kim, Moon, Lock-gain based Graph Partitioning, J Heuristics, 10, 37-57, 2004.