Multidimensional Fractional Programming for Normalized Cuts
Authors: Yannan Chen
Beichen Huang
Licheng Zhao
Kaiming Shen
Venue: NeurIPS 2024 poster (2024)
Keywords: Data clustering
normalized cut
discrete optimization
fractional programming
Primary area: optimization

Abstract: The Normalized cut (NCut) problem is a fundamental and yet notoriously difficult one in the unsupervised clustering field. Because the NCut problem is fractionally structured, the fractional programming (FP) based approach has worked its way into a new frontier. However, the conventional FP techniques are insufficient: the classic Dinkelbach's transform can only deal with a single ratio and hence is limited to the two-class clustering, while the state-of-the-art quadratic transform accounts for multiple ratios but fails to convert the NCut problem to a tractable form. This work advocates a novel extension of the quadratic transform to the multidimensional ratio case, thereby recasting the fractional 0-1 NCut problem into a bipartite matching problem---which can be readily solved in an iterative manner. Furthermore, we explore the connection between the proposed multidimensional FP method and the minorization-maximization theory to verify the convergence.

Multidimensional Fractional Programming for Normalized Cuts
Yannan Chen
Beichen Huang2* Licheng Zhao
Kaiming Shen
School of Science and Engineering, The Chinese University of Hong Kong (Shenzhen), China
McMaster University, Canada
Shenzhen Research Institute of Big Data, China
E-mail: yannanchen @ www.kkcukk.uu..cr huangb21 1 @ memaster.ca, zhaolicheng sribd.en, shenkaiming @ www...eu.ccr
Abstract
The Normalized (NCut) problem fundamental and yet notoriously difficult one in the unsupervised clustering field. Because the NCut problem is fractionally structured, the fractional programming (FP) based approach has worked its way into a new frontier. However, the conventional FP techniques are insufficient: the classic Dinkelbach's 's transform can only deal with single ratio and hence is limited to the two-class clustering, while the state-of-the-ar quadratic transform accounts for multiple ratios but fails to convert the NCut problem to a tractable form. This work advocates a novel extension of the quadratic transform to the multidimensional ratio case, thereby recasting the fractional 0-1 NCut problem into a bipartite matching problem-whiee can be readily solved in an iterative manner. Furthermore, we explore the connection between the proposed multidimensional FP method and the
theory to verify the convergence.
Introduction
Fractional programming (FP) is powerful optimization tool for solving diverse problems involving ratio terms, e.g., the areas of physics, economics, management science, signal processing, computer science, and information theory 222 This paper explores novel application of FP to the normal- ized cut (NCut)-wil which is fundamental and yet notoriously difficult problem for unsupervised data clustering (4) A new FP technique called the multidimensional quadratic transform (5) forms the building block this work. Differing from the classic Dinkelbach's transform [6] that is typically limited to the single-ratio problem with pair of scalar-valued numerator and denominator, the multidimensional quadratic transform is capable of handling multiple ratios simultaneously in the same problem, and further accounts for the denominators take a matrix/vector form. It turns out that the NCut problem solving can be made much easier from multidimensional FP point of view. Two main results have been achieved under the umbrella of FP. First, we show that one most recent advance 7 in the NCut field can be inter- preted special scalar-ratio version of the multidimensional quadratic transform, which already outperforms the classic methods significantly. Second, by fully exploiting the multidimensional quadratic transform
aetiiidiiinnnnna-rtttttt case wherein the numerators and
(5] we develop a superior FP-based algorithm tailored to the NCut problem.
Clustering has been considered extensively in the literature from a variety of perspectives, e.g., K- means 88, hierarchical clustering [9], spectral clustering (SC) [10), graph cuts [1T]. and high-density clustering [2]. The graph cuts approach is of particular interest for its flexibility to cope with wide range of cluster types, e.g., not requiring the desired clusters be center-based many other
"Equal contribution. Codes available at t Corresponding author.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

geometry-based clustering algorithms do [13]. With each data point mapped to vertex in weighted undirected graph, there are different ways measure the relative strength of similarities between subgraphs (each corresponding to cluster), which in turn lead to different classes of graph cuts algorithms, e.g., min cut [4], ratio cut [15], and min-max cut [16] aside from the NCut. Like many modern works in the realm of graph cuts, our study focuses on the NCut metric because it yields stable performance and prevents cluster imbalance [4].
Nevertheless, the optimization criterion of the NCut is numerically difficult to tackle. To be more specific, the NCut entails solving an NP-complete problem 4 The SC method constitutes a popular heuristic approach to the NCut problem A I0], but it cannot provide any performance guarantee. Other works aim the analytical aspect and rely heavily on the optimization theory. For example, the Fast Coordinate Descent (FCD) algorithm proposed in [17 evolves from the standard optimization tool of block coordinate descent. By contrast, the Direct Normalized Cut (DNC) algorithm in [T8] is somewhat less straightforward. The main idea of [8] is to approximate the NCut problem by using a lower bound on the original optimization objective, but it incurs a costly inner iteration in computing such a lower bound. To remedy this, the Fast Iterative Normalized Cut (FINC) in 7 approximates the NCut problem based on closed-form lower bound. However, the resulting new problem is still difficult to solve directly, which can only be addressed in heuristic fashion as shown in 77. The present work is most closely related to DNC [18) and FINC 7 in the sense that it seeks to approximate the NCut problem via bounding well. As compared to the above existing bounds, the new bound proposed in this work can be constructed immediately, and can further enable efficient solving of the problem for the clustering purpose.
2 NCut problem statement
Suppose there are N data points in total. Use i,j E (1,2,...., N) to index these data points. For pair of data points and j, the similarity between them is quantified 0 S Waj S 1. By symmetry, we have Wly Wyj. In the graph theory context, with each data point visualized as a vertex, the edge between vertex and vertex j is assigned the weight Wij (or wj;). Denote by V the set of vertices, and & the set of edges. The resulting graph G = (V, E) can be recognized as a weighted undirected graph. For each vertex i, its degree d, is the sum weights across all the incident edges:
d
Way.
Dividing the N data points into > 1 clusters is equivalent to partitioning V into K disjoint subsets
(V1, V2,... VK}, where U Vi = V and V4 n Vv = for any * k. For any two disjoint subsets A, C V, we define
+ (AI = ΣΣ Wiji
(2)
IEAJER
which is illustrated in Figure !
Wij
B
(A, B)
Figure 1: Graph cut between two disjoint subsets AA and B.
Moreover, for any subset A C V. we define its volume be
vol(A) = Σ dr.
(3)
ieA

---

In principle, data clustering aims to group together those data points that are sufficiently similar to each other. Equivalently, we wish to minimize the similarity between any two clusters. Toward this end, one traditional strategy is to minimize
K Σ 2
1
cut(Vi, V2.... ................................ VK)
②Vv, Ve),
(4)
where VA is the complement of VA, i.e., D4. VVV However, minimizing cut V2. Vx)
alone can be problematic- it tends to put most data points in one particular cluster while leaving other clusters almost empty, namely the cluster imbalance [19]. To resolve this issue, a natural idea is to regularize the cluster volume by considering the normalized cut:
OVv, Va)
ncuu(V1, V22 ................................ Vx)
(5)
vol(V))
Intuitively speaking, the value of Φ(Vx, Va) would soar if very few data points have been assigned to cluster k, thereby discouraging the cluster imbalance.
We are now ready to formalize the NCut problem. The indicator variable Iye E {0.1) equals data point i is assigned to cluster k, and equals 0 otherwise. Moreover, write W = [wyy] E R NNN,
D = diag [d1, d2.... dN] E gNNN and X [ E {0, 10,1] Denote by æ E (0, 1] the kth column of X. be shown that
K
x Lx
neut(Vi, V2...., Vx) = 2
(6)
D
where the graph Laplacian matrix L is given by L= D W. We seek the optimal clustering decision X that minimizes ncut(V/, V2,-.., .,, VK). Further, because neut V2,..., Vx) / K
2x Way the NCut minimization problem boils down to
Ek=1 m Dms
K
1 W
x
maximize X
(7a)
D
k=1
subject
i= i= Σ Tikk 1,
(7b)
Tia {0, 1), i= i= ,, k l,.
(7c)
where the two constraints 7b) and (7)) state that each data point must be assigned to one unique cluster. The difficulties the above problem can be recognized with two respects. First, the clustering variables {zux) } are discrete. Second, even when every Fiz is relaxed to be continuous variable on the interval [0, 1], the problem is still nonconvex.
Fractional programming
The NCut problem in (7) is fractionally structured. To be more specific, 7 takes sum-of-ratios form. This quick observation strongly suggests that the NCut is amenable to FP, but it turns out that very few previous works in the literature have adopted the FP approach. In the of this section, we first review the conventional FP methods to show why they are rarely considered for the NCut, and then introduce a recently proposed FP technique called the multidimensional quadratic wansform-whit forms the building block of our proposed clustering algorithm as introduced in Section
3.1 Conventional FP methods
The early studies in the FP field are restricted to the single-ratio problem:
A(r)
maximize ze.
(8)
B(x)
3

