Prueba de isomorfismo de grafos de Weisfeiler-Leman

En teoría de grafos , la prueba de isomorfismo de grafos de Weisfeiler-Leman es una prueba heurística para la existencia de un isomorfismo entre dos grafos G y H. ^[1] Es una generalización del algoritmo de refinamiento de color y fue descrita por primera vez por Weisfeiler y Leman en 1968. ^[2] La formulación original se basa en la canonización de grafos , una forma normal para grafos, mientras que también hay una interpretación combinatoria en el espíritu del refinamiento de color y una conexión con la lógica.

Existen varias versiones de la prueba (p. ej., k-WL y k-FWL) a las que se hace referencia en la literatura con distintos nombres, lo que fácilmente genera confusión. Además, Andrey Leman se escribe "Lehman" en varios artículos antiguos.

Heurísticas de isomorfismo de grafos basadas en Weisfeiler-Leman

Todas las variantes del refinamiento de color son heurísticas unilaterales que toman como entrada dos gráficos G y H y generan un certificado de que son diferentes o "No sé". Esto significa que si la heurística es capaz de distinguir G y H , entonces son definitivamente diferentes, pero la otra dirección no se cumple: para cada variante de la prueba WL (ver a continuación) hay gráficos no isomorfos donde no se detecta la diferencia. Esos gráficos son gráficos altamente simétricos, como los gráficos regulares para 1-WL/refinamiento de color.

Weisfeiler-Leman unidimensional (1-WL)

La prueba de isomorfismo de grafos unidimensionales es esencialmente la misma que el algoritmo de refinamiento de color (la diferencia tiene que ver con los no bordes y es irrelevante para todos los fines prácticos, ya que es trivial ver que los grafos con una cantidad diferente de nodos no son isomorfos). El algoritmo procede de la siguiente manera:

Inicialización Todos los nodos se inicializan con el mismo color 0

Refinamiento Dos nodos u,v obtienen un color diferente si a) tenían un color diferente antes o b) hay un color c tal que u y v tienen un número diferente de vecinos de color c

Terminación El algoritmo finaliza si la partición inducida por dos pasos de refinamiento sucesivos es la misma.

Para utilizar este algoritmo como una prueba de isomorfismo de grafos, se ejecuta el algoritmo en dos grafos de entrada G y H en paralelo, es decir, se utilizan los colores al dividir de modo que algún color c (después de una iteración) pueda significar "un nodo con exactamente 5 vecinos de color 0". En la práctica, esto se logra ejecutando el refinamiento de color en el grafo de unión disjunto de G y H. Luego, se puede observar el histograma de colores de ambos grafos (contando el número de nodos después de que se estabilizó el refinamiento de color) y, si difieren, esto es un certificado de que ambos grafos no son isomorfos.

El algoritmo finaliza después de un máximo de rondas, donde es el número de nodos del gráfico de entrada, ya que debe dividir una partición en cada paso de refinamiento y esto puede suceder como máximo hasta que cada nodo tenga su propio color. Tenga en cuenta que hay gráficos para los que se necesita este número de iteraciones, aunque en la práctica el número de rondas hasta la finalización tiende a ser muy bajo (<10). ${\estilo de visualización n-1}$ ${\estilo de visualización n}$

El refinamiento de la partición en cada paso se realiza procesando para cada nodo su etiqueta y las etiquetas de sus vecinos más cercanos. Por lo tanto, WLtest puede considerarse como un algoritmo de paso de mensajes que también lo conecta a redes neuronales gráficas .

Weisfeiler-Leman de orden superior

Aquí es donde aparecen las dos variantes antes mencionadas del algoritmo WL. Tanto el algoritmo Weisfeiler-Leman k -dimensional (k-WL) como el algoritmo Weisfeiler-Leman k -dimensional folklórico (k-FWL) son extensiones del 1-WL mencionado anteriormente que operan sobre k-tuplas en lugar de nodos individuales. Si bien su diferencia parece inocente a primera vista, se puede demostrar que k-WL y (k-1)-FWL (para k>2) distinguen los mismos pares de grafos.

