The Graph Mining Library — biblioteca de algoritmos e análise de grafos

 (github.com/google)
3 pontos por GN⁺ 2023-10-05 | 1 comentários | Compartilhar no WhatsApp
  • O objetivo da equipe Google Graph Mining é criar uma biblioteca altamente escalável para algoritmos e análise de grafos e aplicá-la aos produtos do Google; o escopo atualmente oferecido é uma coleção de algoritmos de clustering
  • As ferramentas em desenvolvimento incluem construção de grafos de similaridade, clustering, classificação de nós, embeddings de nós, treinamento de redes neurais de grafos, visualização de grafos, várias formas de amostragem e ranking por similaridade
  • A área de clustering é composta por algoritmos paralelos de memória compartilhada que escalam até grafos com dezenas de bilhões de arestas, além de vários algoritmos sequenciais
  • Os algoritmos paralelos são implementações baseadas em artigos de pesquisa relacionados a HAC, clustering por correlação, affinity clustering e parline
  • O framework de Graph Neural Network é fornecido em um projeto separado, TF-GNN
  • Para executar rapidamente, instale o Bazel e rode bazel run //examples:quickstart
  • Não é um produto com suporte oficial do Google; perguntas e comentários devem ser encaminhados criando issues neste repositório

Leituras relacionadas

