Graphisomorphie: Wann zwei Graphen gleich sind

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Was es heißt, dass zwei Graphen gleich sind

Zwei Graphen heißen isomorph, wenn sie derselbe Graph mit anderen Namen an den Knoten sind. Formal heißen G und H isomorph, geschrieben G ≅ H, wenn es eine Bijektion f von den Knoten von G auf die Knoten von H gibt, sodass u und v genau dann in G benachbart sind, wenn f(u) und f(v) in H benachbart sind. Ein solches f heißt Isomorphismus. Beide Richtungen zählen: Kanten müssen auf Kanten abgebildet werden und Nicht-Kanten auf Nicht-Kanten.

Isomorphie ignoriert alles, was nicht Struktur ist. Die Namen der Knoten zählen nicht, und die Zeichnung ebenso wenig: wo die Knoten auf dem Papier sitzen, wie lang die Kanten sind, ob sie sich kreuzen. Zwei Bilder, die sich überhaupt nicht ähneln, können denselben Graphen zeigen, und genau das macht die Frage interessant. Der Leitfaden zu Knoten und Kanten führt die Idee in einem Satz ein; in diesem Artikel geht es darum, sie zu entscheiden.

Das durchgehende Beispiel ist das dreieckige Prisma aus dem Leitfaden zu planaren Graphen, hier G genannt, und als zweiter Graph H ein Sechseck mit drei Sehnen:

G = {AB, BC, CA, DE, EF, FD, AD, BE, CF}          zwei Dreiecke und drei Sprossen
H = {12, 23, 34, 45, 56, 61, 13, 25, 46}          Sechseck 1..6 plus Sehnen 13, 25, 46

f:  A→1   B→2   C→3   D→6   E→5   F→4

Wählen Sie eine beliebige Kante von G aus, und ihr Bild ist eine Kante von H: AD wird zu 16, DF wird zu 64, BE wird zu 25. Beide Graphen haben neun Kanten, und f bildet die neun auf die neun ab, also schickt es auch Nicht-Kanten auf Nicht-Kanten. G und H sind derselbe Graph. Isomorph zu sein ist eine Äquivalenzrelation, daher zerfallen Graphen in Isomorphieklassen, und genau diese meint man gewöhnlich mit „den Formen“ von Graphen mit einer gegebenen Anzahl von Knoten.

2. Ein Graph, der gleich aussieht und es nicht ist

Nehmen Sie nun einen dritten Graphen K: dasselbe Sechseck, aber mit den drei langen Durchmessern 14, 25 und 36 als Sehnen. Er hat 6 Knoten und 9 Kanten, jeder Knoten hat Grad 3, und er ist im selben Stil gezeichnet wie H. Er ist nicht isomorph zu G.

Der schnellste Beweis sucht nach Dreiecken. G hat zwei, ABC und DEF, und ein Isomorphismus muss Dreiecke auf Dreiecke abbilden. K hat keine: Seine Knoten zerfallen in ungerade und gerade, und jede Kante verbindet einen ungeraden mit einem geraden Knoten, also ist K bipartit und enthält keinen Kreis ungerader Länge, wie der Leitfaden zu bipartiten Graphen erklärt. Tatsächlich ist K der vollständige bipartite Graph K3,3, also genau der Graph, der das Drei-Häuser-Problem unlösbar macht. Zwei Graphen, die in jeder naheliegenden Zählung übereinstimmen, können trotzdem verschieden sein, und ein großer Teil des Gebiets besteht darin, die Zählung zu finden, die sie unterscheidet.

3. Invarianten: beweisen, dass zwei Graphen verschieden sind

Eine Grapheninvariante ist jede Größe, die isomorphe Graphen immer gemeinsam haben: die Anzahl der Knoten und Kanten, die Gradfolge, die Anzahl der Dreiecke, ob der Graph zusammenhängend oder bipartit ist, seine Taillenweite, seine chromatische Zahl, die Eigenwerte seiner Adjazenzmatrix und vieles mehr. Invarianten wirken nur in eine Richtung.

