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

기술 요약: 무작위 보행을 통한 대규모 그래프 속성 추정을 위한 LLM 평가

문제 제기
NLGraph, GraphQA, GraphArena와 같은 대규모 언어 모델 (LLM) 의 그래프 추론 능력을 평가하기 위한 기존 벤치마크는 현재 모델의 컨텍스트 윈도우 제약으로 인해 제한적입니다. 결과적으로 이러한 벤치마크는 전체 구조를 프롬프트에 인코딩할 수 있는 작은 그래프 (일반적으로 10~50 개 노드) 를 활용합니다. 그러나 실제 세계의 그래프 (예: 소셜, P2P, 웹 네트워크) 는 종종 수백만 개의 노드를 포함하며 API 를 통해 부분적으로만 접근 가능한 경우가 많습니다. 이는 전체 가시성이 불가능한 대규모 그래프 작업에서 LLM 의 성능이 어떻게 발휘되는지에 대한 이해에 간극을 만듭니다. 구체적으로, 샘플링에서 도출된 부분적이고 국소적인 정보만을 사용하여 LLM 이 그래프 크기, 커뮤니티 구조, 노드 중심성 등의 전역 그래프 속성을 추정하는 능력에 대한 평가가 부족합니다.

방법론
저자들은 제한된 접근 조건 하에서 대규모 그래프에 대한 LLM 추론을 평가하도록 설계된 새로운 벤치마크 데이터셋 및 프레임워크인 EstGraph를 제안합니다. 방법론은 최대 239 만 개의 노드를 가진 그래프에서 국소 통계를 추출하기 위해 무작위 보행 샘플링을 사용하는 데 중점을 두며, 이를 LLM 컨텍스트 한계에 맞게 요약하여 프롬프트로 변환합니다.

1. 데이터셋 구성:

   • 합성 그래프: NetworkX 및 NetworKit 를 사용하여 생성되었으며, Barabasi-Albert(BA/멱법칙), Erdos-Renyi(ER/무작위), Gaussian Random Partition(GRP) 그래프를 포함합니다. 이는 Small(1001k), Medium(1k10k), Large(10k~100k) 규모로 분류됩니다.
   • 실제 세계 그래프: SNAP 저장소에서 가져온 5 개 데이터셋 (예: ego-Twitter, as-skitter, wiki-Talk) 으로, 노드 수는 81k 에서 239 만 개까지 다양합니다.
   • 커뮤니티 그래프: 커뮤니티 탐지 작업을 위해 알려진 커뮤니티 구조 (5~12 개 클러스터) 를 가진 20 개의 LFR(Lancichinetti-Fortunato-Radicchi) 그래프입니다.

2. 샘플링 전략:

   • 전체 엣지 리스트를 제공하는 대신, 프레임워크는 노드를 샘플링하기 위해 **단순 무작위 보행 (SRW)**과 Metropolis-Hastings(MH) 보행을 사용합니다.
   • 컨텍스트 길이 제한을 해결하기 위해 원시 보행 데이터는 직접 입력되지 않습니다. 대신 보행 통계를 요약하는 작업별 프롬프트 구성이 생성됩니다. 이러한 통계에는 다음이 포함됩니다:
     • 보행 길이와 고유 노드/엣지 수.
     • 첫 번째 노드 충돌까지의 시간 (국소 밀도 지표).
     • 소스 노드로의 복귀 시간.
     • 10% 간격으로 발견된 누적 고유 노드.
     • 차수 분포 (최고/최저 차수 노드, 평균 차수).
     • 총 노드 수 유출을 방지하기 위한 익명화된 노드 이름.

3. 평가 작업:
   벤치마크는 LLM 을 네 가지 고유한 추정 작업에 대해 평가합니다:

   • 그래프 크기 추정: 총 노드 및 엣지 수 예측.
   • 커뮤니티 수 추정: LFR 그래프의 클러스터 수 예측.
   • 그래프 구조 식별: 차수 분포 패턴을 기반으로 그래프 유형 (BA, ER, LFR 또는 Grid) 분류.
   • 영향력 있는 노드 순위 매기기: Betweenness Centrality, Closeness Centrality, PageRank 를 기반으로 상위-$k$개 노드 식별.

4. 모델 및 베이스라인:

   • LLM: gemini-2.5-pro, sonnet-4, o3(OpenAI), DeepSeek-V3.1을 포함한 추론 가능 모델 평가.
   • 베이스라인: Uniform Sampling, MH sampling, Max-degree Random Walk, Return-time Based Estimation 을 포함한 고전적 그래프 추정 알고리즘.

