Abstract The Maximum Vertex Weight Clique (MVWC) problem is NP-hard and also important in realworld applications. In this paper we propose to use the restart and the random walk strategies to improve local search for MVWC. If a solution is revisited in some particular situation, the search will restart. In addition, when the local search has no other options except dropping vertices, it will use random walk. Experimental results show that our solver outperforms state-of-the-art solvers in DIMACS and finds a new best-known solution. Moreover it is the unique solver which is comparable with state-of-the-art methods on both BHOSLIB and large crafted graphs. Also it achieves 100% success rates over all the winner determination graphs within 500s. Furthermore we evaluated our solver in clustering aggregation. Experimental results on a number of real data sets demonstrate that our solver outperforms the state-of-the-art for solving the derived MVWC problem and helps improve the final clustering results