Graph RAGにおけるコミュニティ検出とは、構築されたナレッジグラフに対してLeidenアルゴリズムを適用し、密に接続されたノード群（コミュニティ）を自動的に同定するプロセスである。検出されたコミュニティに対して階層的なサマリが生成され、Global Searchの基盤となる。
Graph RAGにおけるコミュニティ検出は、ナレッジグラフのノード群を意味的に関連するクラスタ（コミュニティ）に分割するプロセスである。このステップがGraph RAGの最大の差別化要因であり、Global Search（コーパス全体を俯瞰する質問への回答）を可能にする技術的基盤となっている。
コミュニティ検出により、大規模なナレッジグラフが管理可能な単位に分割される。各コミュニティはLLMによるサマリ生成の単位となり、クエリ時にはこれらのサマリをMap-Reduceパターンで処理することで、コーパス全体の知識を効率的に参照できる。
Microsoft ResearchのGraph RAG論文では、Leidenアルゴリズムを採用してコミュニティ検出を行い、検出された各コミュニティに対して階層的なサマリを生成している。この階層構造により、異なる粒度レベルでの情報アクセスが可能になる。
Leidenアルゴリズムは、2019年にV.A. Traag, L. Waltman, N.J. van Eckによって提案されたグラフクラスタリングアルゴリズムである。Louvainアルゴリズムの後継として設計され、Louvainが生成する可能性のある「不正に接続されたコミュニティ（badly connected communities）」の問題を解決している。
名前はオランダのライデン大学に由来し、ネットワーク科学分野で最も広く使用されるコミュニティ検出アルゴリズムの一つである。
Leidenアルゴリズムは、以下の3フェーズを反復的に実行する。
| フェーズ | 処理内容 | 目的 |
|---|---|---|
| ローカル移動 | 各ノードを隣接コミュニティに試行移動し、モジュラリティ利得が最大のコミュニティに割り当てる | 初期コミュニティの形成 |
| リファインメント | コミュニティ内のノードをサブパーティションに分割し、接続性を改善する | Louvainの欠陥回避 |
| 集約 | コミュニティをスーパーノードに圧縮し、新しい縮小グラフを生成する | 次の反復への入力 |
この3フェーズを収束（コミュニティ割り当てが変化しなくなる）まで繰り返すことで、最終的なコミュニティ分割が得られる。
Leidenアルゴリズムが最適化するモジュラリティQは以下の式で定義される。
Q = (1/2m) × Σ[Aij - (ki × kj)/(2m)] × δ(ci, cj)
ここで、Aijは隣接行列の要素、ki はノードiの次数、mはグラフのエッジ総数、ci はノードiが属するコミュニティ、δはクロネッカーのデルタ関数（同じコミュニティなら1、異なれば0）である。モジュラリティ値は-0.5〜1.0の範囲を取り、値が高いほどコミュニティ構造が明確であることを示す。
Leidenアルゴリズムには解像度パラメータ（resolution parameter, γ）があり、検出されるコミュニティの粒度を制御する。
| 解像度γ | コミュニティサイズ | コミュニティ数 | 用途 |
|---|---|---|---|
| 0.1〜0.5 | 大（粗粒度） | 少 | 全体テーマの把握 |
| 1.0（デフォルト） | 中 | 中 | 標準的な分析 |
| 2.0〜5.0 | 小（細粒度） | 多 | 詳細トピック分析 |
| 10.0以上 | 極小 | 極多 | マイクロトピック |
Graph RAGでは複数の解像度レベルでコミュニティ検出を実行し、階層的なコミュニティ構造を生成する。
LeidenがLouvainから改良した主要な点は以下のとおりである。
| 比較項目 | Louvain | Leiden |
|---|---|---|
| 接続性保証 | なし（不正接続コミュニティが発生しうる） | あり（リファインメントフェーズで保証） |
| 計算速度 | O(n log n) | O(n log n)（同等、実測では高速） |
| 解の安定性 | 低（実行ごとに異なりやすい） | 高（リファインメントで安定化） |
| 階層構造 | 生成可能だが品質にばらつき | 高品質な階層構造を安定生成 |
| 実装成熟度 | 多数のライブラリで利用可能 | igraph、leidenalg等で利用可能 |
コミュニティ検出後、各コミュニティに対してLLMを用いたサマリが生成される。サマリ生成は以下のステップで行われる。
各コミュニティサマリには以下の情報が含まれる。
| 要素 | 説明 | 用途 |
|---|---|---|
| タイトル | コミュニティの主題を簡潔に表現 | 検索時のプレビュー |
| 概要 | コミュニティ全体の要約（200〜500語） | Global Searchのコンテキスト |
| 主要エンティティ | コミュニティ内の中心的なエンティティリスト | Local Searchとの連携 |
| 主要関係 | 重要な関係のリスト | 構造的理解の支援 |
| インパクト評価 | コミュニティの重要度スコア | 検索結果のランキング |
低レベルのコミュニティは高レベルのコミュニティに包含される入れ子構造を形成する。Global Searchでは、質問の粒度に応じて適切なレベルのサマリを選択する。全体傾向に関する質問には高レベルのサマリを、特定トピックの詳細には低レベルのサマリを参照する。
コミュニティはGraph RAGにおいて以下の3つの重要な役割を果たす。
大規模ナレッジグラフ（数万〜数百万ノード）を、管理可能な数十〜数千のコミュニティサマリに圧縮する。これにより、LLMのコンテキストウィンドウの制約内で、コーパス全体の知識を参照可能にする。
コミュニティ階層は、コーパス内のトピック構造を自動的に可視化する。高レベルのコミュニティが主要テーマを、低レベルのコミュニティがサブトピックを表現し、コーパスのトピックランドスケープを俯瞰できる。
クエリの性質に応じて、参照すべきコミュニティを効率的に特定する。エンティティベースのルーティング（クエリに含まれるエンティティが属するコミュニティを優先）とセマンティックルーティング（サマリの類似度に基づくコミュニティ選択）の2つのアプローチがある。
| 最適化手法 | 効果 | 実装難易度 | 推奨シーン |
|---|---|---|---|
| 解像度パラメータ調整 | コミュニティ粒度の最適化 | 低 | 全プロジェクト |
| 並列サマリ生成 | 処理時間の短縮 | 中 | 大規模コーパス |
| サマリキャッシング | 再計算コスト削減 | 低 | 反復実験 |
| 増分コミュニティ更新 | 更新時の再計算削減 | 高 | 頻繁な更新 |
| 多段階解像度 | 検索精度の向上 | 中 | 本番運用 |
原理的には他のコミュニティ検出手法（Infomap、Label Propagation、Spectral Clustering等）も使用可能である。ただし、Leidenは階層的なコミュニティ構造の生成に優れており、解像度パラメータによる粒度制御が容易なため、Graph RAGとの相性が特に良い。Infomapは情報理論に基づく手法で、フロー構造の検出に優れるが、階層構造の制御がLeidenほど直感的ではない。
定量評価として、サマリに含まれるエンティティのカバー率（コミュニティ内エンティティのうちサマリに言及されている割合）と、ファクトチェック（サマリの記述が元テキストと矛盾しないか）が基本指標となる。定性評価として、ドメイン専門家による読解性・網羅性・正確性のスコアリングが有効である。自動評価にはLLM-as-a-Judgeパターン（別のLLMにサマリの品質を評価させる）を活用できる。
解像度パラメータγの調整が最も直接的な方法である。コミュニティ数が多すぎる場合はγを下げ（例: 1.0→0.5）、少なすぎる場合はγを上げる（例: 1.0→2.0）。目安として、グラフノード数の5〜10%程度のコミュニティ数が適切とされるが、ドメインによって最適値は異なる。実験的に複数の解像度で検出を実行し、サマリの品質と検索結果の質を比較して最適値を決定する。