---

where A(x) 2 0 is a nonnegative function. B(x) > O is a strictly positive function, and A' is nonempty constraint set on æ. In the literature, many works further assume that A(z) concave in (x) is convex in and X' is a convex set, namely the concave-convex condition. Notice that problem ( still nonconvex in general under the concave-convex condition, so the direct solving of 8 is difficult. The classic Dinkelbach's transform in essence aims to decouple the ratio:
Proposition 1 (Dinkelbach's 's transform
6
The single-ratio problem g is equivalent to
maximize aEX'
A(x) - -yB(x),
(9)
where the auxiliary variable y iteratively updated as y A(x)/B(a).
Observe that the new problem (9) is convex in for fixed y under the concave-convex condition, and
hence can be efficiently solved by the standard optimization method. Importantly, solving for æ in (9)
with y iteratively updated guarantees convergence to the global optimum the original problem (8).
However. it is difficult to extend Dinkelbach's 's transform to the multi-ratio problems (except for the
max-min-ration case 20 As such, the use of Dinkelbach's transform the NCut area is limited to
the two-class clustering that only needs to optimize a single ratio (2
We consider K > pairs of the numerator function A& (z)) 2 O and denominator function By (z) > 0 along with a nonempty constraint set X. sum-of-ratios problem is then formulated as
Aa(x)
maximzie xEX
(10)
(x)
It is tempting to decouple each ratio Ax(x)/ (x) by using Dinkelbach's transform separately, but the resulting new problem is not equivalent to problem (TOp. Consequently, the classic Dinkelbach's 's transform does not work for the NCut with general K clusters. A valid method to decouple multiple ratios is presented in the following proposition.
Proposition 2 (Quadratic transform
S
The sun-of-ratios problem
T0 is equivalent to
K
maximzie zEX, yu ER
Σ 1=1
2yk Au(z)= - Bx(),
(11)
in the sense that x² is a solution to (T0p if and only (x" y²) ) is solution to where an auxiliary variable yı is introduced for each ratio term An(x) Ba(x).
We propose optimizing and }yk} iteratively. When is held fixed, each y be optimally determined as
(xx(z)
(12)
Bx(x)
Furthermore, under generalized concave-convex condition 5 wherein each Ax(x:) a concave function, each B, (x) is a convex function, and X' is convex set, it can be shown that the new problem (TT is convex in æ when } are held fixed. Thus, the alternating optimization between a and {yx) can be performed efficiently.
Now let us return the NCut problem in and apply the above FP technique it. Treating 2 W Hy and 2 Dæy respectively as numerator and denominator, we can recast problem 7 into
K
maximize X, BRE
2yk x. Wat V
Dæ
(13a)
subject
(13b)
As before, we optimize X and { iteratively. For fixed X, the optimal solution of yı is
/ W mk
yi
(14)
Dy D

---

It remains to optimize X in 13 for fixed {ux ). Observe that x. Ww is not a concave function of since W is often a positive cemi-defniie matrix [22], and also that the constraint set of X is not convex because of (7c), so the aforementioned generalized concave-convex condition does not hold here. As result, solving for X in (3) with {ys} held fixed no longer convex problem. The above alternating optimization between X and [Uk J can be recognized as the so-called Fast Iterative Normalized Cut (FINC) algorithm of the recent work 77]. Although it manages to decouple multiple ratios in the NCut problem, we are faced with with in a heuristic fashion in [7]. This fact perhaps explains why the FP approach has not yet been considered extensively in the literature despite the fractional structure of the NCut problem.
challenging problem. The new problem is dealt
3.2 Multidimensional FP method
We now proceed to a much more sophisticated FP toolkit that accounts for multidimensional ratios. To start, consider the following matrix extension of the traditional scalar-valued FP problem: each (x 2 0 is generalized as positive semi-definite (x E S $m** while each (x(x) > 0 is generalized as positive definite form as
(xxx)= STx" Accordingly, the ratio term is extended to the matrix
R_
-x(x)-AAn As(()) S4
smxm.
Ba (z)
We then arrive at a matrix extension of the sum-of-ratios problem 10
K
maximzie zEX
( (z)
Σ
ur
(15)
One main result of this paper is that the quadratic transform in Proposition carries over to the matrix ratio case, stated in the following proposition.
Proposition 3 (Multidimensional quadratic transform) Suppose that each As(x) E ST Smxm can be factorizzed as
Ax(x) = [ (Ze(1) where Zx(x) E B fx
(16)
for some positive integer E. The matrix FP problem (1) is then equivalent to
maximize x YLER mm
ir (2(2 (x)) Y,
(17)
where an auxiliary variable Y, E Rem is introduced for each matrix ratio (z)
Proof It can be shown that each YR in 17 is always optimally determined as
Y (z
(18)
Substituting the above Yg in (1 recovers the original problem
Proposition 4 The alternating optimization between and (Ys) in (7) amounts to an MM proce- dure, so it guarantees nondecreasing convergence of the original optimization objective in 11 as specified in Appendix A.I.
The key step is to optimize z for fixed {Ya). Recall that the primal variable r still difficult to optimize for the NCut problem after applying the quadratic transform in Proposition 2 In contrast, it turns out that the multidimensional quadratic transform in Proposition 3 can lead us to an efficient iterative update of for the NCut problem scenario, elaborated in the next section.
4 Proposed Multtidimensiona--Fl-baaa
NCut
The goal of this section is to address problem D by means of the multidimensional FP. We begin with a special case which the similarity matrix W assumed to be positive semi-definite; the indefinite W case will be discussed later on.
5

---

It is crucial to notice that the numerator part z Way can be factorized as
T W z = 2 2 where Z/ W W ag..
(19)
We remark that W i.e., the symmetric square root of W 23 is guaranteed to exist because have assumed that W E S for the current discussion. We then treat æy. Wag, ZR, and æg Dæ, as (x)) Z (x)), and B₃ (z). respectively, in Proposition 3 with m 1 and & = N, thus using the multidimensional quadratic transform to reformulate the NCut problem as
K
maximize x. K.ER
tr WW (T)) - yk (k Dax)ylk
(20a)
subject to
7b
7
(20b)
We then optimize X and } iteratively. When X is held fixed, each yı is optimally determined as
W wh
yi
(21)
D
Now the core question is whether X could be efficiently solved when {yr} are held fixed. The optimization objective of X in (20a) for fixed {yk} is written as
h ((X)=
Σ tr (2yk ( xx)) - (x Das)vit
(22)
It is critical to observe that under the discrete constraint witk {0, 13 must have Dg Dæs 1 Dæ 5 æk
(23)
where = (I,,,....,11 1)T is the all-ones vector and
8 = D = [di, d2, dNlT.
(24)
We can then rewrite ((X) as
K
K
(x)== =
2yk W 2 - yi yno xx
Σ
M xx
(25)
where
14 2 yv: 5yy% yk-
(26)
In (5 the first equality follows since x Dæş scalar. Denote by Pik. the ith component of pa-
In light of (25), we can readily maximize h(X) under the constraints (7b) and (cp:: it is optimal to
set Fit with the largest μı on each row of X to one, while setting the rest 2i of the row to zero, i...
if arg max Mike
(27)
otherwise.
If there exists tie (i.e., when than cluster index K' maximizes Pakk for same i) then break it randomly. Further, with y in (2I) plugged in (26), we obtain an efficient computation μ4 as
2W ER
8x W
2W
8x Was (8 x2
14
(28)
Ig Dx
(x. Dxx
8 8T or
The merits of rewriting μ4 as 28 are two-fold. First, it sidesteps the update of the auxiliary variables {yx}. Second, it no longer entails computing the square root of W. The resulting algorithm referred to as fractional programming programming-bbaed -based clustering (FPC) is summarized in the following.
Clearly, the FPC algorithm is guaranteed to converge in terms of the new objective value l(X), since the iterative update of X and {mu} in FPC amounts to block coordinate ascent for problem (20 so that h( X) monotonically increasing after each iteration. We can actually claim a stronger result for FPC according to Proposition 4 stated in the subsequent proposition.

---

Algorithm 1 Proposed fractional programming-based clustering (FPC)
1: Initialize X feasible value satisfying Ek=1 Eit 1 and 2 {0, } for each (i,
2: repeat
3: Update each μ4 according to 28 for l 1, ................................ K.
4: Update each Tik according to 27 for i = 1, N and = 1,2,.... K.
5: until the value of (xX) - Σ k= 2y converges
Not only the new objective value h(X) in (22) but also the original objective value of the NCul problem, [(X) = Σ
Proposition 5
mi wn is nondecreasing after each iteration of FPC.
n. Dec
We thus far assume that the similarity matrix W is positive semi-definite; this assumption can be justified by arguing that positive definite kernel (24] (e.g.. the Gaussian kernel) is often used generate W. But what if some indefinite kernel has been adopted and hence W is not necessarily positive semi-definite anymore? The following proposition provides solution.
Proposition 6 Suppose that the similarity matrix W is indefintte. We can choose sufficiently large o > O so that the new matrix
W
W + o.D
(29)
is positive semi-definite. Notice that such must exist since
Amin W)
(30)
min, dç
a feasible choice. Then we can equivalently consider problem 7 with W used place of W. which can be readily addressed by the FPC algorithm.
Proof 2 See Appendix A.2.
Finally, we examine the computational complexity of the FPC algorithm. The update of as in (27) incurs computational complexity of O(K2 while the update of (μu} } in (28) incurs computational complexity of O K (²), If W is indefinite, then we would further find the smallest eigenvalue of W required in (30). Rather than computing all the eigenvalues and then picking the smallest, which incurs O ) we propose a more efficient way of computing Amin:
1. Find the largest eigenvalue of [W| W. denoted as \1, by the power method 25 where || ||r is the Frobenius norm.
2. Compute the smallest eigenvalue as Amin W)= = || W |F
A
Thus, the overall complexity of finding a as in 30 is O(N2). To sum up. the per-iteration complexity of FPC equals O(KN²). while the traditional SC algorithm incurs complexity of O(N*).
Experiments
validate the performance of the proposed FPC algorithm on 8 common datasets as summarized in Table The benchmarks are the SC 4 FINC 7 and FCD 177. We use the Gaussian kernel to generate the similarity matrix, i.e., Waj = exp 02 ny 1)))), where v; and vj are the feature vectors of data points i and j. All the tests were carried out desktop equipped with 2.10 GHz CPUx 12. Throughout the tables, we highlight the best performance by using the bold font.
5.1
Optimization objective of NCut
We first evaluate the performance of the different algorithms in minimizing neut(V) (11 V2,..., defined in (6). We run each algorithm 10 times with the random starting point generated for each trial, and then pick the best one. Table 2 summarizes the results. Observe that the proposed FPC method achieves the lowest NCut objective across the datasets. For instance, the NCut objective of FPC is 0.19% lower than that of FCD for the dataset Office+Caltechll with K 10 clusters, and
"ig...,Vy, Vk) as
7

---

Table 1: Datasets used for the task of dividing N data points into K clusters.
Dataset
N
K
Number of features
Source
Breast
UCT datasets 26
Thyroid
215
3
5
UCI datascts 26
OfficeCCatech100
2533
10
800
Github transfer-learning
27
Splice
3175
3
240
UCI datasets 26
Rice
3810
UCI datasets
Landsat
6435
7
36
UCI datasets 26
USPS
9298
10
256
LIBSVM 28
Epileptic
11500
5
178
UCI datasets 26
Table 2: NCut objective values achieved by the different algorithms with random initialization.
SC
FINC
FCD
FPC
Breast
2.438568
2,445278
2,446499
2,431813
Thyroid
0.983144
0.983393
0.986163
0.983115
Office+Calteche
4,483921
4.483962
4.491925
4.483501
Splice
0,997651
0.999867
0.998569
0.997636
Rice
0.499193
0.499999
0.499209
0.499193
Landsat
2.994675
2.999986
2.995302
2.994335
USPS 4.476479
4.476404
4.476591
4.475869
Epileptic
1.992376
1.991369
1.992688
1.991311
Table 3: NCut objective values achieved by the different algorithms with the SC initialization.
SC
SC+FINC
SC+FCD
SC+FPC
Breast
2.438695
2.442353
2.43869547.5e.
2.43793142.8e-4
Thyroid
0,98314410.0
0,98932910.00
0,98314410.0
0,9831441000
Office+Caltech
1.4
4.483373.16.0e-6
4.483635
1483288019.0e-
Splice
0.997651
0,997651
0,997651
0.997638
Rice
0.499193-0.00
0,499193=00.0
0,499193+0.0
0.499193-0.00
Landsat
2.994678+22.0--6
2.994678+22.0--6
2.99449947.50m
2.994335-10.0
USPS 4.476546-1.77-
4.475926-+1.ec.
4.475932+1144 1,99135310.0
4,475913
Epileptic
1.99237813.0e-6
1.991756
1.99131310..
Note:
Each entry has the form [objective + variance]. Red color indicates degradation
while blue color indicates improvement.
0.07% lower for the dataset Epileptic with N 11500 data points. All the benchmarks except SC are strictly inferior to FPC; SC is equally good as FPC only the dataset Rice.
Moreover, we consider first using SC obtain raw clustering decision and then using other algorithms to refine it. The test results are summarized in Table Observe that using FPC after SC can achieve the best performance on all datasets. In particular, it strictly improves upon the SC initialization on 6 datasets. It is worth observing that FINC may even yield worse performance after the initialization by SC: this because FINC cannot guarantee that the new problem is optimally solved per iteration as formerly mentioned in Section 3.1 Finally, in Fig. 2 we find the global optimum for two small-size datasets via exhaustive search, and use it as the benchmark to compare with the proposed FPC algorithm; observe that FPC attains convergence to the global optimum after merely 3 iterates.
5.2 Other performance metrics
Aside from the Neut optimization criterion, the following commonly used performance metrics prac- tice are considered for the different clustering algorithms: the accuracy (ACC), the normalized mutual information (NMI) 29], and the adjusted random index (ARI) 33) Unlike neut(V), V2..... ... Vx), the above metrics are proportional to the performance, i.e., the higher metric value, the better cluster- ing. The test results are summarized in Table Although these performance metrics are not directly tied to the NCut objective, the proposed FPC method still achieves the highest scores in many cases.

---

FPC
Global Optiamus
Global Optimum
NC Objectiv
NCut Objective
0.49
0.48
0.488
0.47
0.486
0.46
0.484
0.482
0.45
Iteration Number
Iveration Number
(a) dataset "Balloons"
(b) dataset "Shuttle"
Figure 2: Convergence in terms of the NCut objective value for two UCI datasets.
Table 4: The performance metrics of ACC, NMI, and ARI achieved by the different algorithms.
SC
FINC
FCD
FPC
SC
FINC
FCD
FPC
Dataset
Breast
Thyroid
ACC
0.4906
0.5000
0,3868
0.5283
0.8837
0.9163
0.7860
0,9070
NMI
0.4942
0.4798
0.3525
0.5052
0.4956
0.6061
0.3396
0.5780
ARI
0.2931
0.3104
0,1582
0,3379
0.6082
0.7167
0.4121
0.6869
Dataset
Office+Caltech10
Splice
ACC
0.3533
0.3308
0.1717
0.3640
0.6646
0.3512
0.5096
0.7225
NMI
0.2347
0.2358
0.0704
0.2491
0.2856
0.0015
0.2149
0.3529
ARI
0.1440
0.1314
0.0440
0.1469
0.2686
0.0007
0.1650
0.3514
Dataset
Rice
Landsat
ACC
0.8966
0.5142
0.8853
0.8992
0.6044
0.1584
0.5809
0.6611
NMI
0.5129
0.0006
0,4845
0.5216
0.4905
0.0013
0.4073
0.6111
ARI
0.6288
0.0005
0.5937
0.6371
0.3948
0.0000
0.3423
0,5328
Dataset
USPS
Epileptic
ACC
0.7037
0.6861
0.7060
0.6920
0.3609
0.3386
0.3743
0.3197
NMI
0.6419
0.6406
0.6333
0.6377
0.1627
0.2419
0.1909
0.2370
ARI
0.5724
0,5626
0,5734
0,5679
0.1119
0.1385
0.1326
0.1332
We further try out the different clustering algorithms in the image segmentation task. Using the image dataset from [3I], we perform the color histogram and the local binary pattern analysis for about 500 superpixels to extract the features as in [32]. As shown in Figure 3 the clustering by FPC gives clearer boundaries of the objects than other methods.
Moreover, Figure 4 shows the average time consumption of the different algorithms. It can be seen that FPC runs 73% faster than FINC, and runs equally fast as SC. We remark that FCD requires the least running time because it tends to get trapped in a suboptimal point prematurely at the early stage.
6 Conclusion and limitation
This work proposes novel application of multidimensional FP to the NCut clustering, differing from the previous works that rely on the traditional scalar-ratio FP such Dinkelbach's transform and quadratic transform. The main merit of using multidimensional FP is that the new 0-1 problem can be efficiently solved via linear search. Further, the resulting FPC algorithm can be interpreted as an MM procedure with provable monotonic convergence in terms of the NCut optimization criterion. Thus far, we only show that its per-iteration complexity lower than the overall complexity of the traditional SC algorithm.

---

Original
SC
FINC FCD
FPC
ID 1001994
ID 10W0929
ID 3000-69
ID 00002755
Figure 3: Image segmentation by the different algorithms.
10a
Time consumption (second)
SC
FCD
10a
Thyroid
Office+Caleec10
Splice
USPS
Epileptic
Dataset
Figure 4: Running time of the different algorithms when applied to the different datasets.
Acknowledgments
The work of Yannan Chen, Beichen Huang, and Kaiming Shen was supported in part by Guangdong Major Project of Basic and Applied Basic Research (No. 2023B0303000001), in part by the National Natural Science Foundation of China (NSFC) under Grant 92167202, and in part Shenzhen Steady Funding Program. The work of Licheng Zhao was supported in part by the NSFC under Grant 62206182, and in part by Guangdong Basic and Applied Basic Research Foundation under Grant 2024A1515010154.
References
[1] I. M. Stancu-Minasian, Fractional programming: theory, methods and applications. Norwell, MA, USA: Kluwer, 2012.
[2] E. B. Bajalinov, Linear- Linear-fructional programming theory, methods, applications and software Norwell, MA, USA: Kluwer, 2003.
[3] Schaible, "Parameter-free free convex equivalent and dual programs fractional programming
problems," Zeitschrift für Oper. Res., vol. 18, no. 5, pp. 187-196, Oct. 1974.
10

---

[4] J. Shi and J. Malik, "Normalized cuts and image segmentation," JEEE Trans. Pattern Anal. Mach. Intell., vol. 22, no. 8, pp. 888- 905, Feb. 2000.
[5] K. Shen and W. Yu, "Fractional programming for communication systems Part I: Power control and beamforming," IEEE Trans. Signal Process., vol. 66, no. 10, pp. 2616-2630, Mar. 2018.
[6] W. Dinkelbach, "On nonlinear fractional programming," Manage. Sci., vol. 13, no. 7, PP.
492 492-498, Mar. 1967.
[7] X. Chen, Z. Xiao, F. Nie, and J. Z. Huang. "FINC: An efficient and effective optimization method for normalized cut," JEEE Trans. Pultern Anal. Mach. Intell., Feb. 2022.
[8] B. MacQueen, "Some methods for classification and analysis multivariate observations," in
Proc. 5th Berkeley Symp. Math. Statist. Probab., vol. 1, 1967, pp. 281-297.
[9] S. C. Johnson, "Hierarchical clustering schemes," Psychometrika, vol. 32, no. 3, pp. 254,
Sept. 1967.
[10] A. Ng. M. Jordan, and Y. Weiss, "On spectral clustering: Analysis and an algorithm," Adv. Neural Inf. Process. Syst. (NeurIPS), vol. 14, 2001.
[11] E. Nie, C. Ding, D. Luo, and H. Huang. "Improved MinMax cut graph clustering with nonnega- tive relaxation," in Proc. Joint Eur. Conf. Mach. Learn. Knowl. Discovery Databases, 2010, pp. 451-466.
[12] M. Ester, H.-P. Kriegel, J. Sander, X. Xu et al., "A censity-based algorithm for discovering clus- ters in large spatial databases with noise," " in Proc. ACM SIGKDD Int. Conf. Knowl. Discovery & Data Min., vol. 96, no. 34, 1996, pp. 226-231.
[13] D. Yan, L. Huang, and M. Jordan, "Fast approximate spectral clustering," " in Proc. ACM SIGKDD Int. Conf. Knowl. Discovery & Data Min., June 2009, pp. 907-916.
[14] M. Stoer and F. Wagner, "A simple min-cut algorithm," J. ACM, vol. 44, no. 4, pp. 585-591, July 1997.
[15] L. Hagen and A. B. Kahng, "New spectral methods for ratio cut partitioning and clustering." IEEE Trans. Comput.-Aider Design Integr. Circuits Syst., vol. 11, no. 9, pp. 1074-1085, Sept. 1992.
[16] C. H. Ding, X. He, H. Zha, M. Gu, and H. D. Simon, "A min-max cut algorithm for graph partitioning and data clustering," IEEE Int. Conf. Data Min. (ICDM), Nov. 2001, pp. 107-114.
[17] F. Nie, J. Lu, D. Wu, R. Wang. and X. Li, "A novel normalized-cut solver with nearest neighbor hierarchical initialization," IEEE Trans. Pattern Anal. Mach. Intell., vol. 46, no. 1, pp. 659-666, May 2024.
[18] X. Chen, W. Hong, F. Nie, D. He, M. Yang, and J. Z. Huang, "Spectral clustering of large-scale data by directly solving normalized cut," in Pruce. ACM SIGKDD Int. Conf. Knowl. Discovery & Data Min., July 2018, pp. 1206-1215.
[19] U. Von Luxburg, "A tutorial on spectral clustering," " Statist. Comput., vol. 17, pp. 395-416, Aug. 2007.
[20] J. J.P. Crouzeix, J. A. Ferland, and S. Schaible, "An algorithm for generalized fractional programs,"
J. Optim. Theory Appl., vol. 47, no. I, pp. 35-49, Sept. 1985.
[21] B. Ghanem and N. Ahuja, "Dinkelbach NCUT: An efficient framework for solving normalized cuts problems with priors and convex constraints," Int. J. Comput. Vision, vol. 89, pp. 40-55, Feb. 2010.
[22] B. Schölkopf, C. J. Burges, and A. J. Smola, Advances in kernel methods: support vector learning. Cambridge, MA, USA: MIT press, 1999.
[23] S. P.. Boyd and L. Vandenberghe, Conver optimization. U.K.: Cambridge univ. Press, 2004.
[24] G. E. Fasshauer, "Positive definite kernels: past, present and future," Dolomites Res. Notes Approx., vol. 4, pp. 21-63, 2011.
[25] G. W. Stewart, Introduction to Matrix Computations. New York, NY, USA: Academic Press,
1973.
[26] K. N. Markelle Kelly, Rachel Longjohn, "The UCI machine learning repository," https://archive ics.uci.edu

---

[27] J. Wang et al., "Everything about transfer learning and domain adapation, httpp////t////assssecccaaaa
xyz
[28] C.-C. Chang and C.-J. Lin, "LIBSVM: a library for support vector machines," ACM Truns. Intell. Syst. Technol., vol. 2, no. 3, pp. 1-27, May 2011.
[29] A. Lancichinetti, S. Fortunato, and J. Kertész, "Detecting the overlapping and hierarchical community structure in complex networks," New J. Phys., vol. 11, no. 3, p. 033015, Mar. 2009.
[30] A. J. Gates and Y. Ahn, "The impact of random models on clustering similarity," J. Mach. Learn. Rex., vol. 18, no. 87, pp. 1-28, Jan. 2017.
[31] S. Gould, R. Fulton, and D. Koller, "Decomposing scene into geometric and semantically consistent regions," in IEEE Inl. Conf. Comput. Vis. (ICCV), Sept. 2009, pp. 1-8.
[32] B. Cheng, G. Liu, J. Wang. Z. Huang, and S. Yan, "Multi-task low-rank affinity pursuit for image segmentation," in IEEE Int. Conf. Comput. Vis. (ICCV), Nov. 2011, pp.
[33] Y. Sun, P. Babu, and D. P. Palomar, "Majorization-mninizaaii algorithms in signal processing, communications, and machine learning," IEEE Trans. Signal Process. vol. 65, no. 3, pp. 794-816, Aug. 2016.
[34] M. Razaviyayn, M. Hong, and Z.-Q. Luo, "A unified convergence analysis of block successive minimization methods for nonsmooth optimization." SIAM J. Optim., vol. 23, no. 2, pp. 1126- 1153, 2013.
12

---

Appendix
A.1 Proof of Proposition 4
We begin with a brief review of the MM theory problem
33 34
Consider general constrained optimization
maximize ZEX
((r)).
(31)
Rather than solving the above problem directly, the MM theory deals with approximation of 311 iteratively. In principle, we construct a surrogate function g ( of x given the condition parameter ft E X, such that
(x) - f(x), g ()) = f()).
(32)
(33)
Then the MM method solves a sequence of new problems of the surrogate function:
maximize xEX
(
(34)
with å iteratively updated to the previous solution Specifically, with the solution of 34 in the
(t - 1)th iteration denoted by ((t-1), we construct surrogate function (x] for the iteeraton
and then obtain the new solution (t) of (34) and so forth, as illustrated in Figure
f(z)
gx2|2(1)
g(0/((t-11)
s (f+1)
(t)
(t-1)
Figure 5: The original objective value f(x) is nondecreasing after each iteration of the MM method.
Theorem (Monotonic convergence 33 34) The MM method yields nondecreasing conver- gence of the original objective value f(x). i.e.,
f(i(t-1) s f(E(9) for t 1,2.....
(35)
We now show that the alternating optimization between and {Yx) in (17) can be interpreted as an MM method. We still use the superscript to index the iteration. Recall also that each Yg in the ith iteration is optimally updated
Yd (t) Z₁ (a((-1))) (x-())
(36)
We now view the update of Y, as a function the previous solution & that
)a(()) Z ) (a((t1).
(37)
Substituting each Y2 with (+) in the new objective function in gives rise to function conditioned on f::
k
g(x(2)) Σ tr 2Zz
B, (
(=(( ( (L (z((0)) (
(38)
13

---

Notice that maximizing the objective function in (77 with { fixed is equivalent to maximizing g(x[)) where is fixed the solution of the previous iteration.
Most importantly, it can be shown that (()( meets the conditions 32 and
33
for the original
objective function in (15 the alternating optimization between and k in amounts
MM procedure. The result of Proposition then immediately follows by Theorem
A.2 Proof of Proposition
First of all, because W is indefinite, its minimum eigenvalue Amia (W) must be negative. With in 30 the matrix W can be rewritten as
Amn ( (W), D
W W
min; d3
dj min; di
1, dx
W Amin (W)I - Amin W diag
(39)
min, d,
is evident that W Amin I and Amiu W diag min; d,
-..... ming d;
1| are both positive
semi-definite, so W positive semi-definite too. Moreover, it is easy to see that problem equivalent to
K
W
maximize
Ka +
(40a)
x
D
subject to
7b
7c
(40b)
which can be further rewritten as
Way Zp
maximize
(41a)
x D
subject
7b
7cc
(41b)
The proof is then completed.
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract describes the motivation behind our algorithm and the novel mathematical tool that leads to the proposed algorithm.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The limitation discussed in Section along with conclusion.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
15

---

Justification: We state the theory assumptions in all the propositions and theorem. For the new result in Proposition 3 we provide the proof right after the proposition. For the new results in Proposition 5 and Proposition 6 we relegate their proofs to Appendix A. Regarding the existing results, i.e., Proposition Proposition their souree references.
2 and Theorem we clarify
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
The details of the proposed algorithm are stated in Algorithm T
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
16

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
We have submitted the source codes as anonymized zip file.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. ec/
gublic/guidess CodeeSumissiionooo
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips cc/ wttpppplllllllpie https//ooooouaaassssooooooool111
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The experimental details are presented in Section The attached source codes are well commented.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We report the standard deviation of the experiment results, and run the experiment 10 times to avoid the extreme cases of the random initialization.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoo bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
17

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The experiments computer resourees are clarified at the beginning of Section
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
We follow the instructions listed in NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. if there special consid- eration due to laws or regulations in their jurisdiction..
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is societal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
18

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g.. gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: This paper describes a new mathematical method to solve the NCut problem. This paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
Yes, have properly credited the creators and original owners of the assets used in our paper. For each dataset, we have provided appropriate citations and links where they be accessed.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
19

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperssi thood cww datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: There are new codes related to the proposed algorithm in this paper, which are submitted anonymized zip file along with the user documentation.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question:
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
This paper does involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
20

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
21


Reviews:
[{"review_id": "slEtVnhQMR", "reviewer": "Reviewer_mC6e", "summary": "The paper addresses the challenge of the Normalized Cut (NCut) problem in unsupervised clustering.\n\nConventional fractional programming (FP) techniques, especially Dinkelbach’s transform, are inadequate as they only handle single ratios and are limited to two-class clustering.\n\nThis paper extends the quadratic transform to multidimensional ratios, converting the fractional 0-1 NCut problem into a solvable problem.\n\nThe authors also show the convergence of their proposed multidimensional FP method using minorization-maximization theory.", "questions": "What are the main novelties of this paper?", "limitations": "Yes", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The proposed method extends the quadratic transform to handle multiple ratios, enabling it to address multi-class classification problems.\n\n2. The proposed method converts the complex NCut problem into a more tractable form, solving it iteratively as a manageable subproblem.\n\n3. The algorithm's performance is validated on multiple datasets, demonstrating superior results compared to existing methods.", "weaknesses": "1. **Application Reformulation**: Reformulating the NCut problem into a multiple ratio problem is not new and has been previously demonstrated in the literature.\n\n2. **Multiple Ratio Fractional Optimization**: Solving multiple ratio fractional optimization using the Quadratic Transform is a standard practice. The convergence of the proposed method follows directly from existing minorization-maximization techniques. The proposed algorithm and its associated theoretical analysis are relatively incremental.\n\nOverall, the problem formulation and optimization algorithm in this paper have limited novelties.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank the reviewer for acknowledging the strengths of this paper. We would like to focus on the \"Weakness'' and \"Questions'' parts in the following.   \n\n1. **Weakness One:** Actually, the paper never claims that the reformulation  of the NCut problem as a multiple-ratio problem is a contribution or novelty. The real contribution lies in how to address the 0-1 NCut problem and the corresponding performance analysis, as opposed to the previous works that simply drop the discrete constraint in a heuristic fashion.\n2. **Weakness Two:** It is true that our method is more or less connected to the existing fractional programming theory. But we wish to clarify that (almost) all the optimization algorithms in the AI field are based on the existing optimization methods/theories, e.g., the well-known Adam optimizer is in essence a momentum-aided gradient method---which has been extensively studied in the optimization community before Adam was proposed. Moreover, we wish to highlight the fundamental difference between our work and the existing literature. There are several highly nontrivial new results/insights that are by no means incremental improvements, e.g., the comparison between the scalar-ratio method and the matrix-ratio method, the new quadratic transform method tailored to the NCut problem, and the convergence rate analysis.\n3. **Conclusion of Weakness:** Again, first of all, we never ever claim the problem formulation as a novelty. This work is aimed at solving a notoriously difficult long-standing problem from a novel perspective. Secondly, this work is much more than just applying the standard quadratic transform to the NCut problem; we have provided many highly nontrivial new results/insights.\n4. **Questions:** The main novelties of this paper can be recognized in the following three respects:\n    -  *New Method:* Our main theoretic contribution is stated in Proposition 3. We clarify that it is fundamentally different from the existing quadratic transform in Theorem 2 in [5]. Actually, the conventional quadratic transform in the literature does not even work for the NCut problem. The new fractional programming method considerably generalizes the existing one to account for a wider range of multiple-ratio problems.\n    -  *New Insight:* There are two types of quadratic transform: the scalar case and the matrix case. In the literature, the choice of quadratic transform simply depends on the original form of the ratios contained in the problem, i.e., the scalar (resp. matrix) quadratic transform is employed if the ratios are scalars (resp. matrices). However, this paper shows that, even though the ratios in the NCut problem are scalar, it is better to rewrite the scalar ratios in the matrix form and thereby apply the matrix quadratic transform, otherwise the discrete constraint is difficult to tackle. This is an interesting nontrivial insight.\n    -  *New Analysis:* Although the convergence behavior of the quadratic transform has been studied extensively in the literature, most of the prior works only discuss the conditions under which the quadratic transform based iterative algorithm can guarantee convergence. To the best of our knowledge, it remains a mystery as to how fast the quadratic transform method converges. As a newly added result, we show that\n   \\begin{align}\n        |f(x^*)-f(x^{(1)})| \\le \\frac{LR^3}{6},\n    \\end{align}\n\\begin{align}\n|f(x^*)-f(x^{(k)})| \\le \\frac{2\\Lambda R^2+2LR^3/3}{k+3},\\quad\\text{for}\\quad k\\ge 2,\n\\end{align}\n   where $f(\\cdot)$ is the optimization objective value, $x^*$ is the converged solution,\n    $k$ is the iterate index, $R$ is the Euclidean distance from the starting point to $x^*$, $L$ is the Lipschitz constant of $\\nabla^2 f(x)$, $\\Lambda$ is the maximum eigenvalue of $\\nabla^2 f(x)$,\n    and $x^{(k)}$ is the solution after $k$ iterates. We emphasize that the convergence rate analysis is highly nontrivial due to the nonconvexity and the discrete constraint of the NCut problem.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LebXPSF1SA", "reviewer": "Reviewer_MUdC", "summary": "This manuscript deals with the **Normlaized cut (NCut)** problem by proposing a new algorithm called **fractional programming-based clustering** (FPC). The main idea of FPC is rewriting the original NCut problem to an equivalent one by using a so-called **Multidimensional quadratic transform**. Then, the clustering result is obtained by an iterative step that is guaranteed to monotonically increase the objective of NCut problem until it converges. Experiments demonstrate that the proposed algorithm outperforms the baselines with a higher objetive value on multiple datasets.", "questions": "My questions are mainly described in the Weaknesses section. \n\nBesides, I wonder if the author could conduct some experiments that compares the performance of the algorithm (especially on the aspect of convergence) on clustering scenarios with **difficulties from easy to hard**, i.e. simply construct a Gaussian Mixtures with two clusters and gradually adjust their center distance from distant to close, and see during the transition, if the convergence becomes more challanging. This could be helpful to understand the limits of the algorithm.", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "I think the strengh of this paper mainly falls onto the following aspects:\n\n**Novelty**:\n- Rewriting the NCut problem by the Multidimensioanl quadratic transform\n- A critical step (Eq. (23) in the manuscript) is proposed to make the clustering result $\\boldsymbol{X}$ can be efficiently solved\n- The designed FPC finds the clustering iteratively that monotonically increases the objective of NCut\n\n**Experimental result**\n- The proposed FPC outperforms other baselines with a higher objective value of NCut obtained on multiple real datasets\n- It also gives a better clustering result in terms of metrics such as accuracy and normalized mutual information\n- The runtime of FPC seems to be similar to the baselines\n\n**Clarity**\n- The writing of this manuscript is clear and easy to follow\n- The proofs are complete that necessarily supports the proposed arguments \n\nOverall, I like the idea of this manuscript and I think the novelty is sufficient to NeurIPS. The proposed algorithm should be a good supply to the field of graph cut that may inspires some further research under the same direction, as long as several concerns (see the weaknesses below) can be adequately addressed.", "weaknesses": "**(1) Lack of analysis and experiments on the convergence of FPC**\n\nSince it is guaranteed that the objective value of NCut is monotonically increasing during the iterations, it is very important to understand how does the convergence of FPC look like. For example, I would like to know **if the objective value could get stuck on some sub-optimal point?** And if yes, **when does this happen in practice?** Without any study (either theoretical or emprical) on the convergece, it is hard to tell if the algorithm has reached its limit or not. So I would suggest the authors to at least show some curves of the objective values during the iterations. \n\n**(2) How far to the global optimum?**\n\nEven though the objective values obtained from FPC are higher than other baselines' in the experiments, it is still unknown how important are such improvements compared to the global optimum. So I would be curious on some cases (could be small and artificial) when global optimum are known and see how far is the result of FPC to the global optimum. So far, the objective value by itself is not that meaningful to me and may not be able to fully showcase the strength of the algorithm", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for the very positive comments on this work. Also thank you so much for providing many constructive suggestions. We have added the convergence rate analysis and many new experiments according to your suggestions, as specified in what follows.  \n\n1. **Weakness One:** We would edit both the theoretic and the experimental aspects of this paper significantly to relieve your concern. On the theory side, we accomplish the convergence rate analysis of the proposed FPC algorithm. It can be shown that\n\\begin{align}\n|f(x^*)-f(x^{(1)})|  \\le \\frac{LR^3}{6},\n\\end{align}\n\\begin{align}\n|f(x^*)-f(x^{(k)})|  \\le \\frac{2\\Lambda R^2+2LR^3/3}{k+3},\\quad\\text{for}\\quad k\\ge 2\n\\end{align}\nwhere $f(\\cdot)$ is the optimization objective value, $x^*$ is the converged solution,\n    $k$ is the iterate index, $R$ is the Euclidean distance from the starting point to $x^*$, $L$ is the Lipschitz constant of $\\nabla^2 f(x)$, $\\Lambda$ is the maximum eigenvalue of $\\nabla^2 f(x)$, and $x^{(k)}$ is the solution after $k$ iterates. We remark that the convergence rate analysis is highly nontrivial here because the NCut problem is nonconvex and incurs discrete constraints. On the experiment side, we add new numerical results on the convergence behavior of the proposed algorithm. In the one-page PDF, Figure 1 shows how fast the FPC algorithm converges; observe that FPC attains convergence after merely 3 iterates. Moreover, Figure 2 shows the local optimum issue of FPC. When two cluster centers are far apart, FPC can always achieve the global optimum; but when the cluster centers get closer so that the NCut problem becomes more difficult (as advised by the reviewer), then FPC may get stuck at a local optimum. In practice, we may reduce the risk of local optimum trapping by trying out various starting points.\n2. **Weakness Two:** We have incorporated this excellent advice into our work. Specifically, we find the global optimum for those small-size dataset via exhaustive search, and use it as the benchmark to compare with the proposed FPC algorithm. The new results are shown in Figure 1 in the attached one-page PDF. The figure shows that the FPC attains the global optimum.\n3. **Questions:** Thank you for the nice advice, which has been fully implemented. As the reviewer suggests, we try out the FPC algorithm on the different clustering scenarios with the distance between two cluster centers being gradually reduced, and consequently the clustering problem becomes increasingly difficult. This new experiment is shown in Figure 2 in the attached one-page PDF, which will be incorporated into the paper after the rebuttal session finishes.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "6d1arO3TT9", "reviewer": "Reviewer_fiXH", "summary": "The paper presents a new fractional programming based algorithm for the multi-cluster normalized cut objective which exploits a multidimensional quadratic transform.\n\nThe paper starts by introducing the Ncut problem. Then it discusses previous fractional programming methods such as Dinkelbach's method for the single-ratio case, and the quadratic transform that can be used to deal with the sum-of-ratios problem. It is then shown that the quadratic transform carries over to the matrix ratio case. The proposed method FPC works by applying the multidimensional quadratic form to the Ncut objective. They then show that the objective as well as the original Ncut objective are nondecreasing after each iteration of their method FPC. \n\nIn the experiments the approach is compared to standard spectral clustering as well as the recently proposed methods FINC and FCD. The proposed method achieves the lowest Ncut value for all datasets, when doing random initializations or refining an existing spectral clustering solution, as well as competitive results when evaluating with other performance metrics. In terms of time consumption, the method runs in the same order of magnitude as standard spectral clustering and faster as FINC method, while being slower than the FCD method.", "questions": "Is Prop. 3 novel? Could you please comment on the differences to Theorem 2 in [5]?", "limitations": "The authors mention in the conclusion that the analysis of the convergence speed of the method could still be extended.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is well-written and technically sound. It proposes a new method for the Ncut objective which has been shown to yield competitive results on several small- to medium-size benchmark datasets. The main contribution of the paper is the application of the multi-dimensional quadratic form to the Ncut objective.", "weaknesses": "The used datasets are relatively small, the paper could be made stronger by showing that the method also scales to some larger datasets. Moreover, the connection to the MM theory is mentioned in the last section as a conclusion without being mentioned before. It only gets discussed in the appendix for the first time. The main results should be at least mentioned before in the main body of the text.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for appreciating the presentation and the technical contributions of this work. We would like to address your concerns and questions in the following.  \n\n1. **Weakness:** Thanks for the constructive suggestion. We have added two larger datasets:  letter recognition (with 20,000 samples) and MNIST subset (with 30,000 samples). The new experimental results are summarized in Table 1 and Table 2 in the attached one-page PDF. Observe that the proposed FPC algorithm still outperforms the benchmarks significantly on these new datasets. Also thanks for the advice on paper organization. We would move the connection to the MM theory to the main body of the text after the rebuttal session finishes.\n2. **Questions:** Yes, Prop. 3 is novel. Prop. 3 deals with the matrix ratio\n$$\n\\boldsymbol B^{-1}\\boldsymbol A\\in\\mathbb R^{m\\times m},\n$$\nwhile Theorem 2 in [5] deals with the scalar ratio\n$$\n    \\boldsymbol a^\\top\\boldsymbol B^{-1} \\boldsymbol a \\in\\mathbb R.\n$$\nFurthermore, when the ratio is nested in $\\mathrm{Tr}(\\cdot)$, we rewrite the scalar ratio problem as the matrix ratio case:\n$$\n    \\mathrm{Tr}(\\boldsymbol a^\\top\\boldsymbol B^{-1} \\boldsymbol a)=\\mathrm{Tr}(\\boldsymbol B^{-1} \\boldsymbol a\\boldsymbol a^\\top)=\\mathrm{Tr}(\\boldsymbol B^{-1} \\boldsymbol A),\\quad\\text{where}\\quad \\boldsymbol A = \\boldsymbol a\\boldsymbol a^\\top.\n$$\nHowever, the reverse is not true since $\\boldsymbol A$ may not be factored as $\\boldsymbol a\\boldsymbol a^\\top$. Thus, Prop. 3 encompasses Theorem 2 in [5] as a special case.\n3.  **Limitations:** We have accomplished the convergence rate analysis of the proposed FPC algorithm. It can be shown that\n\\begin{align*}\n    |f(x^*)-f(x^{(1)})| \\le \\frac{LR^3}{6},\\\\    \n\\end{align*}\n\\begin{align}\n|f(x^*)-f(x^{(k)})| \\le \\frac{2\\Lambda R^2+2LR^3/3}{k+3},\\quad\\text{for}\\quad k\\ge 2,\n\\end{align}\nwhere $f(\\cdot)$ is the optimization objective value, $x^*$ is the converged solution,\n$k$ is the iterate index, $R$ is the Euclidean distance from the starting point to $x^*$, $L$ is the Lipschitz constant of $\\nabla^2 f(x)$, $\\Lambda$ is the maximum eigenvalue of $\\nabla^2 f(x)$, and $x^{(k)}$ is the solution after $k$ iterates. We remark that the convergence rate analysis is highly nontrivial here because the NCut problem is nonconvex and incurs discrete constraints. The above analysis will be added to the paper as a major theoretic contribution.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
First of all, we wish to thank the TPC members for organizing reviews for our paper. The comments from Reviewer MUdC and Reviewer fiXH are quite positive; they both think that the paper is well written and contains sufficient novelty and technical contributions in terms of the NeurIPS criterion. The two reviewers provide some constructive suggestions (e.g., add convergence analysis and new experiments, and use larger datasets), all of which have been accomplished and can be readily incorporated into the paper.  
  

In contrast, Reviewer mC6e has expressed deep concerns about the novelty of this work. But we believe that this is due to misunderstanding. Reviewer mC6e criticizes that formulating the NCut problem as a multiple-ratio problem should not count a novelty. However, this paper never claims this problem formulation as any sort of novelty/contribution. Our real contribution lies in solving this notoriously difficult long-standing problem from a novel fractional programming perspective, and also in highly nontrivial performance analysis.  

The other criticism from Reviewer mC6e concerns the novelty of the proposed method. He or she thinks that the proposed FPC algorithm just follows the existing quadratic transform method in [5]. But the technical contributions of this paper are much more than that:
- As we have confirmed with Reviewer mC6e and Reviewer fiXH, our main theoretic contribution stated in Proposition 3 is fundamentally different from the existing quadratic transform in Theorem 2 in [5]. Actually, the conventional quadratic transform in the literature does not even work for the NCut problem. The new fractional programming method considerably generalizes the existing one to account for a wider range of multiple-ratio problems.
- We tailor quadratic transform to the NCut problem and bring new insight. There are two types of quadratic transform: the scalar case and the matrix case. In the literature, the choice of quadratic transform simply depends on the original form of the ratios contained in the problem, i.e., the scalar (resp. matrix) quadratic transform is employed if the ratios are scalars (resp. matrices). However, this paper shows that, even though the ratios in the NCut problem are scalar, it is better to rewrite the scalar ratios in the matrix form and thereby apply the matrix quadratic transform, otherwise the discrete constraint is difficult to tackle. 
- The convergence rate analysis is by no means an incremental improvement upon the previous works. Although the convergence behavior of the quadratic transform has been studied extensively in the literature, most of the prior works only discuss the conditions under which the quadratic transform based iterative algorithm can guarantee convergence. To the best of our knowledge, it remains a mystery as to how fast the quadratic transform method converges. As a newly added result, we show that

\begin{align}
        |f(x^*)-f(x^{(1)})| \le \frac{LR^3}{6}, 
\end{align}

\begin{align}
        |f(x^*)-f(x^{(k)})| \le \frac{2\Lambda R^2+2LR^3/3}{k+3},\quad\text{for}\quad k\ge 2,
    \end{align}
where $f(\cdot)$ is the optimization objective value, $x^*$ is the converged solution, $k$ is the iterate index, $R$ is the Euclidean distance from the starting point to $x^*$, $L$ is the Lipschitz constant of $\nabla^2 f(x)$, $\Lambda$ is the maximum eigenvalue of $\nabla^2 f(x)$,
and $x^{(k)}$ is the solution after $k$ iterates. We emphasize that the convergence rate analysis is highly nontrivial due to the nonconvexity and the discrete constraint of the NCut problem.   

The above key contributions and novelties may have been overlooked in the last round of review. We sincerely hope that our responses can help highlight them.

Meta-review: The authors proposed to solve Normalized cut via the fractional programming technic. Both Normalized cut and fractional programming are not new, but the usage of fractional programming is new. The experiments need to be improved
Decision: Accept (poster)