How smoothing the affinity matrix affects neighborhood preservation in t-SNE

Technical Summary: How Smoothing the Affinity Matrix Affects Neighborhood Preservation in t-SNE

Problem Statement
t-Distributed Stochastic Neighbor Embedding (t-SNE) is a widely used dimensionality reduction technique known for preserving local neighborhood structures. However, despite its popularity, t-SNE embeddings often exhibit low absolute neighborhood preservation scores, and errors are frequently unevenly distributed. While much research has focused on improving t-SNE's global structure preservation or optimizing the optimization procedure (e.g., initialization, learning rates), there has been limited explicit investigation into whether the local structure preservation of t-SNE can be improved by modifying the high-dimensional affinity matrix itself.

The authors observe that in standard t-SNE, the conditional probability distributions (affinity rows) are often highly "sharp," meaning a few nearest neighbors dominate the probability mass. Furthermore, the sharpness of these distributions varies across data points. The paper investigates how the "sharpness" of these affinity distributions influences neighborhood preservation at different scales and whether modifying this sharpness can yield better embeddings than standard t-SNE or alternative multiscale methods.

Methodology
The study introduces a controlled perturbation to the standard t-SNE affinity construction: a row-wise power transform applied to the conditional probabilities $p_{j|i}$.

1. The Transform: For a given point $i$, the conditional probabilities are transformed using a parameter $\gamma \geq 0$:
   $$\tilde{p}_{j|i} = \frac{p_{j|i}^\gamma}{\sum_{m \neq i} p_{m|i}^\gamma}$$

   • $\gamma = 1$: Recovers standard t-SNE.
   • $\gamma < 1$ (Smoothing): Reduces large probabilities relative to smaller ones, redistributing mass to lower-probability neighbors.
   • $\gamma > 1$ (Sharpening): Concentrates mass further on the largest probabilities.
   • $\gamma = 0$: Results in a uniform distribution over neighbors (discarding rank order).

2. Theoretical Characterization:

   • The authors prove that this power transform is mathematically equivalent to rescaling the Gaussian bandwidth ($\sigma_i$) of the original kernel. Specifically, the new effective bandwidth becomes $\tilde{\sigma}_i = \sigma_i / \sqrt{\gamma}$.
   • Crucially, unlike changing the global perplexity parameter $\rho$ (which forces every point to have the same effective number of neighbors), applying a fixed $\gamma$ results in point-dependent effective perplexities. The effective perplexity varies based on the original distribution's shape for each specific point.

3. Experimental Setup:

   • The method was implemented within openTSNE and evaluated on MNIST, UCI Adult, and Mouse Cortex datasets.
   • The primary metric for evaluation was Neighborhood Overlap at $k$ (NO@k), measuring the fraction of high-dimensional $k$-nearest neighbors preserved in the embedding.
   • Comparisons were made against standard t-SNE, varying global perplexity, and alternative affinity constructions (Multiscale, Fixed Sigma, Uniform, and tt-SNE).

Key Results
The experiments reveal a clear scale-dependent trade-off governed by $\gamma$:

• Sharpening ($\gamma > 1$): Improves the preservation of the very nearest neighbors (small $k$). However, performance degrades rapidly as $k$ increases.
• Smoothing ($\gamma < 1$): Improves the preservation of broader local neighborhoods (mid-range $k$) and global structure.
  • Specifically, smoothing with $\gamma \approx 0.7$ outperformed standard t-SNE and multiscale methods in the "mid-local" range ($k \approx 25–90$).
  • Smoothing also improved global structure preservation (measured by Spearman rank correlation of distances), particularly at higher perplexities.
• Comparison to Global Perplexity Tuning: Simply increasing the global perplexity $\rho$ in standard t-SNE does not replicate the benefits of smoothing. Smoothing creates a heterogeneous distribution of effective neighborhood sizes across points, whereas increasing $\rho$ uniformly shifts the scale for all points. Consequently, smoothed t-SNE achieved higher NO@k scores at specific mid-range $k$ values than standard t-SNE with matched or higher perplexities.
• Comparison to Other Methods: In the mid-local range, the smoothed variant ($\gamma=0.7$) outperformed Multiscale Mixture and Multiscale methods, which incorporate multiple bandwidth scales. Sharpened variants ($\gamma=1.5$) dominated at very small $k$, while uniform distributions ($\gamma=0$) dominated at very large $k$.

Significance and Claims
The paper claims that affinity sharpness is a meaningful and previously underexplored axis of t-SNE behavior. The primary contributions are:

1. Decoupling Neighborhood Size and Distribution: The study demonstrates that the number of neighbors (controlled by perplexity) and the distribution of probability mass among them (controlled by $\gamma$) are distinct factors.
2. Lightweight Tuning: The parameter $\gamma$ offers practitioners a simple, lightweight mechanism to shift the focus of the embedding:
   • Use sharper affinities ($\gamma > 1$) if the goal is high fidelity for the very nearest neighbors.
   • Use smoother affinities ($\gamma < 1$) to improve the preservation of broader local structures and global topology.
3. Limitations: The authors modestly note that while the improvements are consistent, they are modest in absolute terms. The study focuses on a single quality measure (NO@k), and the practical translation of these metric improvements to specific domain insights remains an open question. Additionally, the optimal hyperparameters ($\rho, \gamma$) for specific $k$ values were not exhaustively optimized in this work.

In conclusion, the paper argues that standard t-SNE may concentrate probability mass too heavily on the first few neighbors, limiting its ability to preserve broader local structures. By smoothing the affinity matrix, one can redistribute this mass to mid-ranked neighbors, thereby enhancing the reliability of cluster substructures and global layout without altering the optimization procedure or computational scalability.