1 comentários

 
GN⁺ 2023-10-05
Opiniões no Hacker News

  • Mineração de grafos esteve muito em alta cerca de 10 anos atrás. Isso me faz lembrar do GraphX (https://spark.apache.org/graphx/) e do GraphLab (https://en.wikipedia.org/wiki/GraphLab), além dos bancos de dados de grafos.
    Talvez tenha coincidido com o fenômeno das redes sociais e, mais recentemente, o aprendizado geométrico, isto é, machine learning sobre grafos e outras estruturas, vinha chamando atenção até os LLMs roubarem os holofotes. Ainda assim, acho que o aprendizado geométrico tem muito potencial e gostaria que ganhasse mais popularidade.

    • Em “bancos de dados de grafos”, há uma corrente que vê grafos como uma abordagem universal para dados, com RDF, SPARQL e inúmeras tentativas semelhantes. Também dá para pensar no caso em que a estrutura de dados central em um programa em C é um grafo de ponteiros.
      Esses grafos normalmente têm uma quantidade enorme de tipos de arestas diferentes, como “é casado com” ou “tem temperatura média anual”. Por outro lado, algoritmos de grafos como PageRank ou centralidade em grafos muitas vezes têm apenas um ou poucos tipos de aresta. Existem algoritmos gerais que também podem ser aplicados a grafos com vários tipos de aresta; por exemplo, o padrão SPARQL ?s1 ?p ?o . ?s2 ?p ?o . encontra ?s1 e ?s2 que compartilham algum ?o e uma relação ?p, servindo como base para uma medida de similaridade entre os dois. Grafos, em geral, não têm uma forma fixa e podem assumir qualquer estrutura, o que pode ser um desastre do ponto de vista da latência de memória. Certa vez, usando esse padrão SPARQL, criei um programa que levaria 100 anos; depois reempacotei as estruturas de dados e encontrei aproximações, fazendo o cálculo terminar em menos de 20 minutos. Por isso, profissionais tendem a ser céticos em relação a bibliotecas genéricas de processamento de grafos. É comum haver problemas em que se consegue escrever código especializado em menos tempo do que se gastaria brigando com o sistema de build, e ainda deixá-lo 1000 vezes mais rápido.
      Ainda assim, se você quiser seguir a tendência, hoje o arXiv está cheio de artigos sobre redes neurais de grafos que não são tão exagerados em outros lugares. YOShInOn me fez uma longa lista de artigos sobre GNN para ver, mas só passei os olhos por alguns; há muitos textos dizendo que eles são aplicáveis aos problemas de análise de texto em que trabalho, mas não parecem particularmente melhores que os sistemas que YOShInOn e eu usamos, então não estou com pressa.
    • Para problemas que são melhor resolvidos com análise de grafos, NetworkX ainda é muito usado, e gosto muito da experiência de desenvolvimento desse pacote.

  • Para quem quer experimentar grafos e machine learning, ao consultar recentemente a documentação do ArangoDB vi que ela inclui integração com várias bibliotecas de grafos e frameworks de machine learning: https://docs.arangodb.com/3.11/data-science/adapters/
    Também vi alguns notebooks Jupyter sobre machine learning em grafos: https://github.com/arangodb/interactive_tutorials#machine-learning
    As integrações incluem NetworkX -- https://networkx.org/, DeepGraphLibrary -- https://www.dgl.ai/, cuGraph (Rapids.ai Graph) -- https://docs.rapids.ai/api/cugraph/stable/, PyG (PyTorch Geometric) -- https://pytorch-geometric.readthedocs.io/en/latest/.

  • Se alguém familiarizado com Bazel puder dar uma dica sobre como compilar, agradeço. bazel build até faz alguma coisa, mas no resultado só aparecem bazel-build e bazel-build, e não vejo nenhum artefato de build evidente

    • No Bazel, //... é parecido com o alvo all do make.
      Dá para usar como bazel build //..., bazel test //..., bazel query //.... Pelo que me lembro, o último comando lista todos os alvos
    • Complementando a resposta acima, também dá para compilar só um pacote. Por exemplo, bazel build //in_memory/connected_components:asynchronous_union_find compila o asynchronous_union_find.
      Mas talvez isso não seja muito útil fora do contexto de uma regra cc_binary. Essa abordagem permite compilar e usar apenas os pacotes necessários em outro projeto, sem compilar o repositório inteiro. Por exemplo, se você só quiser usar o header asynchronous_union_find.h, adicione a biblioteca graph-mining em algum lugar do arquivo WORKSPACE do seu projeto com uma regra git_repository (veja o exemplo em WORKSPACE.bazel) e adicione @graph-mining//in_memory/connected_components:asynchronous_union_find à regra cc_library no arquivo BUILD dentro do seu projeto. Assim você poderá incluí-lo como header em outros lugares e, ao compilar o projeto, apenas esse pacote e suas dependências serão compilados, não a biblioteca graph-mining inteira
    • Há tempos eu só pensava que um dia deveria dar uma olhada no Bazel, e esse “um dia” acabou sendo hoje. Para instalar, parece que o método recomendado é primeiro instalar o Bazelisk, depois renomeá-lo para bazel e colocá-lo em um caminho como /usr/local/bin/bazel.
      Mas, ao executar query, apareceu um aviso do JDK; ao executar build, falhou por falta de Java, junto com WARNING: Ignoring JAVA_HOME, because it must point to a JDK, not a JRE.. Passei alguns minutos pesquisando qual JDK/JRE eu deveria usar, já que nem estou usando Java, e acabei desistindo; o “um dia” de hoje ficou para outro dia. É até vergonhoso o quanto fiquei acostumado com cargo ou npm/yarn.
      Edit: graças a https://sdkman.io/, consegui rodar. No fim, não foi tão ruim assim

  • Pergunta de iniciante: será que dá para considerar esta biblioteca como candidata para integrar wrappers ou bibliotecas de extensão e reunir algoritmos de clusterização baseada em grafos em um só lugar? Supondo que ela já não faça isso.
    Ou já existe algum framework que ofereça melhor a mesma funcionalidade? Algo como NetworkX

  • Posso estar muito defasado em relação aos tempos atuais, mas isso tem alguma relação com Pregel?

    • Pregel é um sistema distribuído de processamento de grafos; isto, pelo que vejo, é uma biblioteca para manipular grafos na memória de um único computador

  • Seria muito útil ter exemplos

    • Qualquer tipo de documentação ajudaria muito
    • Deve sair em breve. Se você conferir de novo em 12 horas, provavelmente já haverá algo

  • Alguém poderia explicar onde esta biblioteca é útil?

    • Pode ser usada para clusterização. Já usei o clusterizador por correlação daqui em problemas que podem ser representados como um grafo de nós com uma métrica de similaridade (estes dados são parecidos com aqueles dados) e fortes características de repulsão (sabe-se que estes dados são diferentes daqueles, portanto nunca devem ser mesclados)

  • No GitHub aparece C, C++, Starland. O que é Starland?

    • É Starlark. É a linguagem usada para configurar o sistema de build Bazel, e Bazel é o porte open source do Blaze, sistema de build interno do Google. Starlark é um subconjunto de Python
    • Meu palpite é que seja um typo e deveria ser Starlark. É a linguagem usada nos arquivos de build do Bazel.
      Bazel é o sistema de build usado aqui

  • Algum grau de padronização faz muita falta em algoritmos de grafos. Pense em BLAS e LAPACK

  • Eu esperava que fosse literalmente uma ferramenta para minerar grafos estatísticos e fazer detecção de anomalias