Graφnity: ΠWEEK y afinidad en grafos completos

Resumen (tl;dr)

¿No sería útil conocer la afinidad que dos usuarios cualesquiera tienen en una red social? A menudo tenemos un montón de datos de cada usuario y sería muy interesante usarlos para comparar “similitudes” entre parejas de usuarios o incluso un grupo de usuarios. Alejandro Alonso y yo quisimos desarrollar una biblioteca tanto en python (lenguaje cómodo para nosotros) como en golang (que nunca habíamos tocado) a la que llamamos Graφnity y que nos sirvió no solo para enfrentarnos a un interesante reto sino para comparar la velocidad de ambas implementaciones. golang arrasó a python pero hay algo de espacio de mejora en ambos casos. Especialmente bloqueante es la estructura de datos que ha de generarse y almacenarse en memoria.

Alejandro Alonso y yo nos juntamos en esta VI ΠWEEK para resolver una necesidad de un proyecto de Angela Rivera de próxima publicación.

El objetivo del proyecto era poder resolver de forma cómoda y rápida la afinidad/similitud/química existente entre dos elementos de una red relativamente grande. Un ejemplo que seguro que ayuda a entenderlo sería encontrar la afinidad en gustos entre dos usuarios de una red social.

El problema y sus retos

El enunciado del problema es el siguiente:

_Tenemos un grafo G completo no dirigido de n nodos (todos los nodos conectados entre sí sin importar si vamos de un nodo n1 a un nodo n2 o en sentido contrario).

Cada nodo n tiene un conjunto A de atributos expresados cada uno como una lista de números (enteros, decimales, flotantes). Ese conjunto A es el mismo para todos los nodos.

Cada atributo a del conjunto A tiene asociado una función f de referencia que toma como input la concatenación de las listas de números para ese atributo a para dos o más nodos del grafo.

Existe una función de afinidad fa que aplica una aritmética sencilla sobre los resultados de las funciones f de referencia para todos los atributos._

Pongamos un ejemplo:

Tenemos un grafo G de 5 nodos {n1, n2, n3, n4, n5} y cada nodo tiene 3 atributos {a1, a2, a3}.

• a1 representa la edad (entero de 0 a 120)
• a2 representa los gustos (enteros representando los identificadores de los gustos)
• a3 representa el nivel de conocimientos en una determinada materia (flotante de 0.0 a 100.0)

<br /> n1: edad = [30], gustos = [1,5,7], nivel = [87.5]<br /> n2: edad = [15], gustos = [1], nivel = [70.2]<br /> n3: edad = [33], gustos = [2,3], nivel = [45.1]<br /> n4: edad = [54], gustos = [10], nivel = [80.0]<br /> n5: edad = [27], gustos = [5,7,9,10], nivel = [91.9]<br />

Para el atributo edad, tenemos una función de referencia para dos nodos o más que podemos expresar así:

<br /> func_edad = abs(mean(a) - stdev(x))/mean(x)<br />

que estaría representando una suerte de ratio entre un valor desviado el máximo de la desviación estándar respecto de la media y el valor de la media. Es solo un ejemplo de función.

Para el atributo de gustos, que representan identificadores (no valores numéricos como tales), podemos imaginarnos una función que otorgue 5 puntos por cada elemento repetido.

<br /> func_gustos = 5*(len(x) - distinct(x))<br />

y para la función de nivel de conocimientos podemos pensar en el inverso de su desviación estándar.

<br /> func_nivel = 1/stdev(x)<br />

Finalmente, la función de afinidad combina a su gusto el resultado de las otras tres funciones de referencia. Un ejemplo a vuelapluma podría ser:

<br /> func_afinidad = func_gustos(x) + func_nivel(x)/func_edad(x)<br />

Graφnity es capaz de calcular las funciones de afinidad para cada par de nodos, para un subconjunto arbitrario de nodos (una especie de afinidad de grupo) o la afinidad para un solo nodo con todos los demás (sin tener que hacer todos con todos).

Podemos resumir todo esto usando este gráfico.

Para el cálculo de todas las prejas de nodos, (5 nodos y 3 funciones) creamos una estructura de 25 parejas con 4 atributos cada una (3 para cada valor de la función de referencia por atributo y 1 para el total asociado a la afinidad).

Para el cálculo de un subconjunto basta con crear una estructura de 1 grupo y 4 atributos.

Para el cálculo de un solo nodo con todos lo demás, crearíamos una estructura de 5 parejas (un nodo con cada uno de los nodos) con 4 atributos cada una.

