Problem izomorfizmu grafów dla grafów znakowanych

W przypadku grafów nieznakowanych problemem izomorfizmu grafów można zająć się szeregiem algorytmów, które działają bardzo dobrze w praktyce. Oznacza to, że chociaż najgorszy przypadek czasu działania jest wykładniczy, zwykle ma on czas działania wielomianowego.

Miałem nadzieję, że sytuacja jest podobna w przypadku wykresów oznaczonych. Jednak naprawdę ciężko mi znaleźć jakiekolwiek odniesienie, które proponuje „praktycznie wydajny” algorytm.

Uwaga: W tym przypadku wymagamy, aby izomorfizm zachował etykiety. Oznacza to, że izomorfizm między dwoma skończonymi terminami automat / algebra procesów oznaczałby, że automaty / terminy są w zasadzie „równe aż do zmiany nazwy węzłów”.

Jedyne odniesienie, które znalazłem, to ten z Wikipedii, który stwierdza, że problem izomorfizmu wykresów znakowanych można wielomianowo zredukować do problemu zwykłych wykresów. Podstawowy artykuł dotyczy jednak bardziej teorii złożoności niż praktycznych algorytmów.

Coś mi brakuje, czy też tak naprawdę nie ma wydajnych algorytmów „heurystycznych” decydujących o tym, czy dwa oznaczone wykresy są izomorficzne?

Każda podpowiedź lub odniesienie byłoby świetne.

algorithms graph-theory graph-isomorphism

— Max
źródło

Byłoby miło podać odniesienia do artykułu w Wikipedii i znalezionego papieru, aby zaoszczędzić nam kłopotów.

— babou

Co rozumiesz przez izomorfizm, który „zachowuje etykiety”? W kontekście automatu etykiety wierzchołków są różne. Dlatego każdy izomorfizm w sposób trywialny „zachowuje etykiety” w tym sensie, że dwa wierzchołki w źródle, które mają różne etykiety, również muszą mieć różne etykiety na obrazie. Ten problem jest identyczny jak zwykły problem z izomorfizmem grafowym. Jeśli masz na myśli, że izomorfizm musi odwzorować wierzchołek na jeden z tą samą etykietą, algorytm jest trywialny, gdy etykiety wierzchołków są zawsze odrębne: po prostu sprawdź, czy mapa tożsamości na etykietach jest izomorfizmem.

— David Richerby

Jeśli masz na myśli przypadek, w którym kilka wierzchołków może mieć tę samą etykietę, a obraz wierzchołka musi mieć tę samą etykietę, co oryginalna, jest to często nazywane izomorfizmami między kolorowymi wykresami . W takim przypadku istnieje prosta redukcja ogólnego GI poprzez zastąpienie kolorów gadżetami. Prawdopodobnie można uzyskać przyzwoity praktyczny algorytm, stosując starannie wybrane gadżety, a następnie stosując standardowy algorytm GI.

— David Richerby

Czy naprawdę nie chcesz uważać dwóch digraphów oznaczonych krawędziami za izomorficzne, jeśli istnieje zwykły izomorfizm digrafa, który zachowuje również klasy równoważności etykiet? W twoim przykładzie, biorąc pod uwagę, że oba są FA, języki akceptowane przez

, chociaż różne (być może), są tak naprawdę tylko homorficznymi obrazami siebie przez podstawienia

S^{*}

$S^*$

S^{'}

$S'$

a \leftrightarrow c, b \leftrightarrow d

$a\leftrightarrow c, b\leftrightarrow d$

— Rick Decker,

Problem jest trywialnie kompletny (wystarczy wybrać wykres, na którym wszystkie krawędzie mają tę samą etykietę). Aby pokazać, że nie twardsza niż wykres izomorfizmie, zbudować 1: 1 Mapa z etykiety do liczb (

I dodanie w środku każdej krawędzi oznaczonego symbol

pełny wykres na wierzchołkach

(

g : a \to 1, b \to 2, c \to 3, . . .)

$g : a\to 1, b \to 2, c \to 3, ...)$

s

$s$

g (s)

$g(s)$

K_{g (s)}

$K_{g(s)}$ ) oraz dodatkowy węzeł po stronie strzałki krawędzi. Powstałe wykresy są izomorficzne wtedy i tylko wtedy, gdy oryginalne automaty są izomorficzne.

— Vor

Odpowiedzi:

Ten artykuł może Cię zainteresować:

Aidan Hogan: Skolemizacja pustych węzłów przy jednoczesnym zachowaniu izomorfizmu. WWW 2015: 430–440

Ma algorytm (oparty na Nauty) do testowania izomorfizmu grafów RDF, które są zasadniczo ukierunkowanymi grafami oznaczonymi, które mogą zawierać stałe etykiety. Algorytm uwzględnia etykiety w celu zawężenia przestrzeni wyszukiwania.

