社内に技術報告書が500本たまっているとします。ここで上司から「この資料群を通して、我々が繰り返しぶつかっている技術課題は何か、3つ挙げてくれ」と言われたらどうでしょうか。
普通のRAG（検索拡張生成）システムにこの質問を投げると、まず質問文がベクトルに変換され、それに近い断片が上位5〜10件だけ引っ張られてきます。返ってくるのは「ターボポンプの軸振動が課題です」といった、たまたま質問文と語彙が似ていた1本の報告書の話です。500本を俯瞰した答えにはなりません。類似検索は「似た断片を拾う」装置であって、「全体を数える」装置ではないからです。
もう一つ、別の形で失敗する質問があります。「LE-9エンジンの燃焼室圧力の話と、観測衛星の熱真空試験の話は、どこかでつながっているか？」という問いです。この2つを直接まとめて書いた文書が存在しないとき、ベクトル検索は「LE-9の断片」と「熱真空試験の断片」を別々に拾ってくるだけで、その間をつなぐ経路（たとえば両方ともH3ロケットの打上げ計画に紐づく、など）は復元してくれません。断片を集めても、断片の間の関係は自動的には生えてこないのです。
この2種類の失敗を正面から潰しにいくのが GraphRAG（グラフRAG） です。文書をベクトルの袋として持つのではなく、いったんエンティティと関係からなる知識グラフに変換し、そのグラフをコミュニティ（濃く結ばれた塊）に分解して、コミュニティごとの要約をあらかじめ作っておきます。すると「全体の主要テーマは何か」という問いにはコミュニティ要約の集合が、「AとBの関係は？」という問いにはグラフ上の経路が、それぞれ直接答えてくれます。
GraphRAGが活きる場面は、たとえば次のようなところです。
- 企業内ナレッジ横断: 数百〜数万本の設計文書・議事録・障害報告から、部署をまたいだ論点や再発する不具合の系統を洗い出す
- 調査・インテリジェンス分析: ニュース記事群から人物・組織・事件の関係網を組み立て、「この人物とこの組織の接点は何か」を辿る
- 文献サーベイ: 論文集合を手法・データセット・著者のグラフにして、研究分野の勢力図とその階層構造を出す
本記事の内容
- ベクトルRAGが「全体を問う質問」に構造的に答えられない理由
- GraphRAGのパイプライン6段階（チャンク分割 → 抽出 → グラフ構築 → コミュニティ検出 → 要約 → 検索）
- モジュラリティ $Q$ の定義・導出・Louvain/Leidenの動作・解像度パラメータと解像度限界
- Global SearchとLocal Searchの違い、中心性によるコンテキスト選択
- networkxでコミュニティ検出を実際に走らせる実装
- コスト・増分更新・抽出品質という現実の壁と、軽量な代替案
前提知識
この記事を読む前に、以下の記事を読んでおくと理解が深まります。
ベクトルRAGはなぜ「全体を問う質問」に弱いのか
まず、通常のRAGがやっていることを冷静に書き下しておきましょう。文書集合を断片（チャンク）に切り、各断片 $d_j$ を埋め込み関数 $E$ でベクトル化します。クエリ $q$ も同じ空間に落とし、コサイン類似度が高い上位 $k$ 件を取ってきます。
$$ \mathcal{R}(q) = \operatorname*{arg\,top-}k_{j} \; \frac{E(q)^\top E(d_j)}{\|E(q)\|\,\|E(d_j)\|} $$
この式をじっと見ると、弱点がどこにあるかがはっきりします。選択の基準が「クエリとの類似度」だけなのです。ここには「この断片が資料群のどのくらいの割合を代表しているか」という情報も、「この断片と別の断片が同じ話題か」という情報も入っていません。
そのため、次の2つのタイプの質問で構造的に破綻します。
タイプ1: 全体集約型（query-focused summarization）の質問。 「主要テーマを3つ」「最も繰り返し出てくる懸念は」「全体の傾向はどうか」。これらに正しく答えるには、原理的に全文書を1回は見る必要があります。ところが $k$ は数十が上限です。500本の文書があって $k=10$ なら、見えているのは全体の2%です。そして厄介なことに、類似度が高い上位10件はしばしば互いにそっくりです。同じ話題の断片が固まって上位を占め、残り98%にあった別のテーマは影も形もありません。多様性を明示的に入れないかぎり、top-$k$ は「代表サンプル」にはならないのです。
タイプ2: マルチホップ関係型の質問。 「AとBの関係は？」に答えるには、Aを述べた文書とBを述べた文書に加えて、両者を媒介する中間項 $M$ の情報が要ります。しかしクエリ「AとBの関係」の埋め込みは、$M$ の断片とは語彙的にも意味的にも似ていないことが多い。中間項は検索結果に入ってきません。リランキングで並べ替えても、そもそも候補に入っていないものは救えません。
下の図は、この2つの検索の「見えている範囲」を同じグラフの上に重ねたものです。
左のベクトルRAGは、クエリに表層が似た3つのエンティティだけを橙で拾えていますが、残り22個のエンティティと43本の関係はすべて灰色、つまり視界の外です。しかも拾えた3点はグラフ上で離れており、それらがどう関係するかは断片の中に書かれていません。一方、右のGraphRAGは同じグラフを4つのコミュニティに分割していて、どのエンティティも必ずどれかのコミュニティ要約に含まれます。全体を問う質問に対して「もれなく数える」経路が確保されている、という点が決定的な違いです。
ではどうやって文書の山からこの右側のグラフを作り、どうやって使うのでしょうか。パイプライン全体を先に俯瞰しておきます。
GraphRAGのパイプライン全体像
GraphRAGはMicrosoft Researchが2024年に提案した手法（Edge et al., From Local to Global: A Graph RAG Approach to Query-Focused Summarization）で、オープンソース実装が公開されています。処理は大きく6段階です。
この図で一番大事なのは、下側の矢印が示している時間軸の配分です。(1)〜(5) はすべてオフラインのインデックス構築時に1回だけ実行され、クエリごとに走るのは (6) だけという設計になっています。LLMを大量に呼ぶ高価な処理を前倒しにして、クエリ時のレイテンシとコストを抑える、という交換です。裏を返せば、この前倒し分がそのままGraphRAGの初期コストになります（後述）。
各段階を順に見ていきましょう。
(1) チャンク分割
原文書を300〜1200トークン程度の断片に切ります。ここは通常のRAGと同じですが、GraphRAGではチャンクサイズの意味が少し変わります。通常のRAGではチャンクは「検索してLLMに渡す単位」でしたが、GraphRAGではチャンクは「LLMにエンティティ抽出をさせる単位」です。
チャンクを長くすると、1つの断片から多くの関係が同時に見えるので抽出の文脈は豊かになりますが、LLMは長文の後半でエンティティを取りこぼしやすくなります。逆に短くすると取りこぼしは減りますが、LLM呼び出し回数が増えてコストが上がり、チャンクをまたぐ関係が拾えません。実務では600トークン前後、重なり100トークン程度から始めて、抽出されたエンティティ数を見ながら調整するのが素直です。
(2) LLMによるエンティティ・関係抽出
各チャンクをLLMに渡し、次の3種類を構造化データとして吐かせます。
- エンティティ: 名前、型（人物・組織・技術・場所など）、そのチャンクから読み取れる説明文
- 関係: 始点エンティティ、終点エンティティ、関係の説明、強度スコア
- 主張（claim）: 「XがYを2024年に実施した」のような、時制や真偽を伴う言明（実装によっては省略可）
ここで効いてくる工夫が gleaning（拾い残しの回収） です。1回のプロンプトで抽出させたあと、同じチャンクに対して「まだ抽出されていないエンティティが残っているか？」ともう一度LLMに聞き、残っていれば追加抽出させます。これを数回繰り返します。抽出は再現率（取りこぼさないこと）が命なので、多少の重複を許してでも回収を優先する、という判断です。
抽出の品質がその後のすべてを規定するので、ここはプロンプトにドメイン固有の型定義を書き込む価値が非常に高い部分です。汎用の「人物・組織・場所」だけでは、技術文書から「推進剤」「試験項目」「故障モード」といった本当に欲しいエンティティが出てきません。
(3) 知識グラフの構築
抽出結果をエンティティ名でグルーピングして、重み付き無向グラフ $G = (V, E, w)$ に統合します。
- $V$: 名寄せ後のエンティティ集合
- $E$: 少なくとも1回、同じチャンク内で関係が張られたエンティティ対
- $w_{ij}$: そのペアの関係が抽出された回数（あるいは強度スコアの和）
重みが「何回一緒に語られたか」になっている点は素朴ですが、これが後のコミュニティ検出で効きます。何度も同じ文脈で共起するペアは太い辺になり、1回きりの偶発的な共起は細い辺になるからです。
同じ実体に複数の表記があると（「LE-9」「LE-9エンジン」「第1段エンジン」）グラフが分裂してしまうので、名寄せ（エンティティ解決）は必須です。表層の正規化に加え、埋め込みベクトルの類似度で候補を出してLLMに同一性を判定させる、という二段構えがよく使われます。
さらに、同じエンティティについて複数のチャンクからバラバラの説明文が集まるので、それをLLMに1本の説明にまとめさせます（description summarization）。この時点で、ノードは「名前 + 統合された説明文」を持つようになります。
ここまでで材料はそろいました。次が本記事の数学的な中心、このグラフをどう切り分けるかです。
コミュニティ検出：グラフを「濃い塊」に割る
直感：良い分割とは「偶然より濃い」分割のこと
25人の同僚がいて、誰と誰がよく一緒に昼食に行くかを線で結んだグラフを想像してください。「グループ分けせよ」と言われたら、あなたはグループ内の線が密で、グループ間の線がまばらになるように分けるはずです。
ところが「密」を素朴に「グループ内の線の本数」で測ると、うまくいきません。全員を1つのグループにすれば内部の線は最大になってしまうからです。必要なのは基準線との比較です。すなわち、「もし人々がランダムに昼食相手を選んでいたら、このグループ内にはどれくらいの線が引かれるはずか」を計算し、実際の線がその期待値をどれだけ超えているかを測ればよい。これがモジュラリティの発想です。
ヌルモデル：ランダムなら何本つながるか
比較対象となるランダムグラフの作り方が肝心です。完全にランダム（各ペアが等確率で結ばれる）にしてしまうと、そもそも人気者と孤立者がいるという事実を無視してしまいます。そこで使うのが configuration model（次数保存ランダムグラフ） です。
各ノード $i$ の次数 $k_i$（結ばれている辺の本数）はそのままに、辺の「行き先」だけをランダムに繋ぎ替えます。イメージとしては、各ノードから $k_i$ 本の半端な辺（スタブ）を生やし、全部で $2m$ 本のスタブをシャッフルして無作為にペアリングする、という手続きです（$m$ は辺の総数、握手補題より $\sum_i k_i = 2m$）。
このとき、ノード $i$ のある1本のスタブが、ノード $j$ のスタブと繋がる確率を求めます。全スタブは $2m$ 本あり、そのうち $j$ に属するものは $k_j$ 本なので、確率は $k_j / 2m$ です。$i$ にはスタブが $k_i$ 本あるので、$i$ と $j$ の間に張られる辺の本数の期待値は
$$ \mathbb{E}[A_{ij}] = k_i \cdot \frac{k_j}{2m} = \frac{k_i k_j}{2m} $$
となります。これが「ランダムだったらこのくらい繋がっているはず」という基準線です。次数が大きいノード同士ほど期待値も大きい、という当たり前の性質が入っている点が重要で、ハブ同士が繋がっていても偶然かもしれないと割り引いて評価してくれます。
モジュラリティ $Q$ の定義
基準線ができたので、実際 $A_{ij}$ との差を、同じコミュニティに属するペアについてだけ足し上げます。
$$ Q = \frac{1}{2m}\sum_{i,j}\left(A_{ij} – \frac{k_i k_j}{2m}\right)\delta(c_i, c_j) \tag{1} $$
記号を確認しておきます。$A_{ij}$ は隣接行列（詳しくは隣接行列で表すグラフ理論）、$k_i = \sum_j A_{ij}$ はノード $i$ の次数、$m$ は辺の総数、$c_i$ はノード $i$ が属するコミュニティのラベル、$\delta(c_i,c_j)$ は同じコミュニティなら1、違えば0のクロネッカーのデルタです。先頭の $1/2m$ は、$Q$ が $[-1/2, 1]$ に収まるようにするための正規化です。
式(1)は総和の形なので少し扱いにくいのですが、$\delta$ があるおかげでコミュニティごとの和に分解できます。コミュニティ $C$ の内部辺数を $e_C$、次数の総和を $d_C = \sum_{i \in C} k_i$ と書くと、まず第1項は
$$ \frac{1}{2m}\sum_{i,j \in C} A_{ij} = \frac{2 e_C}{2m} = \frac{e_C}{m} $$
です（$i,j$ を両方向に走らせるので内部辺を2回数えることに注意）。第2項も同様に和を分離できて、
$$ \frac{1}{2m}\sum_{i,j \in C}\frac{k_i k_j}{2m} = \frac{1}{(2m)^2}\left(\sum_{i \in C} k_i\right)\left(\sum_{j \in C} k_j\right) = \left(\frac{d_C}{2m}\right)^2 $$
となります。両者をコミュニティについて足し合わせると、実務でよく使う形が出てきます。
$$ Q = \sum_{C}\left[\frac{e_C}{m} – \left(\frac{d_C}{2m}\right)^2\right] \tag{2} $$
式(2)の読み方はとても素直です。第1項は「全辺のうち何割がこのコミュニティの内部にあるか」、第2項は「ランダムなら何割が内部に落ちるはずか」。その差の総和が $Q$ です。$Q$ が大きいほど、偶然では説明できないほど内部が濃い分割ということになります。
具体例：小さなグラフで $Q$ を計算してみる
三角形2つを1本の橋でつないだ6ノードのグラフで、4通りの分割の $Q$ を実際に計算しました。
手計算でも追えます。辺は7本なので $m = 7$、$2m = 14$。左端の「正しい2分割」では、コミュニティ $\{1,2,3\}$ の内部辺は3本、次数の和は $2+2+3=7$ なので、式(2)より
$$ \frac{3}{7} – \left(\frac{7}{14}\right)^2 = 0.42857 – 0.25 = 0.17857 $$
もう一方も対称なので同じ値になり、合計 $Q = 0.35714$。図の表示値と一致しています。
この図から3つのことが読み取れます。第一に、「全体を1つに」すると $Q$ はぴったり0になります。これは偶然ではなく、$C$ が全体なら $e_C = m$、$d_C = 2m$ なので式(2)が $1 – 1 = 0$ になるためです。つまり $Q > 0$ は「分割しないよりマシ」を意味します。第二に、テーマを無視した分割（$-0.082$）や全ノードを個別にした分割（$-0.173$）では $Q$ が負になります。$Q$ は悪い分割をきちんと罰する指標です。第三に、細かく割りすぎても $Q$ は下がるので、コミュニティ数を人間が指定しなくても $Q$ の最大化が自動的に「ちょうどよい粒度」を選んでくれます。この最後の性質が、GraphRAGのようにドメインが事前にわからない場面で決定的に効きます。
Louvain法：貪欲な局所移動と粗視化の繰り返し
$Q$ を最大化する分割を厳密に求める問題はNP困難です。そこで実際にはヒューリスティクスを使います。標準は Louvain法（Blondel et al., 2008）で、次の2つのフェーズを交互に繰り返します。
フェーズ1（局所移動）: 全ノードを別々のコミュニティに置いた状態から始め、各ノード $i$ について「隣接コミュニティのどれかに移したら $Q$ がどれだけ増えるか」を計算し、最も増える先に移します。増える先がなければ動かしません。全ノードについて改善が止まるまで繰り返します。
フェーズ2（粗視化）: フェーズ1で得られた各コミュニティを1つのスーパーノードに潰し、コミュニティ間の辺数を重みとする新しいグラフを作ります。そしてフェーズ1に戻ります。
この移動の判定に使う $\Delta Q$ が計算できないと話が始まらないので、導出しておきます。孤立していたノード $i$ をコミュニティ $C$ に入れるとき、$C$ の内部辺は $i$ から $C$ へ伸びる辺の本数 $k_{i,\text{in}}$ だけ増え、次数和は $k_i$ だけ増えます。式(2)の該当項の変化を書くと、
$$ \Delta Q = \underbrace{\left[\frac{e_C + k_{i,\text{in}}}{m} – \left(\frac{d_C + k_i}{2m}\right)^2\right]}_{\text{移動後}} – \underbrace{\left[\frac{e_C}{m} – \left(\frac{d_C}{2m}\right)^2 – \left(\frac{k_i}{2m}\right)^2\right]}_{\text{移動前（}i\text{ は単独コミュニティ）}} $$
$e_C/m$ の項が打ち消し合い、2乗の項をまとめます。$(d_C + k_i)^2 – d_C^2 – k_i^2 = 2 d_C k_i$ を使うと、
$$ \Delta Q = \frac{k_{i,\text{in}}}{m} – \frac{2 d_C k_i}{(2m)^2} = \frac{k_{i,\text{in}}}{m} – \frac{d_C\, k_i}{2m^2} \tag{3} $$
式(3)は美しいくらい局所的です。移動先コミュニティの情報として必要なのは $d_C$（次数和）と $k_{i,\text{in}}$（そこへの接続本数）だけで、グラフ全体を舐める必要がありません。だからLouvainは疎グラフに対してほぼ $O(|E|)$ で走り、数百万ノード級でも実用になります。
式(3)の意味も読み取れます。第1項は「そのコミュニティにどれだけ強く繋がっているか」という引力、第2項は「そのコミュニティが既に大きい（$d_C$ が大きい）ほど入りにくくする」という斥力です。巨大な塊が全部飲み込むのを、ヌルモデル項が押しとどめている構図になっています。
Leiden法：Louvainの穴を塞ぐ
Louvainには有名な欠陥があります。得られたコミュニティが内部で連結でないことがあるのです。あるノードが自分のコミュニティ内の「橋」の役割をしていたのに、そのノードだけ別のコミュニティに移動してしまうと、残ったコミュニティが2つに割れてしまう。しかしLouvainはコミュニティ単位でしか粗視化しないので、この分断に気づかず、そのまま次のレベルに持ち上げてしまいます。
Leiden法（Traag, Waltman & van Eck, 2019）は、フェーズ1と2の間に refinement（精錬）フェーズを挟むことでこれを直します。局所移動で得られたコミュニティを、いったんその内部でさらに細かく割り直し（各サブコミュニティが連結であることを保証する）、粗視化はその精錬された分割に対して行います。加えて、移動先の選択をランダム化して局所最適に貼り付くのを防ぎます。
Leidenは「すべてのコミュニティが内部で連結である」ことを保証し、反復を重ねると「どのノードも単独では移動しても改善しない」というより強い最適性条件に収束します。GraphRAGの実装がLouvainではなくLeidenを既定にしているのは、この保証があるためです。コミュニティが分断されていると、その要約が「無関係な2つの話題が混ざった文章」になってしまい、検索品質に直接響きます。
では実際のエンティティグラフに走らせるとどうなるか見てみましょう。
実際に走らせた結果
先ほどの25ノード・43辺のエンティティグラフ（架空の宇宙開発文書コーパスから抽出した想定）にLouvainを適用しました。
左のグラフでは4つのコミュニティが検出され、$Q = 0.6233$ でした。実験用にグラフを作ったときに埋め込んだ4テーマ（推進系・通信系・軌道/デブリ系・試験/構造系）がそのまま復元されています。注目すべきは「H3ロケット」と「観測衛星」という、複数テーマに辺を持つブリッジ・エンティティの扱いです。アルゴリズムはこれらを別コミュニティに切り出すのではなく、最も強く繋がっているコミュニティに吸収しました。式(3)の斥力項が、小さなコミュニティを新規に作ることに罰を与えるからです。
右の図は、同じグラフの隣接行列をコミュニティ順に並べ替えたものです。辺（濃い升目）が対角ブロックにきれいに集まり、ブロック外にはブリッジ由来のわずかな点しか残っていません。これがまさに「内部が濃く、間がまばら」の視覚的な定義であり、$Q$ が測っているものそのものです。ちなみに $Q = 0.6233$ は実データとしてはかなり高い値で、テーマ構造が明確なコーパスであることを示しています。
さて、この分割は「4つ」でしたが、もっと細かく割りたい、あるいはもっと粗く割りたいときはどうするのでしょうか。
解像度パラメータ $\gamma$
式(2)のヌルモデル項に係数 $\gamma$ を掛けたものが、解像度つきモジュラリティです。
$$ Q_\gamma = \sum_{C}\left[\frac{e_C}{m} – \gamma\left(\frac{d_C}{2m}\right)^2\right] \tag{4} $$
$\gamma$ は「ランダムでも繋がるはずの分（＝割り引き）」をどれだけ強く効かせるかのつまみです。$\gamma$ を大きくすると第2項の罰が強くなるので、大きなコミュニティを作ることが不利になり、分割が細かくなります。逆に $\gamma$ を小さくすると罰が弱まり、コミュニティは大きく粗くなります。$\gamma = 1$ が標準のモジュラリティです。式(3)の移動判定も同様に $\Delta Q_\gamma = k_{i,\text{in}}/m – \gamma d_C k_i / 2m^2$ になります。
実際に $\gamma$ を0.2から4.0まで振って、12個の乱数シードで平均した結果が次の図です。
3つのことが読み取れます。第一に、青線（コミュニティ数）は $\gamma$ とともに単調に増える階段状の曲線です。エンティティグラフでは $\gamma = 0.3$ で平均2.8個、$\gamma = 1.0$ で4個、$\gamma = 4.0$ で9.7個になりました。カラテクラブでも $\gamma=0.3$ で2個から $\gamma=4.0$ で11.8個へと同じ傾向です。階段状になるのは、$\gamma$ を少し動かしても最適分割は変わらず、ある閾値を越えた瞬間にコミュニティが割れるからです。平らな踊り場が長い $\gamma$ 領域は、その粒度の構造が頑健であることを示しており、粒度を選ぶ良い手がかりになります。
第二に、紫の破線（最大化している目的関数 $Q_\gamma$ そのもの）は $\gamma$ とともに単調に下がります。これは当然で、式(4)の罰項が大きくなっているからです。$Q_\gamma$ の値どうしを $\gamma$ 違いで比べても意味がないという重要な注意がここにあります。
第三に、橙線（$\gamma$ で最適化した分割を、$\gamma = 1$ の標準 $Q$ で採点し直したもの）は $\gamma \approx 0.6$〜$1.4$ あたりで最大の平坦域を作り、両側で下がります。エンティティグラフの最大値は $0.6244$、カラテクラブは $0.4418$ でした。$\gamma=1$ の既定値が、標準の意味では確かに良い場所に居ることが確認できます。
解像度限界：$\gamma$ を導入せざるを得ない理由
$\gamma$ は単なる便利なつまみではなく、モジュラリティが抱える理論的な欠陥への対処でもあります。解像度限界（Fortunato & Barthélemy, 2007）と呼ばれる現象で、これは式(2)から直接導けます。
コミュニティ $A$ と $B$ が、たった1本の辺で繋がっているとします。この2つは明らかに別のコミュニティに見えます。では、これらをあえて合併したら $Q$ はどうなるかを計算してみましょう。合併すると、間の1本が内部辺に格上げされるので $e$ は1増え、次数和は $d_A + d_B$ になります。式(2)より
$$ \Delta Q = \left[\frac{e_A + e_B + 1}{m} – \left(\frac{d_A + d_B}{2m}\right)^2\right] – \left[\frac{e_A + e_B}{m} – \left(\frac{d_A}{2m}\right)^2 – \left(\frac{d_B}{2m}\right)^2\right] $$
2乗を展開して $(d_A + d_B)^2 – d_A^2 – d_B^2 = 2 d_A d_B$ を使うと、
$$ \Delta Q = \frac{1}{m} – \frac{2 d_A d_B}{(2m)^2} = \frac{1}{m} – \frac{d_A d_B}{2m^2} $$
$\Delta Q > 0$、つまり合併したほうが $Q$ が高くなる条件は
$$ d_A d_B < 2m \tag{5} $$
です。$d_A = d_B = d$ の対称な場合に直すと $d < \sqrt{2m}$。つまり、次数和が $\sqrt{2m}$ 程度より小さいコミュニティは、たとえ1本の辺でしか繋がっていなくても、モジュラリティ最大化によって強制的に合併されてしまうのです。しかも閾値がグラフ全体のサイズ $m$ に依存しているのが厄介で、グラフが大きくなるほど「見えなくなる」小コミュニティのサイズも大きくなっていきます。
本記事のエンティティグラフでは $2m = 86$ なので $\sqrt{2m} \approx 9.3$ です。検出された4コミュニティの次数和は26, 25, 20, 15で、いずれもこの閾値を余裕で超えています。だから小さいテーマが飲み込まれずに済んだわけです。しかし数万ノードのコーパスでは $\sqrt{2m}$ が数百になり、少数の文書にしか出てこない重要な小テーマは $\gamma = 1$ では絶対に見えません。$\gamma$ を上げるのは、この閾値を人為的に下げる操作にほかなりません。より根本的には、ヌルモデル項を定数に置き換えた CPM（Constant Potts Model） のように解像度限界を持たない目的関数を使う選択肢もあり、Leidenの実装はこれもサポートしています。
階層があるとなぜ嬉しいのか
Louvain/Leidenは粗視化を繰り返すので、副産物として階層が自動的に手に入ります。各粗視化ステップで得られる分割を保存しておけばよいだけです。
このグラフではレベル0で6コミュニティ（$Q = 0.5484$）、レベル1で4コミュニティ（$Q = 0.6233$）という2段の階層が得られました。レベル0では「軌道決定・レーダ観測・衝突回避」と「低軌道・デブリ・デオービット装置」が別々の細かい塊として分かれており、レベル1でそれらが「軌道/デブリ」という1つのテーマに統合されています。粒度が粗くなるにつれて $Q$ が上がっている点も注目に値します。この規模のグラフでは、細かく割るより4つにまとめたほうが「偶然を超えた濃さ」の総量が大きい、ということです。
この階層がGraphRAGにとって嬉しい理由は3つあります。
- 要約の抽象度が選べる: 「全体の主要テーマは？」なら上位レベル（粗いコミュニティ）の要約だけで足り、「軌道決定まわりの詳細は？」なら下位レベルを見ればよい。質問の粒度に応じてレベルを切り替えられます。
- トークン予算に合わせられる: 上位レベルはコミュニティ数が少ないので、全要約を足してもコンテキストウィンドウに収まります。下位レベルは詳細だが数が多い。予算に応じてレベルを選ぶ、という単純な制御が可能になります。
- 要約が再帰的に作れる: 下位コミュニティの要約を材料にして上位コミュニティの要約を書けるので、上位の要約を作るときに元テキスト全部を読み直す必要がありません。長大なコーパスでも要約生成が回ります。
グラフをどう割るかがわかったので、次はその割った塊をどう「読める形」にするかです。
(5) コミュニティ要約の事前生成
各コミュニティについて、LLMにコミュニティレポートを書かせます。入力になるのは、そのコミュニティに含まれるエンティティの名前と説明、内部の関係とその説明、（あれば）主張、そして下位コミュニティの要約です。出力は、タイトル・全体サマリ・重要度スコア・主要な発見（findings）を持つ構造化文書です。
ここで重要な設計上の判断が2つあります。
優先順位づけ: コミュニティが大きいと、要素をすべて入れるとプロンプトが溢れます。そこで、内部の関係を両端ノードの次数の和が大きい順に並べ、予算に収まる分だけ入れます。次数が大きいノードに絡む関係を優先する、という単純なルールですが、そのコミュニティの骨格を先に押さえる効果があります。
再帰的な積み上げ: 上位コミュニティの要約は、下位コミュニティの要約を材料に書きます。階層があるおかげで、コーパス全体をLLMに読ませることなく、全体を代表する要約に到達できます。
この工程が終わった時点で、システムは「コーパス全体をカバーする、階層化された要約の集合」を持っていることになります。ベクトルRAGとの最大の違いはここです。ベクトルRAGはクエリが来るまで何も要約していませんが、GraphRAGはクエリが来る前に全体を読み終えているのです。
準備は整いました。いよいよ検索です。
(6) Global Search と Local Search
GraphRAGの検索は2種類あり、問いの形によって使い分けます。
Global Search：コミュニティ要約のmap-reduce
「この資料群の主要テーマは何か」のようにコーパス全体の集約を要求する問いにはGlobal Searchを使います。処理はmap-reduceそのものです。
mapフェーズ: 指定したレベルのコミュニティ要約を、コンテキスト長に収まるバッチに分割します。各バッチについて、要約とクエリをLLMに渡し、「この情報だけで答えられる部分回答」と「その部分回答がクエリにどれだけ役立つか」の有用度スコア（0〜100）を出させます。これらはすべて並列に実行できます。
reduceフェーズ: 集まった部分回答を有用度スコアの降順に並べ、スコア0のものを捨て、上位からコンテキスト予算いっぱいまで詰め込んで、最終回答をLLMに書かせます。
この設計の効果は明確です。回答は必ずコーパス全体を経由します。上位レベルのコミュニティ要約はコーパス全体を分割被覆しているので、どのテーマも少なくとも1回はLLMの目に触れる。これがtop-$k$ 検索との決定的な差です。多様性が確保され、「500本のうち3本にしか出てこないが重要なテーマ」も原理的には拾えます。
一方でコストは正直です。map段のLLM呼び出し回数がコミュニティ要約の数（正確にはバッチ数）に比例するので、1クエリで数十回から数百回のLLM呼び出しが走ります。ベクトルRAGの1クエリ1回とは2桁違うと思っておくべきです。レベルを上げて（コミュニティを粗くして）呼び出し回数を減らすのが現実的な調整弁です。
Local Search：エンティティ近傍の探索
「観測衛星に関係する要素は何か」「LE-9エンジンの冷却方式は？」のように、特定のエンティティを軸にした問いにはLocal Searchを使います。手順は次のとおりです。
- クエリを埋め込み、エンティティの説明文の埋め込みとマッチさせて起点エンティティを見つける
- 起点から1ホップ、必要なら2ホップの近傍エンティティと、その間の関係を集める
- それらのエンティティが登場する元テキスト断片（text unit）を引く
- それらが属するコミュニティのレポートを引く
- 以上を優先度つきでコンテキスト予算に詰め込み、1回のLLM呼び出しで回答する
図の右側は、起点を「観測衛星」としたときの実際の到達範囲です。1ホップで5件、2ホップで11件、合計17件（グラフの68%）に届いています。ここで重要なのは、2ホップ先には「CFRP構造」や「熱真空試験」といった、クエリ文とは語彙的にまるで似ていないエンティティが含まれている点です。ベクトル検索なら絶対に拾えなかったこれらの情報を、グラフ構造が連れてきてくれます。マルチホップ質問に強い理由がここにあります。
Local SearchはLLM呼び出しが基本1回で済むので、コストはベクトルRAGとほぼ同等です。実務ではLocal Searchを主力にして、全体集約が必要なときだけGlobal Searchに切り替える、という運用が費用対効果の面で理にかなっています。
どちらを使うかの判断
| 問いのタイプ | 例 | 適した検索 |
|---|---|---|
| 全体集約・傾向 | 「主要テーマを3つ」「繰り返し現れる懸念は」 | Global Search |
| 比較・網羅 | 「議論されている手法を全部列挙して」 | Global Search |
| 特定エンティティの詳細 | 「LE-9の冷却方式は」 | Local Search |
| 関係・マルチホップ | 「AとBの接点は」 | Local Search |
| 単純な事実照合 | 「試験日は何日か」 | 通常のベクトルRAGで十分 |
最後の行が大事です。ピンポイントの事実照合にGraphRAGを使う必要はありません。むしろ抽出時に情報が落ちている可能性がある分、原文をそのまま引くベクトルRAGのほうが確実です。だから実務では両方を持ち、クエリの種類でルーティングするハイブリッド構成が主流になります（GraphRAGの実装にも、Localから始めてGlobalの要約を織り交ぜるDRIFT Searchのような中間形態が用意されています）。
さて、Local Searchの手順4で「優先度つきで詰め込む」と書きましたが、この優先度をどう決めるかにグラフならではの道具があります。
中心性でコンテキストを選ぶ
コンテキストウィンドウは有限なので、近傍のエンティティ全部は入りません。何を優先するかを決める必要があります。ここでグラフ理論の中心性が効いてきます。3つの代表的な中心性を、同じグラフで実際に計算しました。
次数中心性は、単に接続本数を正規化したものです。
$$ C_D(i) = \frac{k_i}{|V| – 1} $$
このグラフの上位は「LE-9エンジン」（0.250）、「低軌道」「観測衛星」（ともに0.208）でした。次数中心性が高いノードはその場のハブで、そのエンティティの周辺には情報が多く集まっています。「LE-9について教えて」のような問いでは、まずここを入れるべきです。実装が軽い（$O(|E|)$）ので、リアルタイムのコンテキスト選択に向きます。
媒介中心性は、ノード $i$ が他のノード対の最短経路上にどれだけ乗っているかを測ります。
$$ C_B(i) = \sum_{s \neq i \neq t} \frac{\sigma_{st}(i)}{\sigma_{st}} $$
ここで $\sigma_{st}$ は $s$ から $t$ への最短経路の総数、$\sigma_{st}(i)$ はそのうち $i$ を通るものの数です。上位は「低軌道」（0.527）、「観測衛星」（0.479）、「H3ロケット」（0.413）でした。図を見ると、この3つはまさにテーマとテーマをつないでいる橋です。次数中心性で1位だった「LE-9エンジン」は媒介中心性では上位に来ません。推進コミュニティの中では中心的でも、他テーマへの橋にはなっていないからです。
この違いは実用的な意味を持ちます。「AとBの関係は？」のような横断的な問いでは、媒介中心性の高いエンティティを優先的にコンテキストに入れるべきです。橋を落としてしまうと、そもそも関係が説明できなくなるからです。ただし媒介中心性は計算が重く（Brandesのアルゴリズムで $O(|V||E|)$）、大規模グラフではサンプリング近似が必要になります。
PageRank は「重要なノードから参照されているノードは重要」という再帰的定義を、ランダムウォークの定常分布として実現します。
$$ \pi_i = \frac{1 – \alpha}{|V|} + \alpha \sum_{j \to i} \frac{\pi_j}{k_j} $$
$\alpha$（通常0.85）はダンピング係数で、ランダムウォーカーが確率 $1-\alpha$ でどこかへ瞬間移動することを表します。上位は「LE-9エンジン」（0.063）、「低軌道」（0.056）、「観測衛星」（0.055）で、次数中心性とよく似た順位になりました。無向グラフでダンピングがなければPageRankは次数に比例するので、これは理論どおりです。PageRankの真価は重み付きグラフや有向グラフで出ます。GraphRAGのグラフは「何回共起したか」の重みを持つので、PageRankは「よく語られる文脈からよく参照されるエンティティ」を拾ってくれます。
実務的なまとめ方をすると、コンテキスト選択は次のような重み付けスコアで組むのが素直です。
$$ \text{score}(i) = \lambda_1 \cdot \text{sim}(q, i) + \lambda_2 \cdot C(i) – \lambda_3 \cdot \text{dist}(i_0, i) $$
第1項はクエリとの意味的類似度、第2項は中心性（横断的な問いなら媒介、局所的な問いなら次数やPageRank）、第3項は起点からのホップ距離によるペナルティです。ベクトルRAGが第1項しか持っていなかったのに対し、GraphRAGは第2項と第3項という構造由来の情報を追加で使える、というのが本質的な差分です。
理屈は一通り揃ったので、実際に手を動かして確かめてみましょう。
Pythonで動かす
まずグラフを作り、networkxのLouvain実装でコミュニティ検出を走らせます。
import networkx as nx
# LLM抽出を模した (エンティティ, エンティティ) の関係リスト
edges = [
# 推進テーマ
("LE-9エンジン", "液体水素"), ("LE-9エンジン", "ターボポンプ"),
("LE-9エンジン", "再生冷却"), ("LE-9エンジン", "燃焼室圧力"),
("液体水素", "ターボポンプ"), ("再生冷却", "燃焼室圧力"),
("LE-9エンジン", "比推力"), ("液体水素", "比推力"),
("燃焼室圧力", "比推力"), ("ターボポンプ", "再生冷却"),
# 通信テーマ
("Kaバンド", "フェーズドアレイ"), ("Kaバンド", "リンクバジェット"),
("フェーズドアレイ", "地上局"), ("地上局", "リンクバジェット"),
("リンクバジェット", "光通信端末"), ("光通信端末", "データ中継衛星"),
("データ中継衛星", "Kaバンド"), ("データ中継衛星", "地上局"),
("フェーズドアレイ", "リンクバジェット"),
# 軌道・デブリテーマ
("低軌道", "スペースデブリ"), ("スペースデブリ", "レーダ観測"),
("レーダ観測", "軌道決定"), ("軌道決定", "衝突回避"),
("衝突回避", "スペースデブリ"), ("デオービット装置", "スペースデブリ"),
("デオービット装置", "低軌道"), ("軌道決定", "低軌道"),
("衝突回避", "レーダ観測"),
# 試験・構造テーマ
("振動試験", "CFRP構造"), ("熱真空試験", "MLI"),
("熱真空試験", "ヒートパイプ"), ("MLI", "ヒートパイプ"),
("振動試験", "熱真空試験"), ("CFRP構造", "MLI"),
# テーマをまたぐブリッジ
("H3ロケット", "LE-9エンジン"), ("H3ロケット", "比推力"),
("H3ロケット", "低軌道"), ("H3ロケット", "振動試験"),
("観測衛星", "データ中継衛星"), ("観測衛星", "低軌道"),
("観測衛星", "CFRP構造"), ("観測衛星", "Kaバンド"),
("観測衛星", "熱真空試験"),
]
G = nx.Graph()
G.add_edges_from(edges)
print("ノード数:", G.number_of_nodes(), "辺数:", G.number_of_edges())
part = nx.community.louvain_communities(G, seed=7, resolution=1.0)
print("コミュニティ数:", len(part))
print("モジュラリティ Q:", round(nx.community.modularity(G, part), 4))
for c in sorted(part, key=lambda s: -len(s)):
d = sum(dict(G.degree(c)).values())
print(f" {len(c)}件 (次数和={d}):", sorted(c))
実行すると、ノード数25・辺数43のグラフに対して4コミュニティ、$Q = 0.6233$ が得られます。中身は推進系7件（次数和26）、通信系7件（25）、軌道系6件（20）、試験系5件（15）で、こちらが意図した4テーマと完全に一致しました。次数和はすべて $\sqrt{2m} = \sqrt{86} \approx 9.3$ より大きく、式(5)の解像度限界には引っかかっていません。このように、コミュニティ数を指定していないのに正しい粒度が出てくるのがモジュラリティ最大化の強みです。
次に、Louvainのフェーズ1（局所移動）を式(3)から自前で実装してみます。ブラックボックスの中身を見るのが目的です。
def louvain_phase1(g, resolution=1.0, max_pass=50):
"""式(3) の ΔQ を直接使った貪欲な局所移動。Louvainのフェーズ1に相当。"""
m = g.number_of_edges()
comm = {v: i for i, v in enumerate(g.nodes())} # 最初は全員バラバラ
d_tot = {i: g.degree(v) for v, i in comm.items()} # 各コミュニティの次数和
for _ in range(max_pass):
moved = False
for v in g.nodes():
cv, kv = comm[v], g.degree(v)
d_tot[cv] -= kv # いったん v を抜く
# v から各隣接コミュニティへの接続本数 k_{i,in}
k_in = {}
for u in g[v]:
k_in[comm[u]] = k_in.get(comm[u], 0) + 1
# 式(3): ΔQ = k_in/m - γ * d_tot * k_v / (2 m^2)
def gain(c):
return k_in.get(c, 0) / m - resolution * d_tot.get(c, 0) * kv / (2 * m * m)
best, best_gain = cv, gain(cv)
for c in k_in:
if gain(c) > best_gain + 1e-12:
best, best_gain = c, gain(c)
d_tot[best] = d_tot.get(best, 0) + kv # 移動先に入れ直す
if best != cv:
comm[v], moved = best, True
if not moved:
break
groups = {}
for v, c in comm.items():
groups.setdefault(c, set()).add(v)
return list(groups.values())
p1 = louvain_phase1(G)
print("フェーズ1のみ:", len(p1), "コミュニティ, Q =",
round(nx.community.modularity(G, p1), 4))
for c in sorted(p1, key=lambda s: -len(s)):
print(" ", sorted(c))
結果は6コミュニティ、$Q = 0.5484$ でした。これはnetworkxの louvain_partitions が返す階層のレベル0（図6の左パネル）と完全に一致します。40行足らずの実装で本家の第1段階が再現できるわけで、Louvainのアルゴリズムがいかに単純かがわかります。
そして重要なのは、フェーズ1だけでは $Q = 0.5484$ にとどまり、粗視化を経た最終結果の $0.6233$ に届いていない点です。中身を見ると、軌道テーマが「デブリ・低軌道・デオービット装置」と「レーダ観測・衝突回避・軌道決定」の2つに、試験テーマが「MLI・ヒートパイプ・熱真空試験」と「CFRP構造・振動試験」の2つに割れています。局所移動だけでは「コミュニティ全体をまとめて動かす」ことができないため、この分裂が解消されないのです。フェーズ2の粗視化でこれらがスーパーノードになって初めて、統合という選択肢が生まれます。図6の階層は、まさにこの2段階の産物でした。
コストと現実：GraphRAGは高い
ここまでの話は魅力的ですが、GraphRAGには相応の代償があります。導入判断のために、正直に整理しておきます。
インデックス構築コストの見積り
コーパスが $N$ トークン、チャンクサイズが $c$ トークンだとすると、チャンク数は $N/c$ です。抽出は1チャンクにつき最低1回、gleaningを $g$ 回行うなら $(1+g)$ 回のLLM呼び出しが必要です。さらにエンティティ説明の統合、コミュニティ要約の生成が加わります。
$$ \text{LLM呼び出し回数} \approx \underbrace{\frac{N}{c}(1+g)}_{\text{抽出}} + \underbrace{|V_{\text{multi}}|}_{\text{説明統合}} + \underbrace{\sum_{\ell}|C^{(\ell)}|}_{\text{階層要約}} $$
しかも各呼び出しは入力にチャンク全文、出力に構造化データを含むので、決して安い呼び出しではありません。感覚的には、同じコーパスに対する素朴なベクトルインデックス構築（埋め込みAPIを1回通すだけ）と比べて、金額で1〜2桁、時間で1桁は重くなると考えておくべきです。
これは「1回だけ払えばよい」コストではあります。しかしプロンプトを変えたり、チャンクサイズを調整したり、モデルを差し替えたりするたびに全部やり直しになるので、チューニングのイテレーションが高くつくという形で効いてきます。まず小さなサブセットで抽出品質を確認してから全体に流す、という進め方が事実上必須です。
増分更新の難しさ
新しい文書が1本追加されたら何をやり直せばよいでしょうか。抽出だけなら追加分のチャンクで済みます。グラフへの統合も、名寄せさえできれば局所的です。問題はその先です。
- 新しいノードや辺が加わると、$m$ が変わります。式(2)を見れば明らかなように、$m$ が変わるとすべてのコミュニティの $Q$ への寄与が変わります。原理的には全体のコミュニティ検出をやり直す必要があります。
- 解像度限界の閾値 $\sqrt{2m}$ も動くので、以前は独立していた小コミュニティが合併されるようになる、といった構造変化が起こり得ます。
- コミュニティのメンバーが変われば、その要約も作り直しです。上位コミュニティの要約は下位の要約を材料にしているので、変更は階層を上に伝播します。
- Louvain/Leidenは乱数を使うので、同じグラフでもシードが変わればコミュニティIDが変わります。「コミュニティ3の要約」を安定に参照し続けること自体が自明ではありません。
現実的な運用としては、(a) 追加分のエンティティは即座にグラフへ入れてLocal Searchでは使えるようにし、(b) コミュニティ検出と要約の再構築はバッチで定期実行する、という二段構えになります。リアルタイム性が要求されるユースケースにGraphRAGは向きません。
抽出品質への依存
そして最大のリスクがここです。GraphRAGの回答品質は、抽出されたグラフの品質を上回りません。
- 取りこぼし: 抽出されなかったエンティティは、以後どの検索経路にも現れません。ベクトルRAGなら少なくとも原文が残っているので拾える可能性がありましたが、GraphRAGでは構造から消えます。
- 幻覚された関係: LLMが文書に書かれていない関係を作ってしまうと、それがグラフに残り、コミュニティ検出とコミュニティ要約を通じて増幅されます。誤りが「もっともらしい要約」に化けるので、検出しづらい。
- 名寄せの失敗: 同じ実体が2つのノードに分裂すると、次数が薄まって別々のコミュニティに落ちます。逆に過剰な統合をすると、無関係な話題が1ノードに混ざります。
- 抽出の非決定性: 温度を0にしても、モデルのバージョンが変われば抽出結果は変わります。再現性を担保したければ、抽出結果そのものをバージョン管理する必要があります。
対策としては、抽出プロンプトにドメイン固有の型定義を書く、gleaningを回す、関係の強度スコアで弱い辺を足切りする、といったところです。それでも「抽出が正しいか」を人手で検証する工程は省けません。GraphRAGは、コーパスの構造を理解している人間が一度は目を通す前提の技術だと考えたほうが安全です。
ベクトルRAGとの使い分け
| 観点 | ベクトルRAG | GraphRAG |
|---|---|---|
| インデックス構築 | 埋め込み1回、安価 | LLM抽出＋要約、高価 |
| クエリコスト | LLM 1回 | Local: 1回 / Global: 数十〜数百回 |
| 全体集約の質問 | 苦手（top-$k$ の壁） | 得意（全体を被覆） |
| マルチホップ関係 | 苦手 | 得意（グラフ経路） |
| ピンポイント事実照合 | 得意 | 抽出漏れのリスクあり |
| 更新 | 追加分だけ埋め込めばよい | コミュニティと要約の再構築が要る |
| 情報の忠実性 | 原文をそのまま渡す | 抽出・要約を経るので劣化しうる |
この表からわかるとおり、どちらが優れているという話ではなく、得意な問いの形が違うというのが正しい理解です。実務ではベクトル索引とグラフ索引の両方を持ち、クエリ分類器で振り分けるのが現実解になります。
軽量な代替：全部作らないという選択
GraphRAGのフルパイプラインは重いので、コストを下げる方向の変種がいくつも提案されています。
LightRAG的なアプローチ。LightRAG（Guo et al., 2024）は、エンティティ・関係の抽出まではGraphRAGと同じですが、階層的なコミュニティ要約を作りません。代わりに、エンティティのキーワードとリレーションのキーワードという2階層のインデックスをベクトル検索し、ヒットしたエンティティの近傍をグラフから引く、という設計です。コミュニティ検出とその要約という一番高い工程が丸ごと消えるので、インデックスコストが大幅に下がります。しかも新しい文書の追加は「エンティティと辺を足すだけ」で済むため、増分更新が現実的という大きな利点があります。代償は、Global Searchが持っていた「コーパス全体を確実に被覆する」という保証を失うことです。全体集約型の質問への強さは落ちます。
既存の知識グラフを使う。抽出がコストとリスクの本体なのですから、すでに構造化されたグラフがあるなら、それを使わない手はありません。社内であれば製品マスタ、部品表（BOM）、組織図、課題管理システムのチケット間リンク、Gitのコミット履歴といった資産が既にグラフです。公開データならWikidataやUMLS（医療）のような整備済みのオントロジーがあります。これらを骨格にして、文書から抽出したエンティティを既存ノードに紐づけるだけにすれば、抽出の自由度が下がって幻覚も減り、コストも下がります。スキーマを与えた抽出は、スキーマなしの抽出より圧倒的に安定します。
グラフを作らずに階層要約だけ作る。GraphRAGの効き目のうち、「全体集約型の質問への強さ」の大部分は、実はグラフそのものではなく階層的な要約から来ています。であれば、チャンクの埋め込みを直接クラスタリングして再帰的に要約を積み上げる（RAPTOR的な）方式でも、同じ効果の相当部分が得られます。エンティティ抽出が不要な分、コストは大きく下がります。失うのは、明示的なエンティティ関係が持っていたマルチホップ推論の力です。グラフのクラスタリング自体はスペクトラルクラスタリングでも可能ですが、固有値分解が必要で大規模グラフでは重く、コミュニティ数を事前に決める必要があるため、GraphRAGではモジュラリティ最大化が選ばれています。
段階的な導入という現実解も挙げておきます。いきなり全社文書にGraphRAGを流すのではなく、(1) まずベクトルRAGを立てて、答えられない質問のログを集める、(2) そのうち「全体集約型」「マルチホップ型」がどれくらいの割合かを数える、(3) 割合が有意なら、その質問が集中しているサブコーパスにだけGraphRAGを適用する、という順序です。GraphRAGが効くのは質問の一部であって全部ではないので、コストを払う範囲を絞るのが合理的です。
まとめ
本記事では、GraphRAGについて解説しました。
- 課題の出発点: ベクトルRAGのtop-$k$ 検索は「クエリとの類似度」しか選択基準を持たないため、「全体の主要テーマは何か」という集約型の問いと、「AとBの関係は」というマルチホップ型の問いに構造的に答えられない
- 解法: 文書をエンティティ・関係の知識グラフに変換し、コミュニティ検出で階層分割し、コミュニティ要約を事前生成しておく。クエリ時にはその要約またはグラフ近傍を使う
- 数理の核: モジュラリティ $Q = \frac{1}{2m}\sum_{ij}(A_{ij} – k_ik_j/2m)\delta(c_i,c_j)$ は、次数保存ランダムグラフをヌルモデルとして「偶然を超えた濃さ」を測る。$\Delta Q = k_{i,\text{in}}/m – d_C k_i/2m^2$ という局所的な式のおかげで、Louvain/Leidenは大規模グラフでも高速に動く
- 解像度限界: $d_A d_B < 2m$ なら1本の辺しかない2コミュニティすら合併されてしまう。$\gamma$ はこの閾値を動かすつまみであり、単なる好みの調整ではない
- 階層の効用: 粗視化の副産物として階層が得られ、問いの粒度とトークン予算に応じてレベルを選べる。要約も再帰的に積み上げられる
- Global vs Local: 全体集約にはコミュニティ要約のmap-reduce、エンティティ中心の問いには近傍探索。前者はコストが2桁高い
- 中心性: 次数はその場のハブ、媒介はテーマ間の橋、PageRankは重み付き重要度。横断的な問いでは媒介中心性の高いエンティティを落とすと関係が説明できなくなる
- 現実: インデックス構築が高価、増分更新が難しい、抽出品質にすべてが依存する。ベクトルRAGとの併用と、LightRAG的な軽量版・既存KGの活用を検討する価値がある
GraphRAGを一言でまとめるなら、「検索の質を上げる」技術ではなく、「検索の前に構造を作っておく」技術です。類似度という1次元の物差しでは表現できない情報（誰と誰がつながっているか、全体がいくつの塊でできているか）を、明示的なグラフとして保持する。その分だけ前払いのコストがかかる、という単純な交換になっています。
次のステップとして、以下の記事も参考にしてください。
- RAG（検索拡張生成）の仕組みとPython実装 — GraphRAGの土台となる通常のRAGの構成
- ベクトルデータベースの仕組み — FAISS・HNSWの理論とPython実装 — GraphRAGでもエンティティ検索にベクトル索引を使う
- Re-ranking の理論と実装 — Cross-Encoder と ColBERT で検索精度を引き上げる — Local Searchで集めた候補の並べ替えに使える
- グラフラプラシアンとスペクトラルクラスタリングの理論と導出と実装 — モジュラリティ最大化とは別系統のグラフ分割手法
- node2vec/DeepWalkによるグラフ埋め込みの理論と実装 — 知識グラフのノードをベクトル化して検索に使う方向
- 【徹底解説】NetworkX の利用方法や可視化の方法をわかりやすく — 本記事のコードで使ったライブラリの基礎