Introduction
Spectral clustering has become a cornerstone technique for uncovering structure in complex datasets. By mapping data points into a lower-dimensional space and then onto the surface of a $d$-dimensional hypersphere, it transforms non-linear relationships into directional ones. However, the subsequent clustering step on the sphere often relies on the von Mises-Fisher (vMF) distribution, which assumes isotropic, "circular" clusters. In practice, spectral embeddings frequently exhibit elongated or "girdle-shaped" noise, causing vMF-based methods to fail.
The Watson Distribution for Spherical Clustering
To address these limitations, this work proposes a generative mixture model based on the Watson distribution. The Watson distribution is uniquely suited for this task because its concentration parameter, $\kappa$, can take negative values. While a positive $\kappa$ models tight clusters around a mean direction (similar to vMF), a negative $\kappa$ allows the model to capture "girdle" distributions where data is spread thinly across the hypersphere.
As shown in the figure above, the vMF model (a) struggles with the elongated topology of the "two-moons" embedding, incorrectly merging or misclassifying points. In contrast, the Watson-based EM algorithm (b) successfully identifies the two distinct bands by leveraging the flexibility of negative concentration parameters.
Robust Parameter Estimation
A significant challenge in using Watson distributions is the complexity of parameter estimation. The normalization constant involves the Kummer function, making the M-step in an Expectation-Maximization (EM) framework computationally demanding. The authors introduce a fast numerical approximation for $\kappa$ using continued fractions, enabling efficient scaling to real-world datasets. Furthermore, the paper establishes a principled link between the embedding dimension and cluster concentration, suggesting that the optimal dimension is one that maximizes the "tightness" of the resulting model.
Experimental Evaluation
The model was evaluated against the state-of-the-art "soft-moVMF" algorithm across several benchmarks, including USPS handwritten digits, 20 Newsgroups, and Yahoo20 news articles.
Performance on Noisy Embeddings
The Watson mixture model demonstrates remarkable stability as the embedding dimension increases. In high-dimensional spaces, clusters naturally tend to become more "thin" or spread out. While vMF performance often degrades under these conditions, the Watson model adapts.
As illustrated in the USPS digit experiments, the Watson model (blue line) consistently maintains or improves its Mutual Information scores compared to vMF (red dashed line), particularly in the more challenging subsets like {6, 7, 8, 9}.
Text Clustering Results
On natural language datasets like 20 Newsgroups and Yahoo20, the Watson model achieved superior Mutual Information scores. This indicates a better capture of the underlying thematic categories, which often manifest as directional clusters with varying degrees of concentration in the spectral space.
Conclusion
By incorporating the Watson distribution into a generative mixture model, this research provides a more flexible and robust framework for spherical clustering. The ability to model both concentrated and girdle-shaped data allows for better handling of the noise inherent in spectral embeddings. Future work will focus on further optimizing the M-step to handle even higher-dimensional problems where iterative numerical methods for the mean vector $\mu$ may become a bottleneck.
Summary updated