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.

该研究通过使用热核在 Gromov-Wasserstein 的框架上实现了新的多尺度图比较，提出了一种通过最优输运来解决 k-cut 图分割问题的新方法，比当前最先进的 GWL 技术在真实世界网络上表现更佳。

通过 Gromov-Wasserstein 学习实现广义谱聚类

Generalized Spectral Clustering via Gromov-Wasserstein Learning

We propose a scalable Gromov-Wasserstein learning (S-GWL) method and
establish a novel and theoretically-supported paradigm for large-scale graph
analysis. The proposed method is based on the fact that Gromov-Wasserstein
discrepancy is a pseudometric on graphs. Given two graphs, the optimal
transport associated with their Gromov-Wasserstein discrepancy provides the
correspondence between their nodes and achieves graph matching. When one of the
graphs has isolated but self-connected nodes ($i.e.$, a disconnected graph),
the optimal transport indicates the clustering structure of the other graph and
achieves graph partitioning. Using this concept, we extend our method to
multi-graph partitioning and matching by learning a Gromov-Wasserstein
barycenter graph for multiple observed graphs; the barycenter graph plays the
role of the disconnected graph, and since it is learned, so is the clustering.
Our method combines a recursive $K$-partition mechanism with a regularized
proximal gradient algorithm, whose time complexity is $\mathcal{O}(K(E+V)\log_K
V)$ for graphs with $V$ nodes and $E$ edges. To our knowledge, our method is
the first attempt to make Gromov-Wasserstein discrepancy applicable to
large-scale graph analysis and unify graph partitioning and matching into the
same framework. It outperforms state-of-the-art graph partitioning and matching
methods, achieving a trade-off between accuracy and efficiency.

提出了一个可扩展的 Gromov-Wasserstein 学习（S-GWL）方法，用于大规模图分析，通过学习多个观察到的图的 Gromov-Wasserstein 重心图来实现多图分区和匹配，并将其统一到同一框架中，从而在准确性和效率之间取得了平衡。