Note that representing mm-spaces has an \(O(N^2)\)  memory footprint, thus the distortion \(|d_(x,x^{\prime })-d_(y,y^{\prime })|\)  is an \(O(N^4)\)  4D-tensor.
As noted in [1]}, under some assumptions (satisfied by the squared distortion \(|d_- d_|^2\) ), computing the cost \(\pi \)  takes \(O(N^3)\)  in time and \(O(N^2)\)  in space, instead of \(O(N^4)\) .
This might however remain prohibitive for large scale graphs, thus several works propose to perform approximations of the plan to reduce computations.
One can assume for instance a hierarchical [2]} or a low-rank [3]} structure of the plan.
An approach motivated by QAPs but which applies to GW is to interpolate between the optimization of a convex and a concave objective [4]}.
The GW problem can also be reformulated as a semi-definite program where the plan \(\pi \otimes \pi \)  is a 4D-tensor satisfying a low rank constraint.
Removing this rank constraint yields a relaxation with polynomial complexity, and which satisfies the triangle inequality between mm-spaces of same cardinality equipped with a uniform measure [5]}.
