Isomorphisme de graphes : quand deux graphes sont les mêmes

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Ce que signifie être le même graphe

Deux graphes sont isomorphes lorsqu'ils sont le même graphe avec des noms différents sur les sommets. Formellement, G et H sont isomorphes, ce que l'on note G ≅ H, s'il existe une bijection f des sommets de G vers les sommets de H telle que u et v sont adjacents dans G exactement lorsque f(u) et f(v) sont adjacents dans H. Une telle application f est un isomorphisme. Les deux sens comptent : les arêtes doivent aller sur des arêtes, et les non-arêtes sur des non-arêtes.

L'isomorphisme ignore tout ce qui n'est pas la structure. Les noms des sommets ne comptent pas, pas plus que le dessin : l'emplacement des sommets sur la page, la longueur des arêtes, le fait qu'elles se croisent ou non. Deux images qui ne se ressemblent en rien peuvent montrer le même graphe, et c'est précisément ce qui rend la question intéressante. Le guide des sommets et arêtes présente l'idée en une phrase ; cet article porte sur la manière de la trancher.

L'exemple suivi est le prisme triangulaire du guide des graphes planaires, appelé G ici, et un second graphe H dessiné comme un hexagone avec trois cordes :

G = {AB, BC, CA, DE, EF, FD, AD, BE, CF}          deux triangles et trois barreaux
H = {12, 23, 34, 45, 56, 61, 13, 25, 46}          hexagone 1..6 plus les cordes 13, 25, 46

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

Vérifiez n'importe quelle arête de G et son image est une arête de H : AD est envoyée sur 16, DF est envoyée sur 64, BE est envoyée sur 25. Les deux graphes ont neuf arêtes et f envoie les neuf sur les neuf, donc elle envoie aussi les non-arêtes sur des non-arêtes. G et H sont le même graphe. Être isomorphe est une relation d'équivalence, donc les graphes se répartissent en classes d'isomorphisme, qui sont ce que l'on entend habituellement par « les formes » des graphes ayant un nombre de sommets donné.

2. Un graphe qui semble identique et ne l'est pas

Prenez maintenant un troisième graphe K : le même hexagone, mais avec les trois grands diamètres 14, 25 et 36 comme cordes. Il a 6 sommets et 9 arêtes, chaque sommet est de degré 3, et il est dessiné dans le même style que H. Il n'est pas isomorphe à G.

La preuve la plus rapide cherche des triangles. G en a deux, ABC et DEF, et un isomorphisme doit envoyer les triangles sur des triangles. K n'en a aucun : ses sommets se répartissent en impairs et pairs, et chaque arête relie un sommet impair à un sommet pair, donc K est biparti et ne contient aucun cycle de longueur impaire, comme le guide des graphes bipartis l'explique. En fait, K est le graphe biparti complet K3,3, le même graphe qui rend impossible l'énigme des trois maisons. Deux graphes qui coïncident sur tous les décomptes évidents peuvent tout de même être différents, et une grande partie du sujet consiste à trouver le décompte qui les distingue.

3. Invariants : prouver que deux graphes sont différents

Un invariant de graphe est toute quantité que des graphes isomorphes partagent toujours : le nombre de sommets et d'arêtes, la suite des degrés, le nombre de triangles, le fait que le graphe soit connexe ou biparti, sa maille, son nombre chromatique, les valeurs propres de sa matrice d'adjacence, et bien d'autres. Les invariants ne fonctionnent que dans un sens.

Si deux graphes diffèrent sur un invariant quelconque, ils ne sont pas isomorphes. S'ils coïncident sur tous les invariants que vous avez calculés, vous n'avez rien appris de certain.

Tout invariant simple a des angles morts. La suite des degrés ne voit pas la différence entre le prisme et K3,3. Même la liste complète des valeurs propres, qui ressemble à une empreinte digitale, n'en est pas une : l'étoile K1,4 et le cycle à 4 sommets plus un sommet isolé ont tous deux pour valeurs propres 2, 0, 0, 0, −2 et sont clairement des graphes différents, la plus petite paire cospectrale de ce genre, attribuée à Collatz et Sinogowitz en 1957. Un invariant qui séparerait toutes les paires de graphes non isomorphes et se calculerait rapidement réglerait tout le problème, et on n'en connaît aucun.