Unterscheiden sich zwei Graphen in irgendeiner Invariante, sind sie nicht isomorph. Stimmen sie in jeder Invariante überein, die Sie berechnet haben, haben Sie nichts Sicheres gelernt.

Jede einfache Invariante hat blinde Flecken. Die Gradfolge übersieht den Unterschied zwischen dem Prisma und K3,3. Selbst die vollständige Liste der Eigenwerte, die wie ein Fingerabdruck wirkt, ist keiner: Der Stern K1,4 und der 4-Kreis plus ein isolierter Knoten haben beide die Eigenwerte 2, 0, 0, 0, −2 und sind eindeutig verschiedene Graphen, das kleinste solche kospektrale Paar, das Collatz und Sinogowitz 1957 zugeschrieben wird. Eine Invariante, die jedes Paar nicht isomorpher Graphen trennt und sich schnell berechnen lässt, würde das ganze Problem lösen, und keine solche ist bekannt.

4. Wie viele verschiedene Graphen gibt es?

Auf n markierten Knoten gibt es C(n, 2) mögliche Kanten, jede vorhanden oder nicht, also 2C(n, 2) markierte Graphen. Die meisten davon sind Umbenennungen voneinander. Die Anzahl der wirklich verschiedenen Formen, der Isomorphieklassen, wächst weit langsamer:

from itertools import combinations, permutations

def count_graphs(n):
    """Markierte Graphen auf n Knoten und in wie viele verschiedene Formen sie zerfallen."""
    pairs = list(combinations(range(n), 2))
    index = {p: i for i, p in enumerate(pairs)}
    seen, shapes = set(), 0
    for mask in range(1 << len(pairs)):
        if mask in seen:
            continue
        shapes += 1                           # eine neue Isomorphieklasse: alle ihre Umbenennungen markieren
        edges = [p for i, p in enumerate(pairs) if mask >> i & 1]
        for perm in permutations(range(n)):
            m = 0
            for u, v in edges:
                a, b = sorted((perm[u], perm[v]))
                m |= 1 << index[(a, b)]
            seen.add(m)
    return 1 << len(pairs), shapes

for n in range(1, 6):
    print(n, count_graphs(n))
# 1 (1, 1)
# 2 (2, 2)
# 3 (8, 4)
# 4 (64, 11)
# 5 (1024, 34)

Die Zählung mit roher Gewalt hört bei fünf Knoten auf, weil sie jede Umbenennung jedes Graphen ausprobiert. Die Folge geht weiter mit 156 für sechs Knoten, 1.044 für sieben und 12.346 für acht. Es gibt keine einfache geschlossene Formel; das Standardwerkzeug ist Pólyas Abzähltheorie von 1937, die Objekte bis auf Symmetrie zählt. Die Lücke zwischen den beiden Spalten ist der Grund, warum Isomorphietests überhaupt wichtig sind: Ein Programm, das Graphen, Moleküle oder Schaltungen auflistet, muss erkennen, wann zwei seiner Ausgaben dasselbe Objekt in Verkleidung sind.

5. Testen durch Suche

Die Definition legt einen Algorithmus nahe: jede Bijektion ausprobieren und jede einzeln prüfen. Bei n Knoten gibt es n! Bijektionen, 720 für das Beispiel mit sechs Knoten, aber etwa 2,4 × 1018 für zwanzig Knoten, sodass die naive Methode jenseits von Spielzeuggrößen hoffnungslos ist. Zwei Ideen machen die Suche auf kleinen und mittleren Graphen praktikabel. Erstens: sofort ablehnen, wenn sich eine billige Invariante wie die Gradfolge unterscheidet. Zweitens: die Abbildung Knoten für Knoten aufbauen, nur Bilder mit demselben Grad ausprobieren und zurücksetzen, sobald eine Kante oder Nicht-Kante nicht passt.

