  Learning to align multiple datasets is an important problem with many
applications, and it is especially useful when we need to integrate multiple
experiments or correct for confounding. Optimal transport (OT) is a principled
approach to align datasets, but a key challenge in applying OT is that we need
to specify a transport cost function that accurately captures how the two
datasets are related. Reliable cost functions are typically not available and
practitioners often resort to using hand-crafted or Euclidean cost even if it
may not be appropriate. In this work, we investigate how to learn the cost
function using a small amount of side information which is often available. The
side information we consider captures subset correspondence -- i.e. certain
subsets of points in the two data sets are known to be related. For example, we
may have some images labeled as cars in both datasets; or we may have a common
annotated cell type in single-cell data from two batches. We develop an
end-to-end optimizer (OT-SI) that differentiates through the Sinkhorn algorithm
and effectively learns the suitable cost function from side information. On
systematic experiments in images, marriage-matching and single-cell RNA-seq,
our method substantially outperform state-of-the-art benchmarks.
