こんにちは、CCCMKホールディングスAIエンジニアの三浦です。
だいぶ寒くなってきました。近所の街路樹は少しずつ紅葉をはじめたようです。
前回MicrosoftのGraphRAG(MS GraphRAG)というKnowledge GraphとLLMを組み合わせたフレームワークをご紹介しました。
前回は主にGraphRAGでどのようにKnowledge Graphを構築しているのかに焦点を当てて調べましたが、今回はどのようにKnowledge Graphから情報を検索するのかに焦点を当てて調べたことをまとめてみたいと思います。
MSのGraphRAGで実装されている3つの検索方法
MS GraphRAGではKnowledge Graphから情報を検索する方法が3つ実装されています。
- Global Search
- Local Search
- DRIFT Search（Dynamic Reasoning and Inference with Flexible Traversal）
Global Searchはドキュメント全体を見る必要があるときに、Local Searchは特定の物事について詳細に調べる必要があるときに、そしてDRIFT SearchはGlobal SearchとLocal Search双方の観点が必要なときにそれぞれ有効です。
Global Search
Global Searchの動作について述べられているドキュメントはこちらです。
Global Searchの処理フローはMS GraphRAGの論文にも紹介されています。
Knowledge Graphの中で関係性が強いEntityの集団を"Hierarchical Leiden Algorithm"というクラスタリング手法で見つけ出しその集団に含まれるEntityやRelationShipの情報から生成したCommunity Reportを利用してGlobal Searchでは情報検索を行います。
Community Reportのテキストを設定された長さのChunkに分割、それらをシャッフルし、塊(Batch)を生成します。その後Batchごとにユーザークエリに対する回答を生成、その結果をLLMに評価させ、一定の評価値に満たないものは除外、それ以外を集約してユーザークエリに対する最終的な回答を生成する、というアプローチです。
Communityを検出する"Hierarchical Leiden Algorithm"は"Hierarchical"とあるように階層的なクラスタリング手法です。Global Searchで使うCommunity Reportをどの階層から選ぶのかは検索処理実行時に指定します。より細分化された階層のCommunity Reportを使うとより細かい情報を捉えた回答を生成できる一方で、処理コストが増加してしまうデメリットがあります。
Local Search
Local Searchの動作についてはこちらで述べられています。
Local Searchでは、まずユーザークエリと関連性の強いEntityを探し出すところからスタートします。MS GraphRAGではKnowledge Graph構築時にEntityの詳細説明情報を生成し、さらにそのテキストに対する埋め込みベクトルを計算し、Vector DBのIndexに格納する処理を行っています。
Vector DBのIndex構築に関する設定は、Workspace内に生成される"settings.yaml"の以下の箇所に記載されています。
vector_store: default_vector_store: type: lancedb db_uri: "output/lancedb" container_name: default
MS GraphRAGではデフォルトでは"LanceDB"というベクトル検索に対応したデータベースが使用されます。
このVector DBのIndexから、ユーザークエリに関連性が強いEntityをその詳細説明情報を元に抽出します。関連性の強いEntityが見つかったら、各Entityに対し以下の情報を参照していきます。
- Text Unit: 対象Entityの抽出元である元のドキュメントのChunk
- Report: 対象Entityが属するCommunity Report
- Relationships: 対象Entityが接続されたRelationship
- Entities: 対象Entityと接続されたEntity
- Covariate: 対象Entityの持つ属性
CovariateはデフォルトではKnowledge Graph構築時には生成されません。生成していない場合はLocal Search実行時、Covariateのパラメータに"None"を設定する必要があります。
Entityに関する各情報はLLMによってユーザークエリとの関連性から優先度付けや除外がされた上で集約され、ユーザークエリに対する最終的な回答が生成されます。
DRIFT Search
DRIFT Searchの動作についてはこちらのドキュメントに記載されています。
DRIFT Searchはユーザークエリと関連性が強いCommunity Reportを用いたGlobal Searchに近いアプローチで生成した大局的な初期回答を元に、多角的な観点でLocal Searchを多段に実行することでより詳細な内容を回答に含めていく手法です。
DRIFT Searchの処理は大きく3つのフェーズに分かれています。
まずフェーズ1ではユーザークエリと関連性の強いK個のCommunity Reportを集め、一時的な回答を生成します。さらにそれを深堀するためのフォローアップ質問を複数生成します。
フェーズ2ではフォローアップ質問に対し、Local Searchを用いて回答とさらなるフォローアップ質問が生成されます。そして生成されたフォローアップ質問に対し、Local Searchを用いて回答を生成、フォローアップ質問を生成し・・・といったステップを繰り返し、より局所的な詳細情報を取得していきます。フォローアップ質問を実行するか否かは都度スコアリングによって決定され、フォローアップ質問が必要と判断されたものだけ次のステップに進んでいくようになっています。
フェーズ3ではフェーズ2において生成された回答がContextとしてLLMに渡され、最終的なユーザークエリに対する回答が生成されます。このようなアプローチで回答を生成することで大域的・局所的な観点のバランスが取れた回答を生成が可能になります。
それぞれの方法を試すには
これら3つの検索方法を試す、最も簡単な方法はCLIのコマンドによるものだと思います。以下のCLIに関するドキュメントを参考にすると、graphrag queryコマンドの--methodオプションに"global", "local", "drift"を指定することでそれぞれの検索方法を実行できるようです。
...Local Searchが動かない...
ドキュメントによると特別な設定は不要に思えるのですが、私の環境(databricks)ではLocal Searchを実行しようとすると次のようなエラーが発生して処理が実行できませんでした。
ValueError: Table 'default-entity-description' was not found
Local Searchでは先ほどまとめたようにユーザークエリに関連するEntityを取得する際にVector DBへの問い合わせを実行します。その際に検索対象のtable(index?)を見つけることが出来ない、といった内容のようです。
Knowledge Graph構築時に、デフォルトの設定ではWorkspaceのoutputディレクトリの中にlancedbというディレクトリが生成され、その中にVector DBのindexが出力されます。その中にはたしかに" default-entity-description.lance"とうディレクトリが生成されているのでindexの構築自体は完了していそうです。
この辺り、もう少し原因を調べていきたいと思います。
まとめ
ということで今回はMicrosoftのGraphRAGに実装されている3つの検索方法についてそれぞれどのような動作をするものなのか調べてまとめてみました。残念ながらGlobal Search以外は実行させることが出来なかったのですが、もし実現できたら大域的・局所的両面の情報を必要に応じてAI Agentに使い分けさせる、といったことが出来て便利だと思います。はやく実際に動かしてみたいです・・・！