Jeśli możesz przedstawić swój wykres wejściowy jako wykres RDF, możesz spróbować użyć powiązanego pakietu oprogramowania „ blabel” do przetestowania izomorfizmu.

— badroit
źródło

Dowiedziałem się, że algorytm należy do kategorii algorytmów Weisfeiler-Lehman w wymiarze k-wymiaru i zawodzi przy zwykłych grafach. Aby uzyskać więcej tutaj:

http://dabacon.org/pontiff/?p=4148

Oryginalny post:

Wiele lat temu stworzyłem prosty i elastyczny algorytm dla dokładnie tego problemu (izomorfizm wykresu z etykietami).

Nazwałem go „Powerhash”, a aby stworzyć algorytm, potrzebowałem dwóch informacji. Pierwszym z nich jest algorytm wykresu iteracji mocy, również używany w PageRank. Druga to możliwość zastąpienia funkcji wewnętrznego kroku iteracji mocy wszystkim, co chcemy. Zastąpiłem go funkcją, która wykonuje następujące czynności dla każdej iteracji i dla każdego węzła:

Posortuj skróty (z poprzedniej iteracji) sąsiadów węzła
Hash połączonych sortowanych skrótów
Zamień skrót węzła na nowo obliczony skrót

W pierwszym kroku na skrót węzła wpływają jego bezpośredni sąsiedzi. W drugim kroku na skrót węzła wpływ ma sąsiedztwo oddalone od niego o 2 przeskoki. Na piątym kroku na skrót węzła będą miały wpływ otaczające go skoki sąsiedztwa. Musisz więc tylko kontynuować Powerhash dla kroków N = graph_radius. Ostatecznie cały skrót ma wpływ na wartość skrótu węzła centrum wykresu.

Aby utworzyć końcowy skrót, posortuj skróty węzłów ostatniego kroku i połącz je razem. Następnie możesz porównać końcowe wartości skrótu, aby sprawdzić, czy dwa wykresy są izomorficzne. Jeśli masz etykiety, dodaj je (podczas pierwszej iteracji) do skrótów wewnętrznych obliczanych dla każdego węzła.

Więcej informacji na ten temat można znaleźć tutaj:

https://plus.google.com/114866592715069940152/posts/fmBFhjhQcZF

Powyższy algorytm został zaimplementowany w funkcjonalnej relacyjnej bazie danych „madIS”. Kod źródłowy algorytmu można znaleźć tutaj:

https://github.com/madgik/madis/blob/master/src/functions/aggregate/graph.py

— estama
źródło

Tylko ostrzeżenie, że twój algorytm jest wielomianowy, więc jeśli jest kompletny, właśnie rozwiązałeś od dawna otwarty problem w CS dotyczący GI w P. :) (Istnieją różne przypadki, w których opisany algorytm daje fałszywie pozytywne wyniki .)

— badroit

Algorytm jest przybliżony i na pewno nie jest kompletny (mówię to również w poście na blogu). Powodem, dla którego działa, jest to, że tworzone przez nią skróty są ogromne, więc w bazie danych zawierającej nawet miliony wykresów prawdopodobieństwo fałszywie dodatnich kolizji skrótu będzie nieskończenie małe. Jeśli uda Ci się znaleźć przypadek fałszywie pozytywnej kolizji skrótu, bardzo chciałbym o tym wiedzieć. Powodem (przy użyciu skrótów kryptograficznych) jest to, że udało ci się „złamać” funkcję skrótu kryptograficznego.

— estama 30.04.17

Aby wyjaśnić, jak nieskończenie mała jest możliwość kolizji skrótu. Uważam, że kryptograficzny skrót 256 bitów jest więcej niż wystarczający, aby mieć pewność, że wszystkie różne pliki świata nie mają takiego samego wyniku (git na przykład używa SHA-1, który ma 160 bitów, aby to zagwarantować). Hash z Powerhash będzie wynosił 128 bitów * graph_node_count (używając skrótu MD5). Tak więc praktycznie nigdy nie będziesz w stanie stworzyć wystarczającej liczby wykresów (w tym wszechświecie), aby znaleźć między nimi zderzenie mieszające.

— estama 30.04.17

Miałem na myśli, że twój algorytm da fałszywe alarmy, nawet przy założeniu braku kolizji skrótu. W literaturze zaproponowano wiele algorytmów wielomianowych dla izomorfizmu grafowego i wszystkie dają fałszywie pozytywne wyniki. Powiązane pytanie tutaj: cs.stackexchange.com/questions/50939/... .

— badroit

Dziękuję za dyskusję. Po dalszych badaniach odkryłem, że powyższy algorytm należy do kategorii algorytmów Weisfeiler-Lehman w wymiarze k i nie udaje się to w przypadku zwykłych wykresów. Więcej tutaj: dabacon.org/pontiff/?p=4148

— estama