4. Combien de graphes différents existe-t-il ?

Sur n sommets étiquetés, il y a C(n, 2) arêtes possibles, chacune présente ou absente, d'où 2C(n, 2) graphes étiquetés. La plupart sont des réétiquetages les uns des autres. Le nombre de formes réellement différentes, les classes d'isomorphisme, croît beaucoup plus lentement :

from itertools import combinations, permutations

def count_graphs(n):
    """Graphes étiquetés sur n sommets, et nombre de formes distinctes entre lesquelles ils se répartissent."""
    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                           # une nouvelle classe d'isomorphisme : marquer tous ses réétiquetages
        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)

Le décompte par force brute s'arrête à cinq sommets parce qu'il essaie chaque réétiquetage de chaque graphe. La suite continue avec 156 pour six sommets, 1 044 pour sept et 12 346 pour huit. Il n'existe pas de formule close simple ; l'outil standard est la théorie de l'énumération de Pólya, de 1937, qui compte les objets à symétrie près. L'écart entre les deux colonnes est la raison même pour laquelle le test d'isomorphisme compte : un programme qui énumère des graphes, des molécules ou des circuits doit reconnaître quand deux de ses résultats sont le même objet déguisé.

5. Tester par la recherche

La définition suggère un algorithme : essayer chaque bijection et vérifier chacune. Avec n sommets, il y a n! bijections, 720 pour l'exemple à six sommets mais environ 2,4 × 1018 pour vingt sommets, donc la méthode naïve est sans espoir au-delà de tailles jouets. Deux idées rendent la recherche praticable sur des graphes petits et moyens. D'abord, rejeter immédiatement lorsqu'un invariant peu coûteux comme la suite des degrés diffère. Ensuite, construire l'application un sommet à la fois, n'essayer que des images de même degré, et revenir en arrière dès qu'une arête ou une non-arête ne correspond pas.

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):
    """Produit chaque bijection f: V(G) -> V(H) telle que uv soit une arête exactement lorsque f(u)f(v) en est une."""
    if len(G) != len(H) or sorted(map(len, G.values())) != sorted(map(len, H.values())):
        return                                # un invariant peu coûteux dit déjà non
    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                      # les degrés doivent correspondre
            if all((w in G[u]) == (f[w] in H[x]) for w in f):
                f[u] = x                      # cohérent avec chaque sommet déjà placé
                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'])   # le prisme
H = graph(['1-2', '2-3', '3-4', '4-5', '5-6', '6-1', '1-3', '2-5', '4-6'])   # hexagone + 3 cordes
K = graph(['1-2', '2-3', '3-4', '4-5', '5-6', '6-1', '1-4', '2-5', '3-6'])   # hexagone + 3 diamètres

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)))     # autant que G a de symétries
# 12
print(next(isomorphisms(G, K), None))         # mêmes degrés, aucun isomorphisme
# None

La première ligne de sortie est l'application de la section 1. La deuxième montre qu'il existe exactement 12 isomorphismes différents de G vers H, et la section 7 explique pourquoi ce nombre n'est pas un hasard. La troisième confirme qu'aucune application du prisme vers K3,3 n'existe, bien que le test des degrés ait réussi. La fonction a été vérifiée par rapport à networkx sur 3 000 paires aléatoires de graphes, dont la moitié étaient des copies réétiquetées l'une de l'autre, chaque application renvoyée étant vérifiée arête par arête. Le backtracking reste exponentiel dans le pire des cas : les graphes où tous les sommets se ressemblent déjouent l'élagage par les degrés, et c'est là qu'intervient l'idée suivante.

6. Le raffinement de couleurs et son angle mort

Le raffinement de couleurs, aussi appelé algorithme de Weisfeiler–Leman unidimensionnel d'après l'article de Weisfeiler et Leman de 1968, attribue une couleur à chaque sommet et affine sans cesse les couleurs à l'aide des voisinages. Commencez avec une seule couleur pour tous. À chaque tour, donnez la même nouvelle couleur à deux sommets seulement s'ils avaient la même ancienne couleur et si leurs voisins portent le même multiensemble d'anciennes couleurs. Arrêtez-vous lorsqu'aucune classe de couleur ne se scinde. Exécutez-le sur deux graphes à la fois : si les décomptes finaux de couleurs diffèrent, les graphes ne sont pas isomorphes.

