Odległość edycji wykresu

W matematyce i informatyce odległość edycji wykresu ( GED ) jest miarą podobieństwa ( lub odmienności) między dwoma wykresami . Koncepcja odległości edycji wykresu została po raz pierwszy sformalizowana matematycznie przez Alberto Sanfeliu i King-Sun Fu w 1983 roku. Głównym zastosowaniem odległości edycji wykresu jest niedokładne dopasowanie wykresu, takie jak rozpoznawanie wzorców z tolerancją błędów w uczeniu maszynowym .

Odległość edycji wykresu między dwoma wykresami jest związana z odległością edycji łańcucha między łańcuchami . Przy interpretacji strun jako połączonych , skierowanych grafów acyklicznych o maksymalnym stopniu pierwszym, klasyczne definicje odległości edycji, takie jak odległość Levenshteina , odległość Hamminga i odległość Jaro – Winklera, można interpretować jako odległości edycji grafów między odpowiednio ograniczonymi grafami. Podobnie odległość edycji wykresu jest również uogólnieniem odległości edycji drzewa między ukorzenionymi drzewami .

Definicje i własności formalne

Matematyczna definicja odległości edycyjnej grafu zależy od definicji grafów, na których jest zdefiniowana, tj. czy i jak wierzchołki i krawędzie grafu są oznaczone oraz czy krawędzie są skierowane . Ogólnie rzecz biorąc, biorąc pod $uwagę$ zestaw operacji edycji wykresów (znanych również jako podstawowe operacje na wykresach ), odległość edycji wykresu między dwoma wykresami i zapisana jako $g_ {1}}$${\ Displaystyle GED (g_ {1}, g_ {2})}$ można zdefiniować

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

gdzie ${\ Displaystyle {\ mathcal {P}} (g_ {1}, g_ {2})}$ oznacza zbiór ścieżek edycji przekształcających w ( ${\ Displaystyle g_ {1}}$ wykres izomorficzny z) i $Displaystyle$$\ geq 0}$ to koszt każdej operacji edycji wykresu ${\ displaystyle e}$ .

Zestaw podstawowych operatorów edycji wykresów zazwyczaj obejmuje:

wstawianie wierzchołków w celu wprowadzenia pojedynczego nowego wierzchołka z etykietą do grafu.

usuwanie wierzchołków w celu usunięcia pojedynczego (często niepołączonego) wierzchołka z grafu.

podstawienie wierzchołka w celu zmiany etykiety (lub koloru) danego wierzchołka.

wstawianie krawędzi w celu wprowadzenia nowej kolorowej krawędzi między parą wierzchołków.

usuwanie krawędzi , aby usunąć pojedynczą krawędź między parą wierzchołków.

podstawienie krawędzi w celu zmiany etykiety (lub koloru) danej krawędzi.

Dodatkowe, ale mniej powszechne operatory obejmują operacje, takie jak dzielenie krawędzi , które wprowadza nowy wierzchołek do krawędzi (również tworząc nową krawędź), oraz skracanie krawędzi , które eliminuje wierzchołki drugiego stopnia między krawędziami (tego samego koloru). Chociaż takie złożone operatory edycji można zdefiniować w kategoriach bardziej elementarnych przekształceń, ich $użycie$ umożliwia dokładniejszą parametryzację funkcji kosztu, operator jest tańszy niż suma jego składników.

Głęboka analiza podstawowych operatorów edycji grafu jest przedstawiona w

Przedstawiono również metody automatycznego wyprowadzania tych elementarnych operatorów edycji grafu. Niektóre algorytmy uczą się tych kosztów online:

Aplikacje

Graph edit distance znajduje zastosowanie w rozpoznawaniu pisma ręcznego , rozpoznawaniu linii papilarnych i cheminformatyce .

Algorytmy i złożoność

Dokładne algorytmy obliczania odległości edycji wykresu między parą wykresów zazwyczaj przekształcają problem w znalezienie ścieżki edycji minimalnego kosztu między dwoma wykresami. Obliczenie optymalnej ścieżki edycji jest przedstawiane jako ścieżki lub problem najkrótszej ścieżki , często implementowany jako algorytm wyszukiwania A* .

Oprócz algorytmów dokładnych znanych jest również szereg wydajnych algorytmów aproksymacyjnych. Większość z nich ma sześcienny czas obliczeniowy

Ponadto istnieje algorytm, który dedukuje przybliżenie GED w czasie liniowym

Pomimo tego, że powyższe algorytmy czasami dobrze sprawdzają się w praktyce, generalnie problem obliczania odległości edycji wykresu jest NP-trudny (dowód dostępny online, patrz rozdział 2 Zeng et al. ), a nawet trudny do przybliżenia ( formalnie , jest APX -twardy).