论文标题
通过结构化的Gromov-Wasserstein Barycenters学习图形子
Learning Graphons via Structured Gromov-Wasserstein Barycenters
论文作者
论文摘要
我们提出了一种新颖的原则方法，可以学习一个名为Graphon的非参数图模型，该模型在无限维空间中定义并代表任意尺寸的图。基于图形理论的弱规则性引理，我们利用步骤函数近似图形。我们表明，图形子的切割距离可以放松到其步骤功能的Gromov-Wasserstein距离。因此，给定一组由基础图形生成的图，我们将相应的步骤函数学习为给定图的Gromov-Wasserstein Barycenter。此外，我们开发了基本算法的几种增强和扩展，例如$ $，是平滑的Gromov-Wasserstein Barycenter，用于保证学习图形的连续性和混合的Gromov-Wasserent Barycenters，用于学习多个结构化图形。所提出的方法克服了先前最新方法的缺点，并在合成和现实世界中的数据上都优于它们。该代码可在https://github.com/hongtengxu/sgwb-graphon上找到。
We propose a novel and principled method to learn a nonparametric graph model called graphon, which is defined in an infinite-dimensional space and represents arbitrary-size graphs. Based on the weak regularity lemma from the theory of graphons, we leverage a step function to approximate a graphon. We show that the cut distance of graphons can be relaxed to the Gromov-Wasserstein distance of their step functions. Accordingly, given a set of graphs generated by an underlying graphon, we learn the corresponding step function as the Gromov-Wasserstein barycenter of the given graphs. Furthermore, we develop several enhancements and extensions of the basic algorithm, $e.g.$, the smoothed Gromov-Wasserstein barycenter for guaranteeing the continuity of the learned graphons and the mixed Gromov-Wasserstein barycenters for learning multiple structured graphons. The proposed approach overcomes drawbacks of prior state-of-the-art methods, and outperforms them on both synthetic and real-world data. The code is available at https://github.com/HongtengXu/SGWB-Graphon.