from collections import Counter

def colour_refinement(adj, rounds=None):
    """1-WL : recolorer à répétition chaque sommet selon sa couleur et le multiensemble des couleurs de ses voisins."""
    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                             # stable : aucune classe de couleur ne s'est scindée
        colour = new
    return colour

def joint(G, H):
    """Vrai si le raffinement ne peut pas distinguer G et H. Les raffiner ensemble pour que les couleurs correspondent."""
    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'])       # centre b, branches de longueur 2, 2 et 1
T2 = graph(['a-b', 'b-c', 'c-d', 'd-e', 'b-f'])       # centre b, branches de longueur 3, 1 et 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))      # même suite des degrés, mais le raffinement les distingue
# False
print(joint(prism, k33))  # tous deux 3-réguliers : le raffinement ne peut pas les distinguer
# True

Les deux arbres de l'exemple ont la même suite des degrés, (3, 2, 2, 1, 1, 1), donc le test des degrés ne peut pas les séparer. Le raffinement le peut : après quelques tours, une feuille voisine du centre et une feuille au bout d'une longue branche reçoivent des couleurs différentes, et les décomptes de couleurs des deux arbres ne correspondent plus. Le raffinement est puissant en général. Babai, Erdős et Selkow ont montré en 1980 qu'un raffinement simple fondé sur les degrés identifie presque tous les graphes, si bien que sur un graphe aléatoire, l'isomorphisme est facile.

L'angle mort est la régularité. Dans un graphe k-régulier, chaque sommet commence avec la même couleur et a k voisins de cette couleur, donc le premier tour ne change rien et l'algorithme s'arrête aussitôt. Deux graphes réguliers quelconques ayant le même nombre de sommets et le même degré lui paraissent identiques, ce qui explique pourquoi le prisme et K3,3 passent ce test ensemble. La même limite s'étend à l'apprentissage automatique : Xu et ses collègues ont prouvé en 2019 que les réseaux de neurones en graphe à passage de messages ne peuvent distinguer deux graphes que si le raffinement de couleurs le peut, ce qui explique pourquoi le guide des réseaux de neurones en graphe fait du test de Weisfeiler–Leman leur étalon. Des versions plus fortes raffinent les couleurs de paires ou de triplets de sommets au lieu de sommets isolés ; elles voient davantage mais coûtent plus cher.

7. Automorphismes : les symétries propres d'un graphe

Un isomorphisme d'un graphe vers lui-même est un automorphisme, une symétrie du graphe. Les automorphismes d'un graphe forment un groupe, dont la taille mesure à quel point le graphe est symétrique. Le prisme en a 12 : faire tourner ou réfléchir les deux triangles ensemble, ce qui donne 6 symétries, puis éventuellement échanger les deux triangles. K3,3 en a 72, puisque chaque côté peut être permuté de 6 façons et que les deux côtés peuvent être échangés, et le graphe de Petersen en a 120.

Cela explique le 12 de la section 5. Si f est un isomorphisme de G vers H, alors tout autre isomorphisme est f composé avec un automorphisme de G, donc des graphes isomorphes ont toujours exactement autant d'isomorphismes entre eux que chacun a d'automorphismes. Une recherche qui ne veut qu'une seule réponse perd du temps à explorer des copies symétriques de la même application, et les meilleurs algorithmes pratiques utilisent les automorphismes qu'ils découvrent pour élaguer la recherche.

Deux résultats classiques montrent jusqu'où la symétrie peut aller dans chaque sens. Frucht a prouvé en 1939 que tout groupe fini est le groupe d'automorphismes d'un certain graphe, donc la symétrie peut prendre absolument n'importe quelle forme. Et Erdős et Rényi ont prouvé en 1963 que presque tous les graphes sont asymétriques, sans autre automorphisme que l'identité. Les petits graphes sont trompeurs ici : aucun graphe ayant entre deux et cinq sommets n'est asymétrique, les plus petits graphes asymétriques ont six sommets et il y en a huit, et parmi les 1 044 graphes à sept sommets, seuls 152 sont asymétriques. Le « presque tous » ne l'emporte qu'à mesure que n croît.

8. Formes canoniques : un nom par forme

