Graphisomorphismusproblem für beschriftete Graphen

Im Fall von unbeschrifteten Graphen kann das Graphisomorphismusproblem durch eine Reihe von Algorithmen gelöst werden, die in der Praxis sehr gut funktionieren. Das heißt, obwohl die Laufzeit im ungünstigsten Fall exponentiell ist, hat man normalerweise eine polynomielle Laufzeit.

Ich hatte gehofft, dass die Situation bei beschrifteten Grafiken ähnlich ist. Es fällt mir jedoch sehr schwer, eine Referenz zu finden, die einen "praktisch effizienten" Algorithmus vorschlägt.

Anmerkung: Hier benötigen wir, dass der Isomorphismus die Markierungen beibehält. Das heißt, ein Isomorphismus zwischen zwei endlichen Automaten / Prozessalgebra-Begriffen würde bedeuten, dass die Automaten / Begriffe im Wesentlichen "bis zur Umbenennung der Knoten gleich" sind.

Die einzige Referenz, die ich gefunden habe, war die in Wikipedia, die besagt, dass das Isomorphismusproblem von markierten Graphen polynomiell auf das von gewöhnlichen Graphen reduziert werden kann. In der zugrunde liegenden Arbeit geht es jedoch mehr um Komplexitätstheorie als um praktische Algorithmen.

Mir fehlt etwas, oder ist es wirklich so, dass es keine effizienten "heuristischen" Algorithmen gibt, um zu entscheiden, ob zwei beschriftete Graphen isomorph sind?

Jeder Hinweis oder Hinweis wäre großartig.

algorithms graph-theory graph-isomorphism Max
quelle

Es wäre schön, Verweise auf den Wikipedia-Artikel und das gefundene Papier zu geben, um uns die Mühe zu ersparen.

Babou

Was meinst du mit einem Isomorphismus, der "die Etiketten bewahrt"? Im Kontext eines Automaten sind die Scheitelpunktbeschriftungen unterschiedlich. Daher "bewahrt" jeder Isomorphismus trivial "Beschriftungen" in dem Sinne, dass zwei Scheitelpunkte in der Quelle, die unterschiedliche Beschriftungen haben, auch unterschiedliche Beschriftungen im Bild haben müssen. Dieses Problem ist identisch mit dem gewöhnlichen Isomorphismusproblem des Graphen. Wenn Sie meinen, dass der Isomorphismus einen Scheitelpunkt einem mit derselben Bezeichnung zuordnen muss, ist der Algorithmus trivial, wenn Scheitelpunktbeschriftungen immer unterschiedlich sind: Überprüfen Sie einfach, ob die Identitätszuordnung auf den Beschriftungen ein Isomorphismus ist.

David Richerby

Wenn Sie den Fall betrachten möchten, in dem mehrere Scheitelpunkte dieselbe Beschriftung haben können und das Bild eines Scheitelpunkts dieselbe Beschriftung wie das Original haben muss, wird dies häufig als Isomorphismus zwischen farbigen Graphen bezeichnet . In diesem Fall wird der allgemeine GI einfach reduziert, indem die Farben durch Gadgets ersetzt werden. Sie könnten wahrscheinlich einen anständigen praktischen Algorithmus erhalten, indem Sie sorgfältig ausgewählte Gadgets anwenden und dann einen Standard-GI-Algorithmus verwenden.

David Richerby

Sind Sie wirklich nicht bereit, zwei kantenbeschriftete Digraphen als isomorph zu betrachten, wenn es einen gewöhnlichen Digraphenisomorphismus gibt, der auch Äquivalenzklassen von Beschriftungen beibehält? Wenn Sie in Ihrem Beispiel die beiden als FAs betrachten, sind die von

und

akzeptierten Sprachen , obwohl sie (vielleicht) unterschiedlich sind, wirklich nur homorphe Bilder voneinander durch die Substitutionen

S^{*}

$S^*$

S^{'}

$S'$

a \leftrightarrow c, b \leftrightarrow d

$a\leftrightarrow c, b\leftrightarrow d$

Rick Decker

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)}$ ) plus einen zusätzlichen Knoten auf der Pfeilseite der Kante. Die resultierenden Graphen sind genau dann isomorph, wenn die ursprünglichen Automaten isomorph sind.

Vor dem

Antworten:

Dieses Papier könnte Sie interessieren:

Aidan Hogan: Skolemisierung leerer Knoten unter Wahrung des Isomorphismus. WWW 2015: 430-440

Es verfügt über einen Algorithmus (basierend auf Nauty) zum Testen des Isomorphismus von RDF-Graphen, bei denen es sich im Wesentlichen um gerichtete beschriftete Graphen handelt, die feste Beschriftungen enthalten können. Der Algorithmus berücksichtigt Beschriftungen, um den Suchraum einzugrenzen.

Wenn Sie Ihr mit der Eingabe beschriftetes Diagramm als RDF-Diagramm darstellen können, können Sie versuchen, das zugehörige Softwarepaket " blabel" zum Testen des Isomorphismus zu verwenden.

