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

Technische Samenvatting: Het Evalueren van LLM's op Groot-schaal Grafische Eigenschapsschatting via Random Walks

Probleemstelling
Bestaande benchmarks voor het evalueren van de grafische redeneercapaciteiten van Large Language Models (LLM's), zoals NLGraph, GraphQA en GraphArena, worden beperkt door de contextvensterbeperkingen van huidige modellen. Bijgevolg maken deze benchmarks gebruik van kleine grafen (doorgaans 10–50 knopen) waarbij de volledige structuur in de prompt kan worden gecodeerd. Echter, real-world grafen (bijvoorbeeld sociale, peer-to-peer en webnetwerken) bevatten vaak miljoenen knopen en zijn vaak slechts gedeeltelijk toegankelijk via API's. Dit creëert een gat in het begrijpen van hoe LLM's presteren op groot-schaal grafische taken waar volledige zichtbaarheid onmogelijk is. Specifiek ontbreekt er evaluatie met betrekking tot het vermogen van LLM's om globale grafische eigenschappen—zoals grootte, gemeenschapsstructuur en knoopcentraliteit—te schatten met behulp van slechts gedeeltelijke, lokale informatie afgeleid van steekproeven.

Methodologie
De auteurs stellen EstGraph voor, een nieuwe benchmarkdataset en framework ontworpen om LLM-redenering op grote grafen te evalueren onder omstandigheden van beperkte toegankelijkheid. De methodologie concentreert zich op het gebruik van random walk-steekproeven om lokale statistieken uit grafen te extraheren die variëren tot 2,39 miljoen knopen, welke vervolgens worden samengevat tot prompts die binnen de contextlimieten van LLM's passen.

1. Datasetconstructie:

   • Synthetische Grafen: Genereerd met NetworkX en NetworKit, inclusief Barabasi-Albert (BA/machtswet), Erdos-Renyi (ER/willekeurig) en Gaussian Random Partition (GRP) grafen. Deze zijn gecategoriseerd in Kleine (100–1k), Middelgrote (1k–10k) en Grote (10k–100k) schalen.
   • Real-world Grafen: Vijf datasets uit het SNAP-repository (bijv. ego-Twitter, as-skitter, wiki-Talk) met knopaantallen variërend van 81k tot 2,39 miljoen.
   • Gemeenschapsgrafiek: 20 LFR (Lancichinetti-Fortunato-Radicchi) grafen met bekende gemeenschapsstructuren (5–12 clusters) voor gemeenschapsdetectietaken.

2. Steekproefstrategie:

   • In plaats van volledige lijsten van randen te verstrekken, maakt het framework gebruik van Eenvoudige Random Walks (SRW) en Metropolis-Hastings (MH)-wandelingen om knopen te steekproeven.
   • Om beperkingen in de contextlengte aan te pakken, worden de ruwe wandelgegevens niet direct ingevoerd. In plaats daarvan worden taakspecifieke promptconstructies gegenereerd die wandelstatistieken samenvatten. Deze statistieken omvatten:
     • Wandel Lengte en aantal unieke knopen/rand.
     • Tijd tot eerste knoopcollisie (indicatief voor lokale dichtheid).
     • Terugkeer-tijden naar de bronknoop.
     • Cumulatieve unieke knopen ontdekt in stappen van 10%.
     • Graadverdelingen (hoogste/laagste graad knopen, gemiddelde graad).
     • Geanonimiseerde knoopnamen om lekkage van totale knopaantallen te voorkomen.

3. Evaluatietaken:
   De benchmark evalueert LLM's op vier distincte schattings taken:

   • Schatting van Grafgrootte: Voorspellen van het totale aantal knopen en randen.
   • Schatting van Aantal Gemeenschappen: Voorspellen van het aantal clusters in LFR-grafen.
   • Identificatie van Grafstructuur: Classificeren van het grafentype (BA, ER, LFR of Grid) op basis van graadverdelingspatronen.
   • Ranking van Invloedrijke Knoopen: Identificeren van de top-$k$ knopen gebaseerd op Tussencentraliteit, Nabijheidscentraliteit en PageRank.

4. Modellen en Baselines:

   • LLM's: Geëvalueerd op redeneringscapabele modellen waaronder gemini-2.5-pro, sonnet-4, o3 (OpenAI) en DeepSeek-V3.1.
   • Baselines: Klassieke grafische schattingsalgoritmen inclusief Uniforme Steekproef, MH-steekproef, Max-graad Random Walk en Op Terugkeer-tijd Gebaseerde Schatting.

Belangrijkste Resultaten

• Schatting van Grafgrootte: LLM's toonden het vermogen om grafgroottes te schatten met redelijke nauwkeurigheid. Voor synthetische datasets bereikten modellen zoals o3 mediaan relatieve fouten onder de 20%, soms presterend beter dan klassieke baselines. Op real-world datasets leverde gemini-2.5-pro de beste schattingen onder LLM's, hoewel de fouten hoger waren dan op synthetische data. De auteurs merken op dat hoewel onbevooroordeelde steekproeven (MH) theoretisch superieur zijn, eenvoudige random walks (SRW) concurrerende resultaten boekten in praktische settings waar MH moeilijk te implementeren is.
• Gemeenschapsdetectie: LLM's konden de aanwezigheid van gemeenschappen detecteren met een gemiddelde absolute fout van ongeveer 2 clusters (voor grafen met 5–12 gemeenschappen). Echter, ze waren nog niet betrouwbaar voor precieze telling in vergelijking met klassieke algoritmen zoals Greedy Modularity en Louvain, die een bijna-nul fout bereikten op subgrafen.
• Identificatie van Structuur: LLM's onderscheidden succesvol tussen grafentypes op basis van graadverdelingen. o3 presteerde overall het beste, en identificeerde correct Grid- en ER-grafen. De modellen toonden het vermogen om te differentiëren tussen de uniforme graadverdeling van ER-grafen en de scheve verdelingen van BA- en LFR-grafen, hoewel er af en toe verwarring optrad tussen BA- en LFR-types.
• Knoopranking: De prestaties varieerden aanzienlijk per maatstaf. LLM's hadden moeite met op kortste-pad gebaseerde maatstaven (Tussencentraliteit en Nabijheidscentraliteit) vanwege de moeilijkheid om globale paden af te leiden uit lokale wandelingen. Echter, ze presteerden aanzienlijk beter op PageRank, wat correleert met bezoekfrequentie in random walks. Het o3-model presteerde significant beter dan anderen in PageRank-schatting, met een Precision@20 van ~80%.

Betekenis en Bijdragen
Het paper claimt vier primaire bijdragen:

1. EstGraph Benchmark: De introductie van een groot-schaal benchmarkdataset en vier taken specifiek ontworpen om LLM-redenering op grafen te testen die te groot zijn voor volledige zichtbaarheid, waarmee de kloof wordt overbrugd tussen kleine-schaal algoritmische benchmarks en real-world data-beperkingen.
2. Prompt Engineering voor Grote Grafen: Het voorstellen van taakspecifieke promptconstructies die random walk-statistieken coderen. Deze benadering reduceert de promptlengte met tot 559x in vergelijking met naïeve lijst-codering, waardoor evaluatie mogelijk wordt van grafen met miljoenen knopen binnen huidige contextlimieten.
3. Empirische Evaluatie: Een uitgebreide evaluatie van redenerende LLM's op schattings taken over diverse grafische structuren (synthetisch en real-world) en schalen, waarbij wordt aangetoond dat LLM's lokale statistieken kunnen benutten om globale eigenschappen af te leiden.
4. Praktische Aanbevelingen: Het verstrekken van richtlijnen voor groot-schaal grafanalyse met LLM's, zoals het gebruik van mediaanaggregatie om uitbijterschatten te hanteren, het benutten van meerdere korte tot middellange wandelingen om lokale bias te verminderen, en het erkennen dat PageRank-achtige maatstaven realistischer te schatten zijn dan op kortste-pad gebaseerde maatstaven.

De auteurs concluderen dat hoewel LLM's nog geen vervanging zijn voor gespecialiseerde grafalgoritmen, ze redelijke schattingen kunnen bieden voor grote grafische eigenschappen wanneer ze zijn uitgerust met passende steekproef- en promptstrategieën. Het werk benadrukt het potentieel van LLM's om als complementair hulpmiddel te dienen voor het analyseren van groot-schaal netwerken waar volledige graftoegang onuitvoerbaar is.