Title: ErGOT: entropy-regularized graph optimal transport. Abstract: Graph comparison is a fundamental task, which not only relates to graph matching, an NP-hard problem, but also has various applications in graph learning. We tackle this task by studying optimal graph representation and the entropy-regularized optimal transport between graphs (ErGOT). First, we analytically derive a family of Gaussian variables that optimally represent graph topology and node relation. Second, we realize graph comparison by formulating ErGOT, a framework with low sample complexity, on represented graph information. Third, we control biases in the solution by defining ErGOT with a 2-Sinkhorn divergence, whose closed-form expression can be derived on the manifold of Gaussian variables. As the Gaussian geometry changes with entropy regularization magnitude, ErGOT defined with 2-Sinkhorn divergence wanders between pure optimal transport and maximum mean discrepancy among graphs. We demonstrate that these statistically efficient, principally unbiased, and in-between properties ensure theoretically faster convergence of our approach to empirically higher performance than the state-of-art algorithms on graph alignment, sketching, and retrieval tasks. 