When we design a machine learning algorithm or an evaluation metric, we usually start with a wishlist of properties. For a clustering algorithm, we might want it to be indifferent to the units of measurement, capable of finding any true underlying pattern, and stable when the data is cleaned up. These sound like baseline requirements rather than luxury features.
Yet, a powerful thread of research reveals that these intuitive desires frequently collide with mathematical reality. We cannot have it all. This direction of study explores axiomatic impossibility theorems—proofs showing that sets of highly desirable properties are mutually exclusive—and investigates how we can intelligently navigate or bypass these fundamental trade-offs.
The Classic Trilemma of Clustering Algorithms
The foundational roadblock in axiomatic analysis was established by Jon Kleinberg in An Impossibility Theorem for Clustering. The work demonstrated that no single clustering algorithm can simultaneously satisfy three simple, intuitive axioms:
- Scale-Invariance: If you uniformly stretch or shrink the data space (for example, converting distances from inches to centimeters), the resulting clusters must not change.
- Richness: The algorithm must be flexible enough that, given some distance matrix, it is capable of outputting any arbitrary partition of the dataset.
- Consistency: If you modify the dataset by shrinking distances between points within the same cluster, or expanding distances between points in different clusters, the algorithm must return the exact same clustering.
To understand why they conflict, imagine an algorithm trying to decide where to split a dataset. To be consistent, making existing clusters "clearer" shouldn't change the output. But to be rich enough to support any possible partition, the algorithm must be highly sensitive to precise distance thresholds. If you scale the space (Scale-Invariance), you destroy absolute thresholds.
As Margareta Ackerman et al. later demonstrated in Towards Property-Based Classification of Clustering Paradigms, this tension is incredibly deep-seated; even if you significantly relax the consistency requirement, the impossibility persists. This forces a fundamental realization: as noted by Charles Bouveyron et al. in Recent developments in clustering algorithms, clustering is inherently task-specific. There is no single "perfect" algorithm because every method must choose which axiom to sacrifice based on the application's goals.
The Trilemma Extends to Evaluation Metrics
This mathematical friction is not confined to the algorithms that generate partitions; it also plagues the metrics we use to evaluate them. Whether measuring the quality of a cluster or the accuracy of a classifier, we run into a parallel trilemma.
In a systematic study of cluster similarity indices, Martijn Gösgens et al. proved in Systematic Analysis of Cluster Similarity Indices: How to Validate Validation Measures that no pair-counting evaluation index can simultaneously satisfy:
- Monotonicity: Improving a clustering decision (making a correct assignment) should always strictly improve the metric score.
- The Distance Property: The metric must behave like a true geometric distance, satisfying properties like the triangle inequality.
- Constant Baseline: The expected score for random guessing must be constant (e.g., zero), regardless of how many clusters there are or how skewed their sizes are.
The authors proved an identical impossibility theorem for classification metrics in Good Classification Measures and How to Find Them.
The intuition behind this conflict lies in the tension between geometry and statistics. Geometric properties require a rigid, symmetric space. However, correcting for random guessing requires shifting the baseline dynamically based on the distribution of the data (such as class imbalance). This dynamic shifting warps the geometric space, breaking the triangle inequality or violating monotonicity. Practitioners are forced to make a deliberate trade-off between geometric interpretability and robustness to class imbalance.
[ Monotonicity ]
/\
/ \
/ \
/ \
/ \
[ Distance Property ]------[ Constant Baseline ]
(Rigid Geometry) (Dynamic Statistical Correction)
This fundamental trade-off echoes across diverse domains in machine learning:
- Saliency Models: Matthias Kuemmerer et al. showed in Consistent Saliency Benchmarking: How One Model Can Win on All Metrics that a single static representation cannot optimize all evaluation metrics simultaneously, as different metrics reward conflicting mathematical properties.
- Formal Argumentation: In Evaluation of Arguments from Support Relations: Axioms and Semantics, Leila Amgoud et al. proved that an evaluation system cannot simultaneously prioritize both the absolute quantity of supporting arguments and the individual quality of those supporters.
- Social Choice and Voting: When comparing preference distributions across elections of different sizes, Jitka Mertlová et al. demonstrated in Distances Between Top-Truncated Elections of Different Sizes that no single distance metric can simultaneously satisfy basic axioms for identity, antagonism, and uniformity.
Pathways to Redemption: Bypassing the Deadlock
If perfection is mathematically barred, how does the field move forward? Researchers have developed several clever strategies to circumvent these impossibility results, turning a theoretical dead-end into a guide for practical design.
1. Redefining and Refining the Axioms
One approach is to argue that the original axioms were slightly misformulated. In Clustering Redemption-Beyond the Impossibility of Kleinberg's Axioms, Vincent Cohen-Addad et al. pointed out that Kleinberg's consistency axiom behaves unnaturally when changes in data spacing alter the "natural" number of clusters. By refining the axiom to accommodate changing cluster counts, they proved that standard algorithms like $k$-means actually satisfy the revised framework.
Similarly, Fabio Strazzeri et al. introduced a refined "Monotonic Consistency" in Morse Theory and an Impossibility Theorem for Graph Clustering., leveraging topological concepts to make axiomatic harmony possible.
2. Shifting the Target of Evaluation
Instead of trying to find a perfect partitioning algorithm, we can shift our focus to evaluating the quality of a given clustering. In Measures of Clustering Quality: A Working Set of Axioms for Clustering, Shai Ben-David et al. proved that a consistent set of axioms for clustering quality measures is mathematically practical. However, this shift introduces a new, clear trade-off: a quality measure that satisfies richness cannot maintain a bias toward specific cluster counts.
3. Restricting the Domain or Fixing Parameters
By narrowing the scope of the problem, uniqueness can emerge from impossibility. Reza Bosagh Zadeh et al. showed in A Uniqueness Theorem for Clustering that if you fix the number of clusters ($k$) and introduce a property called "MST-Coherence," Single-Linkage emerges as the unique algorithm that satisfies the remaining natural axioms.
4. Data-Driven Supervision
Finally, we can bypass axiomatic deadlocks entirely by changing how the problem is framed. In Supervising Unsupervised Learning, Adam Tauman Kalai et al. introduced Meta-Unsupervised Learning (MUL). By using a repository of labeled datasets to "teach" an algorithm how to cluster new, unlabeled data, they transformed a subjective, axiomatically constrained problem into a data-driven, supervised task—letting empirical data dictate the optimal trade-offs.
Key Foundational Work
An Impossibility Theorem for Clustering (2002) — contributed 3 concept elements to this direction.
Measures of Clustering Quality: A Working Set of Axioms for Clustering (2008) — contributed 2 concept elements to this direction.
A discriminative framework for clustering via similarity functions (2008) — contributed 1 concept elements to this direction.