Normalized Cuts and Data Clustering via Matrix Fractional Programming

Yannan Chen; Beichen Huang; Licheng Zhao; Chris Ding; Kaiming Shen

cs.LGOct 27, 2026

Normalized Cuts and Data Clustering via Matrix Fractional Programming

Authors: Yannan Chen, Beichen Huang, Licheng Zhao, Chris Ding, Kaiming Shen

Organizations: Key Laboratory of Radio Frequency Heterogeneous Integration, Shenzhen University, Shenzhen 518060, China · School of Science and Engineering, The Chinese University of Hong Kong (Shenzhen), Shenzhen 518172, China · Beichen Huang is an undergraduate student at McMaster University, Canada · Shenzhen Research Institute of Big Data, Shenzhen 518172, China ·

Abstract

The normalized cut (NCut) problem is a fundamental one in the area of data clustering. Despite its fractional structure, the NCut problem is seldom considered from a fractional programming (FP) perspective in the existing literature. The main reason is that the conventional FP method is inadequate for this problem case: the classical Dinkelbach's transform can only handle a single ratio and hence is limited to the two-class clustering, whereas the multi-class clustering involves multiple ratio terms. This work proposes a novel so-called multidimensional quadratic transform that is capable of dealing with the multi-ratio case; it recasts the NCut problem into a bipartite matching problem---which can be immediately solved by linear search. Furthermore, we explore the connection between the proposed FP method and the minorization-maximization (MM) theory, and in turn characterize the convergence behavior of our algorithm. Finally, we conduct experiments to numerically demonstrate the advantages of the proposed FP-based algorithm in a variety of data clustering and image segmentation tasks.

Figures & tables

Fig. 1: Graph cut between two disjoint subsets $\mathcal{A}$ and $\mathcal{B}$ .

Fig. 2: The value of the original objective $f(x)$ is nondecreasing after each iteration of the MM method, where $g(x|\hat{x}^{(t)})$ is the surrogate function constructed in the $t$ th iteration.

Dataset	$N$	$K$	# of features	Source
Shuttle	15	2	6	UCI [ 50 ]
Balloons	16	2	4	UCI [ 50 ]
Breast	106	6	9	UCI [ 50 ]
Thyroid	215	3	5	UCI [ 50 ]
Office	2533	10	800	Github [ 51 ]
Splice	3175	3	240	UCI [ 50 ]

TABLE I: Datasets used for dividing

N

data points into

K

clusters.

Fig. 3: Image segmentation by the different algorithms.

Fig. 6: Sensitivity of FPC to random initialization on ”Shuttle” dataset.

	Fully connected graph						Anchor graph
Method	Breast	Thyroid	Office	Splice	Rice	Landsat	Epileptic	STL10	Sensorless	CIFAR10	MNIST	RT-IoT2022
SC	2.431325	0.983145	4.483929	0.997651	0.499193	2.490237	0.557434	1.844406	1.214324	2.073733	1.033129	0.254008
ISR	2.431325	0.983144	4.484089	0.997651	0.499193	2.490253	0.557458	1.844957	1.215714	2.078630	1.033709	0.261397
DSSRC	2.431325	0.983144	4.484115	0.997652	0.499193	2.490246	0.677723	1.992010	1.215714	2.149170	1.057807	–
FINC	2.432491	0.988532	4.483329	0.997651	0.499193	2.490237	0.574284	1.851028	1.162947	2.062307	1.008371	0.242925
FCD	2.431325	0.983145	4.483670	0.997651	0.499193	2.490138	0.555138	1.841004	1.151903	2.047859	0.995819	0.241988

TABLE II: NCut objective values achieved by the different algorithms on datasets constructed using fully connected and anchor graphs. A lower value indicates better performance.

Panel of Figure 8 — Fig. 7: Convergence in terms of the NCut objective value for the different datasets with the similarity matrix generated as fully connected graph.

Panel of Figure 9 — Fig. 8: Convergence in terms of the NCut objective value for the different datasets with the similarity matrix generated as anchor graph.

		Fully connected graph						Anchor graph
