Title: Network Learning via Semi-relaxed Gromov-Wasserstein

Abstract:

A core hurdle in statistical machine learning is estimating the generative mechanisms of large-scale networks. This process necessitates uncovering the latent connectivity structure, a task that is typically an NP-hard combinatorial problem because canonical node labels are often missing. To overcome this obstacle, we introduce probabilistic couplings, which effectively relax the traditional assignment problem. This approach allows us to frame our estimation framework as a semi-relaxed Gromov-Wasserstein objective, yielding a low-dimensional representation of the generative structure. We address this optimization using a block-coordinate conditional gradient algorithm. Although we employ relaxation, the final solution is usually deterministic. Specifically, we demonstrate that the optimality gap between the relaxed solution and the deterministic assignment diminishes at a rate of $O(1/n)$, with $n$ representing the number of nodes. This property facilitates the tractable recovery of the underlying model and supports rigorous statistical analysis. We prove consistency and establish minimax-optimal convergence rates for both Holder-smooth graphons and stochastic block models. Furthermore, our implementation demonstrates efficient scalability with respect to $n$, as validated on both synthetic and real-world datasets.

Source: arXiv Generated at: 2026-06-02 00:00:00 UTC