algorithm - representations - graphs c++

Minería guiada de subestructuras comunes en un gran conjunto de gráficos (4)

Tengo un conjunto grande (> 1000) de gráficos acíclicos dirigidos con un conjunto de vértices grande (> 1000) cada uno. Los vértices están etiquetados, la cardinalidad de la etiqueta es pequeña (<30)

Quiero identificar (minas) las subestructuras que aparecen con frecuencia en todo el conjunto de gráficos.

Una subestructura es un gráfico de al menos dos vértices conectados directamente con etiquetas específicas. Tal subestructura puede aparecer una o más veces en uno o más de los gráficos de entrada dados. Por ejemplo, "a [el vértice etiquetado A con dos niños directamente conectados con la etiqueta B] aparece dos veces en el gráfico U y una vez en el gráfico V" .
Una subestructura que estamos buscando debe obedecer a un conjunto de reglas predeterminadas que se filtran en las etiquetas de los vértices. Como ejemplo: Una subestructura que contiene un vértice etiquetado A es interesante si el sub-gráfico es "un vértice etiquetado A que tiene al menos un niño directamente conectado etiquetado B y no es un hermano directamente conectado de un vértice etiquetado como U o V" . Las subestructuras que no se ajustan a estas reglas pueden aparecer en los gráficos de entrada pero no son de interés para la búsqueda.

El resultado que estamos buscando es una lista de subestructuras y su (número de) apariciones en los gráficos dados .

Intenté investigar las cosas y (como parece suceder siempre conmigo) el problema es NP completo. Por lo que puedo ver, gSpan es el algoritmo más común para resolver este problema. Sin embargo, como se dijo anteriormente, no estoy buscando ninguna subestructura común en los gráficos, sino solo aquellos que obedezcan ciertas reglas. Uno debería poder usarlo para reducir el espacio de búsqueda.

¿Alguna idea sobre cómo abordar este problema?

Actualización: probablemente debería agregar que las reglas mencionadas anteriormente pueden ser recursivas hasta cierto punto. Por ejemplo, "un vértice etiquetado A con al menos dos niños etiquetados B, cada uno con al menos un niño con la etiqueta A". La profundidad máxima de recursión está en algún lugar entre 1 y 10.

Actualización II: Señalando que no estamos buscando subestructuras conocidas o preferidas, sino que las estamos extrayendo. No hay aguja de ~~cuchara~~ .

Asumo en mi respuesta que estás tratando de minimizar el tiempo de ejecución y no querer gastar una cantidad excesiva de tiempo escribiendo el código para hacerlo. Una cosa con la que tuve problemas al principio al aprender a escribir algoritmos altamente eficientes fue que a veces los pases múltiples pueden ser mucho más eficientes. En este caso, yo diría, fundamentalmente, que quieres tener dos pases:

Primero, crea un filtro que te permita ignorar la mayoría (si no todos) los patrones no duplicados. Para hacer esto:

Asigne matrices de dos bits (y considere los tamaños de caché al hacer esto). El primero será un filtro de floración simple. El segundo será un filtro de floración duplicado.
A medida que recorre la estructura en una primera pasada, para cada estructura indexable, calcule un valor hash. Seleccione el bit apropiado en su primer filtro bloom y configúrelo. Si ese bit ya estaba configurado, también establezca el bit correspondiente en el filtro de duplicado de floración.

En su segundo pase, tendrá que hacer el proceso "más pesado" para confirmar las coincidencias. Para lograr esto:

Examine de nuevo el gráfico y registre las estructuras que coincidan con el filtro de duplicación generado generado en la primera pasada.
Coloque los que coinciden en una tabla hash (lo ideal sería utilizar diferentes bits del hash calculado)
Cuando se detecta un duplicado, almacene esa información donde quiera que quiera recolectarla.

Este algoritmo se ejecutará muy rápidamente en grandes conjuntos de datos porque reducirá significativamente la presión en el nivel de caché apropiado. También hay varias mejoras que puede realizar para mejorar su rendimiento en diferentes circunstancias.