k-WL (k>1)

Entrada : un gráfico G = (V,E)#inicializar $c^{0}({\bar {v}})={\text{Hash}}({\text{tipo}}({\bar {v}}))$ para todos repetir para todos hasta que (ambos colorantes induzcan particiones idénticas de ) regresar ${\bar {v}}\en V^{k}$   $c_{i}^{\ell }({\bar {v}})=\{\!\{c^{\ell -1}({\bar {w}}):{\bar {w}}\in {\mathcal {N}}_{i}({\bar {v}})\}\!\}$  ${\bar {v}}\en V^{k},i\en [k]$   $c^{\ell }({\bar {v}})={\text{Hash}}(c^{\ell -1}({\bar {v}}),c_{1}^{\ell }({\bar {v}}),\dots ,c_{k}^{\ell }({\bar {v}}))$   $c^{\ell }\equiv c^{\ell -1}$  $V^{k}$   $c^{\ell }$

Aquí, la vecindad de una k-tupla está dada por el conjunto de todas las k-tuplas alcanzables intercambiando la i-ésima posición de : El tipo atómico de una tupla codifica la información de borde entre todos los pares de nodos de . Por ejemplo, una 2-tupla tiene solo dos tipos atómicos posibles, es decir, los dos nodos pueden compartir un borde o no. Tenga en cuenta que si el gráfico tiene múltiples (diferentes) relaciones de borde o características de nodo adicionales, la pertenencia a ellas también se representa en . ${\mathcal {N}}_{i}({\bar {v}})$ ${\bar {v}}$ ${\bar {v}}$ ${\mathcal {N}}_{i}({\bar {v}})=\{(v_{1},\dots ,v_{i-1},w,v_{i+1},\dots ,v_{k}):w\in V\}$ ${\text{type}}({\bar {v}})$ ${\bar {v}}$ ${\text{type}}({\bar {v}})$

La idea clave de k-WL es expandir la noción de vecindad a k-tuplas y luego ejecutar efectivamente el refinamiento de color en el gráfico resultante.

k-FWL (k>1)

Entrada : un gráfico G = (V,E)#inicializar $c^{0}({\bar {v}})={\text{Hash}}({\text{type}}({\bar {v}})$ ) para todos repetir para todos hasta que (ambos colorantes induzcan particiones idénticas de ) regresar ${\bar {v}}\in V^{k}$   $c_{w}^{\ell }({\bar {v}})={\big (}c^{\ell -1}({\bar {v}}[1]\!\!\leftarrow \!w),\dots ,c^{\ell -1}({\bar {v}}[k]\!\!\leftarrow \!w){\big )}$  ${\bar {v}}\in V^{k},w\in V$   $c^{\ell }({\bar {v}})={\text{Hash}}{\big (}c^{\ell -1}({\bar {v}}),\{\!\{c_{w}^{\ell }({\bar {v}}):w\in V\}\!\}{\big )}$   $c^{\ell }\equiv c^{\ell -1}$  $V^{k}$   $c^{\ell }$

Aquí está la tupla donde la posición i-ésima se intercambia para ser . ${\bar {v}}[i]\!\!\leftarrow \!w$ ${\bar {v}}$ $w$

Tenga en cuenta que existe una diferencia importante entre k-WL y k-FWL: k-FWL verifica qué sucede si se coloca un solo nodo w en cualquier posición de la k-tupla (y luego calcula el multiconjunto de estas k-tuplas), mientras que k-WL analiza los multiconjuntos que se obtienen al cambiar solo el componente i-ésimo de la k-tupla original. Luego, utiliza todos esos multiconjuntos en el hash que calcula el nuevo color.

