近日，香港中文大学（深圳）理工学院的沈闓明教授团队有关数据聚类的工作被NeurIPS 2024接收。NeurIPS是机器学习领域里最负盛名的顶尖学术会议之一，本届NeurIPS将于今年12月份在加拿大温哥华市举行，论文录用率为25.8%。

论文标题：Multidimensional Fractional Programming for Normalized Cuts

作者：Yannan Chen，Beichen Huang，Licheng Zhao，Kaiming Shen

论文链接：https://kaimingshen.github.io/doc/NeurIPS24_FP.pdf

研究介绍

Normalized Cut (NCut)是数据聚类（data clustering）的核心问题。数学上来讲，该问题考虑如何将加权图划分成若干子图，从而使得子图之间的归一化总权重最小，如图1所示。NCut问题的难点包括：（1）子图划分涉及整型优化；（2）即使将整型变量松弛为连续变量，NCut仍为非凸问题而难以求解。

图1 两个子图之间的总权重，还将进行归一化

首先，我们注意到NCut问题具有如下分式结构：

因此自然而然地想起使用分式规划（fractional programming）方法来解决该问题。由于经典Dinkelbach算法只能适用于单分式问题，这里我们使用更前沿的“二次变换（quadratic transform）”方法来处理NCut问题中的多个分式。通过改良后的二次变换，我们能将NCut原问题转化为更容易求解的二分图匹配（bipartite matching）问题，从而实现高效的数据聚类优化。此外，我们还从MM理论角度对该算法的收敛性进行了分析。

事实上，分式规划问题广泛存在于机器学习、信号处理、通信网络、光学、管理学、经济学等众多领域，论文所提算法的应用潜力有待进一步发掘。

实验结果

表1 所提算法FPC在各数据集上与现有方法SC，FINC，FCD的比较，最佳性能加粗表示

  

图2 所提算法FPC在图像压缩任务中有更好效果

 

作者简介

陈雁南，香港中文大学（深圳）理工学院的在读博士生，分别于2018年和2021年在厦门大学获得自动化学士学位和模式识别与智能系统硕士学位。主要研究方向为优化，无线通信和机器学习。

 

黄北辰，麦克马斯特大学的本科生，曾在香港中文大学（深圳）沈闓明教授课题组担任研究实习生。主要研究方向为优化和机器学习。他是本篇论文的共同第一作者。

 

赵立成博士现任深圳市大数据研究院研究科学家。于2014年获得东南大学信息工程学士学位，并于2018年获得香港科技大学电子与计算机工程系博士学位。曾于京东担任推荐系统的算法工程师。研究兴趣包括优化理论和高效算法，并将其应用于信号处理、机器学习以及推荐系统中的深度学习领域。

 

沈闓明博士现任香港中文大学（深圳）理工学院助理教授，校长青年学者。他2011年本科毕业于上海交通大学信息安全专业，并同时取得数学专业学士学位，然后分别于2013年和2020年获得加拿大多伦多大学电子与计算机工程专业的硕士和博士学位。研究方向包括数学优化、无线通信、信息论、数据科学。曾获得2018年国家优秀自费留学生奖学金，2021年IEEE信号处理学会最佳青年论文奖，2024年国际基础科学大会前沿科学奖。沈闓明博士是IEEE高级会员，担任IEEE Transactions on Wireless Communications的编辑。他是本篇论文的通讯作者。

 

供稿 | 沈闓明教授团队