Dirichlet densifier bounds: Densifying beyond the spectral gap constraint
Please use this identifier to cite or link to this item:
http://hdl.handle.net/10045/93236
Title: | Dirichlet densifier bounds: Densifying beyond the spectral gap constraint |
---|---|
Authors: | Curado, Manuel | Lozano, Miguel Angel | Escolano, Francisco | Hancock, Edwin R. |
Research Group/s: | Laboratorio de Investigación en Visión Móvil (MVRLab) |
Center, Department or Service: | Universidad de Alicante. Departamento de Ciencia de la Computación e Inteligencia Artificial |
Keywords: | Graph densification | Commute times | Spectral graph theory |
Knowledge Area: | Ciencia de la Computación e Inteligencia Artificial |
Issue Date: | 1-Jul-2019 |
Publisher: | Elsevier |
Citation: | Pattern Recognition Letters. 2019, 125: 425-431. doi:10.1016/j.patrec.2019.06.001 |
Abstract: | 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 |
Language: | eng |
Type: | info:eu-repo/semantics/article |
Rights: | © 2019 Elsevier B.V. |
Peer Review: | si |
Publisher version: | https://doi.org/10.1016/j.patrec.2019.06.001 |
Appears in Collections: | INV - MVRLab - Artículos de Revistas |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
2019_Curado_etal_PatternRecognLett_final.pdf | Versión final (acceso restringido) | 528,65 kB | Adobe PDF | Open Request a copy |
2019_Curado_etal_PatternRecognLett_preprint.pdf | Preprint (acceso abierto) | 401,73 kB | Adobe PDF | Open Preview |
Items in RUA are protected by copyright, with all rights reserved, unless otherwise indicated.