The t-SNE Pairwise Similarity Model

From Cell Distances to Pairwise Similarities

t-SNE begins by replacing distances among cells with probabilities that express relative neighborhood strength. A cell should assign more probability mass to a nearby cell than to a distant one, but those assignments are made relative to the focal cell’s local distance scale. Consequently, the same distance can receive different conditional probabilities from different cells.

In single-cell analysis, the distances are usually calculated in a chosen feature representation, often a set of principal-component scores, rather than directly from the full matrix of gene counts. The pairwise similarity model described here takes those distances and turns them into a probability distribution. It does not itself establish that two cells share a cell type or biological state.

Definition: Let $x_i$ denote the high-dimensional representation of cell $i$, for $i=1,\ldots,n$, and let $d_{ij}^2=\|x_i-x_j\|^2$ be the squared distance between cells $i$ and $j$. For each focal cell $i$, t-SNE assigns a positive bandwidth $\sigma_i$ and defines, for $j\ne i$, $$ p_{j\mid i}= \frac{\exp\!\left(-d_{ij}^2/(2\sigma_i^2)\right)} {\sum_{k\ne i}\exp\!\left(-d_{ik}^2/(2\sigma_i^2)\right)}. $$ The self-similarity is set to $p_{i\mid i}=0$. The values $p_{j\mid i}$ form a conditional probability distribution over all cells other than $i$.

The Gaussian kernel in the numerator gives a positive weight to each other cell. A smaller squared distance gives a larger weight, all else equal. The denominator normalizes the weights for the particular focal cell $i$, so its conditional probabilities sum to one. The bandwidth $\sigma_i$ controls how quickly weights decline with distance: a small bandwidth concentrates mass on the closest cells, while a larger bandwidth makes the distribution less concentrated. Importantly, each cell can have its own bandwidth.

The inputs and basic conditions should be checked before interpreting these quantities. There must be at least two cells; distances must be finite and nonnegative; and each $\sigma_i$ must be positive. Distances are ordinarily symmetric, so $d_{ij}=d_{ji}$, but the conditional probabilities need not be symmetric because the normalizing denominators and bandwidths can differ by focal cell.

Worked Example: Conditional Similarities From One Cell

Suppose four hypothetical cells have squared distances from cell A of $d_{AB}^2=0.5$, $d_{AC}^2=2$, and $d_{AD}^2=8$, measured in squared units of the chosen representation. Let $\sigma_A=1$. Calculate the conditional probabilities assigned by A.

The unnormalized Gaussian weights are $$ w_{AB}=e^{-0.5/(2\cdot1^2)}=e^{-0.25}\approx0.7788008,\quad w_{AC}=e^{-2/(2\cdot1^2)}=e^{-1}\approx0.3678794,\quad w_{AD}=e^{-8/(2\cdot1^2)}=e^{-4}\approx0.01831564. $$ Their sum is $Z_A\approx1.1649959$. Dividing each unrounded weight by that sum gives $$ p_{B\mid A}\approx0.6685,\qquad p_{C\mid A}\approx0.3158,\qquad p_{D\mid A}\approx0.01572. $$

The probabilities sum to one before rounding. Cell B receives the largest share because it is closest to A, while the distant cell D receives very little. These are conditional shares of A’s neighborhood mass; they are not probabilities that B, C, or D belongs to a biological class.

Why Conditional Similarities Are Symmetrized

The conditional distributions describe neighborhoods from each cell’s point of view. To obtain a single pairwise similarity for use by the embedding objective, t-SNE combines the two directional conditional probabilities for each pair. Under the standard t-SNE convention, the symmetric joint similarities are

p_{ij}=\frac{p_{j\mid i}+p_{i\mid j}}{2n},\qquad p_{ii}=0.

Here $p_{ij}=p_{ji}$. The factor $2n$ matters: the matrix is indexed over ordered pairs $(i,j)$, so both $p_{ij}$ and $p_{ji}$ occur in its total. The construction gives a normalized joint distribution over distinct ordered cell pairs.

