PaperlayerView exact revision on arXiv

Source-linked AI summary

Normalized Cuts and Data Clustering via Matrix Fractional Programming

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

arXiv:2610.36616v1cs.LGeess.SP

TL;DR

NCut's multiple ratios make the classical single-ratio Dinkelbach transform inadequate for multi-class clustering. This paper introduces a multidimensional quadratic transform and matching-based solution; experiments report the lowest NCut objective values on four datasets, though ACC remains suboptimal.

  • Problem

    Classical Dinkelbach's transform handles a single ratio, whereas multi-class NCut involves multiple ratios, leaving conventional fractional programming inadequate for this problem.

    Source: §I · p. 1

  • Method

    The multidimensional quadratic transform handles NCut's multiple ratios and recasts its discrete problem as weighted bipartite matching solvable by linear search.

    Source: §I · pp. 1–2

  • Results

    FPC attained the lowest NCut objective values on Office, STL10, Sensorless, and CIFAR10, but its ACC remained suboptimal.

    Source: F. Saturation of NCut Objective… · p. 12

  • Takeaways & Limitations

    The FP/MM interpretation gives FPC provable monotonic convergence on the NCut criterion, and the paper characterizes its convergence rate.

    Source: §VI · pp. 13–14

    The work focuses on the multiclass NCut objective; other graph partitioning criteria are beyond its main scope.

    Source: §VI · p. 14

Abstract

from arXiv · show

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.

I. INTRODUCTION

The introduction frames multi-class NCut as a difficult discrete, nonconvex clustering problem and motivates a fractional-programming approach. It presents a multidimensional transform that yields a matching-based solution, alongside convergence analysis and scalable graph constructions.

I. INTRODUCTION

  • The multidimensional quadratic transform handles NCut's multiple ratios and converts its 0-1 problem into weighted bipartite matching solvable by linear search.Source: §I · pp. 1–2
  • Conventional spectral clustering is a two-stage heuristic without performance guarantees, while cited SDR and Dinkelbach approaches are limited to two-class NCut,,,.Source: §I · p. 1
  • The proposed FPC method has stationary-point convergence under differentiability conditions, and its local convergence rate is characterized.Source: §I · p. 2
  • For small datasets, a positive-definite kernel yields a PSD similarity matrix; for large datasets, a sparse anchor graph does likewise, and indefinite matrices can be transformed equivalently.Source: §I · p. 2
  • Starting from ground-truth initialization, clustering error rises from 0% despite monotonic objective improvement, revealing a saturation region where NCut cannot distinguish lower-error solutions.Source: §I · p. 2
  • The journal article extends the NeurIPS 2024 version with stronger convergence analysis, sparse anchor graphs, larger datasets, added baselines, and saturation analysis.Source: §I · p. 2

II. PRELIMINARY

  • Section II reviews the NCut problem and conventional spectral clustering as a major experimental benchmark.Source: §II · p. 2

A. NCut Problem for Graph Clustering

B. Conventional Spectral Clustering (SC) Method

Spectral clustering relaxes the NCut constraints into a trace-minimization problem, solves it with eigenvectors, and heuristically recovers discrete assignments using K-means.

B. Conventional Spectral Clustering (SC) Method

  • SC replaces the original constraints with T^⊤T = I, yielding a trace-minimization approximation rather than an equivalent reformulation.The paper calls this rewrite completely heuristic.Source: B. Conventional Spectral Clustering… · p. 3
  • The relaxed problem is solved using the K largest eigenvalues and their eigenvectors, after which P is recovered as D^-1/2T.The passage identifies the eigenvectors as linearly independent.Source: B. Conventional Spectral Clustering… · p. 3
  • Discrete assignments are recovered by applying K-means to the rows of P, because recovering X directly is numerically difficult.Each x_ik is then assigned according to the resulting clusters.Source: B. Conventional Spectral Clustering… · p. 3
  • The method lacks mathematical justification both because the relaxation may not be equivalent to NCut and because assignment recovery is heuristic.The paper identifies K-means as the heuristic used for recovery.Source: B. Conventional Spectral Clustering… · pp. 3–4

