加权拉普拉斯方法及其理论应用

Weighted laplacian method and its theoretical applications

受到图拉普拉斯理论的部分启发,本文提出了一种加权拉普拉斯方法来更加方便地研究现阶段比较流行的图问题,例如,多层图分割,以及平衡最小割问题.由于加权拉普拉斯策略继承了谱方法的众多优点,因此相比于其他现有的启发式算法,用加权拉普拉斯设计图算法在算法性能上具有更强的理论保证.为了说明其在理论与实际中的强有力的应用价值,我们将分别给出加权拉普拉斯方法在多层图分割和平衡最小割问题上的应用.借助变分法和偏微分方程(PDE)理论,我们在加权分割问题(weighted cut problem),平衡最小割问题(balanced minimum cut problem),以及初始聚类问题(initial clustering problem)之间建立了等价性.其中,初始聚类问题会在基于多层结构的图分割算法的中间阶段出现.这些等价性的建立为基于加权拉普拉斯方法的图算法提供了很强的理论支撑.另外,从加权拉普拉斯方法在平衡最小割问题的应用的角度看,加权拉普拉斯方法使得偏微分方程数值解这一成熟的理论得以应用到图问题的算法设计当中,这也进一步证实了我们提出的加权拉普拉斯方法的有效性.

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.