Para mejorar el rendimiento en un sistema multiproceso, es seguro paralizar el primer paso. Para hacer esto, dé a cada hilo (o computadora en un clúster) una parte del gráfico. Cada uno debe calcular su propia copia de las dos flores. Las flores pueden combinarse en un florecimiento final. La función de reducción es justa (presente, duplicado) = (presente1 O presente2, duplicado1 O duplicado2 O (presente1 Y presente2)). Este paso es MUY rápido.
También es completamente seguro paralizar el segundo paso, pero debe modificarse ligeramente. Para hacer eso, tomará el filtro de florecimiento duplicado del primer paso y lo usará como filtro en el segundo paso, el mismo que antes. Sin embargo, no puede completar la comparación final tan fácilmente. En su lugar, debe colocar los posibles duplicados en los depósitos de hash. Luego, después de que cada fragmento de datos se haya escrito en su propia lista de posibles tablas de hash duplicadas, divida los datos entre hash y, en un tercer paso, encuentre los duplicados. Cada cubo hash (de cualquier salida en el segundo paso) debe ser procesado por el mismo trabajador.
En los casos en los que tiene una gran cantidad de estructuras que está indexando, puede mejorar el rendimiento al aplicar recursivamente el algoritmo anterior. El ajuste es que usa cada categoría coincidente para la salida del algoritmo anterior como su entrada en el pase recursivo. Por ejemplo, si indexa solo estructuras que tienen hasta 5 elementos en la primera ejecución del algoritmo, puede, cuando recurse, tomar cada conjunto de subgrafos duplicados y ejecutar el algoritmo solo en esos subgráficos. Esto solo sería necesario con grandes conjuntos de datos, obviamente.
Otro ajuste que puede considerar si el gráfico es muy grande para aumentar la efectividad de sus filtros de floración es iterar en el algoritmo. En la primera pasada, por ejemplo, solo puede considerar los subgráficos que tienen la primera etiqueta como base del sub-gráfico. Esto disminuiría el tamaño requerido de sus filtros de floración y / o le permitiría filtrar más sub-gráficos en la primera pasada.

Un par de notas para ajustar lo anterior:

Considera los tamaños de caché. Por ejemplo, en un chip Intel Haswell, cada núcleo tiene 32K en caché L1 y 256K en caché L2. Cada línea de caché contendrá 512 bits, por lo que si llena el 1% de su filtro de floración, se tocarán la mayoría de las líneas de caché. Dependiendo de qué tan rápido sean otras partes del algoritmo y de que otras cosas usen estas memorias caché, puede crear de manera segura un filtro de floración que tenga hasta 512 * 1024 entradas (8 entradas por bit por filtro = 128k, en sistemas con hiperfrecuencia, que es la cantidad de L2 que obtienes) y aún conserva la mayor parte del conjunto de datos en la memoria caché L2 y las cosas realmente activas en L1. Para conjuntos de datos más pequeños, mantenga este número abajo porque no tiene sentido agrandarlo. Si solo está marcando las características como potenciales duplicados cuando no son menos del 1% del tiempo, eso está totalmente bien.
Paralelizar esto es, nuevamente, solo realmente útil en casos donde tienes toneladas de datos. Supongo que puedes. Si haces la paralelización, debes considerar la geometría. Colocar conjuntos parciales de datos en cada computadora funcionará con este algoritmo. Luego puede ejecutar cada iteración (en la variación n. ° 4) en cada computadora. En los casos en que tenga enormes conjuntos de datos que evitarán tener que transferir todos los datos a todas las computadoras.

De todos modos, para resumir con una declaración sobre la complejidad del tiempo de ejecución, diré que realmente depende. Muchas personas ignoran el hecho de que aumentar el conjunto de datos de trabajo hará que los accesos a memoria no sean todos iguales en costo. Fundamentalmente, el algoritmo anterior, aunque altamente eficiente, si se sintoniza adecuadamente, funcionará muy rápido en un pequeño conjunto de datos, pero realmente brilla con conjuntos de datos mucho más grandes porque permite formas de alta eficiencia de mantener el conjunto de datos en funcionamiento en cualquier nivel de caché es apropiado (L1, L2, L3, RAM, disco local, red local, etc.) La complejidad del algoritmo dependerá de los datos, pero no creo que se pueda crear un algoritmo mucho más rápido. Dejé de lado cómo representas los subgrafos y hay trabajo por hacer allí para lograr el algoritmo óptimo, pero sin saber más, no puedo determinar la mejor manera de almacenar esa información.

