Smita Krishnaswamy

While numerous methods have been proposed for computing distances between probability distributions in Euclidean space, relatively little at… (see more)tention has been given to computing such distances for distributions on graphs. However, there has been a marked increase in data that either lies on graph (such as protein interaction networks) or can be modeled as a graph (single cell data), particularly in the biomedical sciences. Thus, it becomes important to find ways to compare signals defined on such graphs. Here, we propose Graph Fourier MMD (GFMMD), a novel a distance between distributions, or non-negative signals on graphs. GFMMD is defined via an optimal witness function that is both smooth on the graph and maximizes difference in expectation between the pair of distributions on the graph. We find an analytical solution to this optimization problem as well as an embedding of distributions that results from this method. We also prove several properties of this method including scale invariance and applicability to disconnected graphs. We showcase it on graph benchmark datasets as well on single cell RNA-sequencing data analysis. In the latter, we use the GFMMD-based gene embeddings to find meaningful gene clusters. We also propose a novel type of score for gene selection called {\em gene localization score} which helps select genes for cellular state space characterization.

2023-02-01

ICLR.cc/2023/Conference (rejected)

GEODESIC SINKHORN FOR FAST AND ACCURATE OPTIMAL TRANSPORT ON MANIFOLDS

Guillaume Huguet

Alexander Tong

María Ramos Zapatero

Christopher J. Tape

Efficient computation of optimal transport distance between distributions is of growing importance in data science. Sinkhorn-based methods a… (see more)re currently the state-of-the-art for such computations, but require O(n2) computations. In addition, Sinkhorn-based methods commonly use an Euclidean ground distance between datapoints. However, with the prevalence of manifold structured scientific data, it is often desirable to consider geodesic ground distance. Here, we tackle both issues by proposing Geodesic Sinkhorn—based on diffusing a heat kernel on a manifold graph. Notably, Geodesic Sinkhorn requires only O(n log n) computation, as we approximate the heat kernel with Chebyshev polynomials based on the sparse graph Laplacian. We apply our method to the computation of barycenters of several distributions of high dimensional single cell data from patient samples undergoing chemotherapy. In particular, we define the barycentric distance as the distance between two such barycenters. Using this definition, we identify an optimal transport distance and path associated with the effect of treatment on cellular data.

2023-01-01

2023 IEEE 33rd International Workshop on Machine Learning for Signal Processing (MLSP) (published)

arxiv.org

A Heat Diffusion Perspective on Geodesic Preserving Dimensionality Reduction

Guillaume Huguet

Alexander Tong

Edward De Brouwer

Yanlei Zhang

Ian Adelstein

Inferring Dynamic Regulatory Interaction Graphs From Time Series Data With Perturbations

Dhananjay Bhaskar

Daniel Sumner Magruder

Edward De Brouwer

Matheo Morales

Aarthi Venkat

Frederik Wenkel

2023-01-01

LoG (published)

Learning Shared Neural Manifolds from Multi-Subject FMRI Data

Jessie Huang

Je-chun Huang

Erica Lindsey Busch

Tom Wallenstein

Michal Gerasimiuk

Andrew Benz

Guillaume Lajoie

Nicholas Turk-Browne

Functional magnetic resonance imaging (fMRI) data is collected in millions of noisy, redundant dimensions. To understand how different brain… (see more)s process the same stimulus, we aim to denoise the fMRI signal via a meaningful embedding space that captures the data's intrinsic structure as shared across brains. We assume that stimulus-driven responses share latent features common across subjects that are jointly discoverable. Previous approaches to this problem have relied on linear methods like principal component analysis and shared response modeling. We propose a neural network called MRMD-AE (manifold-regularized multiple- decoder, autoencoder) that learns a common embedding from multi-subject fMRI data while retaining the ability to decode individual responses. Our latent common space represents an extensible manifold (where untrained data can be mapped) and improves classification accuracy of stimulus features of unseen timepoints, as well as cross-subject translation of fMRI signals.

2022-08-22

2022 IEEE 32nd International Workshop on Machine Learning for Signal Processing (MLSP) (published)

Multiscale PHATE identifies multimodal signatures of COVID-19

Manik Kuchroo

Je-chun Huang

Patrick Wong

Jean-Christophe Grenier

Dennis Shung

Alexander Tong

Carolina Lucas

Jon Klein

Daniel B. Burkhardt

Scott Gigante

Abhinav Godavarthi

Bastian Rieck

Benjamin Israelow

Michael Simonov

Tianyang Mao

Ji Eun Oh

Julio Silva

Takehiro Takahashi

Camila D. Odio

Arnau Casanovas-Massana … (see 10 more)

John Fournier

Shelli Farhadian

Charles S. Dela Cruz

Albert I. Ko

Matthew Hirn

F. Perry Wilson

Akiko Iwasaki

2022-02-28

Nature Biotechnology (published)

Multiscale PHATE identifies multimodal signatures of COVID-19

Manik Kuchroo

Je-chun Huang

Patrick W. Wong

Jean-Christophe Grenier

Dennis L. Shung

Alexander Tong

C. Lucas

J. Klein

Daniel B. Burkhardt

Scott Gigante

Abhinav Godavarthi

Bastian Rieck

Benjamin Israelow

Michael Simonov

Tianyang Mao

Ji Eun Oh

Julio Silva

Takehiro Takahashi

C. Odio

Arnau Casanovas‐massana … (see 10 more)

John Byrne Fournier

Shelli F. Farhadian

C. D. Dela Cruz

A. Ko

Matthew Hirn

F. Wilson

Akiko Iwasaki

2022-02-28

Nature Biotechnology (published)

Population Genomics Approaches for Genetic Characterization of SARS-CoV-2 Lineages

