A fundamental step in many data-analysis techniques is the construction of an\naffinity matrix describing similarities between data points. When the data\npoints reside in Euclidean space, a widespread approach is to from an affinity\nmatrix by the Gaussian kernel with pairwise distances, and to follow with a\ncertain normalization (e.g. the row-stochastic normalization or its symmetric\nvariant). We demonstrate that the doubly-stochastic normalization of the\nGaussian kernel with zero main diagonal (i.e., no self loops) is robust to\nheteroskedastic noise. That is, the doubly-stochastic normalization is\nadvantageous in that it automatically accounts for observations with different\nnoise variances. Specifically, we prove that in a suitable high-dimensional\nsetting where heteroskedastic noise does not concentrate too much in any\nparticular direction in space, the resulting (doubly-stochastic) noisy affinity\nmatrix converges to its clean counterpart with rate $m^{-1/2}$, where $m$ is\nthe ambient dimension. We demonstrate this result numerically, and show that in\ncontrast, the popular row-stochastic and symmetric normalizations behave\nunfavorably under heteroskedastic noise. Furthermore, we provide examples of\nsimulated and experimental single-cell RNA sequence data with intrinsic\nheteroskedasticity, where the advantage of the doubly-stochastic normalization\nfor exploratory analysis is evident.\n