Learning Graphons via Structured Gromov-Wasserstein Barycenters

Authors

  • Hongteng Xu Gaoling School of Artificial Intelligence, Renmin University of China Beijing Key Laboratory of Big Data Management and Analysis Methods
  • Dixin Luo School of Computer Science and Technology, Beijing Institue of Technology
  • Lawrence Carin Department of Electrical and Computer Engineering, Duke University
  • Hongyuan Zha School of Data Science, Shenzhen Research Institute of Big Data, The Chinese University of Hong Kong, Shenzhen

Keywords:

Graph-based Machine Learning

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.

Downloads

Published

2021-05-18

How to Cite

Xu, H., Luo, D., Carin, L., & Zha, H. (2021). Learning Graphons via Structured Gromov-Wasserstein Barycenters. Proceedings of the AAAI Conference on Artificial Intelligence, 35(12), 10505-10513. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/17257

Issue

Section

AAAI Technical Track on Machine Learning V