Comparer les graphes deux à deux ne passe pas à l'échelle lorsqu'une base de données en contient des millions. L'alternative est une forme canonique : une règle de réétiquetage qui envoie chaque graphe sur un représentant fixe de sa classe d'isomorphisme, de sorte que deux graphes sont isomorphes exactement lorsque leurs formes canoniques sont identiques. Une fois que chaque graphe a une forme canonique, l'isomorphisme devient une égalité de chaînes, et une base de données peut indexer, hacher et dédoublonner les graphes comme n'importe quelle autre clé.

La forme canonique la plus simple retient, parmi les n! réétiquetages, celui dont la matrice d'adjacence, lue comme une chaîne de bits, est la plus petite. C'est correct et beaucoup trop lent. Les outils pratiques calculent les formes canoniques par individualisation et raffinement : lancez le raffinement de couleurs et, lorsqu'il bloque sur une classe de sommets qui se ressemblent, isolez l'un d'eux avec une nouvelle couleur et raffinez de nouveau, en explorant un arbre de recherche de tels choix et en l'élaguant avec les automorphismes trouvés en chemin. Le programme nauty de McKay, décrit en 1981, et Traces, présenté avec nauty par McKay et Piperno en 2014, fonctionnent ainsi et traitent en pratique des graphes de plusieurs milliers de sommets.

9. Quelle est la difficulté de l'isomorphisme de graphes ?

L'isomorphisme de graphes occupe une place singulière en théorie de la complexité. Il est dans NP, car une application proposée peut être vérifiée en temps polynomial. On ne sait pas s'il peut être résolu en temps polynomial. Et il est peu probable qu'il soit NP-complet : Boppana, Håstad et Zachos ont montré en 1987 que s'il l'était, la hiérarchie polynomiale s'effondrerait à son deuxième niveau, ce que la plupart des chercheurs jugent invraisemblable. C'est l'un des très rares problèmes naturels que l'on pense situés strictement entre les problèmes faciles et les problèmes NP-complets.

Le meilleur algorithme général est celui de Babai. Il l'a annoncé en novembre 2015 et publié à STOC en 2016 : l'isomorphisme de graphes peut être décidé en temps quasi-polynomial, exp((log n)O(1)), ce qui n'est pas polynomial mais énormément mieux qu'exponentiel. En janvier 2017, Helfgott a trouvé une erreur dans une étape, Babai a retiré l'affirmation quasi-polynomiale et, en quelques jours, il a annoncé une correction, que Helfgott a confirmée. Pour des classes particulières, on en sait beaucoup plus :

• Les arbres peuvent être testés en temps linéaire avec l'algorithme d'Aho, Hopcroft et Ullman, qui construit un code canonique pour chaque arbre en partant des feuilles, la technique abordée dans les arbres en théorie des graphes.
• Les graphes planaires peuvent être testés en temps linéaire, comme l'ont montré Hopcroft et Wong en 1974.
• Les graphes de degré borné peuvent être testés en temps polynomial, un résultat de Luks datant de 1982 qui est devenu une brique de l'algorithme de Babai.

10. L'isomorphisme de sous-graphe est un autre problème

Un proche parent demande si un graphe apparaît à l'intérieur d'un autre : existe-t-il un sous-graphe de H qui soit isomorphe à G ? Ce problème de l'isomorphisme de sous-graphe est beaucoup plus difficile. L'article de Cook de 1971, celui qui a fondé la théorie de la NP-complétude, montrait déjà qu'il est aussi difficile que la satisfaisabilité, NP-complet dans les termes actuels. Il contient le problème de la clique comme cas particulier : demander si un graphe contient Kk revient à demander si Kk en est un sous-graphe.

Les deux problèmes sont faciles à confondre parce qu'ils partagent un nom et un style algorithmique. Les outils pratiques de recherche de sous-graphes, comme l'algorithme d'Ullmann de 1976 et VF2 de Cordella et ses collègues en 2004, utilisent la même idée de backtracking avec élagage qu'à la section 5, mais ils cherchent un motif, pas une correspondance parfaite, et aucune borne quasi-polynomiale n'est attendue pour eux. Quand quelqu'un dit qu'un problème est « un problème d'isomorphisme de graphes », il vaut la peine de demander lequel des deux il veut dire.