주요 결과

• 그래프 크기 추정: LLM 은 합리적인 정확도로 그래프 크기를 추정할 수 있음을 입증했습니다. 합성 데이터셋의 경우 o3와 같은 모델이 중앙값 상대 오차를 20% 미만으로 달성하여 고전적 베이스라인을 능가하기도 했습니다. 실제 세계 데이터셋에서는 gemini-2.5-pro가 LLM 중 가장 좋은 추정을 제공했으나, 합성 데이터에 비해 오차는 더 높았습니다. 저자들은 편향되지 않은 샘플링 (MH) 이 이론적으로 우월하지만, MH 구현이 어려운 실제 환경에서는 단순 무작위 보행 (SRW) 이 경쟁력 있는 결과를 제공했다고 지적합니다.
• 커뮤니티 탐지: LLM 은 평균 절대 오차가 약 2 개 클러스터 (5~12 개 커뮤니티를 가진 그래프 기준) 로 커뮤니티의 존재를 탐지할 수 있었습니다. 그러나 Greedy Modularity 및 Louvain 과 같은 고전적 알고리즘이 서브그래프에서 거의 0 에 가까운 오차를 달성한 것과 비교할 때, 정밀한 계수에는 아직 신뢰할 수 없었습니다.
• 구조 식별: LLM 은 차수 분포를 기반으로 그래프 유형을 성공적으로 구별했습니다. o3가 전반적으로 가장 잘 수행하여 Grid 및 ER 그래프를 정확히 식별했습니다. 모델들은 ER 그래프의 균일한 차수 분포와 BA 및 LFR 그래프의 편향된 분포를 구별할 수 있었으나, BA 와 LFR 유형 사이에서 혼동이 가끔 발생했습니다.
• 노드 순위 매기기: 성능은 지표에 따라 크게 달라졌습니다. LLM 은 국소 보행에서 전역 경로를 추론하는 어려움으로 인해 최단 경로 기반 지표 (Betweenness 및 Closeness Centrality) 에서는 어려움을 겪었습니다. 그러나 무작위 보행의 방문 빈도와 상관관계가 있는 PageRank에서는 현저히 더 잘 수행했습니다. o3모델은 PageRank 추정에서 다른 모델을 크게 능가하여 약 80% 의 Precision@20 을 달성했습니다.

의의 및 기여
본 논문은 네 가지 주요 기여를 주장합니다:

1. EstGraph 벤치마크: 전체 가시성이 불가능한 대규모 그래프에 대한 LLM 추론을 테스트하도록 설계된 대규모 벤치마크 데이터셋과 네 가지 작업 도입으로, 소규모 알고리즘 벤치마크와 실제 세계 데이터 제약 사이의 간극을 해소합니다.
2. 대규모 그래프를 위한 프롬프트 엔지니어링: 무작위 보행 통계를 인코딩하는 작업별 프롬프트 구성 제안. 이 접근법은 단순한 엣지 리스트 인코딩 대비 프롬프트 길이를 최대 559 배 줄여 현재 컨텍스트 한계 내에서 수백만 개의 노드를 가진 그래프 평가를 가능하게 합니다.
3. 경험적 평가: 다양한 그래프 구조 (합성 및 실제 세계) 및 규모에 걸쳐 추정 작업에 대한 추론 LLM 의 포괄적 평가로, LLM 이 국소 통계를 활용하여 전역 속성을 추론할 수 있음을 입증합니다.
4. 실용적 권장사항: 이상치 추정을 처리하기 위한 중앙값 집계 사용, 국소 편향을 줄이기 위한 여러 개의 짧고 중간 길이의 보행 활용, 최단 경로 지표보다 PageRank 유사 지표 추정이 더 실현 가능하다는 인식 등 LLM 을 활용한 대규모 그래프 분석에 대한 가이드라인 제공.

저자들은 LLM 이 아직 전문 그래프 알고리즘을 대체할 수는 없지만, 적절한 샘플링 및 프롬팅 전략을 갖추면 대규모 그래프 속성에 대한 합리적인 추정을 제공할 수 있다고 결론지었습니다. 이 연구는 전체 그래프 접근이 불가능한 대규모 네트워크 분석을 위해 LLM 이 보완적 도구로 역할을 할 수 있는 가능성을 강조합니다.