def graph(edges):
    adj = {}
    for e in edges:
        u, v = e.split('-')
        adj.setdefault(u, set()).add(v)
        adj.setdefault(v, set()).add(u)
    return adj

def isomorphisms(G, H):
    """Liefert jede Bijektion f: V(G) -> V(H), bei der uv genau dann eine Kante ist, wenn f(u)f(v) eine ist."""
    if len(G) != len(H) or sorted(map(len, G.values())) != sorted(map(len, H.values())):
        return                                # eine billige Invariante sagt bereits nein
    order = sorted(G, key=lambda v: -len(G[v]))
    def extend(f, used):
        if len(f) == len(order):
            yield dict(f)
            return
        u = order[len(f)]
        for x in H:
            if x in used or len(H[x]) != len(G[u]):
                continue                      # Grade müssen übereinstimmen
            if all((w in G[u]) == (f[w] in H[x]) for w in f):
                f[u] = x                      # verträglich mit jedem bisher abgebildeten Knoten
                yield from extend(f, used | {x})
                del f[u]
    yield from extend({}, set())

G = graph(['A-B', 'B-C', 'C-A', 'D-E', 'E-F', 'F-D', 'A-D', 'B-E', 'C-F'])   # das Prisma
H = graph(['1-2', '2-3', '3-4', '4-5', '5-6', '6-1', '1-3', '2-5', '4-6'])   # Sechseck + 3 Sehnen
K = graph(['1-2', '2-3', '3-4', '4-5', '5-6', '6-1', '1-4', '2-5', '3-6'])   # Sechseck + 3 Durchmesser

print(next(isomorphisms(G, H)))
# {'A': '1', 'B': '2', 'C': '3', 'D': '6', 'E': '5', 'F': '4'}
print(sum(1 for _ in isomorphisms(G, H)))     # so viele, wie G Symmetrien hat
# 12
print(next(isomorphisms(G, K), None))         # gleiche Grade, kein Isomorphismus
# None

Die erste Ausgabezeile ist die Abbildung aus Abschnitt 1. Die zweite zeigt, dass es genau 12 verschiedene Isomorphismen von G nach H gibt, und Abschnitt 7 erklärt, warum diese Zahl kein Zufall ist. Die dritte bestätigt, dass keine Abbildung vom Prisma auf K3,3 existiert, obwohl die Gradprüfung bestanden wurde. Die Funktion wurde mit networkx an 3.000 zufälligen Graphenpaaren überprüft, von denen die Hälfte umbenannte Kopien voneinander waren, und jede zurückgegebene Abbildung wurde Kante für Kante verifiziert. Backtracking bleibt im schlimmsten Fall exponentiell: Graphen, in denen jeder Knoten gleich aussieht, hebeln das Beschneiden nach Graden aus, und genau dort kommt die nächste Idee ins Spiel.

6. Farbverfeinerung und ihr blinder Fleck

Farbverfeinerung, nach der Arbeit von Weisfeiler und Leman aus dem Jahr 1968 auch eindimensionaler Algorithmus von Weisfeiler–Leman genannt, gibt jedem Knoten eine Farbe und verfeinert die Farben immer weiter anhand der Nachbarschaften. Beginnen Sie mit einer Farbe für alle. Geben Sie in jeder Runde zwei Knoten nur dann dieselbe neue Farbe, wenn sie dieselbe alte Farbe hatten und ihre Nachbarn dieselbe Multimenge alter Farben tragen. Hören Sie auf, wenn sich keine Farbklasse mehr aufspaltet. Lassen Sie den Algorithmus auf zwei Graphen gemeinsam laufen: Unterscheiden sich die endgültigen Farbhäufigkeiten, sind die Graphen nicht isomorph.

from collections import Counter

