Research map / Graph learning / Graph algorithms and clustering
Fine-Grained Bipartite Concept Factorization for Clustering
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.
Proposes Figer-CF, a concept factorization method that fuses cross-order random-walk neighbor graphs and enforces bipartite graph partitioning structure for clustering, with convergence guarantees and experiments on four image datasets.
Problem
Concept factorization for clustering uses only first-order neighbor information and does not explicitly enforce cluster structure in the factor matrices.
Approach
Fuses multi-order (up to A=3) symmetric random-walk probability matrices into a PSD neighbor graph, and learns score and coefficient factors jointly with a bipartite graph Laplacian constraint so that the coefficient matrix has explicit group structure.
Key results
- Figer-CF ranks in the top three in all 60 cases and first in 47 cases across four datasets and subset sizes.
- On Semeion and COIL20 it reports the best overall ACC/NMI/PUR (e.g., 0.635 ACC, 0.626 NMI on Semeion overall vs 0.615 for GLS-MKNMF).
- Higher-order neighbor graphs (orders 1 to 3) improve clustering performance on COIL20 and Semeion; A=3 is recommended.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Figer-CF instead of the strongest listed baseline | Clustering methods · Jaffe 10 Classes (Overall) | ACC: 0.953 -> 0.977 | Helped |
| Use Figer-CF instead of the strongest listed baseline | Clustering methods · PIX 10 Classes (Overall) | ACC: 0.920 -> 0.940 | Helped |
| Use Figer-CF instead of the strongest listed baseline | Clustering methods · Semeion 10 Classes (Overall) | ACC: 0.654 -> 0.635 | Hurt |
| Use Figer-CF instead of the strongest listed baseline | Clustering methods · COIL20 20 Classes (Overall) | ACC: 0.690 -> 0.652 | Hurt |
| Use Figer-CF instead of the strongest listed baseline | Clustering methods · Jaffe 10 Classes (Overall) | NMI: 0.896 -> 0.970 | Helped |
| Use Figer-CF instead of the strongest listed baseline | Clustering methods · PIX 10 Classes (Overall) | NMI: 0.892 -> 0.950 | Helped |
| Use Figer-CF instead of the strongest listed baseline | Clustering methods · Semeion 10 Classes (Overall) | NMI: 0.553 -> 0.626 | Helped |
| Use Figer-CF instead of the strongest listed baseline | Clustering methods · COIL20 20 Classes (Overall) | NMI: 0.762 -> 0.760 | Hurt |
| Use Figer-CF instead of the strongest listed baseline | Clustering methods · Jaffe 10 Classes (Overall) | PUR: 0.953 -> 0.977 | Helped |
| Use Figer-CF instead of the strongest listed baseline | Clustering methods · PIX 10 Classes (Overall) | PUR: 0.920 -> 0.940 | Helped |
| Use Figer-CF instead of the strongest listed baseline | Clustering methods · Semeion 10 Classes (Overall) | PUR: 0.655 -> 0.682 | Helped |
| Use Figer-CF instead of the strongest listed baseline | Clustering methods · COIL20 20 Classes (Overall) | PUR: 0.690 -> 0.665 | Hurt |
Surprising findings
- Authors report the method is rather insensitive to balancing parameters over a broad range.
Limitations
- Experiments limited to four small image datasets with subset-based evaluation.
- Only orders up to A=3 explored; higher orders give diminishing gains and the choice of A is heuristic.
- Requires adding a scaled identity (tau) to ensure PSD, a heuristic shift of the neighbor graph.
Experimental setup
Datasets: Jaffe PIX Semeion COIL20
Benchmarks: Jaffe PIX Semeion COIL20
Metrics: ACC NMI PUR
Baselines: WNMF ONMF CNMF KNMF RMNMF OPMC MKKM-SR EWNMF GLS-MKNMF
Builds on: Convex-NMF / concept factorization spectral clustering-based subspace clustering Ky-Fan theorem
Closest papers by meaning
- Online Sparsification of Bipartite-Like Clusters in Graphs (ICML 2025 · similarity 0.86)
- Hierarchical Overlapping Clustering on Graphs: Cost Function, Algorithm and Scalability (ICML 2025 · similarity 0.84)
- Approximately Pareto-optimal Solutions for Bi-Objective k-Clustering (NeurIPS 2024 · similarity 0.84)
- Statistically Optimal $K$-means Clustering via Nonnegative Low-rank Semidefinite Programming (ICLR 2024 · similarity 0.84)
- Learning-Augmented Hierarchical Clustering (ICML 2025 · similarity 0.83)
- A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering (ICML 2024 · similarity 0.83)
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.