Se puede demostrar (aunque sólo a través de la conexión con la lógica) que k-FWL y (k+1)-WL son equivalentes (para ). Dado que ambos algoritmos escalan exponencialmente en k (ambos iteran sobre todas las k-tuplas), el uso de k-FWL es mucho más eficiente que el uso del equivalente (k+1)-WL. $k\geq 2$

Ejemplos y código para 1-WL

Código

# ALGORITMO WLpairs # ENTRADA: dos grafos G y H para probar si hay isomorfismo # SALIDA: Certificados para G y H y si concuerdan U  =  combineTwo ( G ,  H ) glabels  =  initializeLabels ( U )  # diccionario donde cada nodo obtiene la misma etiqueta 0 labels  =  {}  # diccionario que proporcionará la traducción de una cadena de etiquetas de un nodo y sus vecinos a un entero newLabel  =  1 done  =  False while  not ( done ):  glabelsNew  =  {}  # configura el diccionario de etiquetas para el siguiente paso  for  node  in  U :  label  =  str ( glabels [ node ])  +  str ([ glabels [ x ]  for  x  in  neighbors  of  node ] . sort ())  if  not ( label  in  labels ):  # se encuentra por primera vez una combinación de etiquetas del nodo y sus vecinos  labels [ label ]  =  newLabel  # asigna la cadena de etiquetas a un nuevo número como un etiqueta abreviada  newLabel  +=  1  # incrementa el contador para asignar nuevas etiquetas abreviadas  glabelsNew [ nodo ]  =  etiquetas [ etiqueta ]  if  ( número  de  etiquetas diferentes  en glabels ) == ( número de etiquetas diferentes en glabelsNew ): done = True else : glabels = glabelsNew . copy ( ) certificadoG = certificado para G de las etiquetas ordenadas de la parte G de U certificadoH = certificado para H de las etiquetas ordenadas                                      de  la  H - parte  de  U si  certificadoG  ==  certificadoH :  prueba  =  True de lo contrario :  prueba  =  False

Aquí hay un código Python real que incluye la descripción de los primeros ejemplos.

g5_00  =  { 0 :  { 1 ,  2 ,  4 },  1 :  { 0 ,  2 },  2 :  { 0 ,  1 ,  3 },  3 :  { 2 ,  4 },  4 :  { 0 ,  3 }} g5_01  =  { 0 :  { 3 ,  4 },  1 :  { 2 ,  3 ,  4 },  2 :  { 1 ,  3 },  3 :  { 0 ,  1 ,  2 },  4 :  { 0 ,  1 }} g5_02  =  { 0 :  { 1 ,  2 ,  4 },  1 :  { 0 ,  3 },  2 :  { 0 ,  3 },  3 :  { 1 ,  2 ,  4 },  4 :  { 0 ,  3 }}def  combineTwo ( g1 ,  g2 ) :  g  =  {  } n  =  len ( g1 )  para  nodo  en  g1 :  s  =  set ( )  para  vecino  en  g1 [ nodo ]  : s.add ( vecino ) g [ nodo ] = s.copy ( ) para nodo en g2 : s = set ( ) para vecino en g2 [ nodo ] : s.add ( vecino + n ) g [ nodo + n ] = s.copy ( ) return g                        g  =  combineTwo ( g5_00 ,  g5_02 ) etiquetas  =  {} etiquetasgla  =  {} para  i  en  rango ( len ( g )):  etiquetasgla [ i ]  =  0 etiquetasglaCount  =  1 nuevaetiqueta  =  1hecho  =  Falso mientras  no  ( hecho ):  glabelsNew  =  {}  glabelsCountNew  =  0  para  nodo  en  g :  etiqueta  =  str ( glabels [ nodo ])  s2  =  []  para  vecino  en  g [ nodo ]:  s2 . append ( glabels [ vecino ])  s2 . sort ()  para  i  en  rango ( len ( s2 )):  etiqueta  +=  "_"  +  str ( s2 [ i ])  si  no  ( etiqueta  en  etiquetas ):  etiquetas [ etiqueta ]  =  newlabel  newlabel  +=  1  glabelsCountNew  +=  1  glabelsNew [ nodo ]  =  etiquetas [ etiqueta ]  si  glabelsCount  ==  glabelsCountNew :  hecho  =  Verdadero  de lo contrario :  glabelsCount  =  glabelsCountNew  glabels  =  glabelsNew . copy () imprimir ( glabels )g0labels  =  [] para  i  en  rango ( len ( g0 )):  g0labels . append ( glabels [ i ]) g0labels . sort () certificado0  =  "" para  i  en  rango ( len ( g0 )):  certificado0  +=  str ( g0labels [ i ])  +  "_" g1labels  =  [] para  i  en  rango ( len ( g1 )):  g1labels . append ( glabels [ i  +  len ( g0 )]) g1labels . sort () certificado1  =  "" para  i  en  rango ( len ( g1 )):  certificado1  +=  str ( g1labels [ i ])  +  "_"si  certificado0  ==  certificado1 :  prueba  =  True de lo contrario :  prueba  =  False print ( "Certificado 0:" ,  certificado0 ) print ( "Certificado 1:" ,  certificado1 ) print ( "La prueba produce:" ,  prueba )