III. FRACTIONAL PROGRAMMING (FP)

NCut has a sum-of-ratios objective, but conventional fractional-programming transforms do not directly solve its general multi-class form. The section introduces the multidimensional quadratic transform as the matrix-ratio approach used to address this gap.

III. FRACTIONAL PROGRAMMING (FP)

  • NCut’s objective is a sum of ratios, making it fractionally structured, but the section notes that few prior works apply fractional programming to it.The section presents multidimensional quadratic transform as the building block of the proposed clustering algorithm.Source: §III · p. 4

A. Existing FP Methods

  • Dinkelbach’s transform handles a single ratio and is therefore limited in NCut to two-class clustering, except for the max-min-ratios case.Under the stated concave-convex condition, its single-ratio reformulation is convex in x for fixed y and iteratively updating y guarantees convergence to the original problem’s global optimum.Source: A. Existing FP Methods · p. 4
  • For a sum of ratios, separately applying Dinkelbach’s transform to each ratio produces a problem not equivalent to the original.Thus the classic transform does not work for NCut with general K clusters.Source: A. Existing FP Methods · p. 4
  • The section introduces the quadratic transform as an equivalent reformulation of the sum-of-ratios problem, with an auxiliary variable for each ratio and iterative updates.With the stated concave-convex conditions, the reformulated problem is convex in x for fixed auxiliary variables.Source: A. Existing FP Methods · p. 4
  • Applying conventional alternating FP updates to NCut yields FINC, but its fixed-y x-subproblem is nonconvex because x⊤Wx is not concave and the constraint set is nonconvex.The cited work handles that subproblem heuristically.Source: A. Existing FP Methods · p. 4

B. Proposed Multidimensional Quadratic Transform

The multidimensional quadratic transform extends fractional programming to matrix ratios by introducing matrix auxiliary variables. The resulting iterative procedure updates those variables and the optimization variable, and the paper connects its convergence behavior to MM.

B. Proposed Multidimensional Quadratic Transform

  • The multidimensional quadratic transform extends the sum-of-ratios transform to matrix ratios, with each positive-semidefinite numerator matrix factorized as Z_k(x)^⊤Z_k(x).The factorization follows from positive semidefiniteness rather than adding a modeling assumption.Source: B. Proposed Multidimensional Quadratic… · p. 5
  • The matrix transform is exact and preserves the original matrix-fractional objective’s optimizer.It encompasses the conventional quadratic transform as a special case and differs from relaxed low-rank nonnegative factorization.Source: B. Proposed Multidimensional Quadratic… · p. 5
  • The transformed problem supports alternating updates: each auxiliary Y_k has a closed-form update for fixed x, followed by optimizing x with the Y_k fixed.The generic procedure repeats until the original objective value converges.Source: B. Proposed Multidimensional Quadratic… · p. 5
  • The MM connection uses a surrogate g(x|ˆx(t)) and makes the original objective nondecreasing after each iteration.The surrogate is constructed at iteration t.Source: Figure 2 · p. 5

C. Connection to MM Theory

The alternating optimization induced by the multidimensional quadratic transform is an MM procedure, yielding monotonic objective improvement and stationary-point convergence under differentiability. For NCut, the transform also supports efficient updates of discrete cluster assignments.

C. Connection to MM Theory

  • The alternating optimization is an MM procedure, guaranteeing nondecreasing objective values and stationary-point convergence when the relevant functions are differentiable.The MM interpretation follows because the constructed surrogate satisfies the required conditions for the original objective.Source: C. Connection to MM Theory · p. 6

IV. FP-BASED APPROACH TO NCUT PROBLEM

