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

作者：许仕杰; 方佳艳; 李向阳^*

来源：微电子学与计算机, 2020, 37(07): 12-20.

DOI：10.19304/j.cnki.issn1000-7180.2020.07.003

• 谱聚类
• 图分割
• 图拉普拉斯
• 偏微分方程
• 最小割问题

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

• 单位
  中国科学技术大学