def colour_refinement(adj, rounds=None):
    """1-WL: jeden Knoten wiederholt anhand seiner Farbe und der Multimenge der Farben seiner Nachbarn umfärben."""
    colour = {v: 0 for v in adj}
    for _ in range(rounds or len(adj)):
        signature = {v: (colour[v], tuple(sorted(colour[w] for w in adj[v]))) for v in adj}
        palette = {s: i for i, s in enumerate(sorted(set(signature.values())))}
        new = {v: palette[signature[v]] for v in adj}
        if len(set(new.values())) == len(set(colour.values())):
            break                             # stabil: keine Farbklasse hat sich aufgespalten
        colour = new
    return colour

def joint(G, H):
    """True, wenn die Verfeinerung G und H nicht unterscheiden kann. Beide gemeinsam verfeinern, damit die Farben zusammenpassen."""
    union = {('g', v): {('g', w) for w in G[v]} for v in G}
    union.update({('h', v): {('h', w) for w in H[v]} for v in H})
    c = colour_refinement(union)
    return (sorted(Counter(c[k] for k in union if k[0] == 'g').items()) ==
            sorted(Counter(c[k] for k in union if k[0] == 'h').items()))

def graph(edges):
    adj = {}
    for e in edges:
        u, v = e.split('-')
        adj.setdefault(u, set()).add(v)
        adj.setdefault(v, set()).add(u)
    return adj

T1 = graph(['a-b', 'b-c', 'c-d', 'b-e', 'e-f'])       # Zentrum b, Beine der Länge 2, 2 und 1
T2 = graph(['a-b', 'b-c', 'c-d', 'd-e', 'b-f'])       # Zentrum b, Beine der Länge 3, 1 und 1
prism = graph(['A-B', 'B-C', 'C-A', 'D-E', 'E-F', 'F-D', 'A-D', 'B-E', 'C-F'])
k33 = graph(['1-2', '2-3', '3-4', '4-5', '5-6', '6-1', '1-4', '2-5', '3-6'])

print(joint(T1, T2))      # gleiche Gradfolge, aber die Verfeinerung unterscheidet sie
# False
print(joint(prism, k33))  # beide 3-regulär: die Verfeinerung kann sie nicht unterscheiden
# True

Die beiden Bäume im Beispiel haben dieselbe Gradfolge, (3, 2, 2, 1, 1, 1), daher kann die Gradprüfung sie nicht trennen. Die Verfeinerung kann es: Nach einigen Runden erhalten ein Blatt neben dem Zentrum und ein Blatt am Ende eines langen Beins verschiedene Farben, und die Farbhäufigkeiten der beiden Bäume stimmen nicht mehr überein. Im Allgemeinen ist die Verfeinerung stark. Babai, Erdős und Selkow zeigten 1980, dass eine einfache, gradbasierte Verfeinerung fast alle Graphen identifiziert, sodass Isomorphie auf einem Zufallsgraphen leicht ist.

Der blinde Fleck ist die Regularität. In einem k-regulären Graphen beginnt jeder Knoten mit derselben Farbe und hat k Nachbarn dieser Farbe, also ändert die erste Runde nichts, und der Algorithmus hält sofort an. Je zwei reguläre Graphen mit derselben Knotenzahl und demselben Grad sehen für ihn identisch aus, weshalb das Prisma und K3,3 diesen Test gemeinsam bestehen. Dieselbe Grenze reicht bis ins maschinelle Lernen: Xu und Kollegen bewiesen 2019, dass Graph Neural Networks mit Message Passing zwei Graphen nur dann unterscheiden können, wenn die Farbverfeinerung es kann, weshalb der Leitfaden zu Graph Neural Networks den Weisfeiler–Leman-Test als ihren Maßstab verwendet. Stärkere Varianten verfeinern die Farben von Paaren oder Tripeln von Knoten statt einzelner Knoten; sie sehen mehr, kosten aber auch mehr.

7. Automorphismen: die eigenen Symmetrien eines Graphen

