Evaluating LLMs on Large-Scale Graph Property Estimation via Random Walks

Resumo Técnico: Avaliação de LLMs na Estimação de Propriedades de Grafos em Grande Escala via Passeios Aleatórios

Declaração do Problema
Os benchmarks existentes para avaliar as capacidades de raciocínio em grafos de Modelos de Linguagem de Grande Escala (LLMs), como NLGraph, GraphQA e GraphArena, são limitados pelas restrições da janela de contexto dos modelos atuais. Consequentemente, esses benchmarks utilizam grafos pequenos (tipicamente 10–50 nós), onde toda a estrutura pode ser codificada no prompt. No entanto, grafos do mundo real (por exemplo, redes sociais, peer-to-peer e da web) frequentemente contêm milhões de nós e são frequentemente acessíveis apenas parcialmente via APIs. Isso cria uma lacuna na compreensão de como os LLMs se desempenham em tarefas de grafos em grande escala onde a visibilidade total é impossível. Especificamente, há uma falta de avaliação sobre a capacidade dos LLMs de estimar propriedades globais do grafo — como tamanho, estrutura de comunidades e centralidade de nós — usando apenas informações parciais e locais derivadas de amostragem.

Metodologia
Os autores propõem o EstGraph, um novo conjunto de dados de benchmark e framework projetado para avaliar o raciocínio de LLMs em grafos grandes sob condições de acessibilidade limitada. A metodologia centra-se no uso de amostragem por passeio aleatório para extrair estatísticas locais de grafos que variam até 2,39 milhões de nós, que são então resumidas em prompts que se encaixam nos limites de contexto dos LLMs.

1. Construção do Conjunto de Dados:

   • Grafos Sintéticos: Gerados usando NetworkX e NetworKit, incluindo grafos Barabasi-Albert (BA/lei de potência), Erdos-Renyi (ER/aleatório) e Gaussian Random Partition (GRP). Estes são categorizados em escalas Pequena (100–1k), Média (1k–10k) e Grande (10k–100k).
   • Grafos do Mundo Real: Cinco conjuntos de dados do repositório SNAP (por exemplo, ego-Twitter, as-skitter, wiki-Talk) com contagens de nós variando de 81k a 2,39 milhões.
   • Grafos de Comunidade: 20 grafos LFR (Lancichinetti-Fortunato-Radicchi) com estruturas de comunidade conhecidas (5–12 clusters) para tarefas de detecção de comunidades.

2. Estratégia de Amostragem:

   • Em vez de fornecer listas completas de arestas, o framework emprega Passeios Aleatórios Simples (SRW) e passeios Metropolis-Hastings (MH) para amostrar nós.
   • Para abordar as limitações de comprimento do contexto, os dados brutos do passeio não são alimentados diretamente. Em vez disso, são geradas construções de prompts específicas para a tarefa que resumem as estatísticas do passeio. Essas estatísticas incluem:
     • Comprimento do passeio e número de nós/arestas únicos.
     • Tempo até a primeira colisão de nós (indicativo de densidade local).
     • Tempos de retorno ao nó de origem.
     • Nós únicos cumulativos descobertos em incrementos de 10%.
     • Distribuições de grau (nós de grau mais alto/menor, grau médio).
     • Nomes de nós anonimizados para evitar vazamento de contagens totais de nós.

3. Tarefas de Avaliação:
   O benchmark avalia os LLMs em quatro tarefas distintas de estimação:

   • Estimação do Tamanho do Grafo: Prever o número total de nós e arestas.
   • Estimação da Quantidade de Comunidades: Prever o número de clusters em grafos LFR.
   • Identificação da Estrutura do Grafo: Classificar o tipo de grafo (BA, ER, LFR ou Grid) com base em padrões de distribuição de grau.
   • Classificação de Nós Influenciais: Identificar os top-$k$ nós com base em Centralidade de Intermediação (Betweenness Centrality), Centralidade de Proximidade (Closeness Centrality) e PageRank.

