Fused Partial Gromov-Wasserstein for Structured Objects
This work addresses the problem of comparing structured data with unequal mass for machine learning applications, particularly in graph analysis, providing a solution for researchers and practitioners working with complex relational data.
The authors tackled the problem of comparing structured data with unequal mass by proposing the Fused Partial Gromov-Wasserstein framework, which demonstrated robust performance in graph matching, classification, and clustering experiments. The framework extends the Fused Gromov-Wasserstein distance to accommodate unbalanced data.
Structured data, such as graphs, is vital in machine learning due to its capacity to capture complex relationships and interactions. In recent years, the Fused Gromov-Wasserstein (FGW) distance has attracted growing interest because it enables the comparison of structured data by jointly accounting for feature similarity and geometric structure. However, as a variant of optimal transport (OT), classical FGW assumes an equal mass constraint on the compared data. In this work, we relax this mass constraint and propose the Fused Partial Gromov-Wasserstein (FPGW) framework, which extends FGW to accommodate unbalanced data. Theoretically, we establish the relationship between FPGW and FGW and prove the metric properties of FPGW. Numerically, we introduce Frank-Wolfe solvers and Sinkhorn solvers for the proposed FPGW framework. Finally, we evaluate the FPGW distance through graph matching, graph classification and graph clustering experiments, demonstrating its robust performance.