The Complexity of k-Means Clustering when Little is Known

Robert Ganian, Thekla Hamm, Viktoriia Korchemna, Karolina Okrasa, Kirill SimonovICML 2022 · OpenReview

Introduction

$k$-means clustering is a foundational task in machine learning, yet it is notoriously NP-hard. In many real-world applications, such as recommender systems (e.g., the Netflix Prize), the data matrix is extremely sparse, often with 99% of the entries missing. This paper provides a theoretical breakthrough for $k$-means clustering on such highly incomplete datasets. By applying the "parameterized complexity" framework to the structure of the known data points, the authors develop the first fixed-parameter tractable (FPT) algorithms for clustering sparse data, even when the number of clusters $k$ is very large.

The Challenge of Extreme Sparsity

Previous theoretical work on "Clustering with Missing Entries" (MCME) primarily focused on the "nearly complete" case, where only a few entries are missing. This paper flips the script, asking a critical question: Can we achieve computational tractability when we know very little?

Instead of trying to "cover" or impute the missing entries—which is computationally prohibitive when there are many—the authors look for algorithms whose running time is efficient (polynomial) relative to the size of the data, provided that the structure of the known entries remains simple according to specific graph-theoretic measures.

Graph-Theoretic Representations

To analyze the structure of the known data, the authors represent the "mask" $W$ (a binary matrix where 1 indicates a known entry and 0 indicates a missing one) as different types of graphs:

  1. Incidence Graph ($G_I$): A bipartite graph with vertices for every row and every column. An edge exists between row $a$ and column $b$ if the entry $(a, b)$ is known.
  2. Primal Graph ($G_P$): A graph where vertices represent rows, and an edge connects two rows if they share at least one known coordinate.
Example of a mask W alongside its incidence graph and primal graph.

Tractability through Structural Parameters

The core of the authors' approach involves using treewidth, a measure of how "tree-like" a graph is. If the mask's graph representation has low treewidth, the clustering problem can be broken down into smaller, manageable sub-problems using dynamic programming.

However, for real-valued data, treewidth alone is sometimes insufficient to guarantee tractability without solving long-standing open problems in computer science. To bypass this "dimension barrier," the authors introduce the local feedback edge number (lfen). This parameter measures how many edges need to be removed locally to make the graph a forest.

Graph and spanning tree used for calculating local feedback edge number.

By identifying orthogonal structural parameters like Primal Treewidth and lfen, the authors ensure that if a dataset is structurally complex according to one measure, it might still be solvable according to another.

Key Results

The paper establishes three main tractability results for Means Clustering with Missing Entries (MCME). Crucially, these algorithms operate in linear-time relative to the number of rows and columns, suggesting potential scalability to massive, sparse datasets:

  • Result 1 (Bounded Domains): For data coming from a bounded domain (e.g., integer ratings from 1 to 5), the problem is FPT when parameterized by the incidence treewidth of the mask, regardless of the number of clusters $k$.
  • Result 2 (Real-Valued Data): For real-valued data, the problem is FPT when parameterized by the primal treewidth of the mask.
  • Result 3 (Real-Valued Data): For real-valued data, the problem is also FPT when parameterized by the local feedback edge number (lfen) of the incidence graph.

Limitations and Future Directions

While these algorithms are theoretically efficient (FPT), the constant factors involved in treewidth-based dynamic programming can be extremely large. Currently, these serve as "existence proofs" of tractability rather than ready-to-use production code.

A major remaining theoretical challenge is the "Real-Valued Gap": determining whether real-valued MCME can be solved using incidence treewidth alone, without falling back on more restrictive parameters like primal treewidth. In practice, the authors suggest that these structural parameters could eventually be used to develop better heuristics or to guide existing clustering methods on highly sparse data.

Summary updated

BibTeX
@inproceedings{ganian2022complexity,
  author = {Robert Ganian and Thekla Hamm and Viktoriia Korchemna and Karolina Okrasa and Kirill Simonov},
  title = {{The Complexity of k-Means Clustering when Little is Known}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
  url = {https://openreview.net/forum?id=t9PPiYcUukv},
}
Figure