Ein Isomorphismus von einem Graphen auf sich selbst heißt Automorphismus, eine Symmetrie des Graphen. Die Automorphismen eines Graphen bilden eine Gruppe, und ihre Größe misst, wie symmetrisch der Graph ist. Das Prisma hat 12: Man dreht oder spiegelt die beiden Dreiecke gemeinsam, was 6 Symmetrien ergibt, und vertauscht wahlweise die beiden Dreiecke. K3,3 hat 72, da jede Seite auf 6 Arten permutiert und die beiden Seiten vertauscht werden können, und der Petersen-Graph hat 120.

Das erklärt die 12 aus Abschnitt 5. Ist f ein Isomorphismus von G nach H, dann ist jeder andere f verknüpft mit einem Automorphismus von G, sodass isomorphe Graphen stets genau so viele Isomorphismen zwischen sich haben, wie jeder von ihnen Automorphismen hat. Eine Suche, die nur eine Antwort will, verschwendet Zeit mit symmetrischen Kopien derselben Abbildung, und die besten praktischen Algorithmen nutzen die gefundenen Automorphismen, um die Suche zu beschneiden.

Zwei klassische Ergebnisse zeigen, wie weit Symmetrie in jede Richtung gehen kann. Frucht bewies 1939, dass jede endliche Gruppe die Automorphismengruppe irgendeines Graphen ist, Symmetrie also jede beliebige Form annehmen kann. Und Erdős und Rényi bewiesen 1963, dass fast alle Graphen asymmetrisch sind, ohne einen Automorphismus außer der Identität. Kleine Graphen täuschen hier: Kein Graph mit zwei bis fünf Knoten ist asymmetrisch, die kleinsten asymmetrischen Graphen haben sechs Knoten, und es gibt acht davon, und unter den 1.044 Graphen mit sieben Knoten sind nur 152 asymmetrisch. Das „fast alle“ setzt sich erst durch, wenn n wächst.

8. Kanonische Formen: ein Name pro Form

Graphen paarweise zu vergleichen skaliert nicht, wenn eine Datenbank Millionen davon enthält. Die Alternative ist eine kanonische Form: eine Umbenennungsregel, die jeden Graphen auf einen festen Vertreter seiner Isomorphieklasse abbildet, sodass zwei Graphen genau dann isomorph sind, wenn ihre kanonischen Formen identisch sind. Sobald jeder Graph eine kanonische Form hat, wird Isomorphie zur Gleichheit von Zeichenketten, und eine Datenbank kann Graphen wie jeden anderen Schlüssel indizieren, hashen und deduplizieren.

Die einfachste kanonische Form wählt unter allen n! Umbenennungen diejenige, deren Adjazenzmatrix als Bitfolge gelesen am kleinsten ist. Das ist korrekt und viel zu langsam. Praktische Werkzeuge berechnen kanonische Formen mit Individualisierung und Verfeinerung: Man lässt die Farbverfeinerung laufen, und wenn sie an einer Klasse gleich aussehender Knoten hängen bleibt, hebt man einen davon mit einer neuen Farbe hervor und verfeinert erneut, wobei man einen Suchbaum solcher Entscheidungen durchläuft und ihn mit den unterwegs gefundenen Automorphismen beschneidet. McKays Programm nauty, beschrieben 1981, und Traces, von McKay und Piperno 2014 zusammen mit nauty vorgestellt, arbeiten auf diese Weise und bewältigen in der Praxis Graphen mit vielen tausend Knoten.

9. Wie schwer ist Graphisomorphie?

Graphisomorphie hat einen ungewöhnlichen Platz in der Komplexitätstheorie. Sie liegt in NP, weil sich eine vorgeschlagene Abbildung in Polynomialzeit prüfen lässt. Es ist nicht bekannt, ob sie in Polynomialzeit lösbar ist. Und sie ist wahrscheinlich nicht NP-vollständig: Boppana, Håstad und Zachos zeigten 1987, dass sonst die polynomielle Hierarchie auf ihre zweite Stufe kollabieren würde, was die meisten Forscher für unplausibel halten. Sie ist eines von sehr wenigen natürlichen Problemen, von denen man annimmt, dass sie echt zwischen den leichten und den NP-vollständigen liegen.

