Graph Similarity through Entropic Manifold Alignment
Por favor, use este identificador para citar o enlazar este ítem:
http://hdl.handle.net/10045/68248
Título: | Graph Similarity through Entropic Manifold Alignment |
---|---|
Autor/es: | Escolano, Francisco | Hancock, Edwin R. | Lozano, Miguel Angel |
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 similarity | Graph matching | Graph embedding | Graph kernels | Nonparametric entropy estimation |
Área/s de conocimiento: | Ciencia de la Computación e Inteligencia Artificial |
Fecha de publicación: | 27-jun-2017 |
Editor: | Society for Industrial and Applied Mathematics |
Cita bibliográfica: | SIAM Journal on Imaging Sciences. 2017, 10(2): 942-978. doi:10.1137/15M1032454 |
Resumen: | In this paper we decouple the problem of measuring graph similarity into two sequential steps. The first step is the linearization of the quadratic assignment problem (QAP) in a low-dimensional space, given by the embedding trick. The second step is the evaluation of an information-theoretic distributional measure, which relies on deformable manifold alignment. The proposed measure is a normalized conditional entropy, which induces a positive definite kernel when symmetrized. We use bypass entropy estimation methods to compute an approximation of the normalized conditional entropy. Our approach, which is purely topological (i.e., it does not rely on node or edge attributes although it can potentially accommodate them as additional sources of information) is competitive with state-of-the-art graph matching algorithms as sources of correspondence-based graph similarity, but its complexity is linear instead of cubic (although the complexity of the similarity measure is quadratic). We also determine that the best embedding strategy for graph similarity is provided by commute time embedding, and we conjecture that this is related to its inversibility property, since the inverse of the embeddings obtained using our method can be used as a generative sampler of graph structure. |
Patrocinador/es: | The work of the first and third authors was supported by the projects TIN2012-32839 and TIN2015-69077-P of the Spanish Government. The work of the second author was supported by a Royal Society Wolfson Research Merit Award. |
URI: | http://hdl.handle.net/10045/68248 |
ISSN: | 1936-4954 |
DOI: | 10.1137/15M1032454 |
Idioma: | eng |
Tipo: | info:eu-repo/semantics/article |
Derechos: | © 2017 Society for Industrial and Applied Mathematics |
Revisión científica: | si |
Versión del editor: | http://dx.doi.org/10.1137/15M1032454 |
Aparece en las colecciones: | INV - MVRLab - Artículos de Revistas |
Archivos en este ítem:
Archivo | Descripción | Tamaño | Formato | |
---|---|---|---|---|
2017_Escolano_etal_SIAMJImagingSci.pdf | 6,33 MB | Adobe PDF | Abrir Vista previa | |
Todos los documentos en RUA están protegidos por derechos de autor. Algunos derechos reservados.