Ejemplos

Los primeros tres ejemplos son para gráficos de orden 5. ^[3]

WLpair realiza 3 rondas en 'G0' y 'G1'. La prueba es satisfactoria, tal y como indican los certificados.

WLpair realiza 4 rondas en 'G0' y 'G2'. La prueba falla porque los certificados no coinciden. De hecho, 'G0' tiene un ciclo de longitud 5, mientras que 'G2' no, por lo que 'G0' y 'G2' no pueden ser isomorfos.

WLpair realiza 4 rondas en 'G1' y 'G2'. La prueba falla porque los certificados no coinciden. De las dos instancias anteriores ya sabemos ... $G_{1}\cong G_{0}\not \cong G_{2}$

De hecho, G0 y G1 son isomorfos. Cualquier isomorfismo debe respetar los componentes y, por lo tanto, las etiquetas. Esto se puede utilizar para la kernelización del problema de isomorfismo de grafos. Nótese que no todo mapa de vértices que respeta las etiquetas da un isomorfismo. Sean y mapas dados por resp. . Mientras que no es un isomorfismo constituye un isomorfismo. $\varphi :G_{0}\rightarrow G_{1}$ $\psi :G_{0}\rightarrow G_{1}$ $\varphi (a)=D,\varphi (b)=C,\varphi (c)=B,\varphi (d)=E,\varphi (e)=A$ $\psi (a)=B,\psi (b)=C,\psi (c)=D,\psi (d)=E,\psi (e)=A$ $\varphi$ $\psi$

Al aplicar WLpair a G0 y G2 obtenemos para G0 el certificado 7_7_8_9_9 . Pero el isomorfo G1 obtiene el certificado 7_7_8_8_9 al aplicar WLpair a G1 y G2 . Esto ilustra el fenómeno sobre las etiquetas que dependen del orden de ejecución de WLtest en los nodos. O bien se encuentra otro método de reetiquetado que mantenga la unicidad de las etiquetas, lo que se vuelve bastante técnico, o se omite el reetiquetado por completo y se mantienen las cadenas de etiquetas, lo que aumenta significativamente la longitud del certificado, o se aplica WLtest a la unión de los dos grafos probados, como hicimos en la variante WLpair. Tenga en cuenta que aunque G1 y G2 pueden obtener certificados distintos cuando WLtest se ejecuta en ellos por separado, obtienen el mismo certificado por WLpair.

El siguiente ejemplo trata de grafos regulares . WLtest no puede distinguir grafos regulares de igual orden, ^[4]^{: 31} pero WLpair puede distinguir grafos regulares de distinto grado incluso si tienen el mismo orden. De hecho, WLtest termina después de una sola ronda como se ve en estos ejemplos de orden 8, que son todos 3-regulares excepto el último que es 5-regular.

