Algorithms for clustering of Word Usage Graphs are not optimal in terms of efficiency and often do not find the optimal clustering loss on larger graphs. Our aim in this paper is to find efficient ways to approximate the global minimum of a clustering loss function on three Word Usage Graphs data sets using correlation clustering and simulated annealing. Therefore we define 321 models with different initialization modifications, parameter combinations and stopping criterion and evaluate them in terms of loss, similarity to word sense description annotation, robustness and runtime. We evaluate different approaches and define efficient models with dynamic stopping criterion to find the lowest loss, which yield robust cluster solutions. We find that lowering the loss lead to better and clustering solutions.