Abstract: Unbalanced optimal transport (UOT) has lately gained much attention owing to its flexible framework to handle un-normalized measures and noisy noisy scenarios in a variety of applications. In this work, we explore learning (structured) sparse transport plan in UOT setting, i.e., transport plans having at most $K$ non-sparse entries or having at most $K$ non-sparse entries in each column. We propose novel sparsity-constrained UOT formulations building on a recently explored maximum mean discrepancy based UOT. We show that the proposed optimization problem is equivalent to maximization of weakly submodular functions over uniform matroid or partition matroid. We develop efficient gradient-based discrete greedy algorithms and provide the corresponding theoretical guarantees. We empirically observe that our proposed greedy algorithms select diverse support set. The efficacy of the proposed modeling is shown in a number of applications including designing topology, word alignment, and sparse mixture-of-experts.