Abstract
Similarity graph construction is a fundamental step in many machine learning algorithms, yet traditional methods like $k$-nearest neighbors and Gaussian kernels are highly sensitive to hyperparameter selection. This paper introduces Simplex Sparse Representation (SSR), a parameter-free model that represents each data point as a sparse linear combination of others under simplex constraints. By leveraging non-negativity and sum-to-one constraints, SSR automatically identifies optimal local neighborhoods, ensuring robustness to noise and scale variations. Experimental results across ten diverse datasets demonstrate that SSR consistently outperforms existing methods in clustering accuracy and graph quality.
Introduction
Many unsupervised and semi-supervised learning techniques, including spectral clustering and manifold learning, rely on an underlying similarity graph to capture the manifold structure of data. The performance of these methods is often bottlenecked by the quality of the graph construction. Traditional approaches require manual tuning of parameters such as the number of neighbors ($k$) or kernel width ($\sigma$), which is challenging in the presence of multi-scale data or outliers. We propose SSR to address these limitations by formulating similarity as a self-adjusting sparse reconstruction problem.
Methodology
The Simplex Sparse Representation (SSR) Model
The core of our approach is to represent each data point $x_i$ as a linear combination of the remaining points $X_{-i}$. Unlike standard sparse coding, we impose a simplex constraint on the reconstruction weights $\alpha_i$:
- Non-negativity: $\alpha_i \ge 0$
- Sum-to-one: $\mathbf{1}^T \alpha_i = 1$
These constraints offer several theoretical advantages. First, the geometry of the simplex naturally induces sparsity without requiring an explicit $\ell_1$ penalty parameter. Second, the sum-to-one constraint provides shift invariance, ensuring that the similarity measure is robust to global translations of the dataset.
Optimization via Accelerated Projected Gradient
To solve the SSR objective efficiently, we employ an Accelerated Projected Gradient (APG) algorithm. The projection onto the simplex is handled via a Lagrangian formulation and a Newton root-finding method, achieving quadratic convergence ($O(t^2)$). This allows the model to scale to high-dimensional data, typically converging in fewer than 30 iterations.
Experimental Evaluation
We evaluated SSR on a diverse set of benchmarks, including face recognition datasets (AR, AT&T, JAFFE, PIE, UMIST), handwritten digits (MNIST), and UCI datasets (Abalone, Ecoli, Scale). SSR was compared against $k$-means, Non-negative Matrix Factorization (NMF), Normalized Cut (NCut), and Self-Tuning Spectral Clustering (STSC).
Results and Discussion
SSR demonstrated superior performance across all metrics, including Accuracy, Normalized Mutual Information (NMI), and Purity. Notably, on the JAFFE face dataset, SSR achieved a clustering accuracy of 90.2%, a significant improvement over STSC's 81.3%.
The visualization of similarity coefficients confirms that SSR produces "sharper" graphs than competing methods. By effectively ignoring outliers and focusing on the most representative neighbors, SSR provides a more reliable foundation for subsequent clustering steps.
Conclusion
Simplex Sparse Representation offers a robust, parameter-free alternative for similarity graph construction. By integrating sparsity and shift invariance directly into the optimization constraints, SSR eliminates the "guessing game" of hyperparameter tuning while delivering state-of-the-art clustering performance. Future work will explore the application of SSR to semi-supervised learning and the incorporation of group-level structural sparsity.
Summary updated