Fatima Mostefai

Isabel Gamache

Arnaud N’Guessan

Justin Pelletier

Jessie Huang

Carmen Lia Murall

Ahmad Pesaranghader

Vanda Gaonac'h-Lovejoy

David J. Hamelin

Raphael Poujol

Jean-Christophe Grenier

Martin Smith

Etienne Caron

Morgan Craig

B. Jesse Shapiro

2022-02-21

Frontiers in Medicine (published)

Population Genomics Approaches for Genetic Characterization of SARS-CoV-2 Lineages

Fatima Mostefai

I. Gamache

Arnaud N’Guessan

Justin Pelletier

Jessie Huang

Carmen Lia Murall

Ahmad Pesaranghader

Vanda Gaonac'h-Lovejoy

David J. Hamelin

Raphael Poujol

Jean-Christophe Grenier

Martin W. Smith

Étienne Caron

Morgan Craig

B. Jesse Shapiro

The genome of the Severe Acute Respiratory Syndrome coronavirus 2 (SARS-CoV-2), the pathogen that causes coronavirus disease 2019 (COVID-19)… (see more), has been sequenced at an unprecedented scale leading to a tremendous amount of viral genome sequencing data. To assist in tracing infection pathways and design preventive strategies, a deep understanding of the viral genetic diversity landscape is needed. We present here a set of genomic surveillance tools from population genetics which can be used to better understand the evolution of this virus in humans. To illustrate the utility of this toolbox, we detail an in depth analysis of the genetic diversity of SARS-CoV-2 in first year of the COVID-19 pandemic. We analyzed 329,854 high-quality consensus sequences published in the GISAID database during the pre-vaccination phase. We demonstrate that, compared to standard phylogenetic approaches, haplotype networks can be computed efficiently on much larger datasets. This approach enables real-time lineage identification, a clear description of the relationship between variants of concern, and efficient detection of recurrent mutations. Furthermore, time series change of Tajima's D by haplotype provides a powerful metric of lineage expansion. Finally, principal component analysis (PCA) highlights key steps in variant emergence and facilitates the visualization of genomic variation in the context of SARS-CoV-2 diversity. The computational framework presented here is simple to implement and insightful for real-time genomic surveillance of SARS-CoV-2 and could be applied to any pathogen that threatens the health of populations of humans and other organisms.

2022-02-21

Frontiers in Medicine (published)

Fixing Bias in Reconstruction-based Anomaly Detection with Lipschitz Discriminators

Alexander Tong

Anomaly detection is of great interest in fields where abnormalities need to be identified and corrected (e.g., medicine and finance). Deep … (see more)learning methods for this task often rely on autoencoder reconstruction error, sometimes in conjunction with other penalties. We show that this approach exhibits intrinsic biases that lead to undesirable results. Reconstruction-based methods can sometimes show low error on simple-to-reconstruct points that are not part of the training data, for example the all black image. Instead, we introduce a new unsupervised Lipschitz anomaly discriminator (LAD) that does not suffer from these biases. Our anomaly discriminator is trained, similar to the discriminator of a GAN, to detect the difference between the training data and corruptions of the training data. We show that this procedure successfully detects unseen anomalies with guarantees on those that have a certain Wasserstein distance from the data or corrupted training set. These additions allow us to show improved performance on MNIST, CIFAR10, and health record data. Further, LAD does not require decoding back to the original data space, which makes anomaly detection possible in domains where it is difficult to define a decoder, such as in irregular graph structured data. Empirically, we show this framework leads to improved performance on image, health record, and graph data.

2021-11-28

Journal of Signal Processing Systems (published)

Data-driven approaches for genetic characterization of SARS-CoV-2 lineages

Fatima Mostefai

Isabel Gamache

Jessie Huang

Arnaud N’Guessan

Justin Pelletier

Ahmad Pesaranghader

David J. Hamelin

Carmen Lia Murall

Raphael Poujol

Jean-Christophe Grenier

Martin Smith

Etienne Caron

Morgan Craig

Jesse Shapiro

The genome of the Severe Acute Respiratory Syndrome coronavirus 2 (SARS-CoV-2), the pathogen that causes coronavirus disease 2019 (COVID-19)… (see more), has been sequenced at an unprecedented scale, leading to a tremendous amount of viral genome sequencing data. To understand the evolution of this virus in humans, and to assist in tracing infection pathways and designing preventive strategies, we present a set of computational tools that span phylogenomics, population genetics and machine learning approaches. To illustrate the utility of this toolbox, we detail an in depth analysis of the genetic diversity of SARS-CoV-2 in first year of the COVID-19 pandemic, using 329,854 high-quality consensus sequences published in the GISAID database during the pre-vaccination phase. We demonstrate that, compared to standard phylogenetic approaches, haplotype networks can be computed efficiently on much larger datasets, enabling real-time analyses. Furthermore, time series change of Tajima’s D provides a powerful metric of population expansion. Unsupervised learning techniques further highlight key steps in variant detection and facilitate the study of the role of this genomic variation in the context of SARS-CoV-2 infection, with Multiscale PHATE methodology identifying fine-scale structure in the SARS-CoV-2 genetic data that underlies the emergence of key lineages. The computational framework presented here is useful for real-time genomic surveillance of SARS-CoV-2 and could be applied to any pathogen that threatens the health of worldwide populations of humans and other organisms.

2021-09-29

bioRxiv (preprint)

Embedding Signals on Knowledge Graphs with Unbalanced Diffusion Earth Mover's Distance

Alexander Tong

Guillaume Huguet

Dennis L. Shung

Amine Natik

Manik Kuchroo

Guillaume Lajoie