Research map / Learning theory and algorithms / Clustering
Incremental Nyström-based Multiple Kernel 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 INMKC, a parameter-free incremental multiple kernel clustering method that approximates each base kernel with leverage-score Nyström sampling and fuses views incrementally via a consensus cluster structure, avoiding storage of past kernels.
Problem
Multiple kernel clustering on large-scale datasets is costly: uniform Nyström sampling yields large approximation errors on unbalanced data, shared landmarks reduce kernel diversity, and base kernels arriving over time force re-fusion of all historical kernels.
Approach
Use recursive RLS (ridge leverage score) Nyström sampling with different landmarks per view, then jointly factorize each approximate kernel and align it to a consensus cluster structure updated incrementally from the previous consensus, so only the latest kernel and consensus matrix are stored.
Key results
- INMKC outperforms the second-best method by 1.83%, 1.73%, 3.21%, 2.71%, 6.15%, 5.82%, 1.22% and 0.24% in ACC across the eight datasets (reported in text).
- On YTF10 INMKC reaches 89.01% ACC versus 82.86% for CAMVC, and outperforms SMKKM by 20.57% on YTF100-related comparison as stated.
- Leverage score sampling beats uniform sampling for INMKC on all eight datasets, e.g. Winnipeg 60.31 vs 54.28 ACC and YTF10 89.01 vs 77.58 ACC.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use leverage score sampling instead of uniform sampling (ablation) | INMKC · CUB | ACC: 78.83 -> 81.33 | Helped |
| Use leverage score sampling instead of uniform sampling (ablation) | INMKC · Fashion | ACC: 77.08 -> 77.09 | No clear effect |
| Use leverage score sampling instead of uniform sampling (ablation) | INMKC · ALOI | ACC: 73.17 -> 73.69 | Helped |
| Use leverage score sampling instead of uniform sampling (ablation) | INMKC · NMNIST | ACC: 57.15 -> 65.73 | Helped |
| Use leverage score sampling instead of uniform sampling (ablation) | INMKC · PFold | ACC: 36.89 -> 37.75 | Helped |
| Use leverage score sampling instead of uniform sampling (ablation) | INMKC · YTF10 | ACC: 77.58 -> 89.01 | Helped |
| Use leverage score sampling instead of uniform sampling (ablation) | INMKC · YTF100 | ACC: 68.72 -> 69.45 | Helped |
| Use leverage score sampling instead of uniform sampling (ablation) | INMKC · Winnipeg | ACC: 54.28 -> 60.31 | Helped |
| Use leverage score sampling instead of uniform sampling (ablation) | CMVC · Eight benchmark datasets | ACC | Mixed |
| Add incremental learning (ablation) | INMKC · CUB | ACC: 53.67 -> 81.33 | Helped |
| Add incremental learning (ablation) | INMKC · PFold | ACC: 35.01 -> 37.75 | Helped |
| Add incremental learning (ablation) | INMKC · Fashion | ACC: 49.95 -> 77.09 | Helped |
Surprising findings
- Incremental learning NMKC variant without it reaches 63.34 ACC on Winnipeg, higher than INMKC's 60.31, which the authors acknowledge.
Limitations
- Baselines and INMKC are evaluated with a fixed landmark count s=300 and the algorithm relies on an assumption that rank of approximate kernel equals k.
- Incremental variant slightly underperforms the non-incremental NMKC on Winnipeg in ACC.
Experimental setup
Datasets: CUB PFold Fashion ALOI YTF10 NMNIST YTF100 Winnipeg
Benchmarks: CUB PFold Fashion ALOI YTF10 NMNIST YTF100 Winnipeg
Metrics: ACC NMI Purity running time
Baselines: LMVSC OMSC FDAGF CAMVC SMKKM OLICAG IMSC SCGL CMVC
Builds on: recursive RLS-Nystrom SimpleMKKM CMVC
Closest papers by meaning
- Stability and Generalization of Kernel Clustering: from Single Kernel to Multiple Kernel (NeurIPS 2022 · similarity 0.91)
- Hierarchical Multiple Kernel Clustering (AAAI 2021 · similarity 0.90)
- COKE: Core Kernel for More Efficient Approximation of Kernel Weights in Multiple Kernel Clustering (ICML 2025 · similarity 0.90)
- Consistency of Multiple Kernel Clustering (ICML 2023 · similarity 0.90)
- Recursive Sampling for the Nystrom Method (NeurIPS 2017 · similarity 0.89)
- Scalable Multiple Kernel Clustering: Learning Clustering Structure from Expectation (ICML 2024 · similarity 0.88)
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.