Distancia de edición del gráfico

En matemáticas y ciencias de la computación , la distancia de edición de grafos ( GED ) es una medida de similitud (o disimilitud) entre dos grafos . El concepto de distancia de edición de grafos fue formalizado matemáticamente por primera vez por Alberto Sanfeliu y King-Sun Fu en 1983. ^[1] Una aplicación importante de la distancia de edición de grafos es la correspondencia inexacta de grafos , como el reconocimiento de patrones tolerante a errores en el aprendizaje automático . ^[2]

La distancia de edición de grafos entre dos grafos está relacionada con la distancia de edición de cadenas entre cadenas . Con la interpretación de las cadenas como grafos acíclicos dirigidos y conexos de máximo grado uno, las definiciones clásicas de distancia de edición como la distancia de Levenshtein , ^{[3] [4]} la distancia de Hamming ^[5] y la distancia de Jaro-Winkler pueden interpretarse como distancias de edición de grafos entre grafos adecuadamente restringidos. Asimismo, la distancia de edición de grafos también es una generalización de la distancia de edición de árboles entre árboles enraizados . ^{[6] [7] [8] [9]}

Definiciones formales y propiedades

La definición matemática de la distancia de edición de gráficos depende de las definiciones de los gráficos sobre los que se define, es decir, si los vértices y los bordes del gráfico están etiquetados y cómo lo están , y si los bordes están dirigidos . En general, dado un conjunto de operaciones de edición de gráficos (también conocidas como operaciones de gráficos elementales ), la distancia de edición de gráficos entre dos gráficos y , escrita como , se puede definir como ${\displaystyle g_{1}}$ ${\displaystyle g_{2}}$ ${\displaystyle GED(g_{1},g_{2})}$

${\displaystyle GED(g_{1},g_{2})=\min _{(e_{1},...,e_{k})\in {\mathcal {P}}(g_{1},g_{2})}\sum _{i=1}^{k}c(e_{i})}$

donde denota el conjunto de rutas de edición que se transforman en (un gráfico isomorfo a) y es el costo de cada operación de edición de gráfico . ${\displaystyle {\mathcal {P}}(g_{1},g_{2})}$ ${\displaystyle g_{1}}$ ${\displaystyle g_{2}}$ ${\displaystyle c(e)\geq 0}$ ${\displaystyle e}$

El conjunto de operadores de edición de gráficos elementales normalmente incluye:

inserción de vértice para introducir un único vértice nuevo etiquetado en un gráfico.

eliminación de vértice para eliminar un solo vértice (a menudo desconectado) de un gráfico.

sustitución de vértices para cambiar la etiqueta (o color) de un vértice dado.

inserción de arista para introducir una nueva arista coloreada entre un par de vértices.

eliminación de arista para eliminar una sola arista entre un par de vértices.

sustitución de borde para cambiar la etiqueta (o color) de un borde determinado.

Otros operadores menos comunes son las operaciones de división de aristas , que introduce un nuevo vértice en una arista (lo que crea una nueva arista), y la contracción de aristas , que elimina los vértices de grado dos entre aristas (del mismo color). Aunque estos operadores de edición complejos se pueden definir en términos de transformaciones más elementales, su uso permite una parametrización más precisa de la función de costo cuando el operador es más económico que la suma de sus componentes. ${\displaystyle c}$

^{En [10] [11] [12]} se presenta un análisis profundo de los operadores de edición de gráficos elementales.

Y se han presentado algunos métodos para deducir automáticamente estos operadores elementales de edición de gráficos. ^{[13] [14] [15] [16] [17]} Y algunos algoritmos aprenden estos costos en línea: ^[18]

Aplicaciones

La distancia de edición de gráficos encuentra aplicaciones en el reconocimiento de escritura a mano , ^[19] reconocimiento de huellas dactilares ^[20] y quimioinformática . ^[21]

Algoritmos y complejidad

Los algoritmos exactos para calcular la distancia de edición de gráficos entre un par de gráficos generalmente transforman el problema en uno de encontrar la ruta de edición de costo mínimo entre los dos gráficos. El cálculo de la ruta de edición óptima se plantea como una búsqueda de ruta o un problema de ruta más corta , a menudo implementado como un algoritmo de búsqueda A* .