A. Proposed Multidimensional FP-Based Clustering

  • FPC assigns each data point to the cluster with the largest corresponding μ_ik, breaking ties randomly.Rewriting μ_k avoids updating auxiliary y_k variables and avoids computing the square root of W.Source: A. Proposed Multidimensional FP-Based… · p. 6
  • FPC monotonically increases the original NCut objective, but this does not guarantee a global optimum for the NP-complete discrete problem.The analysis instead concerns monotonic improvement and local convergence behavior.Source: A. Proposed Multidimensional FP-Based… · pp. 6–7

B. Convergence Rate Analysis

The convergence-rate analysis is local: it studies iterates near a local maximizer under concavity and a Lipschitz-continuous Hessian. It relaxes the binary assignment constraints for the rate analysis while preserving the FPC updates.

B. Convergence Rate Analysis

  • The paper characterizes a local convergence rate when the continuous-relaxation objective has a Lipschitz-continuous Hessian.The rate analysis uses the alternating optimization procedure.Source: B. Convergence Rate Analysis · p. 7
  • For the rate analysis, the binary constraints are relaxed to 0 ≤ x_ik ≤ 1, although the original discrete problem and its relaxation yield the same FPC updates.This relaxation is specific to the convergence-rate analysis.Source: B. Convergence Rate Analysis · p. 7
  • The analysis is restricted to a sufficiently small neighborhood of a local maximizer where the objective is concave and the iterates remain feasible.The paper states that global analysis is intractable for the nonconvex NCut objective.Source: B. Convergence Rate Analysis · p. 7

C. Similarity Matrix Generation

The paper constructs similarity matrices using a Gaussian kernel for fully connected graphs and anchor graphs for large datasets. For indefinite similarities, a diagonal shift makes the matrix positive semidefinite so FPC can be applied.

C. Similarity Matrix Generation

  • For a fully connected graph, a positive definite kernel such as the Gaussian kernel generates a positive semidefinite similarity matrix.The passage describes this setting for datasets sufficiently small to permit a fully connected graph.Source: C. Similarity Matrix Generation · p. 8
  • If the similarity matrix is indefinite, adding a sufficiently large diagonal shift produces a positive semidefinite matrix that can be used with FPC.The paper gives an equivalent NCut formulation using the shifted matrix.Source: C. Similarity Matrix Generation · p. 8
  • For large datasets, an anchor graph forms a sparse bipartite representation and yields a positive semidefinite similarity matrix.The construction uses M anchors and connects each data point to its k closest anchors.Source: C. Similarity Matrix Generation · p. 9

D. Computational Complexity

FPC has per-iteration complexity O(KN^2) for fully connected graphs and a sparse-graph implementation whose complexity is linear in N. The paper compares these costs with spectral clustering.

D. Computational Complexity

  • The passage reports that FPC has per-iteration complexity O(KN^2), while the traditional SC algorithm incurs O(N^3), giving the stated complexity comparison for the two methods.The overall complexity of finding α as in (53) is O(N^2).Source: D. Computational Complexity · p. 9
  • For an anchor graph, FPC costs O(NkK + NK + MK) per iteration, while spectral clustering costs O(Nk^2 + M^3 + NkK + NK^2) overall.Here M is the number of anchors and each sample is connected to k anchors.Source: D. Computational Complexity · p. 9
  • Both anchor-graph algorithms scale linearly with N, according to the paper’s comparison.The comparison is for the stated anchor-graph construction and complexity expressions.Source: D. Computational Complexity · p. 9

V. EXPERIMENTS

The experiments evaluate FPC on benchmark clustering datasets and compare it with two-stage spectral methods and direct NCut optimizers under fully connected and anchor-graph settings.

V. EXPERIMENTS

  • Twelve benchmark datasets are evaluated, with two additional mini-datasets reserved for optimality tests.Table I summarizes the datasets.Source: §V · p. 9, Table I · p. 9
  • Baselines include two-stage spectral methods SC, ISR, and DSSRC, plus direct NCut methods FINC, FCD, and FPC.FPC combines the multidimensional quadratic transform with weighted bipartite matching.Source: §V · p. 9
  • Small datasets use Gaussian-kernel similarities, while large datasets use anchor graphs with 1,024 anchors and k = 20.Anchor-graph experiments use a factorized similarity representation; all methods receive the corresponding SC initialization and are evaluated over 20 runs.Source: §V · p. 9

