  The current best practice for computing optimal transport (OT) is via entropy
regularization and Sinkhorn iterations. This algorithm runs in quadratic time
as it requires the full pairwise cost matrix, which is prohibitively expensive
for large sets of objects. In this work we propose two effective log-linear
time approximations of the cost matrix: First, a sparse approximation based on
locality-sensitive hashing (LSH) and, second, a Nystr\"om approximation with
LSH-based sparse corrections, which we call locally corrected Nystr\"om (LCN).
These approximations enable general log-linear time algorithms for
entropy-regularized OT that perform well even for the complex, high-dimensional
spaces common in deep learning. We analyse these approximations theoretically
and evaluate them experimentally both directly and end-to-end as a component
for real-world applications. Using our approximations for unsupervised word
embedding alignment enables us to speed up a state-of-the-art method by a
factor of 3 while also improving the accuracy by 3.1 percentage points without
any additional model changes. For graph distance regression we propose the
graph transport network (GTN), which combines graph neural networks (GNNs) with
enhanced Sinkhorn. GTN outcompetes previous models by 48% and still scales
log-linearly in the number of nodes.