11. Où sert le test d'isomorphisme

• Chimie. Les liaisons d'une molécule forment un graphe, et les bases de données chimiques utilisent des formes canoniques pour stocker chaque structure une seule fois et retrouver un composé instantanément. L'isomorphisme de graphes est nécessaire mais pas suffisant pour l'identité chimique : les stéréoisomères partagent le même graphe de liaisons et diffèrent par leur disposition dans l'espace.
• Vérification de circuits. Vérifier qu'un dessin de puce met bien en œuvre son schéma, ce que l'on appelle « layout versus schematic », implique de mettre en correspondance le réseau de transistors extrait du dessin avec le réseau prévu.
• Énumération et bases de données. Générer tous les graphes, toutes les molécules ou toutes les conceptions d'une taille donnée oblige à écarter les doublons, ce qui demande un calcul de forme canonique pour chaque candidat.
• Apprentissage automatique sur les graphes. Le lien avec Weisfeiler–Leman de la section 6 sert à la fois à mesurer ce que les réseaux de neurones en graphe peuvent exprimer et comme méthode de référence rapide pour comparer des graphes.
• Symétrie en optimisation. Les automorphismes de la structure d'un problème signifient de nombreuses solutions équivalentes ; les détecter permet à un solveur d'en sauter les copies.

12. Erreurs fréquentes

13. Glossaire

15. Références

Les définitions, théorèmes et attributions ci-dessus proviennent de ces sources, classées par ordre chronologique.

1. Pólya, G. (1937). "Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen." Acta Mathematica 68, 145 à 254. Dénombrer des objets à symétrie près.
2. Frucht, R. (1939). "Herstellung von Graphen mit vorgegebener abstrakter Gruppe." Compositio Mathematica 6, 239 à 250.
3. Collatz, L. et Sinogowitz, U. (1957). "Spektren endlicher Grafen." Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 21, 63 à 77. Graphes cospectraux.
4. Erdős, P. et Rényi, A. (1963). "Asymmetric Graphs." Acta Mathematica Academiae Scientiarum Hungaricae 14, 295 à 315.
5. Weisfeiler, B. et Leman, A. (1968). "The Reduction of a Graph to Canonical Form and the Algebra Which Appears Therein." Nauchno-Technicheskaya Informatsia, série 2, n° 9, 12 à 16.
6. Cook, S. A. (1971). "The Complexity of Theorem-Proving Procedures." Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, 151 à 158. L'isomorphisme de sous-graphe aussi difficile que la satisfaisabilité.
7. Aho, A. V., Hopcroft, J. E. et Ullman, J. D. (1974). The Design and Analysis of Computer Algorithms. Reading, Massachusetts : Addison-Wesley. Isomorphisme d'arbres en temps linéaire.
8. Hopcroft, J. E. et 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 à 184.
9. Ullmann, J. R. (1976). "An Algorithm for Subgraph Isomorphism." Journal of the ACM 23(1), 31 à 42.
10. Babai, L., Erdős, P. et Selkow, S. M. (1980). "Random Graph Isomorphism." SIAM Journal on Computing 9(3), 628 à 635.
11. McKay, B. D. (1981). "Practical Graph Isomorphism." Congressus Numerantium 30, 45 à 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 à 65.
13. Boppana, R. B., Håstad, J. et Zachos, S. (1987). "Does co-NP Have Short Interactive Proofs?" Information Processing Letters 25(2), 127 à 132.
14. Cordella, L. P., Foggia, P., Sansone, C. et Vento, M. (2004). "A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs." IEEE Transactions on Pattern Analysis and Machine Intelligence 26(10), 1367 à 1372.
15. McKay, B. D. et Piperno, A. (2014). "Practical Graph Isomorphism, II." Journal of Symbolic Computation 60, 94 à 112.
16. Babai, L. (2016). "Graph Isomorphism in Quasipolynomial Time." Proceedings of the 48th Annual ACM Symposium on Theory of Computing, 684 à 697.
17. Diestel, R. (2017). Graph Theory, 5e édition. Graduate Texts in Mathematics 173. Berlin : Springer.
18. Xu, K., Hu, W., Leskovec, J. et Jegelka, S. (2019). "How Powerful are Graph Neural Networks?" International Conference on Learning Representations.