Key result: If every conditional distribution is normalized, then the symmetric joint similarities satisfy $\sum_i\sum_j p_{ij}=1$. For any two distinct cells, a large $p_{ij}$ indicates that they receive substantial combined neighborhood mass from their two conditional distributions.

The normalization follows directly from the definition. Summing over all ordered pairs and using $p_{ii}=0$,

\sum_i\sum_j p_{ij} =\frac{1}{2n}\left(\sum_i\sum_{j\ne i}p_{j\mid i} +\sum_i\sum_{j\ne i}p_{i\mid j}\right) =\frac{1}{2n}(n+n)=1.

In the first double sum, the conditional probabilities for each fixed $i$ add to one, giving $n$. In the second, for each fixed $j$, the probabilities $p_{i\mid j}$ also add to one, giving another $n$. Thus the two directions contribute equally to the total mass. This argument depends on including all cells in the sum and setting self-probabilities to zero.

Worked Example: A Pair Can Have Unequal Directional Similarities

Consider three hypothetical cells on a line, with coordinates $x_A=0$, $x_B=1$, and $x_C=2$. Their squared distances are $d_{AB}^2=1$, $d_{AC}^2=4$, and $d_{BC}^2=1$. Let $\sigma_A=1$, $\sigma_B=2$, and $\sigma_C=1$. Calculate the directional probabilities needed to find the symmetric similarities.

For A, the weights to B and C are $e^{-1/2}\approx0.6065307$ and $e^{-2}\approx0.1353353$. Therefore, $$ p_{B\mid A}=\frac{e^{-1/2}}{e^{-1/2}+e^{-2}}\approx0.8176,\qquad p_{C\mid A}\approx0.1824. $$ For B, both other cells are at squared distance 1, and $\sigma_B^2=4$. The two weights are both $e^{-1/8}$, so $p_{A\mid B}=p_{C\mid B}=0.5000$. For C, the distances mirror those from A, giving $p_{A\mid C}\approx0.1824$ and $p_{B\mid C}\approx0.8176$.

Since $n=3$, the symmetric similarities are $$ p_{AB}=\frac{0.8176+0.5000}{6}\approx0.2196,\qquad p_{AC}=\frac{0.1824+0.1824}{6}\approx0.06081,\qquad p_{BC}=\frac{0.5000+0.8176}{6}\approx0.2196. $$ These displayed results are rounded; the calculations use the unrounded conditional probabilities. The off-diagonal entries sum to approximately $0.5000$ when counted once per unordered pair. Counting both matrix entries for each pair gives approximately 1, as required. Although A and B are equally far apart as B and C, their pairwise similarities also reflect each cell’s local conditional distribution.

How the Bandwidth Changes Probability Mass

The bandwidth is not a cosmetic parameter. To see its effect while holding distances fixed, consider one focal cell with three other cells at squared distances 1, 4, and 16. With $\sigma_i^2=1$, the weights are $e^{-0.5}$, $e^{-2}$, and $e^{-8}$. The nearest cell receives conditional probability approximately $0.8172$. With $\sigma_i^2=4$, the weights become $e^{-0.125}$, $e^{-0.5}$, and $e^{-2}$, and the nearest cell’s conditional probability is approximately $0.5433$. The farthest cell still has the least weight, but the broader kernel distributes more mass to the other cells.

In practice, t-SNE uses cell-specific bandwidths rather than requiring a single bandwidth for all cells. This adaptation is useful when the density of sampled cells varies across the high-dimensional space: a bandwidth can be narrower in a dense region and broader in a sparse one. The resulting $p_{j\mid i}$ values are therefore relative neighborhood weights, not a direct encoding of raw distance alone.

Symmetrization also changes how a pair is represented. A pair receives mass from both directions, so it can have appreciable $p_{ij}$ if either cell assigns substantial conditional mass to the other. The formula averages the two conditional contributions after scaling by $n$; it does not simply declare a pair similar when it is among the nearest neighbors of either cell. This distinction is one reason to inspect the actual normalized similarities rather than infer them from a distance ranking alone.

Worked Example: Comparing Narrow and Broad Kernels

