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

技術的サマリー：ランダムウォークによる大規模グラフ特性推定における LLM の評価

問題定義
NLGraph、GraphQA、GraphArena などの大規模言語モデル（LLM）のグラフ推論能力を評価するための既存のベンチマークは、現在のモデルのコンテキストウィンドウの制約によって制限されています。その結果、これらのベンチマークは、構造全体をプロンプトにエンコードできる小規模なグラフ（通常 10〜50 ノード）を利用しています。しかし、現実世界のグラフ（例：ソーシャルネットワーク、ピアツーピアネットワーク、ウェブネットワーク）は、数百万のノードを含むことが多く、API を通じて部分的にしかアクセスできないことが頻繁にあります。これにより、完全な可視化が不可能な大規模グラフタスクにおける LLM の性能を評価するギャップが生じています。具体的には、サンプリングから得られる部分的で局所的な情報のみを用いて、サイズ、コミュニティ構造、ノード中心性などの大域的特徴を推定する LLM の能力に関する評価が不足しています。

手法
著者は、アクセス制限された条件下での大規模グラフにおける LLM の推論を評価するために設計された新しいベンチマークデータセットおよびフレームワーク「EstGraph」を提案します。この手法の中心は、最大 239 万ノードに及ぶグラフから局所統計量を抽出するためにランダムウォークサンプリングを使用し、それを LLM のコンテキスト制限に適合するように要約してプロンプト化することです。

1. データセット構築:

   • 合成グラフ: NetworkX および NetworKit を使用して生成され、Barabasi-Albert（BA/べき則）、Erdos-Renyi（ER/ランダム）、および Gaussian Random Partition（GRP）グラフを含みます。これらは小規模（100〜1k）、中規模（1k〜10k）、大規模（10k〜100k）のスケールに分類されます。
   • 実世界グラフ: SNAP リポジトリからの 5 つのデータセット（例：ego-Twitter、as-skitter、wiki-Talk）で、ノード数は 81k から 239 万までです。
   • コミュニティグラフ: コミュニティ検出タスク用の、既知のコミュニティ構造（5〜12 クラスター）を持つ 20 の LFR（Lancichinetti-Fortunato-Radicchi）グラフ。

2. サンプリング戦略:

   • 完全なエッジリストを提供する代わりに、このフレームワークはノードをサンプリングするために単純ランダムウォーク（SRW）およびメトロポリス・ヘイスティングス（MH）ウォークを採用します。
   • コンテキスト長の制限に対処するため、生ウォークデータを直接入力するのではなく、ウォーク統計量を要約したタスク固有のプロンプト構成を生成します。これらの統計量には以下が含まれます：
     • ウォーク長と一意のノード/エッジの数。
     • 最初のノード衝突までの時間（局所密度の指標）。
     • 始点ノードへの復帰時間。
     • 10% 刻みで発見された累積一意ノード数。
     • 次数分布（最高/最低次数ノード、平均次数）。
     • 総ノード数の漏洩を防ぐための匿名化されたノード名。

3. 評価タスク:
   このベンチマークは、LLM を以下の 4 つの異なる推定タスクで評価します：

   • グラフサイズ推定: ノード数とエッジ数の総数を予測する。
   • コミュニティ数推定: LFR グラフにおけるクラスターの数を予測する。
   • グラフ構造識別: 次数分布パターンに基づいてグラフタイプ（BA、ER、LFR、またはグリッド）を分類する。
   • 影響力のあるノードのランキング: 媒介中心性、近接中心性、および PageRank に基づいて上位 k ノードを特定する。

4. モデルとベースライン:

   • LLM: gemini-2.5-pro、sonnet-4、o3（OpenAI）、およびDeepSeek-V3.1を含む推論能力を備えたモデルで評価。
   • ベースライン: 一様サンプリング、MH サンプリング、最大次数ランダムウォーク、および復帰時間ベース推定を含む古典的なグラフ推定アルゴリズム。

主要な結果

• グラフサイズ推定: LLM は、妥当な精度でグラフサイズを推定する能力を示しました。合成データセットでは、o3 などのモデルが中央値相対誤差を 20% 未満に抑え、古典的なベースラインを上回る場合もありました。実世界データセットでは、gemini-2.5-pro が LLM の中で最良の推定を提供しましたが、誤差は合成データよりも高くなりました。著者は、理論的には不偏サンプリング（MH）が優れているものの、MH の実装が困難な実用的な設定では、単純ランダムウォーク（SRW）が競争力のある結果を提供したと指摘しています。
• コミュニティ検出: LLM は、5〜12 コミュニティを持つグラフにおいて、平均絶対誤差が約 2 クラスターでコミュニティの存在を検出できました。しかし、サブグラフでほぼゼロの誤差を達成した Greedy Modularity や Louvain などの古典的アルゴリズムと比較して、正確な数え上げについてはまだ信頼性が十分ではありませんでした。
• 構造識別: LLM は次数分布に基づいてグラフタイプを区別することに成功しました。o3 が全体的に最も優れた性能を発揮し、グリッドおよび ER グラフを正しく識別しました。モデルは、ER グラフの一様次数分布と BA および LFR グラフの歪んだ分布を区別する能力を示しましたが、BA と LFR タイプの間で混同が時々発生しました。
• ノードランキング: 性能は指標によって大きく異なりました。LLM は、局所的なウォークから大域的な経路を推論することが困難なため、最短経路に基づく指標（媒介中心性と近接中心性）では苦労しました。しかし、ランダムウォークでの訪問頻度と相関するPageRankでは、顕著に良いパフォーマンスを発揮しました。o3 モデルは PageRank 推定において他を大きく凌駕し、Precision@20 で約 80% を達成しました。

意義と貢献
本論文は 4 つの主要な貢献を主張しています：

1. EstGraph ベンチマーク: 完全な可視化が不可能な大規模グラフにおける LLM の推論をテストするために設計された大規模ベンチマークデータセットと 4 つのタスクの導入。小規模なアルゴリズムベンチマークと実世界のデータ制約の間のギャップを埋める。
2. 大規模グラフのためのプロンプトエンジニアリング: ランダムウォーク統計量をエンコードするタスク固有のプロンプト構成の提案。このアプローチは、単純なエッジリストエンコーディングと比較してプロンプト長を最大 559 倍削減し、現在のコンテキスト制限内で数百万ノードのグラフの評価を可能にする。
3. 実証的評価: 多様なグラフ構造（合成および実世界）およびスケールにわたる推定タスクにおける推論 LLM の包括的な評価。LLM が局所統計量を活用して大域的特性を推論できることを実証。
4. 実用的な推奨事項: LLM による大規模グラフ分析のためのガイドラインの提供。例えば、外れ値の推定を処理するための中央値集約の使用、局所的バイアスを軽減するための複数の短〜中距離ウォークの利用、および最短経路指標よりも PageRank 類似の指標の方が推定が現実的であることの認識。

著者は、LLM はまだ専門的なグラフアルゴリズムの代替にはならないが、適切なサンプリングおよびプロンプト戦略を備えれば、大規模グラフ特性に対して妥当な推定を提供し得ると結論付けています。この研究は、完全なグラフアクセスが不可能な大規模ネットワークの分析において、LLM が補完的なツールとして機能する可能性を浮き彫りにしています。