The Graph Mining Library — bibliothèque d’algorithmes et d’analyse de graphes

 (github.com/google)
3 points par GN⁺ 2023-10-05 | 1 commentaires | Partager sur WhatsApp
  • L’objectif de l’équipe Google Graph Mining est de construire une bibliothèque hautement scalable pour les algorithmes et l’analyse de graphes, puis de l’appliquer aux produits Google ; le périmètre actuellement proposé couvre un ensemble d’algorithmes de clustering
  • Les outils visés portent sur la construction de graphes de similarité, le clustering, la classification de nœuds, les embeddings de nœuds, l’entraînement de réseaux de neurones de graphes, la visualisation de graphes, divers échantillonnages et le ranking par similarité
  • Le domaine du clustering se compose d’algorithmes parallèles à mémoire partagée scalables jusqu’à des graphes comptant des dizaines de milliards d’arêtes, ainsi que de plusieurs algorithmes séquentiels
  • Les algorithmes parallèles sont des implémentations fondées sur des articles de recherche liés à HAC, au clustering par corrélation, à l’affinity clustering et à parline
  • Le framework de Graph Neural Network est fourni dans un projet séparé, TF-GNN
  • Pour un démarrage rapide, installez Bazel puis exécutez bazel run //examples:quickstart
  • Ce n’est pas un produit officiellement pris en charge par Google ; les questions et commentaires doivent être adressés en créant une issue dans ce dépôt

À lire aussi

