The Graph Mining Library - Biblioteca de algoritmos y análisis de grafos

 (github.com/google)
3 puntos por GN⁺ 2023-10-05 | 1 comentarios | Compartir por WhatsApp
  • El objetivo del equipo Google Graph Mining es crear una biblioteca altamente escalable para algoritmos y análisis de grafos y aplicarla en productos de Google; actualmente ofrece un conjunto de algoritmos de clustering
  • Las herramientas en desarrollo abarcan construcción de grafos de similitud, clustering, clasificación de nodos, embeddings de nodos, entrenamiento de redes neuronales de grafos, visualización de grafos, diversos tipos de muestreo y ranking por similitud
  • El área de clustering está compuesta por algoritmos paralelos de memoria compartida que escalan hasta grafos con decenas de miles de millones de aristas, junto con varios algoritmos secuenciales
  • Los algoritmos paralelos son implementaciones basadas en trabajos de investigación relacionados con HAC, clustering por correlación, affinity clustering y parline
  • El framework de Graph Neural Network se ofrece en un proyecto separado, TF-GNN
  • Para ejecutarlo rápidamente, instala Bazel y luego ejecuta bazel run //examples:quickstart
  • No es un producto con soporte oficial de Google; las preguntas y comentarios se gestionan creando issues en este repositorio

Lecturas relacionadas

