Learning Graphons via Structured Gromov-Wasserstein Barycenters

Abstract

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.

References in corpus (8)

• Matrix estimation by Universal Singular Value Thresholding
• TUDataset: A collection of benchmark datasets for learning with graphs
• Graph limits and exchangeable random graphs
• Optimal Transport for structured data with application on graphs
• A Fast Proximal Point Method for Computing Exact Wasserstein Distance
• A Consistent Histogram Estimator for Exchangeable Graph Models
• Fused Gromov-Wasserstein distance for structured objects: theoretical foundations and mathematical properties
• Hierarchical Optimal Transport for Robust Multi-View Learning

Cited by in corpus (1)

• Hawkes Processes on Graphons