# Generalized Spectral Clustering via Gromov-Wasserstein Learning

arXiv: https://arxiv.org/abs/2006.04163 · HTML: https://mlsanity.com/paper/2006.04163/

## Key facts

- Cited by 38 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Jun 2020.

## Built on by (most cited first, 30 of 38)

- [Online Graph Dictionary Learning](https://mlsanity.com/paper/2102.06555/) (2021)
- [Semi-relaxed Gromov-Wasserstein divergence with applications on graphs](https://mlsanity.com/paper/2110.02753/) (2021)
- [Template based Graph Neural Network with Optimal Transport Distances](https://mlsanity.com/paper/2205.15733/) (2022)
- [Quantized Gromov-Wasserstein](https://mlsanity.com/paper/2104.02013/) (2021)
- [DIGRAC: Digraph Clustering Based on Flow Imbalance](https://mlsanity.com/paper/2106.05194/) (2021)
- [Robust Attributed Graph Alignment via Joint Structure Learning and Optimal Transport](https://mlsanity.com/paper/2301.12721/) (2023)
- [A Gromov--Wasserstein Geometric View of Spectrum-Preserving Graph Coarsening](https://mlsanity.com/paper/2306.08854/) (2023)
- [Fused Gromov-Wasserstein Graph Mixup for Graph-level Classifications](https://mlsanity.com/paper/2306.15963/) (2023)
- [Distributional Reduction: Unifying Dimensionality Reduction and Clustering with Gromov-Wasserstein](https://mlsanity.com/paper/2402.02239/) (2024)
- [The Z-Gromov-Wasserstein Distance](https://mlsanity.com/paper/2408.08233/) (2024)
- [Efficient Approximation of Gromov-Wasserstein Distance Using Importance Sparsification](https://mlsanity.com/paper/2205.13573/) (2022)
- [A Convergent Single-Loop Algorithm for Relaxation of Gromov-Wasserstein in Graph Data](https://mlsanity.com/paper/2303.06595/) (2023)
- [Restructuring Graph for Higher Homophily via Adaptive Spectral Clustering](https://mlsanity.com/paper/2206.02386/) (2022)
- [Outlier-Robust Gromov-Wasserstein for Graph Data](https://mlsanity.com/paper/2302.04610/) (2023)
- [Uncovering Challenges of Solving the Continuous Gromov-Wasserstein Problem](https://mlsanity.com/paper/2303.05978/) (2023)
- [Multiscale Graph Comparison via the Embedded Laplacian Discrepancy](https://mlsanity.com/paper/2201.12064/) (2022)
- [Subspace Detours Meet Gromov-Wasserstein](https://mlsanity.com/paper/2110.10932/) (2021)
- [Structure-Aware E(3)-Invariant Molecular Conformer Aggregation Networks](https://mlsanity.com/paper/2402.01975/) (2024)
- [Nonparametric Multi-shape Modeling with Uncertainty Quantification](https://mlsanity.com/paper/2206.09127/) (2022)
- [Fast Gradient Computation for Gromov-Wasserstein Distance](https://mlsanity.com/paper/2404.08970/) (2024)
- [Metric properties of partial and robust Gromov-Wasserstein distances](https://mlsanity.com/paper/2411.02198/) (2024)
- [Gradual Domain Adaptation for Graph Learning](https://mlsanity.com/paper/2501.17443/) (2025)
- [Fast and Provably Convergent Algorithms for Gromov-Wasserstein in Graph Data](https://mlsanity.com/paper/2205.08115/) (2022)
- [LogSpecT: Feasible Graph Learning Model from Stationary Signals with Recovery Guarantees](https://mlsanity.com/paper/2305.01379/) (2023)
- [Graph Cuts with Arbitrary Size Constraints Through Optimal Transport](https://mlsanity.com/paper/2402.04732/) (2024)
- [Linear Partial Gromov-Wasserstein Embedding](https://mlsanity.com/paper/2410.16669/) (2024)
- [Graph-based Clustering Revisited: A Relaxation of Kernel k-Means Perspective](https://mlsanity.com/paper/2509.18826/) (2025)
- [Metrics for Parametric Families of Networks](https://mlsanity.com/paper/2509.22549/) (2025)
- [Balanced Coarsening for Multilevel Hypergraph Partitioning via Wasserstein Discrepancy](https://mlsanity.com/paper/2106.07501/) (2021)
- [Interpolating between Clustering and Dimensionality Reduction with Gromov-Wasserstein](https://mlsanity.com/paper/2310.03398/) (2023)

## Abstract (arXiv)

We establish a bridge between spectral clustering and Gromov-Wasserstein Learning (GWL), a recent optimal transport-based approach to graph partitioning. This connection both explains and improves upon the state-of-the-art performance of GWL. The Gromov-Wasserstein framework provides probabilistic correspondences between nodes of source and target graphs via a quadratic programming relaxation of the node matching problem. Our results utilize and connect the observations that the GW geometric structure remains valid for any rank-2 tensor, in particular the adjacency, distance, and various kernel matrices on graphs, and that the heat kernel outperforms the adjacency matrix in producing stable and informative node correspondences. Using the heat kernel in the GWL framework provides new multiscale graph comparisons without compromising theoretical guarantees, while immediately yielding improved empirical results. A key insight of the GWL framework toward graph partitioning was to compute GW correspondences from a source graph to a template graph with isolated, self-connected nodes. We show that when comparing against a two-node template graph using the heat kernel at the infinite time limit, the resulting partition agrees with the partition produced by the Fiedler vector. This in turn yields a new insight into the k-cut graph partitioning problem through the lens of optimal transport. Our experiments on a range of real-world networks achieve comparable results to, and in many cases outperform, the state-of-the-art achieved by GWL.