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

Resumen Técnico: Evaluación de LLMs en la Estimación de Propiedades de Grafos a Gran Escala Mediante Caminatas Aleatorias

Enunciado del Problema
Los benchmarks existentes para evaluar las capacidades de razonamiento en grafos de los Modelos de Lenguaje Grandes (LLM), como NLGraph, GraphQA y GraphArena, están limitados por las restricciones de la ventana de contexto de los modelos actuales. En consecuencia, estos benchmarks utilizan grafos pequeños (típicamente de 10 a 50 nodos) donde toda la estructura puede codificarse en el prompt. Sin embargo, los grafos del mundo real (por ejemplo, redes sociales, peer-to-peer y web) a menudo contienen millones de nodos y frecuentemente solo son parcialmente accesibles mediante APIs. Esto crea una brecha en la comprensión de cómo se desempeñan los LLM en tareas de grafos a gran escala donde la visibilidad completa es imposible. Específicamente, existe una falta de evaluación sobre la capacidad de los LLM para estimar propiedades globales del grafo —como tamaño, estructura comunitaria y centralidad de nodos— utilizando únicamente información parcial y local derivada del muestreo.

Metodología
Los autores proponen EstGraph, un nuevo conjunto de datos de referencia y marco diseñado para evaluar el razonamiento de LLM en grafos grandes bajo condiciones de acceso limitado. La metodología se centra en el uso de muestreo por caminata aleatoria para extraer estadísticas locales de grafos que llegan hasta 2,39 millones de nodos, las cuales luego se resumen en prompts que caben dentro de los límites de contexto de los LLM.

1. Construcción del Conjunto de Datos:

   • Grafos Sintéticos: Generados utilizando NetworkX y NetworKit, incluyendo grafos Barabasi-Albert (BA/potencia), Erdos-Renyi (ER/aleatorio) y Partición Aleatoria Gaussiana (GRP). Estos se categorizan en escalas Pequeña (100–1k), Mediana (1k–10k) y Grande (10k–100k).
   • Grafos del Mundo Real: Cinco conjuntos de datos del repositorio SNAP (por ejemplo, ego-Twitter, as-skitter, wiki-Talk) con conteos de nodos que van desde 81k hasta 2,39 millones.
   • Grafos Comunitarios: 20 grafos LFR (Lancichinetti-Fortunato-Radicchi) con estructuras comunitarias conocidas (5–12 clústeres) para tareas de detección de comunidades.

2. Estrategia de Muestreo:

   • En lugar de proporcionar listas completas de aristas, el marco emplea Caminatas Aleatorias Simples (SRW) y caminatas Metropolis-Hastings (MH) para muestrear nodos.
   • Para abordar las limitaciones de longitud del contexto, los datos brutos de la caminata no se alimentan directamente. En su lugar, se generan construcciones de prompts específicas de la tarea que resumen las estadísticas de la caminata. Estas estadísticas incluyen:
     • Longitud de la caminata y número de nodos/aristas únicos.
     • Tiempo hasta la primera colisión de nodos (indicativo de densidad local).
     • Tiempos de retorno al nodo fuente.
     • Nodos únicos acumulados descubiertos en incrementos del 10%.
     • Distribuciones de grado (nodos de grado más alto/más bajo, grado promedio).
     • Nombres de nodos anonimizados para prevenir la filtración de conteos totales de nodos.

3. Tareas de Evaluación:
   El benchmark evalúa a los LLM en cuatro tareas de estimación distintas:

   • Estimación del Tamaño del Grafo: Predecir el número total de nodos y aristas.
   • Estimación del Número de Comunidades: Predecir el número de clústeres en grafos LFR.
   • Identificación de la Estructura del Grafo: Clasificar el tipo de grafo (BA, ER, LFR o Grid) basándose en patrones de distribución de grado.
   • Clasificación de Nodos Influyentes: Identificar los nodos top-$k$ basándose en la Centralidad de Intermediación, la Centralidad de Cercanía y PageRank.

