Network Learning with Semi-relaxed Gromov-Wasserstein: graphon estimation is a barycenter problem

Published in NeurIPS 2026, 2026

Sorting the nodes of a large network into a few groups that connect in similar ways is a hard combinatorial problem. We relax it into a semi-relaxed Gromov–Wasserstein (optimal transport) problem, prove that the relaxed solutions are nearly discrete and that the resulting estimator attains minimax-optimal rates, and give a solver that scales to networks with thousands of nodes.

Recommended citation: C. Dufour, U. Naepels and L. V. Santoro, "Network Learning with Semi-relaxed Gromov-Wasserstein: graphon estimation is a barycenter problem", Advances in Neural Information Processing Systems (NeurIPS), 2026.
Download Paper