Introduction
Multidimensional Scaling (MDS) is a fundamental technique in data science for visualizing high-dimensional data by preserving pairwise distances in a lower-dimensional embedding. Weighted MDS (WMDS) extends this by assigning importance weights to specific pairs, allowing for more nuanced visualizations. However, optimizing the non-convex "Stress" objective function presents a significant challenge.
Traditional optimization methods like Stress Majorization (SMACOF) offer stability but suffer from $O(n^3)$ complexity due to global matrix operations, making them impractical for large datasets. Conversely, Newton-based methods like the Kamada-Kawai algorithm are faster per iteration but lack convergence guarantees, often failing if initial positions are suboptimal. This paper introduces StableMDS, a gradient descent-based approach that achieves the stability of SMACOF with significantly higher performance and scalability.
Methodology
The core innovation of StableMDS lies in replacing global matrix updates with independent point-wise updates. The authors theoretically bound the Hessian of the stress function to derive a "safe" step size ($\eta_i$). By applying the Descent Lemma, they prove that this step size guarantees non-increasing loss and convergence. This approach reduces per-iteration complexity to $O(n^2p)$.
To further scale the method, the authors propose FastMDS, a stochastic variant. FastMDS approximates the gradient by sampling a random subset of $b$ points for each update, reducing complexity to $O(nbp)$. Both algorithms were implemented using Numba, a Just-In-Time compiler for Python, to ensure a fair comparison against high-performance C++ and FORTRAN baselines.
Experimental Evaluation
The methods were evaluated across diverse tasks, including dimensionality reduction on the MNIST, COIL2000, and Shuttle datasets (sampling 3,000 points from each), and topological visualization of synthetic manifolds like the SwissRoll and Spheres.
Results and Discussion
Experimental results confirm that StableMDS significantly outperforms traditional Stress Majorization in terms of speed while maintaining identical stability. On the "Spheres" dataset, StableMDS reached convergence in 18.71 seconds, compared to 59.37 seconds for SMACOF. FastMDS (10% sampling) further reduced this time to 8.43 seconds while preserving the essential topological structure of the data.
In graph drawing tasks, such as the 3elt dataset, StableMDS was approximately 6.6x faster than SMACOF. FastMDS (10%) achieved a staggering 30x speedup, producing high-quality layouts in roughly 11 seconds versus 352 seconds for the baseline. The convergence plots demonstrate that StableMDS maintains a strictly non-increasing loss, validating the theoretical safety of the derived step size and mirroring the stability of SMACOF but with a much steeper descent.
Conclusion
StableMDS bridges the gap between slow, stable majorization methods and fast, unstable second-order methods. By leveraging Hessian bounding for safe gradient descent, it provides a robust and scalable solution for large-scale Weighted MDS. Future work includes extending these stability guarantees to Non-Metric MDS and exploring adaptive step-size strategies to further enhance optimization efficiency.
Summary updated