Is density normalization applied to the kernel?

[davisidarta]

Hi,

I would like to know if the parameter density_norm represents a choice to wether normalize or not the Gaussian kernel. I'm particularly interested if this is the case because that's how Setty et al (https://www.nature.com/articles/s41587-019-0068-4) define their kernel prior to computing the diffusion operator, which seems an especially robust approach to single-cell data.

If that is not the case, is there any way to make it into destiny? In other words, how hard-coded is this into the implementation?

Edit: Sorry, I have one more question. Is it possible to set the alpha parameter to the diffusion operator?

[flying-sheep]

The default is to normalize the transition probability matrix by density:

destiny/R/diffusionmap.r

Line 231 in c262b9e

d <- rowSums(trans_p, na.rm = TRUE) + 1 # diagonal set to 1

destiny/R/diffusionmap.r

Lines 432 to 442 in c262b9e

	get_norm_p <- function(trans_p, d, d_new, density_norm) {
	if (density_norm) {
	trans_p <- as(trans_p, 'dgTMatrix') # use non-symmetric triples to operate on all values
	stopifsmall(max(trans_p@x, na.rm = TRUE))
	#creates a dgCMatrix
	sparseMatrix(trans_p@i, trans_p@j, x = trans_p@x / (d_new[trans_p@i + 1] * d[trans_p@j + 1]), dims = dim(trans_p), index1 = FALSE)
	} else {
	trans_p
	}
	}

Is that what you mean?

[davisidarta]

Thanks for the answer, @flying-sheep ! That's not exactly what I meant, my question was specifically about the kernel. I'm comparing the performance of destiny vs. palantir kernel implementation. The normalization by density seems to correspond to palantir's multispace-scaling.

[flying-sheep]

Hmm, density_norm does what you see in the code quoted above. The kernel is applied here:

destiny/R/diffusionmap.r

Lines 408 to 427 in e952e95

	no_censoring <- function(dists, sigma, cb = invisible) {
	d2 <- dists ^ 2
	stopifnot(isSymmetric(d2))
	t_p <- if (length(sigma) == 1L) {
	exp(-d2@x / (2 * sigma ^ 2))
	} else {
	stopifnot(d2@uplo == 'U')
	coords <- as(d2, 'dsTMatrix')
	i <- coords@i + 1L
	j <- coords@j + 1L
	sig2 <- sigma^2
	S1 <- sigma[i] * sigma[j]
	S2 <- sig2[i] + sig2[j]
	sqrt(2 * S1 / S2) * exp(-d2@x / S2)
	}
	sparseMatrix(d2@i, p = d2@p, x = t_p, dims = dim(d2), symmetric = TRUE, index1 = FALSE)
	}

The default kernel width sigma is set to 'local' which means that it’s adapted to density:

destiny/R/diffusionmap.r

Lines 303 to 304 in e952e95

	sig_mat <- nn_dists[, n_local, drop = FALSE]
	sigma <- rowSums(sig_mat) / length(n_local) / 2

[davisidarta]

Thank you for your answer, @flying-sheep.

I'm still having trouble understanding how the package relates to the original Diffusion Maps algorithm (Coifman et al., 2005) and to destiny's associated publications (Haghverdi, 2015, 2016).

I'm specially confused regarding the alpha parameter and the local scaling. According to Coifman, an adaptative kernel ('local normalized' according to Haghverdi 2016) is accompanied by an alpha parameter, which controls how much the sampling distribution is allowed to bias the diffusion operator. However, this should be independent from the kernel itself ( an anisotropic kernel can be built with alpha = 0,5 or 1, for instance). Destiny is one of the few diffusion maps packages lacking the choice of this parameter and it is not clear from documentation wether this means that alpha is simply not taken into account or set to a default value. If alpha is not taken into account, how is the Laplace-Beltrami operator approximated?

[flying-sheep]

Destiny is one of the few diffusion maps packages lacking the choice of this parameter

Could you please list them, I don’t know that many implementations: In R AFAIK most people are using destiny these day, in Python people are using scanpy which has parameters for its kernels, and nobody uses MATLAB anymore.

---

Regarding your question: destiny allows the choice between two kernels, a gaussian kernel with a global kernel width and (as scanpy) one with a kernel width that’s simply the distance to the kth nearest neighbor (as approximation for local density).

References

We started using the locally adaptive kernel after submission of the destiny paper and before the DPT paper.

1. Coifman 2005: Geometric diffusions as a tool for harmonic analysis and structure definition of data: Diffusion maps
2. Haghverdi 2015: Diffusion maps for high-dimensional single-cell analysis of differentiation data
3. Angerer 2016: destiny: diffusion maps for large-scale single-cell data in R
4. Haghverdi 2016: Diffusion pseudotime (DPT) robustly reconstructs lineage branching

The DPT paper defines it in its supplementary materials, “1.1 Locally scaled transition matrix”. α is only mentioned in Coifman (2005), “One-Parameter Family of Diffusion Maps”.