El reto es poder resolver esto, no con 5 nodos, sino con 1.000 o con 1.000.0000. La implementación actual obliga a crear la estructura n x n x a cuando queremos la solución completa. Con 1.000 nodos y 3 atributos, tendríamos 4.000.000 de registros (1.000.000 de parejas con 3+1 registros por pareja). Si un registro ocupa 100 bytes, el total rondaría los 380 MB de memoria RAM para almacenar la estructura de datos.

Si en lugar de 1.000 nodos tuviéramos 10.000, nos iríamos a 12 GB de RAM. El problema pasa a ser de gestión de recursos de memoria, no de procesamiento de las funciones en sí.

Para el cálculo de un solo nodo con el resto, la estructura de datos no crece n x n y con un grafo de 1.000.000 de nodos, la estructura de datos ocuparía en memoria menos de 1GB.

La implementación

Durante la PIWEEK realizamos dos implementaciones; una en python y otra en golang. Tanto Alex como yo nos sentimos cómodos en python pero nunca habíamos tocado golang.

La estrategia general era:

1. Creamos la estructura de datos necesaria para resolver n x n, n1 x n y {n1,n2…nm} (un proceso)
2. paralelizamos el cálculo de cada función de referencia para cada atributo (múltiples procesos)
3. con todos los subcálculos terminados, aplicamos la función de afinidad (un proceso)

Python

Graφnity (python) en github.

La creación y manejo de estructuras de datos y sus funciones lambda fue muy sencillo. Mucho más complicado fue paralelizar el cálculo de las funciones de referencia por problemas pickleando los datos y las funciones lambda. A su favor tiene la enorme colección de bibliotecas que nos permite definir funciones de referencia de forma muy cómoda.

Los tiempos se volvieron rápidamente inasumibles cuando pasamos el umbral de los 1000 nodos.

Nota: py-user representa el tiempo total de consumo agregado de cpus mientras que py-real representa el tiempo natural desde que se lanza la tarea.

Golang

Graφnity-go en github.

La creación y manejo de estructuras de datos fue bastante más laboriosa, probablemente también por ser nuestra primera experiencia con golang. La posibilidad de usar funciones lambda / function literals nos permitió reutilizar buena parte de la estrategia ya implementada en python. El uso de gorutinas y canales hizo prácticamente trivial el paralelizado de los trabajos por función, incluso compartiendo el puntero a una estructura común. En su contra la ausencia de bibliotecas estadísticas de uso común por la juventud del lenguaje.

En golang los tiempos de cálculo son excelentes pero a partir de 3.000 nodos topamos con el problema del tamaños de las estructuras de datos en memoria.

Nota: go-user representa el tiempo total de consumo agregado de cpus mientras que go-real representa el tiempo natural desde que se lanza la tarea. go-real-calculus es el tiempo natural dedicado solo al cálculo de funciones de referencia y la función de afinidad excluyendo el tiempo de creación de la estructura de datos en memoria.

Haciendo unos cálculos de servilleta sobre regresión por mínimos cuadrados sabemos que si no tuviéramos problemas de almacenamiento en memoria de los datos, en cinco minutos podríamos calcular el caso general de 10.000 nodos, es decir, una estructura de 2,100,000,000 (dos mil cien millones) de registros. No está mal, pero necesitaríamos 200GB de RAM 🙁

Podemos comparar fácilmente los dos comportamientos, de python y golang en esta gráfica.

Mejoras previstas

Las mejoras previstas para los próximos días son:

• Tratar de optimizar el espacio requerido para la estructura de datos. El objetivo es evitar la creación de estructuras n_ x n x _f.
• Permitir definir funciones de clases de equivalencia para agrupar grupos de nodos en un nodo representativo y evitar recalcular para cada nodo de cada grupo.
• Evaluar pypy como alternativa a python. No es difícil hacer backporting de módulos de estadísticas de python 3.4 a pypy 3.2 pero mucho más complejo se nos antoja el uso de dill (pickleado chulo) en pypy…

Conclusiones de la ΠWEEK

La ΠWEEK fue el escenario perfecto para resolver un problema de estas características. Combinando el trabajo en paralelo con el pair programming avanzamos a buen ritmo y disfrutamos de los éxitos parciales. Desarrollar con TDD aun en este pequeño programa fue clave para tener un marco de referencia entre las dos implementaciones, la de python y la de golang, lenguaje de programación que aprendimos a mitad de la ΠWEEK y que nos dejó bastante buen sabor de boca.