Is Marina Meila's work "The Uniqueness of a Good Optimum for K-Means" a general result applicable to other clustering algorithms as well?

Question

In this paper, a bound on the “error subspace” projection is established, which is then used to show that any two clusterings with small distortion are close. Which immediately follows that, if a good clustering, $C$, is discovered for a given dataset (say manually, or by whatever ssuitable means), then another clustering, $C_1$, is going to be close to the optimal clustering if it minimizes the distortion between the two clusterings.

The paper was presented as optimality for k-means. But I could not find any specific detail that stops it from being applicable to general clustering algorithms. That's why I want to confirm here by asking whether this method of determining existence of an optimal algorithmic clustering applicable to other algorithms beyond k-means.

---

Meilă, Marina. "The uniqueness of a good optimum for k-means." In Proceedings of the 23rd international conference on Machine learning, pp. 625-632. ACM, 2006.

Answer 1

The distortion function they use is highly specific to k-means.

So in essence: if there exist a "good k-means clustering", then most k-means results will be close. If no good result exists (and this is the common case) then they will be much more different.

The takeaway is to try k-means several times. If the results are very different, then none of them is good.

While I do think similar results can exist for other clusterings, it doesn't directly apply to others. In some cases like DBSCAN, the result is (except for some corner cases with identical distances) exactly defined. There is no random initialization involved, and no optimization function to use as "distortion".