4. Modelos e Baselines:

   • LLMs: Avaliados em modelos com capacidade de raciocínio, incluindo gemini-2.5-pro, sonnet-4, o3 (OpenAI) e DeepSeek-V3.1.
   • Baselines: Algoritmos clássicos de estimação de grafos, incluindo Amostragem Uniforme, amostragem MH, Passeio Aleatório de Grau Máximo e Estimação Baseada em Tempo de Retorno.

Principais Resultados

• Estimação do Tamanho do Grafo: Os LLMs demonstraram capacidade de estimar tamanhos de grafos com precisão razoável. Para conjuntos de dados sintéticos, modelos como o3 alcançaram erros relativos medianos abaixo de 20%, às vezes superando baselines clássicos. Em conjuntos de dados do mundo real, o gemini-2.5-pro forneceu as melhores estimativas entre os LLMs, embora os erros tenham sido maiores do que nos dados sintéticos. Os autores observam que, embora a amostragem não enviesada (MH) seja teoricamente superior, passeios aleatórios simples (SRW) forneceram resultados competitivos em configurações práticas onde a MH é difícil de implementar.
• Detecção de Comunidades: Os LLMs puderam detectar a presença de comunidades com um erro absoluto médio de aproximadamente 2 clusters (para grafos com 5–12 comunidades). No entanto, eles ainda não eram confiáveis para contagem precisa em comparação com algoritmos clássicos como Modularidade Gananciosa e Louvain, que alcançaram erro próximo de zero em subgrafos.
• Identificação de Estrutura: Os LLMs distinguiram com sucesso entre tipos de grafos com base em distribuições de grau. O o3 teve o melhor desempenho geral, identificando corretamente grafos Grid e ER. Os modelos demonstraram capacidade de diferenciar entre a distribuição de grau uniforme de grafos ER e as distribuições enviesadas de grafos BA e LFR, embora confusão ocasional tenha ocorrido entre os tipos BA e LFR.
• Classificação de Nós: O desempenho variou significativamente por métrica. Os LLMs tiveram dificuldade com métricas baseadas em caminho mais curto (Centralidade de Intermediação e Centralidade de Proximidade) devido à dificuldade de inferir caminhos globais a partir de passeios locais. No entanto, eles se saíram notavelmente melhor no PageRank, que correlaciona com a frequência de visitação em passeios aleatórios. O modelo o3 superou significativamente os outros na estimação de PageRank, alcançando ~80% de Precision@20.

Significância e Contribuições
O artigo reivindica quatro contribuições primárias:

1. Benchmark EstGraph: A introdução de um conjunto de dados de benchmark em grande escala e quatro tarefas especificamente projetadas para testar o raciocínio de LLMs em grafos grandes demais para visibilidade total, preenchendo a lacuna entre benchmarks algorítmicos em pequena escala e restrições de dados do mundo real.
2. Engenharia de Prompt para Grafos Grandes: A proposta de construções de prompts específicas para a tarefa que codificam estatísticas de passeios aleatórios. Essa abordagem reduz o comprimento do prompt em até 559x em comparação com a codificação ingênua de listas de arestas, permitindo a avaliação de grafos com milhões de nós dentro dos limites de contexto atuais.
3. Avaliação Empírica: Uma avaliação abrangente de LLMs de raciocínio em tarefas de estimação através de diversas estruturas de grafos (sintéticos e do mundo real) e escalas, demonstrando que os LLMs podem aproveitar estatísticas locais para inferir propriedades globais.
4. Recomendações Práticas: A fornecimento de diretrizes para análise de grafos grandes com LLMs, como o uso de agregação mediana para lidar com estimativas de outliers, a utilização de múltiplos passeios curtos a médios para reduzir viés local e o reconhecimento de que medidas semelhantes ao PageRank são mais viáveis de estimar do que métricas de caminho mais curto.

Os autores concluem que, embora os LLMs ainda não sejam um substituto para algoritmos especializados de grafos, eles podem fornecer estimativas razoáveis para propriedades de grafos grandes quando equipados com estratégias adequadas de amostragem e prompting. O trabalho destaca o potencial dos LLMs para servir como uma ferramenta complementar para analisar redes em grande escala onde o acesso total ao grafo é inviável.