  We present new refinement heuristics for the balanced graph partitioning
problem that break with an age-old rule. Traditionally, local search only
permits moves that keep the block sizes balanced (below a size constraint). In
this work, we demonstrate that admitting large temporary balance violations
drastically improves solution quality. The effects are particularly strong on
irregular instances such as social networks. Designing efficient
implementations of this general idea involves both careful selection of
candidates for unconstrained moves as well as algorithms for rebalancing the
solution later on. We explore a wide array of design choices to achieve this,
in addition to our third goal of high parallel scalability. We present
compelling experimental results, demonstrating that our parallel unconstrained
local search techniques outperform the prior state of the art by a substantial
margin. Compared with four state-of-the-art solvers, our new technique finds
75\% of the best solutions on irregular graphs. We achieve a 9.6\% improvement
in edge cut over the next best competitor, while being only 7.7\% slower in the
geometric mean.
