Grafredigeringsavstånd

Grafredigeringsavståndet är koefficienten för likhet (eller olikhet) mellan två grafer . Begreppet grafredigeringsavstånd formulerades först matematiskt av Alberto Sanfeliu och King-San Fu 1983 [1] . Den huvudsakliga tillämpningen av grafredigeringsavstånd är i inexakt grafmatchning , såsom robust mönsterigenkänning i maskininlärning [2] .

Grafredigeringsavståndet mellan två grafer är relaterat till redigeringsavståndet mellan rader . Vid tolkning av sänkor som kopplade riktade acykliska grafer med en maximal grad av två, kan de klassiska definitionerna av redigeringsavstånd, som Levenshtein-avstånd [3] , Hamming-avstånd [4] och Jaro-Winkler-avstånd , tolkas som grafredigeringsavstånd mellan lämpliga grafer. På liknande sätt är grafredigeringsavstånd en generalisering av trädredigeringsavstånd mellan rotade träd [5] [6] [7] [8] .

Formella definitioner och egenskaper

Den matematiska definitionen av grafredigeringsavståndet beror på definitionen av de grafer för vilka avståndet är definierat. Det beror till exempel på om och hur grafens hörn och kanter är märkta , och även på om grafen är riktad . I allmänhet, givet en uppsättning grafredigeringsoperationer (även känd som elementära grafoperationer ), kan grafredigeringsavståndet mellan två grafer och skrivs som , definieras som ${\displaystyle g_{1))$ ${\displaystyle g_{2))$ $GED(g_{1},g_{2})$

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

där betyder uppsättningen av transformationsvägar till ( isomorfisk till grafen) , och är lika med kostnaden för varje redigeringsåtgärd . ${\mathcal {P}}(g_{1},g_{2})$ ${\displaystyle g_{1))$ ${\displaystyle g_{2))$ $c(e)\geqslant 0$ $e$

Uppsättningen av elementära grafoperationer inkluderar vanligtvis:

vertex infogning — en ny märkt vertex infogas i grafen. vertexborttagning — en (ofta orelaterade) vertex tas bort från grafen. ersätta en vertex - ändra etiketten (eller färgen) för en given vertex. kantinsättning — en ny färgad kant infogas i grafen mellan ett par hörn. kantborttagning — borttagning av en kant mellan ett par hörn. kantsubstitution - ändra etiketten (eller färgen) för en given kant.

Dessutom, men mer sällan, operationer som att dela en kant , som infogar en ny vertex i en kant (vilket resulterar i två kanter), och att krympa en kant , vilket tar bort en vertex av grad två mellan kanterna (av samma färg) medan sammanslagning av de två kanterna ingår i en. Även om sådana komplexa operationer kan definieras i termer av enklare transformationer, tillåter deras användning en bättre parametrisering av kostnadsfunktionen när operatören är billigare än summan av dess delar. $c$

Applikationer

Grafredigeringsavstånd har applikationer inom handskriftsigenkänning [9] , fingeravtrycksigenkänning [10] och kemoinformatik [11] .

Algoritmer och komplexitet

Exakta algoritmer för att beräkna grafredigeringsavståndet mellan ett par grafer omvandlar vanligtvis problemet till ett problem att hitta den minsta transformationsvägen mellan två grafer. Att beräkna den optimala redigeringsvägen reduceras till sökvägssökning eller det kortaste vägproblemet , ofta implementerat som A*-sökalgoritmen .

Förutom exakta algoritmer är många effektiva approximationsalgoritmer kända [12] [13] .

Även om ovanstående algoritmer ibland fungerar bra i praktiken, i allmänhet är problemet med att beräkna redigeringsavståndet för en graf NP-komplett [14] (ett bevis på detta finns tillgängligt i avsnitt 2 på Zeng et al.s webbplats ) och till och med svårt att uppskatta (formellt är det APX -hårt [15] ).

Anteckningar

↑ Sanfeliu, Fu, 1983 , sid. 353–363.
↑ Gao, Xiao, Tao, Li, 2010 , sid. 113-129.
↑ Levenshtein, 1965 , sid. 845–848.
↑ Hamming, 1950 , sid. 147–160.
↑ Shasha och Zhang 1989 , sid. 1245–1262.
↑ Zhang, 1996 , sid. 205–222.
↑ Bille, 2005 , sid. 22–34.
↑ Demaine, Mozes, Rossman, Weimann, 2010 , sid. A2.
↑ Fischer, Suen, Frinken, Riesen, Bunke, 2013 , sid. 194–203.
↑ Neuhaus, Bunke, 2005 , sid. 191–200.
↑ Birchall, Gillet, Harper, Pickett, 2006 , sid. 557–586.
↑ Neuhaus, Bunke, 2007 .
↑ Riesen, 2016 .
↑ Garey, Johnson, 1979 .
↑ Lin, 1994 , sid. 74–82.