Metric	Method	Breast	Thyroid	Office	Splice	Rice	Landsat	Epileptic	STL10	Sensorless	CIFAR10	MNIST	RT-IoT2022
ACC	SC	0.509434	0.888372	0.350178	0.664882	0.896325	0.668500	0.378261	0.205769	0.259054	0.196583	0.464271	0.229221
	ISR	0.509434	0.883721	0.346625	0.664567	0.896325	0.668500	0.378087	0.205615	0.259071	0.200283	0.478629	0.228336
	DSSRC	0.509434	0.883721	0.347809	0.660787	0.896588	0.677000	0.381478	0.217769	0.259071	0.206983	0.462614	–
	FINC	0.509434	0.604651	0.350572	0.664882	0.896325	0.668500	0.382870	0.206000	0.265771	0.209117	0.479329	0.235248
	FCD	0.509434	0.888372	0.348993	0.664882	0.896325	0.654500	0.377826	0.206615	0.266198	0.198717	0.480314	0.235361

TABLE III: Clustering performance achieved by the different algorithms on datasets constructed using fully connected and anchor graphs. A higher value indicates better performance.

Panel of Figure 11 — Fig. 9: Saturation behavior of FPC on Epileptic, STL10, and CIFAR10. FPC is initialized with the ground-truth labels, for which the clustering error is 0%. The objective value decreases while the error increases.

Fig. 10: Average running time of the different algorithms on datasets constructed using fully connected and anchor graphs.

Clustering

Clustering groups data points by shared structure, developing methods to discover, validate, and interpret groups across diverse data and constraints.

See all 347 papers

Semidefinite programming relaxations and debiasing for MAXCUT-based clustering
Jan 16, 2024Shuheng ZhouSemidefinite Programming Unsupervised Clustering
University of California, Riverside, CA 92521
A Fast and Effective Method for Euclidean Anticlustering: The Assignment-Based-Anticlustering Algorithm
Jan 9, 2026Philipp Baumann, Olivier Goldschmidt, Dorit S. Hochbaum +1Clustering Combinatorial Optimization
Department of Business Administration, University of Bern, Engehaldenstr. 4, 3012 Bern, Switzerland · Riverside County Office of Education, Riverside, CA 92501, USA · Industrial Engineering and Operations Research Department, University of California, Berkeley, CA 94720, USA
Graph Partitioning with Demands: Generalized Conductance and its Applications
Jul 14, 2026Michał Szyfelbein, Dariusz DereniowskiHierarchical Clustering Approximation Algorithms
Gdańsk University of Technology

Jan 16, 2024J/K move · Enter open · S save

Semidefinite programming relaxations and debiasing for MAXCUT-based clustering

Shuheng Zhou

University of California, Riverside, CA 92521

Semidefinite Programming Unsupervised Clustering Graph Clustering Spectral Methods Max-Cut

Open paper AskPDF arXiv

In this paper, we consider the problem of partitioning a small data sample of size

n

drawn from a mixture of

2

sub-gaussian distributions in

\mathbb{R}^p

. We consider semidefinite programming relaxations of an integer quadratic program that is formulated essentially as finding the maximum cut on a graph, where edge weights in the cut represent dissimilarity scores between two nodes based on their

p

features. We define the signal-to-noise ratio (SNR) as

s^2 := \min\{n p γ^2, Δ^2\}

, where

Δ^2 := p γ

denotes the

\ell_2^2

distance between the two cluster centers. Our contributions are twofold. First, we provide a unified framework for analyzing three computationally efficient algorithms: SDP1, BalancedSDP, and Spectral clustering, yielding universal polynomial-rate misclassification guarantees for all three algorithms. Moreover, our theory allows for partial recovery (success rate

< 100\%

) as long as

s^2

is lower bounded by a constant. Second, we prove that the misclassification errors for SDP1 and BalancedSDP decay exponentially with respect to the SNR

s^2

and the BalancedSDP requires no explicit debiasing when the two clusters have equal sizes. To our knowledge, this is the first time such results are obtained for semidefinite relaxations of MAX CUT in population clustering. We provide simulation evidence illuminating the theoretical predictions.

Abstract

Clustering

Explore similar work

Semidefinite programming relaxations and debiasing for MAXCUT-based clustering

A Fast and Effective Method for Euclidean Anticlustering: The Assignment-Based-Anticlustering Algorithm

Graph Partitioning with Demands: Generalized Conductance and its Applications