Several works in the literature have studied the graph comparison problem. For example, graph alignment has been formulated as a quadratic assignment problem [1]}, [2]}, under the constraint that the solution is a permutation matrix. This results in an NP-hard problem, and several relaxations have been proposed to find approximate solutions to this problem [3]}, [4]}, [5]}. Recently, some works have studied the graph alignment problem from the perspective of optimal transport, which has inspired several advances in machine learning [6]}, [7]}. For example, [8]} define a spectral distance by assigning a probability measure to the nodes via the spectrum representation of each graph and using Wasserstein distances between probability measures. This approach, however, disregards graph eigenvectors and thus does not take into account the full graph structure in the alignment problem. The authors in [9]} propose to match the graph embeddings, where the latter are represented as bags of vectors, and the Wasserstein distance is computed between them. The authors also propose a heuristic to take into account possible node labels or signals. A Gumbel-sinkhorn network inspired by optimal transport was further proposed to infer permutations from data [10]}, [11]}. The approach consists of producing a discrete permutation from a continuous doubly-stochastic matrix obtained with the Sinkhorn operator [12]}. More recently, optimal transport between stationary Markov chains has been used to find a coupling between graphs [13]}.
