Equivalent spectral theory for fundamental graph cut problems
科研大讨论系列报告
报告题目(Title)：Equivalent spectral theory for fundamental graph cut problems
报告人(Speaker)：邵嗣烘（北京大学）
地点(Place)：教四201
时间(Time)：2024年12月27日（周五）16:00-17:00
邀请人(Inviter)：陈华杰
报告摘要
We introduce and develop equivalent spectral theory for several fundamental graph cut problems including maxcut, the Cheeger cut, anti-Cheeger cut, dual Cheeger problem and their useful variants. Using the resulting novel equivalent continuous formulations, we propose a simple inverse power (SIP) method for maxcut, the Cheeger cut and the anti-Cheeger cut, and its inner subproblem allows an explicit analytic solution, which constitutes the main reason why we call it ‘simple’. By fully exploiting the closed-form of the inner subproblem solution, we design a boundary-detected subgradient selection with which SIP is proved to be locally converged. Numerical experiments on G-set demonstrate that SIP outperforms Gurobi in terms of both computational cost and solution quality.