A. Image Segmentation by Clustering

In image segmentation, FPC produces clearer object boundaries than the other evaluated methods.

A. Image Segmentation by Clustering

  • FPC gives clearer object boundaries than the other methods in the image-segmentation comparison.The images are partitioned into 500 superpixels, with color-histogram and local-binary-pattern features extracted before clustering.Source: A. Image Segmentation by Clustering · p. 9
  • The segmentation pipeline clusters image features extracted after partitioning each image into 500 superpixels.The features include color histograms and local binary patterns.Source: A. Image Segmentation by Clustering · p. 9

B. Optimality Tests

FPC reaches the global optimum after three iterations in the reported mini-dataset tests and remains fairly close to the optimum as Gaussian cluster centers approach. Random initializations can nevertheless lead to different local solutions.

B. Optimality Tests

  • 3 iterations suffice for FPC to reach the global optimum in the reported convergence tests.The tests use two mini-datasets and compare the objective trajectory with the exhaustive-search optimum.Source: B. Optimality Tests · p. 10, Figure 4 · p. 10
  • As Gaussian cluster centers move closer and clustering becomes harder, FPC's solution remains fairly close to the global optimum.The two clusters follow N(0, I2) and N(d, I2), with d controlling center separation.Source: B. Optimality Tests · p. 10, Figure 5 · p. 10

C. Sensitivity to Initialization

D. NCut Objective Optimization Performance

FPC generally leads direct methods on NCut and external clustering metrics, while saturation tests expose a limit to what NCut alone can distinguish. Runtime comparisons report lower average times against several baselines, and the paper characterizes the method's convergence and scope.

D. NCut Objective Optimization Performance

  • FPC achieves the best or tied-best NCut objective on 11 of 12 datasets, with reported reductions versus SC and DSSRC on several datasets.The passage reports reductions versus SC of 5.14% on Sensorless, 4.73% on RT-IoT2022, and 3.61% on MNIST; versus DSSRC, reductions are 18.09% on Epileptic, 7.58% on STL10, and 5.86% on MNIST.Source: D. NCut Objective Optimization… · p. 11

E. Clustering Performance

  • FPC attains the most top rankings across clustering metrics, leading in ACC on 7 datasets, NMI on 7, and ARI on 8.These metrics are evaluated on solutions selected by NCut objective over 20 runs; higher values indicate better performance.Source: E. Clustering Performance · p. 11, Table III · p. 12

F. Saturation of NCut Objective Function for FPC

  • Starting from ground-truth labels with 0% error, FPC lowers NCut while error rises, so the lowest NCut solutions can have suboptimal ACC.Below the observed saturation error, NCut alone cannot reliably distinguish or rank solutions by agreement with ground truth; this limitation does not imply that lower error lacks practical value.Source: F. Saturation of NCut Objective… · pp. 12–13, Figure 9 · p. 13

G. Time Consumption

  • 56.58%, 63.87%, 99.07%, and 97.38% lower average running time than SC, ISR, DSSRC, and FINC, respectively, under fully connected graphs.Under anchor graphs, FPC requires 38.92%, 85.10%, and 97.83% less average running time than SC, ISR, and FINC, respectively; runtime includes optimization only, excluding initialization and common preprocessing.Source: G. Time Consumption · p. 13, Figure 10 · p. 13

VI. CONCLUSION

  • FPC has provable monotonic NCut convergence and a characterized rate; this work focuses on multiclass NCut, leaving other criteria and online, streaming, multi-view, and distributed extensions for future work.Source: §VI · pp. 13–14

Related papers

Loading 2610.36616v1…