Graph clustering and the nuclear Wasserstein metric
PDF 
VER Citas bibliográficas
Gestores Bibliográficos
Indexadores
Enlace de Referencia
Autores
Autor corporativo
Recolector de datos
Otros/Desconocido
Director audiovisual
Editor/Compilador
Fecha
Resumen
Estudiamos el problema de aprender la estructura de clusters de un grafo aleatorio G usando una muestra independiente. Proponemos una formulación robusta basada en la métrica de Wasserstein de este problema de optimización y probamos que se puede formular como un problema tratable de optmización convexa. Damos garantías teóricas exactas para este problema cuando la métrica de Wasserstein es inducida por la norma nuclear y G se distribuye según el modelo estocástico por bloques. Finalmente presentamos nuestra implementación en Julia del algoritmo propuesto y mostramos su desempeño numérico en datos sintéticos.
Resumen
We study the problem of learning the cluster structure of a random graph G from an independent sample. We propose a Wasserstein robust formulation of this optimization problem and prove that it can be reformulated as a tractable convex optimization problem. We give theoretical exact recovery guarantees for this problem when the Wasserstein metric is induced by the nuclear norm and G is distributed according to the stochastic block model. Finally we present our Julia implementation of the proposed algorithm and show its numerical performance on synthetic data.