Además de los algoritmos exactos, también se conocen varios algoritmos de aproximación eficientes. La mayoría de ellos tienen un tiempo de cálculo cúbico ^{[22] [23] [24] [25] [26]}

Además, existe un algoritmo que deduce una aproximación del GED en tiempo lineal ^[27]

A pesar de que los algoritmos anteriores a veces funcionan bien en la práctica, en general el problema de calcular la distancia de edición de gráficos es NP-difícil (para una prueba disponible en línea, consulte la Sección 2 de Zeng et al.), e incluso es difícil de aproximar (formalmente, es APX -difícil ^[28] ).

Referencias

1. Sanfeliu, Alberto; Fu, King-Sun (1983). "Una medida de distancia entre gráficos relacionales atribuidos para el reconocimiento de patrones". IEEE Transactions on Systems, Man, and Cybernetics . 13 (3): 353–363. doi :10.1109/TSMC.1983.6313167. S2CID  1087693.
2. Gao, Xinbo; Xiao, Bing; Tao, Dacheng; Li, Xuelong (2010). "Un estudio de la distancia de edición de gráficos". Análisis de patrones y aplicaciones . 13 : 113–129. doi :10.1007/s10044-008-0141-y.
3. Влади́мир И. Levènstein (1965). Двоичные коды с исправлением выпадений, вставок и замещений символов[Códigos binarios capaces de corregir eliminaciones, inserciones y reversiones]. Доклады Академий Наук СССР (en ruso). 163 (4): 845–848.
4. Levenshtein, Vladimir I. (febrero de 1966). "Códigos binarios capaces de corregir eliminaciones, inserciones e inversiones". Soviet Physics Doklady . 10 (8): 707–710.
5. Hamming, Richard W. (1950). "Códigos de detección y corrección de errores" (PDF) . Bell System Technical Journal . 29 (2): 147–160. doi :10.1002/j.1538-7305.1950.tb00463.x. hdl :10945/46756. MR  0035935. S2CID  61141773. Archivado desde el original el 25 de mayo de 2006.{{cite journal}}: CS1 maint: bot: estado de URL original desconocido ( enlace )
6. Shasha, D; Zhang, K (1989). "Algoritmos rápidos y sencillos para la distancia de edición entre árboles y problemas relacionados". SIAM J. Comput. 18 (6): 1245–1262. CiteSeerX 10.1.1.460.5601 . doi :10.1137/0218082. S2CID  10970317.  
7. Zhang, K (1996). "Una distancia de edición restringida entre árboles etiquetados no ordenados". Algorithmica . 15 (3): 205–222. doi :10.1007/BF01975866. S2CID  20043881.
8. Bille, P (2005). "Un estudio sobre la distancia de edición de los árboles y problemas relacionados". Theor. Comput. Sci. 337 (1–3): 22–34. CiteSeerX 10.1.1.100.2577 . doi : 10.1016/j.tcs.2004.12.030 .  
9. Demaine, Erik D .; Mozes, Shay; Rossman, Benjamin; Weimann, Oren (2010). "Un algoritmo de descomposición óptimo para la distancia de edición de árboles". ACM Transactions on Algorithms . 6 (1): A2. arXiv : cs/0604037 . CiteSeerX 10.1.1.163.6937 . doi :10.1145/1644015.1644017. MR  2654906. S2CID  7878119. 
10. Serratosa, Francesc (2021). Redefiniendo la distancia de edición de gráficos . SN Computer Science, pp: 2-438.
11. Serratosa, Francesc (2019). Distancia de edición de grafos: restricciones para ser una métrica . Pattern Recognition, 90, pp: 250-256.
12. Serratosa, Francesc; Cortés, Xavier (2015). Distancia de edición de grafos: pasar de la estructura global a la local para resolver el problema de correspondencia de grafos . Pattern Recognition Letters, 65, pp: 204-210.
13. Santacruz, Pep; Serratosa, Francesc (2020). Aprendizaje de los costes de edición de grafos basado en un modelo de aprendizaje aplicado al emparejamiento de grafos subóptimos . Neural Processing Letters, 51, pp: 881–904.
14. Algabli, Shaima; Serratosa, Francesc (2018). Incorporación de las asignaciones de nodo a nodo para aprender los parámetros de distancia de edición de grafos . Pattern Recognition Letters, 112, pp: 353-360.
15. Xavier, Cortés; Serratosa, Francesc (2016). Aprendizaje de pesos de sustitución de correspondencia de grafos basados ​​en la correspondencia de nodos de verdad fundamental . Revista internacional de reconocimiento de patrones e inteligencia artificial, 30(2), pp: 1650005 [22 páginas].
16. Xavier, Cortés; Serratosa, Francesc (2015). Aprendizaje de costes de edición de correspondencia de grafos en función de la optimalidad de las correspondencias entre nodos del oráculo . Pattern Recognition Letters, 56, pp: 22 - 29.
17. Conte, Donatello; Serratosa, Francesc (2020). Aprendizaje interactivo en línea para la asociación de grafos mediante estrategias activas . Knowledge Based Systems, 105, pp: 106-275.
18. Rica, Elena; Álvarez, Susana; Serratosa, Francesc (2021). Aprendizaje en línea del gráfico editar costos de distancia . Cartas de reconocimiento de patrones, 146, págs: 52-62.
19. Fischer, Andrés; Suen, Ching Y.; Friken, Volkmar; Riesen, Caspar; Bunke, Horst (2013), "Un algoritmo de coincidencia rápida para el reconocimiento de escritura a mano basado en gráficos", Representaciones basadas en gráficos en el reconocimiento de patrones , Apuntes de conferencias sobre informática , vol. 7877, págs. 194–203, doi :10.1007/978-3-642-38221-5_21, ISBN 978-3-642-38220-8
20. Neuhaus, Michel; Bunke, Horst (2005), "Un enfoque basado en la correspondencia de gráficos para la clasificación de huellas dactilares utilizando varianza direccional", Autenticación biométrica de personas basada en audio y video , Lecture Notes in Computer Science , vol. 3546, págs. 191–200, doi :10.1007/11527923_20, ISBN 978-3-540-27887-0
21. Birchall, Kristian; Gillet, Valerie J.; Harper, Gavin; Pickett, Stephen D. (enero de 2006). "Entrenamiento de medidas de similitud para actividades específicas: aplicación a gráficos reducidos". Revista de información y modelado químico . 46 (2): 557–586. doi :10.1021/ci050465e. PMID  16562986.
22. Neuhaus, Michel; Bunke, Horst (noviembre de 2007). Salvando la brecha entre la distancia de edición de gráficos y las máquinas de núcleo . Percepción de máquinas e inteligencia artificial. Vol. 68. World Scientific. ISBN 978-9812708175.
23. Riesen, Kaspar (febrero de 2016). Reconocimiento de patrones estructurales con distancia de edición de gráficos: algoritmos de aproximación y aplicaciones . Avances en visión artificial y reconocimiento de patrones. Springer. ISBN 978-3319272511.
24. Serratosa, Francesc (2014). Cálculo rápido de correspondencia de grafos bipartitos . Pattern Recognition Letters, 45, pp: 244 - 250.
25. Serratosa, Francesc (2015). Aceleración del emparejamiento rápido de grafos bipartitos mediante una nueva matriz de costes . Revista Internacional de Reconocimiento de Patrones e Inteligencia Artificial, 29 (2), 1550010, [17 páginas].
26. Serratosa, Francesc (2015). Cálculo de la distancia de edición de grafos: razonamiento sobre optimalidad y aceleración . Image and Vision Computing, 40, pp: 38-48.
27. Santacruz, Pep; Serratosa, Francesc (2018). Emparejamiento de grafos tolerante a errores en un coste computacional lineal utilizando un pequeño emparejamiento parcial inicial . Letras de reconocimiento de patrones.
28. Lin, Chih-Long (25 de agosto de 1994). "Dificultad de aproximación del problema de transformación de grafos". En Du, Ding-Zhu; Zhang, Xiang-Sun (eds.). Algoritmos y computación . Apuntes de clase en informática. Vol. 834. Springer Berlin Heidelberg. págs. 74–82. doi :10.1007/3-540-58325-4_168. ISBN. 9783540583257.