La razón por la que un algoritmo no puede ejecutarse mucho más rápido que el que he presentado es que el primer paso requerirá mucho menos trabajo para ejecutarse que el segundo porque no requiere ramificación y es menos trabajo realizar operaciones bit a bit. Por lo tanto, podemos decir que agrega poco al trabajo general que estamos haciendo. La segunda etapa también es lo más eficiente posible. Debes (salvo que exista una manera de describir perfectamente cada posibilidad con un conjunto finito de bits, que explicaré por segundo) comparar realmente cada característica del gráfico y escribir la información en algún lugar. La única variable es cuánto trabajo es verificar si necesita hacer esto. Controlar un poco donde se puede escalar arbitrariamente la tasa de error hacia 0% es lo mejor que se puede obtener.

Para conjuntos de datos pequeños, la razón por la que dos pases lo benefician es que puede tener un número mucho mayor de cardinalidad de floración en una cantidad menor de memoria. Pero para conjuntos de datos realmente pequeños, también podría usar el segundo paso e ignorar el primero. Pero, como mínimo, deberá almacenar un puntero por cada destino hash. Esto significa que tendrá que escribir 32 o 64 veces más datos para el mismo nivel de filtrado. Para conjuntos de datos lo suficientemente pequeños, esto no importa porque una lectura es una lectura y una escritura es una escritura, pero para conjuntos de datos más grandes, esto puede permitirle lograr el mismo nivel de filtrado mientras permanece en un nivel dado de caché. En los casos en que deba trabajar en múltiples computadoras o hilos, el mecanismo provisto en este algoritmo será MUCHO más eficiente ya que los datos se pueden combinar mucho más rápido y se puede intercambiar mucha más información sobre posibles coincidencias.

Ahora, finalmente, como aludí, es posible que pueda mejorar un poco si se reduce aún más el número de funciones que comprueba en cada iteración. Por ejemplo, si solo está buscando 32 etiquetas posibles y la cantidad de niños con una etiqueta en particular en cada pasada (y está limitada a 1024), podría representar esto perfectamente con 15 bits. Si limitó el conteo a 255, puede almacenar esta información perfectamente con 32K. Para sacar esto adelante en su caso, necesitaría usar las estrategias de iteración, recursión y fragmentación que mencioné anteriormente y también necesitaría seguir el gráfico fuente y otra información. Sinceramente, dudo que esto funcione bien, excepto en situaciones muy limitadas, pero lo incluyo para que esté completo.

De todos modos, esta es mi primera respuesta en , así que no seas demasiado duro conmigo. ¡Espero que esto haya sido útil!

Tu pregunta:

Usted tiene: un conjunto de gráficos y un conjunto de reglas (vamos a llamar a la regla un patrón de subestructura).
Desea: un conteo de la ocurrencia de cada una de las subestructuras en el conjunto de gráficos.

Como los gráficos son DAG, en la búsqueda de subestructura no se verán atrapados en el ciclo.

El pseudocódigo de solución simple es:

for each graph G { //Sub-problem 4 for each node N { //Sub-problem 3 for each substructure pattern P { //Sub-problem 2 if N''s structure is like P { //Sub-problem 1 PatternCountMap.Get(G).Get(P)++; } } } }

En cada lugar he marcado el sub-problema que necesita ser manejado.

^{Si no conoce Map-Reduce, mi solución no será del todo clara para usted.} ^{Avísame si ese es el caso.} ^{En general, el código Map-Reduce siempre se puede ejecutar de forma general, excepto que tomará más tiempo para datos grandes.}

Subproblema 1

Este problema se puede simplemente escribir como:

Dado un nodo ''Root'' y dado un patrón P, ¿el árbol representado con este nodo como raíz sigue el patrón dado?

Este problema es solucionable. Simplemente recorra el gráfico comenzando desde la ''raíz'' y vea si se sigue el patrón. Si es así, aumente su conteo en el PatternCountMap , de lo contrario pase al siguiente patrón y vea si el ''root'' sigue el siguiente patrón.

El PatternCountMap es un HashMap>, que asigna los gráficos a otro HashMap que asigna patrones a su frecuencia. Entonces, si P se encuentra en los Gráficos G ₁ y G ₂ , 12 y 17 veces respectivamente, entonces PatternCountMap.Get (G ₁ ) .Get (P) será 12 y PatternCountMap.Get (G ₂ ) .Get (P) ser 17 al final de la ejecución de este algoritmo.

Consejo útil: dado que no desea recurrir demasiado profundo, use soluciones iterativas. Si tiene que realizar DFS, realice DFS iterativo usando una pila. El algoritmo iterativo DFS es bastante fácil.

Sub-problema 2

Aquí estamos simplemente repitiendo cada patrón (o reglas). No hay magia aquí. Para cada regla, vemos si el nodo N del Gráfico G sigue la regla.

Consejo útil: preprocesar las reglas. Por ejemplo, si se sigue una regla, vea qué otras reglas definitivamente no se pueden seguir para omitirlas. O bien, si seguir un patrón significa que también se puede seguir otro, vea si la segunda regla puede reducirse debido a la comprobación ya realizada como parte de la primera.

Sub-problema 3 y 4

Estos dos son simples bucles como el Sub-problema 2. Pero hay una idea que se puede aplicar aquí. Y eso es Map-Reduce (aunque ^[1] Map-Reduce no califica al 100% para estos problemas).

Tienes numerosos nodos de numerosos gráficos diferentes. Siempre que pueda identificar el gráfico al que pertenece el nodo, si un nodo en particular sigue un determinado patrón, puede emitir <N_G, P> , lo que significa que el Nodo N en el Gráfico G sigue el patrón (norma aka) P.

El resultado del mapa se puede recopilar en los reductores que pueden llenar el PatternCountMap con los valores. Mucho de eso es manejado por el marco Map-Reduce en sí mismo, por lo que se encargarán automáticamente de usted muchas cosas.

Después de que haya creado PatternCountMap , tiene el recuento de cada patrón útil en cada gráfico y eso es lo que quería.

^{^[1] Map-Reduce es para problemas que pueden resolverse en hardware básico.} ^{Si las reglas que está extrayendo son complejas, entonces el hardware básico puede no ser el que desea ejecutar con su algoritmo.}

Editar : Aquí es de lo que comenzaría:

Cree un índice de las posibles combinaciones padre / hijo de 30x30 en los nodos correspondientes
Intersecta los partidos para una subestructura dada
Verifique otras condiciones manualmente

(Publicación original):

Encuentre una forma de construir claves hash para las subestructuras
Construye un mapa hash desde las subestructuras hasta los nodos correspondientes
Encuentre candidatos usando el mapa hash, verifique las condiciones detalladas manualmente

De la forma en que leo su pregunta, es posible que desee algo así como el código a continuación. Encuentra todos los subgrafos coincidentes en un DAG en tiempo lineal. No admite filtros, pero puede verificar los resultados una vez que se encuentran y filtrarlos manualmente. También puede encontrar gráficos con algunas partes colapsadas. Digamos que está buscando un árbol a((b|c)|(c|d)) , entonces podría encontrar un subgráfico, donde el nodo c se comparte entre los dos subárboles. De nuevo, puede inspeccionar la salida y filtrar los resultados de esa manera. Por supuesto, hacer tal inspección solo es posible si el tamaño de salida no es demasiado grande. Para eso, tendrás que hacer algunos experimentos en tus propios gráficos.

from collections import namedtuple, defaultdict Node = namedtuple(''Node'', [''label'', ''children'', ''id'']) # Simple tree patternA(B|AB) pattern = Node(''A'', (Node(''B'', (), 1), Node(''A'', (Node(''B'', (), 3),), 2)), 0) # Generate random DAG import random labels = ''ABCDE'' dag = [] for _ in range(1000): label = random.choice(labels) children = tuple(random.sample(dag, min(len(dag)//2, 10))) dag.append(Node(label, children, len(dag))) # Helper def subtrees(pattern): yield pattern for sub in pattern.children: yield from subtrees(sub) colors = defaultdict(list) # Iterate the nodes in topologically sorted order for node in dag: # Check if the node is the head of some sub-pattern for sub in subtrees(pattern): if node.label == sub.label / and all(any(sc.id in colors[nc.id] for nc in node.children) for sc in sub.children): # If so, color the node with that sub-pattern''s color colors[node.id].append(sub.id) matches = [node for node in dag if pattern.id in colors[node.id]] print(''Found {} matches.''.format(len(matches)))

Creo que esto es muy similar al enfoque que Stefan Haustein tenía en mente.