An Enhanced Gromov-Wasserstein Barycenter Method for Graph-based Clustering

Abstract

Optimal Transport (OT) recently has gained remarkable success in machine learning. These methods based on the Gromov-Wasserstein (GW) distance have proven highly effective in capturing complex data topologies and underlying structures. More specifically, Gromov-Wasserstein Learning (GWL) has recently introduced a framework for graph partitioning by minimizing the GW distance. Various improved versions stemming from this framework have showcased state-of-the-art performance on clustering tasks. Building upon GW barycenter, we introduce a novel approach that significantly enhances other GW-based models flexibility by relaxing the target distribution (cluster size) in GWL and using a wide class of positive semi-definite matrices. We then develop an efficient algorithm to solve the resulting non-convex problem by utilizing regularization and the successive upper-bound minimization techniques. The proposed method exhibits the capacity to identify improved partition results within an enriched searching space, as validated by our developed theoretical framework and numerical experiments. Furthermore, we bridge the proposed model with the well-known clustering methods including Non-negative Matrix Factorization, Min-Cut, Max-Dicut and other GW-based models. This connection provides a new solution to these traditional clustering problems from the perspective of OT. Real data experiments illustrate our method outperforms state-of-the-art graph partitioning methods on both directed and undirected graphs.