  We introduce COPT, a novel distance metric between graphs defined via an
optimization routine, computing a coordinated pair of optimal transport maps
simultaneously. This gives an unsupervised way to learn general-purpose graph
representation, applicable to both graph sketching and graph comparison. COPT
involves simultaneously optimizing dual transport plans, one between the
vertices of two graphs, and another between graph signal probability
distributions. We show theoretically that our method preserves important global
structural information on graphs, in particular spectral information, and
analyze connections to existing studies. Empirically, COPT outperforms state of
the art methods in graph classification on both synthetic and real datasets.
