Dirichlet densifier bounds: Densifying beyond the spectral gap constraint
Por favor, use este identificador para citar o enlazar este ítem:
http://hdl.handle.net/10045/93236
Título: | Dirichlet densifier bounds: Densifying beyond the spectral gap constraint |
---|---|
Autor/es: | Curado, Manuel | Lozano, Miguel Angel | Escolano, Francisco | Hancock, Edwin R. |
Grupo/s de investigación o GITE: | Laboratorio de Investigación en Visión Móvil (MVRLab) |
Centro, Departamento o Servicio: | Universidad de Alicante. Departamento de Ciencia de la Computación e Inteligencia Artificial |
Palabras clave: | Graph densification | Commute times | Spectral graph theory |
Área/s de conocimiento: | Ciencia de la Computación e Inteligencia Artificial |
Fecha de publicación: | 1-jul-2019 |
Editor: | Elsevier |
Cita bibliográfica: | Pattern Recognition Letters. 2019, 125: 425-431. doi:10.1016/j.patrec.2019.06.001 |
Resumen: | In this paper, we characterize the universal bounds of our recently reported Dirichlet Densifier. In particular we aim to study the impact of densification on the bounding of intra-class node similarities. To this end we derive a new bound for commute time estimation. This bound does not rely on the spectral gap, but on graph densification (or graph rewiring). Firstly, we explain how our densifier works and we motivate the bound by showing that implicitly constraining the spectral gap through graph densification cannot fully explain the cluster structure in real-world datasets. Then, we pose our hypothesis about densification: a graph densifier can only deal with a moderate degradation of the spectral gap if the inter-cluster commute distances are significantly shrunk. This points to a more detailed bound which explicitly accounts for the shrinking effect of densification. Finally, we formally develop this bound, thus revealing the deeper implications of graph densification in commute time estimation. |
URI: | http://hdl.handle.net/10045/93236 |
ISSN: | 0167-8655 (Print) | 1872-7344 (Online) |
DOI: | 10.1016/j.patrec.2019.06.001 |
Idioma: | eng |
Tipo: | info:eu-repo/semantics/article |
Derechos: | © 2019 Elsevier B.V. |
Revisión científica: | si |
Versión del editor: | https://doi.org/10.1016/j.patrec.2019.06.001 |
Aparece en las colecciones: | INV - MVRLab - Artículos de Revistas |
Archivos en este ítem:
Archivo | Descripción | Tamaño | Formato | |
---|---|---|---|---|
2019_Curado_etal_PatternRecognLett_final.pdf | Versión final (acceso restringido) | 528,65 kB | Adobe PDF | Abrir Solicitar una copia |
2019_Curado_etal_PatternRecognLett_preprint.pdf | Preprint (acceso abierto) | 401,73 kB | Adobe PDF | Abrir Vista previa |
Todos los documentos en RUA están protegidos por derechos de autor. Algunos derechos reservados.