Abstract
The Sliced Gromov-Wasserstein (SGW) distance, aiming to relieve thecomputational cost of solving a non-convex quadratic program that is theGromov-Wasserstein distance, utilizes projecting directions sampled uniformlyfrom unit hyperspheres. This slicing mechanism incurs unnecessary computationalcosts due to uninformative directions, which also affects the representativepower of the distance. However, finding a more appropriate distribution overthe projecting directions (slicing distribution) is often an optimizationproblem in itself that comes with its own computational cost. In addition, withmore intricate distributions, the sampling itself may be expensive. As aremedy, we propose an optimization-free slicing distribution that provides fastsampling for the Monte Carlo approximation. We do so by introducing theRelation-Aware Projecting Direction (RAPD), effectively capturing the pairwiseassociation of each of two pairs of random vectors, each following theirambient law. This enables us to derive the Relation-Aware Slicing Distribution(RASD), a location-scale law corresponding to sampled RAPDs. Finally, weintroduce the RASGW distance and its variants, e.g., IWRASGW (ImportanceWeighted RASGW), which overcome the shortcomings experienced by SGW. Wetheoretically analyze its properties and substantiate its empirical prowessusing extensive experiments on various alignment tasks.