Litteratur

Alberto Sanfeliu, King-Sun Fu. Ett avståndsmått mellan tillskrivna relationsgrafer för mönsterigenkänning // IEEE Transactions on Systems, Man and Cybernetics . - 1983. - T. 13 , nr. 3 . — S. 353–363 . - doi : 10.1109/TSMC.1983.6313167 .
Xinbo Gao, Bing Xiao, Dacheng Tao, Xuelong Li. En undersökning av grafredigeringsavstånd // Mönsteranalys och tillämpningar. - 2010. - T. 13 . — s. 113–129 . - doi : 10.1007/s10044-008-0141-y .
Vladimir I. Levenshtein. Binära koder med korrigering av raderingar, infogningar och ersättningar av symboler // Rapporter från CCCP:s vetenskapsakademier. - 1965. - T. 163 , nr. 4 . — S. 845–848 .
Richard W. Hamming. Feldetektering och felkorrigeringskoder // Bell System Technical Journal . - 1950. - T. 29 , nr. 2 . — S. 147–160 . - doi : 10.1002/j.1538-7305.1950.tb00463.x . Arkiverad från originalet den 25 maj 2006.
Shasha D., Zhang K. Enkla snabba algoritmer för redigeringsavståndet mellan träd och relaterade problem // SIAM J. Comput. . - 1989. - T. 18 , nr 6 . - S. 1245-1262 . - doi : 10.1137/0218082 .
Zhang K. Ett begränsat redigeringsavstånd mellan oordnade märkta träd // Algorithmica . - 1996. - T. 15 , nr 3 . — S. 205–222 . - doi : 10.1007/BF01975866 .
Bille P. En undersökning om trädredigeringsavstånd och relaterade problem // Theor. Comput. sci. . - 2005. - T. 337 , nr. 1–3 . — S. 22–34 . - doi : 10.1016/j.tcs.2004.12.030 .
Erik D. Demaine, Shay Mozes, Benjamin Rossman, Oren Weimann. En optimal nedbrytningsalgoritm för trädredigeringsavstånd // ACM Transactions on Algorithms . - 2010. - T. 6 , nr. 1 . - S. A2 . - doi : 10.1145/1644015.1644017 .
Andreas Fischer, Ching Y. Suen, Volkmar Frinken, Kaspar Riesen, Horst Bunke. En snabb matchande algoritm för grafbaserad handskriftsigenkänning // Grafbaserade representationer i mönsterigenkänning. - 2013. - T. 7877. - S. 194-203. — ( Lecture Notes in Computer Science ). — ISBN 978-3-642-38220-8 . - doi : 10.1007/978-3-642-38221-5_21 .
Michel Neuhaus, Horst Bunke. En grafmatchningsbaserad metod för fingeravtrycksklassificering med hjälp av riktningsvarians // ljud- och videobaserad biometrisk personautentisering. - 2005. - T. 3546. - S. 191-200. — ( Lecture Notes in Computer Science ). — ISBN 978-3-540-27887-0 . - doi : 10.1007/11527923_20 .
Kristian Birchall, Valerie J. Gillet, Gavin Harper, Stephen D. Pickett. Utbildningslikhetsåtgärder för specifika aktiviteter: Tillämpning på reducerade grafer // Journal of Chemical Information and Modeling . - 2006. - Januari ( vol. 46 , nr 2 ). — S. 557–586 . - doi : 10.1021/ci050465e . — PMID 16562986 .
Michel Neuhaus, Horst Bunke. Överbrygga gapet mellan grafredigeringsavstånd och kärnmaskiner. - World Scientific, 2007. - V. 68. - (Maskinuppfattning och artificiell intelligens). — ISBN 978-9812708175 .
Kaspar Riesen. Strukturell mönsterigenkänning med grafredigeringsavstånd: Approximationsalgoritmer och applikationer. - Springer, 2016. - (Framsteg inom datorseende och mönsterigenkänning). — ISBN 978-3319272511 .
Garey MR, Johnson DS Computers and Intractability: A Guide to the Theory of NP-Completeness . - W.H. Freeman and Company, 1979. - ISBN 978-0-7167-1045-5 .
Chih Long Lin. Hårdhet för approximativt graftransformationsproblem // Algoritmer och beräkningar / Ding-Zhu Du, Xiang-Sun Zhang. - Springer Berlin Heidelberg, 1994. - T. 834. - (Lecture Notes in Computer Science). — ISBN 9783540583257 . - doi : 10.1007/3-540-58325-4_168 .