1 comentarios

 
GN⁺ 2023-10-05
Opiniones en Hacker News

  • La minería de grafos estuvo muy de moda hace unos 10 años. Me hace pensar en GraphX (https://spark.apache.org/graphx/) y GraphLab (https://en.wikipedia.org/wiki/GraphLab), y en las bases de datos de grafos.
    Probablemente coincidió con el fenómeno de las redes sociales y, más recientemente, el aprendizaje geométrico, es decir, machine learning sobre grafos y otras estructuras, estaba llamando la atención hasta que los LLM le robaron el protagonismo. Aun así, creo que el aprendizaje geométrico todavía tiene mucho potencial y me gustaría que ganara más popularidad.

    • En las “bases de datos de grafos” hay una corriente que ve los grafos como un enfoque universal para los datos, con RDF y SPARQL, y muchísimos intentos similares. También se puede pensar en casos donde la estructura de datos central de un programa en C es un grafo de punteros.
      Estos grafos suelen tener una enorme cantidad de tipos de aristas distintos, como “casado con” o “tiene temperatura media anual”. En cambio, los algoritmos de grafos como PageRank o centralidad de grafos suelen tener un solo tipo de arista, o apenas unos pocos. Sí existen algoritmos generales que pueden aplicarse a grafos con múltiples tipos de aristas; por ejemplo, el patrón SPARQL ?s1 ?p ?o . ?s2 ?p ?o . encuentra ?s1 y ?s2 que comparten algún ?o y una relación ?p, y sirve como base para una medida de similitud entre ambos. En general, los grafos no tienen una forma fija, pueden tener cualquier estructura y, desde el punto de vista de la latencia de memoria, pueden ser un desastre. Hace tiempo, usando este patrón SPARQL, hice un programa que habría tardado 100 años; luego reempaqué la estructura de datos y encontré una aproximación para que se calculara en menos de 20 minutos. Por eso, en la práctica, muchos son escépticos respecto de las bibliotecas de procesamiento de grafos de propósito general. Es común encontrar problemas en los que se puede escribir código especializado en menos tiempo del que lleva pelearse con el sistema de build, y hacerlo 1000 veces más rápido.
      Aun así, si quieres seguir la tendencia, hoy arXiv está lleno de papers sobre redes neuronales de grafos que no reciben tanto hype en otros lugares. YOShInOn me preparó una larga lista de papers de GNN para revisar, pero solo hojeé algunos; hay muchos artículos que dicen que se pueden aplicar a problemas de análisis de texto como los míos, pero no parecen claramente mejores que el sistema que usamos YOShInOn y yo, así que no tengo prisa.
    • En problemas que se resuelven mejor con análisis de grafos, todavía se usa mucho NetworkX, y realmente me gusta la experiencia de desarrollo de este paquete.

  • Si alguien quiere experimentar con grafos y machine learning, hace poco, revisando la documentación de ArangoDB, vi que incluye integraciones con varias bibliotecas de grafos y frameworks de machine learning: https://docs.arangodb.com/3.11/data-science/adapters/
    También vi algunos notebooks de Jupyter sobre machine learning en grafos: https://github.com/arangodb/interactive_tutorials#machine-learning
    Entre las integraciones están NetworkX -- https://networkx.org/, DeepGraphLibrary -- https://www.dgl.ai/, cuGraph (Rapids.ai Graph) -- https://docs.rapids.ai/api/cugraph/stable/, y PyG (PyTorch Geometric) -- https://pytorch-geometric.readthedocs.io/en/latest/.

  • Si hay alguien familiarizado con Bazel, ¿podría dar alguna pista sobre cómo compilar? bazel build parece hacer algo, pero como resultado solo se crean bazel-build y bazel-build, y no veo ningún artefacto de compilación evidente

    • En Bazel, //... es parecido al objetivo all de make
      Se usa como bazel build //..., bazel test //..., bazel query //.... Si mal no recuerdo, el último comando lista todos los objetivos
    • Para complementar la respuesta anterior, también se puede compilar un solo paquete. Por ejemplo, se puede compilar asynchronous_union_find con bazel build //in_memory/connected_components:asynchronous_union_find
      Aunque quizá no sea muy útil fuera del contexto de una regla cc_binary. Este enfoque permite compilar y usar solo los paquetes que se necesitan en otros proyectos, sin compilar todo el repositorio. Por ejemplo, si solo quieres usar el header asynchronous_union_find.h, agrega la biblioteca graph-mining con una regla git_repository en algún lugar del archivo WORKSPACE de tu proyecto (ver el ejemplo de WORKSPACE.bazel) y agrega @graph-mining//in_memory/connected_components:asynchronous_union_find a una regla cc_library en el archivo BUILD dentro de tu proyecto. Entonces podrás incluirlo como header desde otros lugares y, al compilar tu proyecto, solo se compilarán ese paquete y sus dependencias, no toda la biblioteca graph-mining
    • Desde hace tiempo venía pensando que algún día tenía que revisar Bazel, y ese “algún día” terminó siendo hoy. Parece que la forma recomendada de instalarlo es instalar primero Bazelisk, renombrarlo a bazel y ponerlo en una ruta como /usr/local/bin/bazel
      Pero al ejecutar query aparece una advertencia del JDK, y al ejecutar build falla porque no hay Java, junto con WARNING: Ignoring JAVA_HOME, because it must point to a JDK, not a JRE.. Pasé unos minutos buscando qué JDK/JRE debía usar si ni siquiera uso Java, hasta que no pude más, así que el “algún día” de hoy volvió a quedar para otro día. Es casi vergonzoso lo mal acostumbrado que estoy a cargo o npm/yarn
      Edición: gracias a https://sdkman.io/ pude ejecutarlo. Al final no estuvo tan mal

  • Pregunta de principiante: ¿esta biblioteca podría considerarse una candidata para integrarla con wrappers o bibliotecas de extensión y reunir en un solo lugar algoritmos de clustering basados en grafos? Suponiendo que todavía no esté pensada así
    ¿O ya existe algún framework que ofrezca mejor la misma funcionalidad? Algo como NetworkX

  • Tal vez estoy muy atrasado con los tiempos, pero ¿esto está relacionado con Pregel?

    • Pregel es un sistema distribuido de procesamiento de grafos, y esto, por lo que veo, es una biblioteca para trabajar con grafos en la memoria de una sola computadora

  • Sería de mucha ayuda tener ejemplos

    • Sería de mucha ayuda tener documentación de cualquier tipo
    • Saldrá pronto. Si vuelves a revisar en unas 12 horas, probablemente ya haya algo

  • ¿Alguien puede explicar para qué es útil esta biblioteca?

    • Puede usarse para clustering. He usado el clusterizador por correlación de aquí en problemas que se pueden representar como grafos de nodos con una medida de similitud (este dato se parece a aquel dato) y una característica de repulsión fuerte (se sabe que este dato es distinto de aquel, así que nunca deben fusionarse)

  • En GitHub aparece como C, C++, Starland. ¿Qué es Starland?

    • Es Starlark. Es el lenguaje para configurar el sistema de build Bazel, y Bazel es el port open source de Blaze, el sistema de build interno de Google. Starlark es un subconjunto de Python
    • Supongo que es un typo y debería ser Starlark. Es el lenguaje que se usa en los archivos de build de Bazel
      Bazel es el sistema de build que se usa aquí

  • Los algoritmos de grafos necesitan urgentemente cierto grado de estandarización. Piensa en BLAS y LAPACK

  • Esperaba que fuera literalmente una herramienta para minar grafos estadísticos y hacer detección de anomalías