4. Modelos y Líneas Base:

   • LLM: Evaluados en modelos con capacidades de razonamiento que incluyen gemini-2.5-pro, sonnet-4, o3 (OpenAI) y DeepSeek-V3.1.
   • Líneas Base: Algoritmos clásicos de estimación de grafos que incluyen Muestreo Uniforme, muestreo MH, Caminata Aleatoria de Máximo Grado y Estimación Basada en Tiempos de Retorno.

Resultados Clave

• Estimación del Tamaño del Grafo: Los LLM demostraron la capacidad de estimar tamaños de grafos con una precisión razonable. Para conjuntos de datos sintéticos, modelos como o3 lograron errores relativos medianos inferiores al 20%, superando a veces a las líneas base clásicas. En conjuntos de datos del mundo real, gemini-2.5-pro proporcionó las mejores estimaciones entre los LLM, aunque los errores fueron mayores que en los datos sintéticos. Los autores señalan que, aunque el muestreo no sesgado (MH) es teóricamente superior, las caminatas aleatorias simples (SRW) proporcionaron resultados competitivos en configuraciones prácticas donde MH es difícil de implementar.
• Detección de Comunidades: Los LLM pudieron detectar la presencia de comunidades con un error absoluto medio de aproximadamente 2 clústeres (para grafos con 5–12 comunidades). Sin embargo, aún no eran fiables para un conteo preciso en comparación con algoritmos clásicos como Modularidad Greedy y Louvain, que lograron errores cercanos a cero en subgrafos.
• Identificación de Estructura: Los LLM distinguieron con éxito entre tipos de grafos basándose en distribuciones de grado. o3 tuvo el mejor rendimiento general, identificando correctamente los grafos Grid y ER. Los modelos demostraron una capacidad para diferenciar entre la distribución de grado uniforme de los grafos ER y las distribuciones sesgadas de los grafos BA y LFR, aunque ocasionalmente se produjo confusión entre los tipos BA y LFR.
• Clasificación de Nodos: El rendimiento varió significativamente según la métrica. Los LLM tuvieron dificultades con las métricas basadas en caminos más cortos (Centralidad de Intermediación y Centralidad de Cercanía) debido a la dificultad de inferir caminos globales a partir de caminatas locales. Sin embargo, se desempeñaron notablemente mejor en PageRank, que se correlaciona con la frecuencia de visitas en caminatas aleatorias. El modelo o3 superó significativamente a los demás en la estimación de PageRank, alcanzando una Precisión@20 de ~80%.

Significado y Contribuciones
El artículo afirma cuatro contribuciones principales:

1. Benchmark EstGraph: La introducción de un conjunto de datos de referencia a gran escala y cuatro tareas diseñadas específicamente para probar el razonamiento de LLM en grafos demasiado grandes para una visibilidad completa, cerrando la brecha entre benchmarks algorítmicos a pequeña escala y las restricciones de datos del mundo real.
2. Ingeniería de Prompts para Grafos Grandes: La propuesta de construcciones de prompts específicas de la tarea que codifican estadísticas de caminata aleatoria. Este enfoque reduce la longitud del prompt hasta en 559 veces en comparación con la codificación ingenua de listas de aristas, permitiendo la evaluación de grafos con millones de nodos dentro de los límites de contexto actuales.
3. Evaluación Empírica: Una evaluación exhaustiva de LLMs de razonamiento en tareas de estimación a través de diversas estructuras de grafos (sintéticos y del mundo real) y escalas, demostrando que los LLM pueden aprovechar estadísticas locales para inferir propiedades globales.
4. Recomendaciones Prácticas: La provisión de directrices para el análisis de grafos grandes con LLM, como el uso de agregación mediana para manejar estimaciones atípicas, la utilización de múltiples caminatas cortas a medianas para reducir el sesgo local, y el reconocimiento de que medidas similares a PageRank son más factibles de estimar que las métricas de caminos más cortos.

Los autores concluyen que, aunque los LLM aún no son un reemplazo para algoritmos de grafos especializados, pueden proporcionar estimaciones razonables de propiedades de grafos grandes cuando están equipados con estrategias adecuadas de muestreo y prompts. El trabajo destaca el potencial de los LLM para servir como una herramienta complementaria para analizar redes a gran escala donde el acceso completo al grafo es inviable.