Los cuatro gráficos son no isomorfos por pares. G8_00 tiene dos componentes conectados, mientras que los demás no. G8_03 es 5-regular, mientras que los demás son 3-regulares. G8_01 no tiene 3-ciclos, mientras que G8_02 sí los tiene.

Aquí se da otro ejemplo de dos gráficos no isomorfos que WLpair no puede distinguir . ^[5]

Aplicaciones

La teoría detrás de la prueba de Weisfeiler Leman se aplica en redes neuronales gráficas .

Núcleos de gráficos de Weisfeiler-Leman

En el aprendizaje automático de datos no lineales, se utilizan núcleos para representar los datos en un espacio de características de alta dimensión, tras lo cual se pueden aplicar técnicas lineales como las máquinas de vectores de soporte . Los datos representados como gráficos a menudo se comportan de forma no lineal . Los núcleos de gráficos son un método para preprocesar dichos datos no lineales basados en gráficos para simplificar los métodos de aprendizaje posteriores. Dichos núcleos de gráficos se pueden construir ejecutando parcialmente una prueba de Weisfeiler-Leman y procesando la partición que se ha construido hasta ese punto. ^[6] Estos núcleos de gráficos de Weisfeiler-Leman han atraído una considerable investigación en la década posterior a su publicación. ^[1] También se implementan en bibliotecas dedicadas a núcleos de gráficos como GraKeL. ^[7]

Tenga en cuenta que los núcleos para redes neuronales artificiales en el contexto del aprendizaje automático , como los núcleos de gráficos, no deben confundirse con los núcleos aplicados en algoritmos heurísticos para reducir el costo computacional para resolver problemas de alta complejidad, como los casos de problemas NP-hard en el campo de la teoría de la complejidad . Como se indicó anteriormente, la prueba de Weisfeiler-Leman también se puede aplicar en el contexto posterior.

Véase también

Referencias

^ ab Huang, Ningyuan; Villar, Soledad (2022), "Un breve tutorial sobre la prueba Weisfeiler-Lehman y sus variantes", ICASSP 2021 - 2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) , pp. 8533–8537, arXiv : 2201.07083 , doi :10.1109/ICASSP39728.2021.9413523, ISBN 978-1-7281-7605-5, Número de identificación del sujeto 235780517
^ Weisfeiler, B. Yu. ; Leman, AA (1968). "Una reducción de un gráfico a una forma canónica y un álgebra que surge durante esta reducción" (PDF) . Nauchno-Technicheskaya Informatsia . 2 (9): 12–16 . Consultado el 28 de octubre de 2023 .
^ Bieber, David (10 de mayo de 2019). «La prueba de isomorfismo de Weisfeiler-Lehman» . Consultado el 28 de octubre de 2023 .
^ Kiefer, Sandra (2020). Potencia y límites del algoritmo Weisfeiler-Leman (tesis doctoral). Universidad RWTH de Aquisgrán . Consultado el 29 de octubre de 2023 .
^ Bronstein, Michael (1 de diciembre de 2020). "Poder expresivo de las redes neuronales gráficas y la prueba de Weisfeiler-Lehman" . Consultado el 28 de octubre de 2023 .
^ Shervashidze, Nino; Schweitzer, Pascal; Van Leeuwen, Erik Jan; Mehlhorn, Kurt; Borgwardt, Karsten M. (2011). "Weisfeiler-Lehman Graph Kernels". Revista de investigación en aprendizaje automático . 12 (9): 2539−2561 . Consultado el 29 de octubre de 2023 .
^ "Weisfeiler Lehman Framework". 2019 . Consultado el 29 de octubre de 2023 . Este marco de Weisfeiler Lehman opera sobre núcleos de grafos existentes y está inspirado en la prueba de isomorfismo de grafos de Weisfeiler-Lehman [WL68].