Research map / Learning theory and algorithms / Clustering
Multidimensional Fractional Programming for Normalized Cuts
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Extends the multidimensional quadratic transform to the matrix-ratio case and applies it to normalized cut clustering, yielding an iterative bipartite-matching-style update (FPC) with monotone MM convergence.
Problem
Normalized cut (NCut) clustering is a sum-of-ratios, NP-complete 0-1 problem; existing fractional programming tools (Dinkelbach, scalar quadratic transform) either handle only one ratio or do not yield a tractable subproblem for NCut.
Approach
Generalizes the quadratic transform to multidimensional (matrix) ratios and factorizes x^T W x so that the 0-1 subproblem reduces to a per-row argmax over cluster scores, giving a closed-form iterative update (FPC) with no auxiliary variable updates and MM-based monotone convergence.
Key results
- FPC achieves the lowest NCut objective on all 8 datasets with random initialization (e.g., 0.19% lower than FCD on Office+Caltech10 with K=10).
- FPC initialized from SC attains the best NCut objective on all 8 datasets, strictly improving on the SC initialization on 6.
- FPC runs 73% faster than FINC and about as fast as SC; per-iteration complexity O(KN^2) versus O(N^3) for SC.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use FPC instead of the strongest reported baseline | NCut clustering · Eight datasets in Table 2 | NCut objective: 2.438568 -> 2.431813; 0.499193 -> 0.499193 | Mixed |
| Use FPC instead of the strongest reported baseline | Clustering · ACC across the eight Table 4 datasets | ACC: 0.5000 -> 0.5283; 0.9163 -> 0.9070 | Mixed |
| Refine SC initialization with FPC | SC initialization · Six of eight datasets | NCut objective | Helped |
| Refine SC initialization with FINC | SC initialization · Some datasets | NCut objective | Hurt |
| Use FPC instead of FINC | Clustering runtime · Datasets in Figure 4 | time consumption: 73% faster | Helped |
Surprising findings
- FINC can yield worse NCut objective than its SC initialization, attributed to its heuristic subproblem solving.
Limitations
- Only computational complexity relative to SC is shown; the authors acknowledge limited analysis beyond that.
- Global optimality is only verified on two small datasets via exhaustive search; otherwise only local convergence is guaranteed.
- Indefinite similarity matrices require shifting W by alpha D, which is a modification of the original problem.
Experimental setup
Datasets: Breast Thyroid Office+Caltech10 Splice Rice Landsat USPS Epileptic Balloons Shuttle
Benchmarks: NCut objective on 8 UCI/LIBSVM/transfer-learning datasets ACC/NMI/ARI on 8 datasets image segmentation qualitative comparison runtime comparison
Metrics: NCut objective ACC NMI ARI running time
Baselines: SC FINC FCD
Builds on: Dinkelbach's transform quadratic transform FINC DNC spectral clustering
Closest papers by meaning
- Statistically Optimal $K$-means Clustering via Nonnegative Low-rank Semidefinite Programming (ICLR 2024 · similarity 0.82)
- Equivalence between Graph Spectral Clustering and Column Subset Selection (Student Abstract) (AAAI 2024 · similarity 0.82)
- Competitively Consistent Clustering (ICML 2025 · similarity 0.81)
- The Balanced-Pairwise-Affinities Feature Transform (ICML 2024 · similarity 0.81)
- A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering (ICML 2024 · similarity 0.80)
- Continuous Partitioning for Graph-Based Semi-Supervised Learning (NeurIPS 2024 · similarity 0.80)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.