Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper tackles the NP-hard problem of estimating the generative mechanisms of large-scale networks by introducing a semi-relaxed Gromov-Wasserstein objective that allows for probabilistic couplings. The authors develop a block-coordinate conditional gradient algorithm to efficiently solve this framework, demonstrating that the optimality gap between the relaxed and deterministic solutions diminishes at a rate of \(O(1/n)\). Their method not only recovers the underlying model effectively but also achieves consistency and minimax-optimal convergence rates for stochastic block models and Holder-smooth graphons, validated on both synthetic and real datasets.
The optimality gap in network structure estimation shrinks at a surprising rate of \(O(1/n)\), enabling efficient recovery of complex generative models.
Estimating the generative mechanism of large-scale networks is a fundamental challenge in statistical machine learning. It requires the identification of the latent connectivity structure, which is in general an NP-hard combinatorial problem due to the absence of canonical node labels. We address this challenge by allowing for probabilistic couplings, thereby relaxing the assignment problem. Our estimation framework can be formulated as a semi-relaxed Gromov-Wasserstein objective and provides a low-dimensional representation of the generative structure. We solve this via a block-coordinate conditional gradient algorithm. Despite the relaxation, the resulting solution is typically deterministic: in fact, we show that the optimality gap between the relaxed solution and the deterministic assignment vanishes at rate $O(1/n)$, where $n$ is the number of nodes. This allows for tractable recovery of the underlying model and enables rigorous statistical analysis: we establish consistency and minimax-optimal convergence rates for both stochastic block models and Holder-smooth graphons. Our implementation scales efficiently with $n$, as demonstrated on both synthetic and real-world datasets.