Badroit
quelle

Ich habe herausgefunden, dass der Algorithmus in die Kategorie der Weisfeiler-Lehman-Algorithmen mit k-Dimension gehört und bei regulären Graphen fehlschlägt. Für mehr hier:

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

Der ursprüngliche Beitrag folgt:

Vor Jahren habe ich einen einfachen und flexiblen Algorithmus für genau dieses Problem erstellt (Graphisomorphismus mit Beschriftungen).

Ich nannte es "Powerhash", und um den Algorithmus zu erstellen, waren zwei Erkenntnisse erforderlich. Der erste ist der Power Iteration Graph-Algorithmus, der auch in PageRank verwendet wird. Die zweite ist die Möglichkeit, die Inside-Step-Funktion der Power-Iteration durch alles zu ersetzen, was wir wollen. Ich habe es durch eine Funktion ersetzt, die bei jeder Iteration und für jeden Knoten Folgendes ausführt:

Sortieren Sie die Hashes (aus der vorherigen Iteration) der Nachbarn des Knotens
Hash die verketteten sortierten Hashes
Ersetzen Sie den Hash des Knotens durch einen neu berechneten Hash

Im ersten Schritt wird der Hash eines Knotens von seinen direkten Nachbarn beeinflusst. Im zweiten Schritt wird der Hash eines Knotens von der Nachbarschaft beeinflusst, die 2 Hops von ihm entfernt ist. Im N-ten Schritt wird der Hash eines Knotens von den N-Hops in der Umgebung beeinflusst. Sie müssen den Powerhash also nur für N = graph_radius-Schritte fortsetzen. Am Ende wurde der Hash des Diagrammmittelknotens vom gesamten Diagramm beeinflusst.

Um den endgültigen Hash zu erstellen, sortieren Sie die Knoten-Hashes des letzten Schritts und verketten Sie sie miteinander. Danach können Sie die endgültigen Hashes vergleichen, um festzustellen, ob zwei Diagramme isomorph sind. Wenn Sie Beschriftungen haben, fügen Sie diese (bei der ersten Iteration) zu den internen Hashes hinzu, die Sie für jeden Knoten berechnen.

Weitere Informationen hierzu finden Sie in meinem Beitrag hier:

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

Der obige Algorithmus wurde in der funktionalen relationalen Datenbank "madIS" implementiert. Den Quellcode des Algorithmus finden Sie hier:

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

estama
quelle

Nur eine Warnung, dass Ihr Algorithmus polynomisch ist. Wenn er vollständig ist, haben Sie gerade ein seit langem offenes Problem in CS gelöst, bei dem GI in P. ist :) (Es gibt verschiedene Fälle, in denen der von Ihnen beschriebene Algorithmus falsch positive Ergebnisse liefert .)

Badroit

Der Algorithmus ist ungefähr und sicherlich nicht vollständig (ich sage es auch im Blog-Beitrag). Der Grund dafür ist, dass die von ihm erstellten Hashes sehr groß sind. In einer Datenbank mit sogar Millionen von Diagrammen ist die Möglichkeit falsch positiver Hash-Kollisionen daher infinitesimal. Wenn es Ihnen gelingt, einen Fall einer falsch positiven Hash-Kollision zu finden, wäre ich sehr daran interessiert, davon zu erfahren. Der Grund (bei Verwendung von kryptografischen Hashes) ist, dass Sie es geschafft haben, die kryptografische Hash-Funktion zu "unterbrechen".

Estama

Um herauszufinden, wie infinitesimal die Möglichkeit einer Hash-Kollision ist. Ich würde einen kryptografischen Hash von 256 Bit als mehr als genug betrachten, um sicherzugehen, dass nicht alle verschiedenen Dateien der Welt den gleichen Wert haben (Git verwendet beispielsweise SHA-1, das 160 Bit beträgt, um dies zu gewährleisten). Ein Hash von Powerhash ist 128 Bit * graph_node_count (unter Verwendung von MD5-Hash). In der Praxis könnten Sie also nie genug Diagramme (in diesem Universum) erstellen, um eine Hash-Kollision zwischen ihnen zu finden.

Estama

Ich meinte, Ihr Algorithmus wird falsch positive Ergebnisse liefern, selbst wenn keine Hash-Kollisionen vorliegen. In der Literatur wurden viele Polynom-Zeit-Algorithmen für den Graphisomorphismus vorgeschlagen, die alle falsch positive Ergebnisse liefern. Eine verwandte Frage hier: cs.stackexchange.com/questions/50939/… .

Badroit

Vielen Dank für die Diskussion. Mit etwas mehr Forschung habe ich herausgefunden, dass der obige Algorithmus in der Kategorie der k-dimensionalen Weisfeiler-Lehman-Algorithmen liegt und mit regulären Graphen versagt. Für mehr hier: dabacon.org/pontiff/?p=4148

estama