Der beste allgemeine Algorithmus stammt von Babai. Er kündigte ihn im November 2015 an und veröffentlichte ihn 2016 auf der STOC: Graphisomorphie lässt sich entscheiden in quasipolynomieller Zeit, exp((log n)O(1)), was nicht polynomiell, aber enorm viel besser als exponentiell ist. Im Januar 2017 fand Helfgott einen Fehler in einem Schritt, Babai zog die quasipolynomielle Behauptung zurück und kündigte innerhalb weniger Tage eine Reparatur an, die Helfgott bestätigte. Für spezielle Klassen weiß man viel mehr:

• Bäume lassen sich in linearer Zeit testen, mit dem Algorithmus von Aho, Hopcroft und Ullman, der für jeden Baum von den Blättern aufwärts einen kanonischen Code aufbaut, die Technik aus dem Leitfaden zu Bäumen in der Graphentheorie.
• Planare Graphen lassen sich in linearer Zeit testen, wie Hopcroft und Wong 1974 zeigten.
• Graphen mit beschränktem Grad lassen sich in Polynomialzeit testen, ein Ergebnis von Luks aus dem Jahr 1982, das zu einem Baustein von Babais Algorithmus wurde.

10. Teilgraph-Isomorphie ist ein anderes Problem

Ein naher Verwandter fragt, ob ein Graph innerhalb eines anderen vorkommt: Enthält H einen Teilgraphen, der isomorph zu G ist? Dieses Problem der Teilgraph-Isomorphie ist viel schwerer. Cooks Arbeit von 1971, die die Theorie der NP-Vollständigkeit begründete, zeigte bereits, dass es so schwer ist wie das Erfüllbarkeitsproblem, nach heutiger Sprechweise NP-vollständig. Es enthält das Cliquenproblem als Spezialfall: Die Frage, ob ein Graph Kk enthält, ist die Frage, ob Kk ein Teilgraph von ihm ist.

Die beiden Probleme werden leicht verwechselt, weil sie einen Namen und einen algorithmischen Stil teilen. Praktische Teilgraph-Matcher wie Ullmanns Algorithmus von 1976 und VF2 von Cordella und Kollegen aus dem Jahr 2004 verwenden dieselbe Idee des Backtrackings mit Beschneiden wie Abschnitt 5, aber sie suchen nach einem Muster, nicht nach einer perfekten Übereinstimmung, und für sie wird keine quasipolynomielle Schranke erwartet. Wenn jemand sagt, ein Problem sei „ein Graphisomorphieproblem“, lohnt es sich nachzufragen, welches der beiden gemeint ist.

11. Wo Isomorphietests eingesetzt werden

• Chemie. Die Bindungen eines Moleküls bilden einen Graphen, und chemische Datenbanken verwenden kanonische Formen, um jede Struktur nur einmal zu speichern und eine Verbindung sofort nachzuschlagen. Graphisomorphie ist für chemische Identität notwendig, aber nicht hinreichend: Stereoisomere haben denselben Bindungsgraphen und unterscheiden sich in ihrer räumlichen Anordnung.
• Schaltungsverifikation. Die Prüfung, ob ein Chip-Layout seinen Schaltplan umsetzt, bekannt als Layout versus Schematic, umfasst den Abgleich des aus dem Layout extrahierten Transistornetzes mit dem beabsichtigten.
• Aufzählung und Datenbanken. Alle Graphen, alle Moleküle oder alle Entwürfe einer gegebenen Größe zu erzeugen, erfordert das Verwerfen von Duplikaten, also eine Berechnung der kanonischen Form für jeden Kandidaten.
• Maschinelles Lernen auf Graphen. Die Weisfeiler–Leman-Verbindung aus Abschnitt 6 dient sowohl dazu, die Ausdrucksstärke von Graph Neural Networks zu messen, als auch als schnelle Vergleichsbasis beim Vergleichen von Graphen.
• Symmetrie in der Optimierung. Automorphismen der Struktur eines Problems bedeuten viele äquivalente Lösungen; erkennt man sie, kann ein Solver die Kopien überspringen.