Use the squared distances 1, 4, and 16 from a hypothetical focal cell. First take $\sigma_i^2=1$. The weights are approximately $0.6065307$, $0.1353353$, and $0.00033546$, with sum $0.7422014$. The nearest cell’s conditional probability is therefore $0.6065307/0.7422014\approx0.8172$.

Now take $\sigma_i^2=4$. The exponent is $-d^2/8$, so the weights are approximately $0.8824969$, $0.6065307$, and $0.1353353$, with sum $1.6243629$. The nearest cell’s conditional probability becomes $0.8824969/1.6243629\approx0.5433$. The nearest cell remains the highest-weight neighbor, but receives a smaller fraction of the total mass because the broader kernel makes the other cells relatively more influential.

Both calculations satisfy the model assumptions: all distances are finite and nonnegative, the bandwidth is positive, and the three weights are normalized over cells other than the focal cell. The comparison isolates the bandwidth effect; it does not imply that increasing the bandwidth changes the distances themselves.

Diagnostics, Alternatives, and Limitations

Several checks can catch errors before these similarities are used downstream. For each cell $i$, verify that $p_{j\mid i}\ge0$, $p_{i\mid i}=0$, and $\sum_{j\ne i}p_{j\mid i}=1$, up to numerical rounding. For the joint matrix, check $p_{ij}=p_{ji}$, $p_{ii}=0$, and $\sum_i\sum_jp_{ij}=1$. A matrix that sums to one when only its upper triangle is added is using a different counting convention or has been normalized incorrectly; in the convention here, the full ordered-pair matrix sums to one.

A common numerical issue is underflow: if a bandwidth is extremely small relative to the distances, many exponential weights may be numerically represented as zero. A stable calculation subtracts the largest exponent before exponentiating, which leaves the normalized probabilities unchanged. If every computed weight is zero, the calculation has failed numerically and should not be treated as a valid conditional distribution. Duplicate cells or tied distances do not by themselves violate the model, but they can produce equal weights and should be handled consistently.

One alternative is to use a single global bandwidth for every cell. That still yields normalized conditional probabilities, but it does not adapt to local density differences. Another is to examine distances directly without converting them into probabilities; distances retain their metric units, whereas the $p$ values are dimensionless normalized affinities. Neither is interchangeable with the t-SNE pairwise similarity model. The probability construction also has limitations: its output depends on the chosen representation, distance metric, and bandwidths, and it summarizes local relationships rather than guaranteeing preservation of all global geometry.

Common mistake: “A and B are close, so $p_{AB}$ must be large,” or “$p_{AB}$ is the probability that A and B have the same cell type.” Neither follows. The joint similarity depends on both directional conditional distributions, their bandwidths, and the factor $2n$. It is a normalized algorithmic affinity, not a biological-class probability.

Check Your Understanding

Use the definitions and normalization convention above. Each problem includes its solution.

If a focal cell has three other cells with equal distances and the same positive bandwidth, what is each conditional probability? Solution: All three Gaussian weights are equal. Their normalized probabilities are $1/3$ each, and they sum to one.
Suppose $p_{j\mid i}=0.6$, $p_{i\mid j}=0.2$, and $n=10$. Find $p_{ij}$. Solution: $p_{ij}=(0.6+0.2)/(2\cdot10)=0.04$. The symmetric matrix entry is dimensionless and is not either directional probability by itself.
Why can $p_{j\mid i}$ differ from $p_{i\mid j}$ even when the distance is symmetric? Solution: The conditional probabilities use cell-specific bandwidths and normalize over all neighbors of the focal cell. Thus their denominators, and potentially their $\sigma$ values, differ, even though $d_{ij}=d_{ji}$.
For $n=4$, if the conditional distributions each sum to one, what should the sum of all entries in the full symmetric joint matrix be? Solution: It should equal one: $\sum_i\sum_jp_{ij}=(4+4)/(2\cdot4)=1$. A value near $0.5$ may indicate that only one triangle of the symmetric matrix was summed.

The t-SNE Pairwise Similarity Model

What You'll Learn