Geometric Methods for Graph Partitioning

图划分的几何方法

• 批准号: 1461138
• 负责人: Braxton Osting
• 金额: $ 7.9万
• 依托单位: University of Utah
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-07-01 至 2016-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1461138&HistoricalAwards=false
• 关键词: Geometric; Methods; Graph; Partitioning

The proposed activity is to develop and analyze new computational methods for a graph partitioning problem based on the Beltrami energy. This problem has diverse applications in machine learning and image analysis (medical, satellite, and material). For example, a clear need for such methods in imaging has been identified by collaborators at the California NanoSystems Institute, where the proposed work will directly impact fundamental research in nano science and foster the understanding of amyloid beta sheets. Such amyloids are associated with the pathology of more than 20 serious human diseases including Alzheimer's and other neurodegenerative diseases. Thanks to the multidisciplinary nature of the activity, awareness and literacy outside one's field will also be mutually fostered for all involved parties.The PIs, together with their students and collaborators, will seek new methods that combine variational arguments with ideas from geometry and partial differential equations in order to extend and overcome the limitations of existing methods. The research has three goals. The first goal concerns fundamental theoretical questions raised by the proposed model: analyze the existence, uniqueness, and properties of the minimizers of the variational problems; establish a generalized isoperimetric inequality related to the Beltrami functional in the continuum; and explore relations to existing theorems and conjectures about optimal partitions. A graph analogue of the Beltrami energy is formulated and is the foundation for a graph partitioning objective. The PIs have identified a relaxation of this objective and propose an in-depth study of a provably convergent rearrangement method for its solution. The second goal addresses the important computational and numerical aspects of the proposed graph partitioning model. An efficient optimization strategy is key for the framework to be usable in practical applications. Here, promising primal-dual methods from convex optimization will be utilized, as well as other competitive state-of-the-art methods. To develop the most efficient solution method, it will be crucial to explore the similarities to other models, including those for non-negative matrix factorization and those related to motion by mean curvature. The third goal is to address concrete, real-world problems and to engage the developed algorithms in practical applications of societal importance.

提出的活动是开发和分析基于Beltrami能量的图划分问题的新的计算方法。这个问题在机器学习和图像分析(医学、卫星和材料)中有着广泛的应用。例如，加州纳米系统研究所的合作者已经确定了成像中对这种方法的明显需求，在那里拟议的工作将直接影响纳米科学的基础研究，并促进对淀粉样β片剂的理解。这种淀粉样蛋白与包括阿尔茨海默氏症和其他神经退行性疾病在内的20多种严重人类疾病的病理有关。由于活动的跨学科性质，所有参与者都将相互培养自己领域外的意识和素养。PI将与他们的学生和合作者一起，寻求将变分论点与几何和偏微分方程式的思想相结合的新方法，以扩展和克服现有方法的局限性。这项研究有三个目标。第一个目标涉及由所提出的模型提出的基本理论问题：分析变分问题极小值的存在、唯一性和性质；建立与连续统中的Beltrami泛函有关的广义等周不等式；以及探索与现有关于最优划分的定理和猜想的关系。建立了Beltrami能量的图模拟，它是图划分目标的基础。投资促进机构已经确定了这一目标的放松，并提议深入研究可证明收敛的重排方法来解决这一问题。第二个目标解决了所提出的图划分模型的重要计算和数值方面的问题。一个有效的优化策略是该框架能否在实际应用中使用的关键。在这里，将使用来自凸优化的有前途的原始-对偶方法，以及其他竞争最先进的方法。为了开发最有效的求解方法，关键是要探索与其他模型的相似性，包括非负矩阵分解模型和与平均曲率运动相关的模型。第三个目标是解决具体的、现实世界的问题，并将开发的算法应用于具有社会重要性的实际应用。