12. Häufige Fehler

13. Glossar

15. Quellen

Die Definitionen, Sätze und Zuschreibungen oben stammen aus diesen Quellen, in chronologischer Reihenfolge.

1. Pólya, G. (1937). "Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen." Acta Mathematica 68, 145 bis 254. Zählen von Objekten bis auf Symmetrie.
2. Frucht, R. (1939). "Herstellung von Graphen mit vorgegebener abstrakter Gruppe." Compositio Mathematica 6, 239 bis 250.
3. Collatz, L. und Sinogowitz, U. (1957). "Spektren endlicher Grafen." Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 21, 63 bis 77. Kospektrale Graphen.
4. Erdős, P. und Rényi, A. (1963). "Asymmetric Graphs." Acta Mathematica Academiae Scientiarum Hungaricae 14, 295 bis 315.
5. Weisfeiler, B. und Leman, A. (1968). "The Reduction of a Graph to Canonical Form and the Algebra Which Appears Therein." Nauchno-Technicheskaya Informatsia, Serie 2, Nr. 9, 12 bis 16.
6. Cook, S. A. (1971). "The Complexity of Theorem-Proving Procedures." Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, 151 bis 158. Teilgraph-Isomorphie so schwer wie das Erfüllbarkeitsproblem.
7. Aho, A. V., Hopcroft, J. E. und Ullman, J. D. (1974). The Design and Analysis of Computer Algorithms. Reading, Massachusetts: Addison-Wesley. Baumisomorphie in linearer Zeit.
8. Hopcroft, J. E. und Wong, J. K. (1974). "Linear Time Algorithm for Isomorphism of Planar Graphs (Preliminary Report)." Proceedings of the 6th Annual ACM Symposium on Theory of Computing, 172 bis 184.
9. Ullmann, J. R. (1976). "An Algorithm for Subgraph Isomorphism." Journal of the ACM 23(1), 31 bis 42.
10. Babai, L., Erdős, P. und Selkow, S. M. (1980). "Random Graph Isomorphism." SIAM Journal on Computing 9(3), 628 bis 635.
11. McKay, B. D. (1981). "Practical Graph Isomorphism." Congressus Numerantium 30, 45 bis 87.
12. Luks, E. M. (1982). "Isomorphism of Graphs of Bounded Valence Can Be Tested in Polynomial Time." Journal of Computer and System Sciences 25(1), 42 bis 65.
13. Boppana, R. B., Håstad, J. und Zachos, S. (1987). "Does co-NP Have Short Interactive Proofs?" Information Processing Letters 25(2), 127 bis 132.
14. Cordella, L. P., Foggia, P., Sansone, C. und Vento, M. (2004). "A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs." IEEE Transactions on Pattern Analysis and Machine Intelligence 26(10), 1367 bis 1372.
15. McKay, B. D. und Piperno, A. (2014). "Practical Graph Isomorphism, II." Journal of Symbolic Computation 60, 94 bis 112.
16. Babai, L. (2016). "Graph Isomorphism in Quasipolynomial Time." Proceedings of the 48th Annual ACM Symposium on Theory of Computing, 684 bis 697.
17. Diestel, R. (2017). Graph Theory, 5. Auflage. Graduate Texts in Mathematics 173. Berlin: Springer.
18. Xu, K., Hu, W., Leskovec, J. und Jegelka, S. (2019). "How Powerful are Graph Neural Networks?" International Conference on Learning Representations.