1 commentaires

 
GN⁺ 2023-10-05
Avis de Hacker News

  • Le graph mining était vraiment à la mode il y a une dizaine d’années. Cela me rappelle GraphX (https://spark.apache.org/graphx/) et GraphLab (https://en.wikipedia.org/wiki/GraphLab), ainsi que les bases de données orientées graphe.
    C’était probablement lié à l’essor des réseaux sociaux à la même période ; plus récemment, c’est le geometric learning, c’est-à-dire le machine learning sur des graphes et d’autres structures, qui a attiré l’attention avant de se faire voler la vedette par les LLM. Je pense toutefois que le geometric learning a encore beaucoup de potentiel, et j’aimerais qu’il devienne plus populaire.

    • Avec les « bases de données orientées graphe », il existe un courant qui considère les graphes comme une approche universelle des données, avec RDF et SPARQL, ainsi que de nombreuses tentatives similaires. On peut aussi penser aux cas où la structure de données centrale d’un programme C est un graphe de pointeurs.
      Dans ce type de graphe, il y a généralement énormément de types d’arêtes différents, comme « est marié à » ou « a pour température moyenne annuelle ». À l’inverse, les algorithmes de graphe comme PageRank ou la centralité de graphe ont souvent un seul type d’arête, ou seulement quelques-uns. Il existe bien des algorithmes généraux applicables aux graphes comportant plusieurs types d’arêtes ; par exemple, le motif SPARQL ?s1 ?p ?o . ?s2 ?p ?o . trouve les ?s1 et ?s2 qui partagent un certain ?o et une relation ?p, et sert de base à une mesure de similarité entre eux. Les graphes n’ont généralement pas de forme prédéfinie : ils peuvent avoir n’importe quelle structure, ce qui peut être catastrophique du point de vue de la latence mémoire. Il m’est déjà arrivé, en utilisant ce motif SPARQL, de produire un programme qui aurait pris 100 ans ; en repackant la structure de données et en trouvant des approximations, j’ai réussi à faire le calcul en moins de 20 minutes. C’est pourquoi les praticiens ont tendance à se méfier des bibliothèques génériques de traitement de graphes. Il est courant de rencontrer des problèmes pour lesquels on peut écrire du code spécialisé en moins de temps qu’il n’en faut pour se battre avec le système de build, et le rendre 1000 fois plus rapide.
      Cela dit, si vous voulez suivre la tendance, arXiv regorge aujourd’hui d’articles sur les réseaux de neurones de graphes qui ne sont pas aussi survendus ailleurs. YOShInOn m’a préparé une longue liste d’articles sur les GNN à lire, mais je n’en ai parcouru que quelques-uns ; beaucoup disent que c’est applicable aux problèmes d’analyse de texte sur lesquels je travaille, mais cela ne semble pas vraiment meilleur que le système que YOShInOn et moi utilisons, donc je ne suis pas pressé.
    • Pour les problèmes qui se résolvent le mieux par l’analyse de graphes, NetworkX reste très utilisé, et j’aime beaucoup l’expérience développeur offerte par ce package.

  • Si vous voulez expérimenter avec les graphes et le machine learning, j’ai récemment parcouru la documentation d’ArangoDB et vu qu’elle inclut des intégrations avec plusieurs bibliothèques de graphes et frameworks de machine learning : https://docs.arangodb.com/3.11/data-science/adapters/
    J’ai aussi vu quelques notebooks Jupyter consacrés au machine learning sur graphes : https://github.com/arangodb/interactive_tutorials#machine-learning
    Les intégrations couvrent NetworkX -- https://networkx.org/, DeepGraphLibrary -- https://www.dgl.ai/, cuGraph (Rapids.ai Graph) -- https://docs.rapids.ai/api/cugraph/stable/, et PyG (PyTorch Geometric) -- https://pytorch-geometric.readthedocs.io/en/latest/.

  • S’il y a quelqu’un qui connaît bien Bazel, pourrait-il donner des pistes sur la manière de compiler ? bazel build fait bien quelque chose, mais au final seuls bazel-build et bazel-build apparaissent, et je ne vois aucun artefact de build évident

    • Dans Bazel, //... ressemble à la cible all de make
      On l’utilise comme bazel build //..., bazel test //..., bazel query //.... De mémoire, la dernière commande liste toutes les cibles
    • Pour compléter la réponse ci-dessus, on peut aussi ne compiler qu’un seul package. Par exemple, bazel build //in_memory/connected_components:asynchronous_union_find permet de compiler asynchronous_union_find
      Cela dit, en dehors du contexte d’une règle cc_binary, ce n’est pas forcément très utile. Cette approche permet de ne pas compiler tout le dépôt, mais seulement les packages nécessaires à un autre projet. Par exemple, si vous voulez seulement utiliser l’en-tête asynchronous_union_find.h, vous pouvez ajouter la bibliothèque graph-mining dans le fichier WORKSPACE de votre projet avec une règle git_repository (voir l’exemple WORKSPACE.bazel), puis ajouter @graph-mining//in_memory/connected_components:asynchronous_union_find à une règle cc_library dans un fichier BUILD de votre projet. Vous pourrez alors l’inclure ailleurs comme en-tête, et lors du build du projet, seuls ce package et ses dépendances seront compilés, pas toute la bibliothèque graph-mining
    • Depuis longtemps, je me disais qu’il faudrait un jour que je regarde Bazel, et ce “un jour” est arrivé aujourd’hui. Pour l’installer, la méthode recommandée semble être d’installer d’abord Bazelisk, puis de le renommer en bazel et de le placer dans un chemin comme /usr/local/bin/bazel
      Mais en lançant query, j’obtiens un avertissement JDK, et en lançant build, ça échoue faute de Java avec WARNING: Ignoring JAVA_HOME, because it must point to a JDK, not a JRE.. J’ai cherché quelques minutes quel JDK/JRE il fallait utiliser alors que je n’utilise même pas Java, puis j’ai abandonné : le “un jour” d’aujourd’hui redevient un autre jour. C’est presque pitoyable à quel point je suis devenu habitué à cargo ou npm/yarn
      Édition : grâce à https://sdkman.io/, ça fonctionne. Finalement, ce n’était pas si terrible

  • Question de débutant : cette bibliothèque pourrait-elle être considérée comme une candidate pour être intégrée à des wrappers ou bibliothèques d’extension afin de regrouper au même endroit des algorithmes de clustering basés sur les graphes ? En supposant que ce ne soit pas déjà le cas
    Ou bien existe-t-il déjà un framework qui fournit mieux les mêmes fonctionnalités ? Quelque chose comme NetworkX, par exemple

  • Je suis peut-être très en retard sur mon époque, mais est-ce que cela a un lien avec Pregel ?

    • Pregel est un système de traitement distribué de graphes ; ici, à mon avis, il s’agit d’une bibliothèque qui manipule des graphes en mémoire sur une seule machine

  • Des exemples seraient vraiment utiles

    • Une documentation, sous quelque forme que ce soit, serait vraiment utile
    • Elle devrait arriver bientôt. Si vous revenez voir dans 12 heures, il y en aura probablement une

  • Quelqu’un peut-il expliquer à quoi cette bibliothèque peut servir ?

    • On peut l’utiliser pour du clustering. J’ai déjà utilisé le clusterer par corrélation ici pour des problèmes qui peuvent être représentés comme un graphe de nœuds avec une mesure de similarité (ces données ressemblent à celles-là) et des caractéristiques de forte répulsion (ces données sont connues comme différentes de celles-là, donc ne jamais les fusionner)

  • Sur GitHub, il est indiqué C, C++, Starland. Qu’est-ce que Starland ?

    • C’est Starlark. C’est le langage utilisé pour configurer le système de build Bazel, et Bazel est le port open source de Blaze, le système de build interne de Google. Starlark est un sous-ensemble de Python
    • À mon avis, c’est une faute de frappe et cela devrait être Starlark. C’est le langage utilisé dans les fichiers de build Bazel
      Bazel est le système de build utilisé ici

  • Les algorithmes de graphes ont vraiment besoin d’une certaine standardisation. Pensez à BLAS et LAPACK

  • J’espérais que ce soit littéralement un outil pour miner des graphes statistiques et faire de la détection d’anomalies