Estoy comparando un gran conjunto de gráficos de networkx para el isomorfismo, donde la mayoría de los gráficos no deberían ser isomorfos (digamos que 0-20% son isomorfos a algo en la lista, por ejemplo).

He intentado el siguiente enfoque.

graphs = [] # A list of networkx graphs
unique = [] # A list of unique graphs

for new in graphs:
    for old in unique:
        if nx.is_isomorphic(new, old[0]):
            break
    else:
        unique.append([new])

Esto me permitió obtener un conjunto reducido mucho más rápido, pero aún lo encuentro demasiado lento para un uso ideal. ¿Existe algún algoritmo más rápido para manejar este tipo de problema (comparando pares de propiedades conmutativas transitivas) o una forma de extender este algoritmo a una configuración multinúcleo (que se ejecuta en una máquina de 20 núcleos)?

Ya estoy filtrando estos conjuntos de datos en función del número de nodos / aristas, podemos suponer que la función nx.is_isomorphic no se puede hacer más rápido por ningún tipo de operaciones de filtrado. Tampoco puedo cambiar las herramientas fácilmente en este momento, por lo que usar un paquete compilado no es una opción.

Información Adicional:

Los gráficos tienden a ser aproximadamente 16-20 nodos con 24-48 bordes en total, hay mucha interconexión, por lo que cada nodo tiene aproximadamente 8 bordes. Cada borde también está etiquetado, pero solo se utilizan 2-3 tipos de bordes.

13
Tristan Maxson 29 oct. 2017 a las 14:46

3 respuestas

La mejor respuesta

Como otros han mencionado, si desea permanecer en Python + Networkx, puede usar could_be_isomorphic para filtrar sus gráficos.

El problema es que este método espera 2 gráficos como entrada, no millones. Si compara cada par de gráficos con este método, tomaría mucho tiempo.

Mirando el código fuente de {{X0 }}, compara el grado, el triángulo y el número de secuencias de camarillas para ambos gráficos. Si no son iguales, los gráficos no pueden ser isomorfos.

Puede empaquetar esta huella digital en una función, ordenar sus gráficos de acuerdo con esta huella digital y agruparlos con itertools.groupby. Habrá una gran mayoría de gráficos solitarios. Los pocos gráficos que tienen las mismas huellas digitales pueden verificarse por isomorfismo.

Usando una lista de 100 000 gráficos aleatorios:

many_graphs = [nx.fast_gnp_random_graph(random.randint(16, 22), 0.2) for _ in range(100000)]

Hubo solo 500 huellas digitales que fueron compartidas por al menos 2 gráficos. Si agrega información de tipos de bordes, habrá aún menos huellas digitales comunes.

Aquí hay un ejemplo con 3000 gráficos, cada uno con entre 10 y 14 nodos:

import networkx as nx
from itertools import groupby
import random

many_graphs = [nx.fast_gnp_random_graph(
    random.randint(10, 14), 0.3) for _ in range(3000)]


def graph_fingerprint(g):
    order = g.order()
    d = g.degree()
    t = nx.triangles(g)
    c = nx.number_of_cliques(g) 
    props = [[d[v], t[v], c[v]] for v in d]
    props.sort()
    # TODO: Add count of edge types.
    return(props)


sorted_graphs = sorted(many_graphs, key=graph_fingerprint)

for f, g in groupby(sorted_graphs, key=graph_fingerprint):
    similar_graphs = list(g)
    n = len(similar_graphs)
    if n > 1:
        print("Found %d graphs which could be isomorphic." % n)
        for i in range(n):
            for j in range(i + 1, n):
                g1, g2 = similar_graphs[i], similar_graphs[j]
                if g1 != g2 and nx.is_isomorphic(g1, g2):
                    print(" %s and %s are isomorphic!" %
                          (nx.generate_graph6(g1,header=False), nx.generate_graph6(g2,header=False)))

Encuentra 4 pares isomorfos en menos de 1s:

