Resetting local connectivity and metrics

[jlmelville]

Somewhat related to #838 (and maybe #58 although the code has changed substantially since then), there are rather esoteric questions which are not likely to have huge practical significance currently, but may be of interest in terms of extending UMAP to mixed data sets.

1. When resetting local connectivity, when should the local metric also be reset?

   The local metric is not reset in:

   • discrete_metric_simplicial_set_intersection
   • __sub__

   It is reset in:

   • __mul__
   • __add__
   • fit (as part of supervised UMAP)

   It's not easy to discern a pattern here.

2. Resetting the local metric involves:

   • normalizing each observation's weights so the maximum is 1.
   • Reweighting by v_j^x (where v_j are the weights) and x is found by binary search so the sum of the weights is log2(n_neighbors). This step is superficially similar to the smooth_knn_dist routine, but the functional form differs and there is no local connectivity constraint. Is there a deeper connection or equivalence here? Or is this is a rough approximation to smooth_knn_dist?

3. The final step in reset_local_connectivity seems to be algorithmically equivalent to the fuzzy union step in fuzzy_simplicial_set. Is it conceptually the same thing? It makes sense that resymmetrization needs to occur. In that case, as a hypothetical extension of this to the case with a "bipartite" simplicial set (e.g. when transforming new data) then is it the case that this step must be omitted? Obviously the current step wouldn't work anyway because a square matrix is needed, but I am wondering if there is an equivalent process that is needed in the bipartite case (assuming this step just looks like fuzzy set union by coincidence).

4. In this hypothetical bipartite extension, would an adjusted local connectivity need to be introduced as used in transform?

[lmcinnes]

Let's see if I can provide at least some answers. The first question is at least relatively straightforward: mostly resetting local connectivity should be the right thing to do, but the __sub__ routine is pretty experimental (I added simply because it seemed like an obvious counterpart once I added the __add__ and __mul__), and resetting local connectivity there ... pretty much eliminated anything __sub__ did, so I just didn't do it in that case. It is just an odd and quirky example really.

For the second question: it's a rough approximation to smooth_knn_dist; the first step is equivalent to the local connectivity to a degree. Perhaps this could be done better/more accurately with more care, but this was working well enough so I haven't really messed with it.

For the third question: I think reading it as the fuzzy-set union is the right approach. The bipartite case is trickier. That leads into the fourth question. The transform, as written currently, is really just trying to attach new points without altering the existing structure (unlike, for example, the update function. With that in mind resetting local connectivity etc. doesn't really make sense as it would change the relationships among the existing vertices, which we are trying not to do. It is possible to imagine an operation that did do something like that, but I think it would have to look more like update (assuming I got all the parts correct in that) with a transform style optimization at the end.

[jlmelville]

Thank you @lmcinnes, I appreciate you taking time to answer this.