Installation

MultiscaleEMD is available in pypi. Install by running the following

pip install MultiscaleEMD

Quick Start

MultiscaleEMD is written following the sklearn estimator framework.

For DiffusionEMD: We provide two functions that operate quite differently. First the Chebyshev approximation of the operator in DiffusionCheb, which we recommend when the number of distributions is small compared to the number of points. Second, the Interpolative Decomposition method that computes dyadic powers of $P^{2^k}$ directly in DiffusionTree. These two classes are used in the same way, first supplying parameters, fitting to a graph and array of distributions

import numpy as np
from MultiscaleEMD import DiffusionCheb

# Setup an adjacency matrix and a set of distributions to embed
adj = np.ones((10, 10))
distributions = np.random.randn(10, 5)
dc = DiffusionCheb()

# Embeddings where the L1 distance approximates the Earth Mover's Distance
embedding = dc.fit_transform(adj, distributions)
# Shape: (5, 60)

For Tree Earth Mover’s Distances and Trellis: we provide a number of ways to embed pointcloud data in $\mathbb{R}^d$ into a hierarchical tree. These are implemented as options in the MetricTree class.

from MultiscaleEMD.metric_tree import MetricTreeCollection

mt = MetricTreeCollection(n_trees=10, tree_type="cluster", n_levels=4, n_clusters=4)
embedding = mt.fit_embed(data, distributions)

Requirements can be found in requirements.txt

Examples

Examples are in the notebooks directory.

Take a look at the examples provided there to get a sense of how the parameters behave on simple examples that are easy to visualize.

Papers

This code implements the algorithms described in the following papers:

1. Diffusion EMD (ICML 2021)

2. Unbalanced Diffusion EMD (ICASSP 2022)

3. Trellis (Preprint 2022)

For bibtex see below:

ArXiv Link: http://arxiv.org/abs/2102.12833:

@InProceedings{pmlr-v139-tong21a,
  title =       {Diffusion Earth Mover’s Distance and Distribution Embeddings},
  author =      {Tong, Alexander and Huguet, Guillaume and Natik, Amine and Macdonald, Kincaid and Kuchroo, Manik and Coifman, Ronald and Wolf, Guy and Krishnaswamy, Smita},
  booktitle =   {Proceedings of the 38th International Conference on Machine Learning},
  pages =       {10336--10346},
  year =        {2021},
  editor =      {Meila, Marina and Zhang, Tong},
  volume =      {139},
  series =      {Proceedings of Machine Learning Research},
  month =       {18--24 Jul},
  publisher =   {PMLR},
  pdf =         {http://proceedings.mlr.press/v139/tong21a/tong21a.pdf},
  url =         {http://proceedings.mlr.press/v139/tong21a.html},
}

ArXiv Link: https://arxiv.org/abs/2107.12334:

@inproceedings{tong_embedding_2022,
  author={Tong, Alexander and Huguet, Guillaume and Shung, Dennis and Natik, Amine and Kuchroo, Manik and Lajoie, Guillaume and Wolf, Guy and Krishnaswamy, Smita},
  booktitle={ICASSP 2022 - 2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)},
  title={Embedding Signals on Graphs with Unbalanced Diffusion Earth Mover’s Distance},
  year={2022},
  volume={},
  number={},
  pages={5647-5651},
  doi={10.1109/ICASSP43922.2022.9746556}
}

BioRXiv Link: https://www.biorxiv.org/content/10.1101/2022.10.19.512668v1:

@article {Ramos Zapatero2022.10.19.512668,
    author = {Ramos Zapatero, Maria and Tong, Alexander and Sufi, Jahangir and Vlckova, Petra and Cardoso Rodriguez, Ferran and Nattress, Callum and Qin, Xiao and Hochhauser, Daniel and Krishnaswamy, Smita and Tape, Christopher J},
    title = {Cancer-Associated Fibroblasts Regulate Patient-Derived Organoid Drug Responses},
    elocation-id = {2022.10.19.512668},
    year = {2022},
    doi = {10.1101/2022.10.19.512668},
    publisher = {Cold Spring Harbor Laboratory},
    URL = {https://www.biorxiv.org/content/early/2022/10/21/2022.10.19.512668},
    eprint = {https://www.biorxiv.org/content/early/2022/10/21/2022.10.19.512668.full.pdf},
    journal = {bioRxiv}
}

As well as other algorithms under development.