Bridging Graph Worlds: Neural Approximation of Gromov-Wasserstein Distances

Graph-structured data is crucial in various domains like biology and social networks. Comparing graphs, which is a fundamental problem in graph data analysis, is nonetheless highly challenging. Recently, the Gromov-Wasserstein (GW) distance has provided a principled way to compare two graphs. However, computing the GW distance involves solving a complex non-convex optimization problem, making it computationally expensive, especially when the graphs are large. In this work, we propose a neural approximation of the GW distance, called NeuralGW. In NeuralGW, we use a combination of a graph isomorphism network and a transformer to represent the nodes of two graphs as two sets of vectors, treated as two discrete distributions, on which we compute multiple maximum mean discrepancy values given by different kernels. We then use a multilayer perceptron to convert the vector formed by these values into a single value, which is the prediction of the GW distance. Once trained, the model allows for efficient inference, enabling fast structural comparisons between graphs across diverse domains. We also provide a theoretical guarantee for the generalization ability of NeuralGW. Experiments demonstrate the effectiveness and practical applicability of our approach on real-world datasets, in comparison to baselines.