Develop prototype ROI merging code based on Louvain clustering

[danielsf]

The Louvain clustering algorithm is a well-established algorithm for finding communities in a graph network. It is a central part of the algorithm used by the RNASeq scientists for discovering cell types. The relevant part of the cell cluster finding algorithm is (this is copy-and-pasted from a summary @danielsf wrote for himself after reading Tasic et al. 2018)

For each pixel find the 15 nearest neighbors in PCA space. These 15 cells define the neighborhood for each pixel To find the weight of the edge between pixels A and B, use the intersection over union of A and B's neighborhood. Use these neighborhoods as the seed communities for the Louvain cluster finding algorithm.

This ticket represents work to experiment with using the Louvain clustering algorithm to solve the ROI merging problem. If it works well, we can consider using the algorithm to find ROIs in the first place.

Tasks

• [ ] Find an efficient implementation of the Louvain algorithm
• [ ] Determine a low-dimensional feature space in which to cluster the pixels in an ROI.
• [ ] Try running the Louvain algorithm using ROIs found by one of our prototype segmenters as seed communities
• [ ] Assess quality of merged ROI's by eye

Stretch task

• [ ] Try running the Louvain algorithm on previously unsegmented data using spatial location and feature space location to determine seed communities for pixels

Validation

• [ ] Plots showing the result of ROI merging with the Louvain algorithm
• [ ] Prototype code that can later be turned into a production-like module, if the above plots look reasonable

[danielsf]

I suspect this is not actually going to get closed this sprint (9/10), so I wanted to post an update.

I do have a prototype implementation in this branch https://github.com/AllenInstitute/ophys_etl_pipelines/tree/segmentation/dev/louvain/clustering

It appears to work well on experiments that clearly need merging, see, for example

experiment 795901850

experiment 850517348

However, in cases that do not obviously need merging, it seems to merge over-enthusiastically, sometimes with egregious results. See the upper-left corner of

experiment 785569447

I have some ideas how we can amend this behavior, namely

• Set some pixel-to-pixel correlation floor below which we set the correlation to zero by-hand to minimize the interconnectivity of otherwise distinct ROIs
• In each case when we are considering clusters of ROIs for merging, add a "background" cluster to which all pixels are connected but into which they can never merge. This might change the decision calculus of the louvain algorithm when evaluating which pairs of clusters to merge.

These are largely speculative and will require some numerical experiments to evaluate.