02/02/2021

Learning Graphons via Structured Gromov-Wasserstein Barycenters

Hongteng Xu, Dixin Luo, Lawrence Carin, Hongyuan Zha

Keywords:

Abstract Paper Similar Papers

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.

The video of this talk cannot be embedded. You can watch it here:
https://slideslive.com/38949064
(Link will open in new window)
 0
 0
 0
 0
  Share    
This is an embedded video. Talk and the respective paper are published at AAAI 2021 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd Characters remaining: 140

Similar Papers

 0
 0
 0
 0
 5:17 
 0
 0
 0
 1
 4:57 
 0
 0
 0
 0
 1:00 
 0
 0
 0
 0
 5:16 
 0
 0
 0
 0
 15:08 
 0
 0
 0
 0
 13:18 
 0
 0
 0
 0
 11:06 
 0
 0
 0
 0
 5:12 
 0
 0
 0
 0
 17:06 
 0
 0
 0
 0
 19:09 
 0
 0
 0
 0
 3:23 
 0
 0
 0
 0
 7:35 
 0
 0
 0
 0
 12:32 
 0
 0
 0
 0
 11:07 
 0
 0
 0
 0
 14:36 
 0
 0
 0
 0
 14:35 
 0
 0
 0
 0
 9:39 
 0
 0
 0
 0
 14:37 
 0
 0
 0
 0
 13:39 
 0
 0
 0
 0
 13:43 
 0
 0
 0
 0
 10:06 
 0
 0
 0
 0
 13:07 
 0
 0
 0
 0
 3:20 
 0
 0
 0
 0
 16:46 
 0
 0
 0
 0
 6:58 
 0
 0
 0
 0
 21:49 
 0
 0
 0
 0
 25:27 
 0
 0
 0
 0
 25:50 
 0
 0
 0
 0
 5:07 
 0
 0
 0
 0
 12:57 
 0
 0
 0
 0
 4:59 
 0
 0
 0
 0
 5:16 
 0
 0
 0
 0
 22:55 
 0
 0
 0
 0
 5:08 
 0
 0
 0
 0
 13:24 
 0
 0
 0
 0
 11:40 
 0
 0
 0
 0
 12:17 
 0
 0
 0
 0
 4:59 
 0
 0
 0
 0
 9:57 
 0
 0
 0
 0
 13:04