In this paper

we develop a novel weighted Laplacian method

which is partially inspired by the theory of graph Laplacian

to study recent popular graph problems

such as multilevel graph partitioning and balanced minimum cut problem

in a more convenient manner. Since the weighted Laplacian strategy inherits the virtues of spectral methods

graph algorithms designed using weighted Laplacian will necessarily possess more robust theoretical guarantees for algorithmic performances

comparing with those existing algorithms that are heuristically proposed. In order to illustrate its powerful utility both in theory and in practice

we also present two effective applications of our weighted Laplacian method to multilevel graph partitioning and balanced minimum cut problem

respectively. By means of variational methods and theory of partial differential equations (PDEs)

we have established the equivalence relations among the weighted cut problem

balanced minimum cut problem and the initial clustering problem that arises in the middle stage of graph partitioning algorithms under a multilevel structure. These equivalence relations can indeed provide solid theoretical support for algorithms based on our proposed weighted Laplacian strategy. Moreover

from the perspective of the application to the balanced minimum cut problem

weighted Laplacian can make it possible for research of numerical solutions of PDEs to be a powerful tool for the algorithmic study of graph problems.