Found 2 graphs which could be isomorphic.
Found 3 graphs which could be isomorphic.
 Id?OGG_C? and IaKO_@?@? are isomorphic!
Found 6 graphs which could be isomorphic.
 I?OWcGG?G and I?OCSa?@_ are isomorphic!
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
 I_uI???JG and II??QDNA? are isomorphic!
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 3 graphs which could be isomorphic.
Found 3 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 3 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 3 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
 IDOCCY@GG and IOGC@`dS? are isomorphic!
Found 3 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 3 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 3 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 3 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.
Found 2 graphs which could be isomorphic.

Aquí están los 2 últimos gráficos isomorfos. "IDOCCY @ GG":

enter image description here

Y "IOGC @ \ dS?":

enter image description here

Aquí hay 2 gráficos que tienen la misma huella digital pero no son isomórficos:

enter image description here enter image description here

Las huellas digitales se pueden hacer en paralelo. La clasificación y la agrupación tendrían que ocurrir en 1 CPU, pero la verificación del isomorfismo para cada grupo podría realizarse en CPU distintas.

5
Eric Duminil 9 nov. 2017 a las 08:53

Puede probar su código en PyPy, que proporciona una compilación justo a tiempo para código Python puro. Para un posible aumento de rendimiento lo dicen ...

... depende en gran medida del tipo de tarea que se realiza. El promedio geométrico de todos los puntos de referencia es 0.13 o 7.5 veces más rápido que CPython

Si su carga de trabajo está vinculada a la CPU (lo que parece ser así) y el proceso de Python es de larga duración (por lo que se puede realizar la compilación JIT), entonces el aumento del rendimiento puede ser significativo. NetworkX es Python puro (tiene dependencias opcionales como numpy, pero son necesarias para una funcionalidad adicional) y específicamente módulo isomorph. Intenté los pases de PyPy 5.7.1 y networkx/algorithms/isomorphism/tests/test_isomorphism.py. La suite en general tiene algunas fallas:

Ran 2952 tests in 51.311s

FAILED (failures=3, skipped=54)
Test failed: <unittest.runner.TextTestResult run=2952 errors=0 failures=3>

En Python 2.7.12 es:

Ran 2952 tests in 88.915s

OK (skipped=54)
1
saaj 1 nov. 2017 a las 20:04

¿Se puede usar nauty (http://users.cecs.anu.edu.au/ ~ bdm / nauty /, disponible en distribuciones de linux)? Tiene un algoritmo de etiqueta canónica que es rápido y podría funcionar para su problema. Un etiquetado canónico hace que los gráficos isomórficos sean idénticos (canonización). Por ejemplo, el uso de la salida en formato graph6 de un conjunto de gráficos aleatorios proporciona el siguiente recuento de gráficos isomórficos

$ cat g6.py
import networkx as nx
for i in range(100000):
    print(nx.generate_graph6(nx.fast_gnp_random_graph(4,0.2),header=False))


$ python g6.py  |nauty-labelg  |sort |uniq -c 
>A labelg
>Z 100000 graphs labelled from stdin to stdout in 0.21 sec.
   4898 C`
    167 C^
     10 C~
  26408 C?
  39392 C@
  19684 CB
   1575 CF
   1608 CJ
   1170 CN
    288 Cr
   4800 CR

Esos son los 11 gráficos de 4 nodos:

$ cat atlas.py 
import networkx as nx
for g in  nx.atlas.graph_atlas_g()[8:19]:
     print(nx.generate_graph6(g,header=False))
$ python atlas.py  |nauty-labelg  |sort |uniq -c 
>A labelg
>Z 11 graphs labelled from stdin to stdout in 0.00 sec.
      1 C`
      1 C^
      1 C~
      1 C?
      1 C@
      1 CB
      1 CF
      1 CJ
      1 CN
      1 Cr
      1 CR

Sería bastante fácil paralelizar este enfoque si se ejecuta demasiado lento.

7
Aric 6 nov. 2017 a las 04:35