# Learning Graphons via Structured Gromov-Wasserstein Barycenters

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

## Key facts

- Cited by 37 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Dec 2020.

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

- [G-Mixup: Graph Data Augmentation for Graph Classification](https://mlsanity.com/paper/2202.07179/) (2022)
- [Does Graph Distillation See Like Vision Dataset Counterpart?](https://mlsanity.com/paper/2310.09192/) (2023)
- [Semi-relaxed Gromov-Wasserstein divergence with applications on graphs](https://mlsanity.com/paper/2110.02753/) (2021)
- [Implicit Graphon Neural Representation](https://mlsanity.com/paper/2211.03329/) (2022)
- [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)
- [Fine-tuning Graph Neural Networks by Preserving Graph Generative Patterns](https://mlsanity.com/paper/2312.13583/) (2023)
- [InfiGFusion: Graph-on-Logits Distillation via Efficient Gromov-Wasserstein for Model Fusion](https://mlsanity.com/paper/2505.13893/) (2025)
- [Joint Network Topology Inference via a Shared Graphon Model](https://mlsanity.com/paper/2209.08223/) (2022)
- [A Convergent Single-Loop Algorithm for Relaxation of Gromov-Wasserstein in Graph Data](https://mlsanity.com/paper/2303.06595/) (2023)
- [Scalable Implicit Graphon Learning](https://mlsanity.com/paper/2410.17464/) (2024)
- [Graphon Pooling for Reducing Dimensionality of Signals and Convolutional Operators on Graphs](https://mlsanity.com/paper/2212.08171/) (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)
- [Learning Graphon Autoencoders for Generative Graph Modeling](https://mlsanity.com/paper/2105.14244/) (2021)
- [A Unified Invariant Learning Framework for Graph Classification](https://mlsanity.com/paper/2501.12595/) (2025)
- [Nonparametric Teaching for Graph Property Learners](https://mlsanity.com/paper/2505.14170/) (2025)
- [Prior-Informed Flow Matching for Graph Reconstruction](https://mlsanity.com/paper/2601.22107/) (2026)
- [Private graphon estimation via sum-of-squares](https://mlsanity.com/paper/2403.12213/) (2024)
- [Motif-Consistent Counterfactuals with Adversarial Refinement for Graph-Level Anomaly Detection](https://mlsanity.com/paper/2407.13251/) (2024)
- [HGOE: Hybrid External and Internal Graph Outlier Exposure for Graph Out-of-Distribution Detection](https://mlsanity.com/paper/2407.21742/) (2024)
- [A Few Moments Please: Scalable Graphon Learning via Moment Matching](https://mlsanity.com/paper/2506.04206/) (2025)
- [The Graphon Limit Hypothesis: Understanding Neural Network Pruning via Infinite Width Analysis](https://mlsanity.com/paper/2510.17515/) (2025)
- [Fast and Provably Convergent Algorithms for Gromov-Wasserstein in Graph Data](https://mlsanity.com/paper/2205.08115/) (2022)
- [Transfer Learning on Edge Connecting Probability Estimation under Graphon Model](https://mlsanity.com/paper/2510.05527/) (2025)
- [Hawkes Processes on Graphons](https://mlsanity.com/paper/2102.02741/) (2021)
- [SC-MAD: Mixtures of Higher-order Networks for Data Augmentation](https://mlsanity.com/paper/2309.07453/) (2023)
- [A Deep Learning Method for Optimal Investment Under Relative Performance Criteria Among Heterogeneous Agents](https://mlsanity.com/paper/2402.07365/) (2024)
- [Graph data augmentation with Gromow-Wasserstein Barycenters](https://mlsanity.com/paper/2404.08376/) (2024)
- [The Spectral Barycentre of a Set of Graphs with Community Structure](https://mlsanity.com/paper/2502.00038/) (2025)

## Abstract (arXiv)

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.