Microsoft GraphRAG でこれまでの RAG にはできなかった質問に回答させるメモ

Microsoft Research が OSS として公開している GraphRAG について色々遊んだときのメモです。

Microsoft GraphRAG についての詳細な解説はアルファシステムズさんの Tech blog が優れています。

データパイプライン

処理の流れ

1. データをチャンク化してテキストユニットに分割する
2. エンティティ抽出
3. 主張（肯定的な事実）抽出
4. リレーション抽出
5. グラフ拡張
6. コミュニティ要約、グラフ埋め込み
   →インプットデータ: 階層別エンティティ、リレーションシップ
7. テキストユニット---[エンティティ、リレーション、クレーム] 接続
8. テキストユニット---ドキュメント接続

デフォルトでは CLI による全自動処理で、各種成果物がファイルで出力されます。デフォルトでは重厚長大なので、それぞれを分解して理解していきます。

特にグローバル検索に用いるためのグラフの作成、クラスタリング、コミュニティ要約について注目していきたいと思います。

使用するデータ

AI Challenge Day のために作成した仮想的な世界遺産（日本の文化遺産）の PDF を2本用意しました。というのも、GPT-4o の登場によってマイナーな戦国武将に対する質問も正確に回答できるようになったため、純粋に RAG の効果を見るためにトレーニングデータには存在しないデータを LLM の助けを借りて生成しています。

• 近藤寺：京都にある仮想的な寺院
• 花ケ咲神社：京都にある仮想的な神社

これらの PDF を Azure AI Document Intelligence を用いて Markdown 形式のテキストに変換しています。

面白ポイント：階層 Leiden クラスタリング

Microsoft GraphRAG では階層 Leiden クラスタリングを使用してクラスターごとの概要文の粒度を変えています。

階層 Leiden クラスタリングは、通常の Leiden クラスタリングをさらに「段階的」に行うものです。最初に大まかなグループ分けをしてから、特に大きなグループをさらに細かく分割していく手法です。Microsoft Research は 2021 年、Microsoft 社内のコミュニケーションのパターンに基づいてワークグループをクラスタリングする際にこれを使用しました。ベースとなっている Leiden クラスタリングが、大規模なデータに対して高速で動作する、かつ、以前の手法と比較して性能が向上したことから採用しました。

1. 最初に通常の Leiden クラスタリングを使って全体を大まかにグループ分けします（これが「レベル0」）。ここでは、同じグループに属するノード同士が多くのエッジで結ばれている、異なるグループのノード間のエッジはできるだけ少ない状態を目指します。

   

2. ただし、ここで分けられたグループが大きすぎる場合、たとえば「20人以上のグループがある」というような時、その大きなグループだけをさらに分割します。これを max_cluster_size パラメータで制御します。

3. これを繰り返して、最終的にすべてのグループが指定された大きさ以下になるまで、またはこれ以上分割できなくなるまで進めます。

   
   （有名な空手クラブグラフの例, max_cluster_size=5）

大規模なネットワークにおいて、大きなグループをさらに細かく分ける必要がある場合に便利です。

コミュニティのサイズ調整

Microsoft GraphRAG では、max_cluster_size を使用してクラスター＝コミュニティに含まれるノードの最大値を指定することができます。max_cluster_size を小さめに指定して分割されたコミュニティごとに概要文を作成していくとなると、元のコミュニティの概要文よりも粒度が細かくなっていくと想定できます。

import networkx as nx
from graphrag.index.verbs.graph.clustering.cluster_graph import run_layout

# クラスタリングの設定
strategy = {
    "type": "leiden",
    "max_cluster_size": 10,  # クラスタの最大サイズ
    "use_lcc": True,         # 最大全結合成分のみを使用
    "seed": 0xDEADBEEF,      # ランダムシード
    "levels": None,          # すべてのレベルを使用
    "verbose": True          # ログを表示
}

# グラフをロード　snapshots:　graphml: true in settings.yaml 
G = nx.read_graphml("./merged_graph.graphml")

# クラスタリングを実行
communities = run_layout(strategy, G)

# 結果を表示
print("Detected communities:")
for community_level, community_id, nodes in communities:
    print(f"Level: {community_level}, Community: {community_id}, Nodes: {nodes}")

再現性を保持しつつ graphrag の動作をチェックするためにソース直叩きしてます。merged_graph.graphml は settings.yaml の snapshots:　graphml: を true とすることで生成されます。

通常の Leiden クラスタリング

レベル 0 が通常の Leiden クラスタリングです。コミュニティは 6 個に分割されました。以下の図ではエンティティの title をノードに、円の大きさを degree に、エッジの太さを weight、色をコミュニティに割り当てています。この時点でも非常に優秀なクラスタリングかと思います。

色分けした各コミュニティごとに、完全なレポート（full_content）および短い要約文（summary）が生成されます。

max_cluster_size=20 のときのコミュニティ

階層レベル 0 と 1 が生成されました。コミュニティのサイズが 20 ノードを超えると、そのコミュニティは再帰的に分割されます。

	レベル 0	レベル 1	レベル 2
近藤寺コミュニティ	21 ノード	19:2 ノード	-
花ケ咲神社コミュニティ	22 ノード	17:2:3 ノード	-

max_cluster_size=10 のときのコミュニティ

階層レベル 0, 1, 2 が生成されました。コミュニティのサイズが 10 ノードを超えると、そのコミュニティは再帰的に分割されます。

(レベル 0 は省略）

	レベル 0	レベル 1	レベル 2
近藤寺コミュニティ	21 ノード	19:2 ノード	15:4ノード
花ケ咲神社コミュニティ	22 ノード	17:2:3 ノード	-

Leiden アルゴリズムは、コミュニティ内のモジュラリティが最大化されるまで実行されますが、ある時点でこれ以上の改善が見込めないと判断されるとクラスタリングが終了します。つまり、クラスタサイズが上限に達していなくても、モジュラリティの改善が行われない場合、次の階層に進まない可能性があります。

検索クエリ

グローバル検索

LLM が生成したナレッジ グラフの構造から、データセット全体の構造を把握したいときに向いています。膨大なナレッジベースやドメインデータセットを、事前に要約されたセマンティック クラスターに整理しておくことができます。グローバル検索は LLM を使用してこれらのクラスターから、ユーザー クエリの応答に沿うようにテーマを要約します。

グローバル検索というか、グローバル要約…？

処理の流れ

質問

result = await search_engine.asearch(
    "このデータセットの主要なテーマとは？"
)

この質問は一般的な検索エンジンではヒットが難しい

1. Map

mapステップでは、コミュニティレポートが事前に定義されたサイズのテキストチャンクに分割されます。次に、各テキストチャンクを使用して、ポイントのリストを含む中間応答が生成されます。各ポイントには、ポイントの重要性を示す数値評価が付随します。

context_data = コミュニティレポート

プロンプト

MAP_SYSTEM_PROMPT が使用されます。

---役割---
あなたは、提供された表のデータに関する質問に答える、親切なアシスタントです。

---目標---
ユーザーの質問に答えるキーポイントのリストで構成される応答を生成し、入力データ表の関連情報をすべて要約します。

応答を生成する際には、以下のデータ表に提供されたデータを主なコンテキストとして使用してください。
答えがわからない場合、または入力データ表に答えを導くのに十分な情報が含まれていない場合は、その旨を伝えてください。でっち上げることはしないでください。

回答の各要点には、以下の要素を含める必要があります。
- 説明:要点の包括的な説明。
- 重要度スコア:ユーザーの質問に回答する上で、その要点がどの程度重要であるかを表す 0 ~ 100 の整数値。「わからない」という回答には、スコアとして 0 を指定します。

回答は、以下の形式で JSON 形式にする必要があります。
{{
    "points": [
        {{ "description": "ポイント1の説明 [データ: レポート (レポートID)]", "score": score_value }},
        {{ "description": "ポイント2の説明 [データ: レポート (レポートID)]", "score": score_value }}
    ]
}}

---Data tables---

{context_data}

（省略）

中間回答

[{'answer': '近藤寺の歴史的および文化的価値: 近藤寺は室町時代に創建され、織田信長との歴史的な関わりを持つ寺院であり、百八面千手観世音菩薩や天平時代の経典、江戸時代の襖絵などの文化財を所蔵している [Data: Reports (3, 4)]',
  'score': 95},
 {'answer': '花ケ咲神社の歴史的および文化的価値: 花ケ咲神社は平安初期に創建され、桜花女神が祀られている。ユネスコの世界遺産「古都京都の文化財」の一部として登録されており、桜の名所としても知られている [Data: Reports (5)]',
  'score': 90},
 {'answer': '近藤寺の建築様式とその美しさ: 近藤寺の本堂は室町時代の伝統的な仏教建築様式で建てられており、木造で瓦屋根を持つ壮麗な建物である [Data: Reports (3, 4)]',
  'score': 85},
 {'answer': '花ケ咲神社の桜花祭とその文化的影響: 花ケ咲神社で行われる桜花祭は、地域の社会的な行事として重要な位置を占め、多くの人々が参加する [Data: Reports (5)]',
  'score': 80},
 {'answer': '近藤寺の文化的エンティティ: 近藤寺には舞供楼の庭や阿須杯庵といった重要な文化的エンティティがあり、訪問者に静かな癒しの空間と文化交流の場を提供している [Data: Reports (0)]',
  'score': 75}]

2. Reduce

reduce ステップでは、中間応答からフィルタリングされた最も重要なポイントの一覧が集約され、最終応答を生成するためのコンテキストとして使用されます。

プロンプト

REDUCE_SYSTEM_PROMPT が使用されます。

---役割---

あなたは、複数のアナリストの視点を取り入れながら、データセットに関する質問に答える親切なアシスタントです。


---目標---

ユーザーの質問に回答する、指定の長さと形式の回答を作成し、データセットの異なる部分に焦点を当てた複数のアナリストからのすべてのレポートを要約します。

以下のアナリストのレポートは、**重要度の降順**でランク付けされています。

回答がわからない場合、または提供されたレポートに回答に必要な情報が十分に記載されていない場合は、その旨を述べる。でっちあげてはならない。

最終的な回答では、アナリストのレポートからすべての無関係な情報を削除し、その情報を統合して、回答の長さと形式に適したすべての重要なポイントと影響についての説明を含む包括的な回答を作成する。

回答の長さと形式に合わせて、セクションと解説を追加する。回答のスタイルはマークダウン形式とする。

回答は、「shall」、「may」、「will」などの助動詞の本来の意味と用法を維持するものとする。

回答には、アナリストのレポートに以前含まれていたすべてのデータ参照を維持するものとするが、分析プロセスにおける複数のアナリストの役割については言及しないものとする。

1つの参照に5件以上のレコードIDを記載しないこと。代わりに、最も関連性の高い上位5件のレコードIDを記載し、「+more」を追加して、さらにレコードIDがあることを示すこと。

---Analyst Reports---

{report_data}

（省略）

最終回答

### 主要なテーマ

このデータセットの主要なテーマは、**近藤寺**と**花ケ咲神社**という二つの歴史的および文化的に重要な場所に関する情報です。以下に、それぞれの場所について詳しく説明します。

#### 近藤寺の歴史的および文化的価値

近藤寺は室町時代に創建され、織田信長との歴史的な関わりを持つ寺院です。この寺院は、百八面千手観世音菩薩や天平時代の経典、江戸時代の襖絵などの貴重な文化財を所蔵しています [Data: Reports (3, 4)]。また、近藤寺の本堂は室町時代の伝統的な仏教建築様式で建てられており、木造で瓦屋根を持つ壮麗な建物です [Data: Reports (3, 4)]。

#### 花ケ咲神社の歴史的および文化的価値

花ケ咲神社は平安初期に創建され、桜花女神が祀られています。この神社はユネスコの世界遺産「古都京都の文化財」の一部として登録されており、桜の名所としても知られています [Data: Reports (5)]。さらに、花ケ咲神社で行われる桜花祭は、地域の社会的な行事として重要な位置を占め、多くの人々が参加します [Data: Reports (5)]。

#### 近藤寺の文化的エンティティ

近藤寺には舞供楼の庭や阿須杯庵といった重要な文化的エンティティがあり、訪問者に静かな癒しの空間と文化交流の場を提供しています [Data: Reports (0)]。

### まとめ

このデータセットは、近藤寺と花ケ咲神社という二つの歴史的および文化的に重要な場所に焦点を当てています。これらの場所は、それぞれの歴史的背景や文化財、建築様式、そして地域社会における役割を通じて、訪問者に深い文化的体験を提供しています。

COMMUNITY_LEVEL の指定

COMMUNITY_LEVEL は Leiden コミュニティ階層におけるコミュニティレベルです。このレベルからコミュニティレポートを読み込みます。より高い値は、より細かいコミュニティからのレポートを使用することを意味します(計算コストが高くなるという代償を伴います)。

1. COMMUNITY_LEVEL=0

最上位の階層で、もっとも粒度が荒い。全体を俯瞰した回答が欲しい場合に良い。

Q:応仁の乱で焼失を免れた建造物ってなに？

A:

###応仁の乱で焼失を免れた建造物
応仁の乱は1467年から1477年にかけて日本で発生した内乱で、多くの建造物が焼失しました。しかし、その中で焼失を免れた建造物も存在します。
###花ケ咲神社
花ケ咲神社は、応仁の乱の焼失を免れた建造物として有名です [Data: Reports (5)]。この神社は、戦乱の中でもその姿を保ち続け、現在でもその歴史的価値を伝えています。
応仁の乱の影響を受けなかった建造物は非常に少なく、その中でも花ケ咲神社は特に注目されています。戦乱の激しさを物語ると同時に、歴史的な建造物の保存の重要性を示しています。
###結論
応仁の乱で焼失を免れた建造物として、花ケ咲神社が挙げられます。この神社は、戦乱の中でもその姿を保ち続け、現在でもその歴史的価値を伝えています。

GlobalSearch に渡されるコミュニティレポートは 5 のみです。意図としては、もう少し細かい建造物名まで知りたかったのですが、5 番にはそこまで細かい建造物名は含まれていませんので上記のような回答となります。

2. COMMUNITY_LEVEL=1

コンテキストとして渡されるコミュニティレポートの粒度がより細かくなり、細かい内容の回答ができるようになる。

Q:応仁の乱で焼失を免れた建造物ってなに？

A:

###応仁の乱で焼失を免れた建造物
応仁の乱は15世紀後半に日本で発生した大規模な内乱で、多くの建造物が焼失しました。しかし、その中でもいくつかの重要な建造物は奇跡的に焼失を免れました。
###花ケ咲神社
花ケ咲神社は、応仁の乱の焼失を免れた歴史的な建造物の一つです。この神社の境内には、国宝に指定されている本殿や美しい桜参道が存在します [Data: Reports (10)]。これにより、花ケ咲神社は歴史的および文化的な価値が非常に高い場所として知られています。
###近藤寺
花ケ咲神社と共に、近藤寺も応仁の乱の焼失を免れた建造物として有名です [Data: Reports (8)]。この寺院もまた、歴史的な価値が高く、多くの人々に尊敬されています。
###まとめ
応仁の乱で焼失を免れた建造物として、花ケ咲神社と近藤寺が挙げられます。これらの建造物は、歴史的な価値が高く、現在でも多くの人々に訪れられています。特に花ケ咲神社は国宝に指定されている本殿を有しており、その文化的な重要性は非常に高いです。

GlobalSearch に渡されるコミュニティレポートは 8,9,10 となり、より粒度が細かくなりました。そして欲しかった、「国宝に指定されている本殿や美しい桜参道」という文言が得られました。

ニーズによって、どのレベルまでの粒度をコンテキストに含めたいかを調整することができます。

各レベルでエンティティが重複していた場合の処理

1. COMMUNITY_LEVEL 以下のレベルに該当する行のみを残す
2. entity_df は title 列ごとにグループ化され、各 title に対して最大の community 値が取得される。この処理により、community の値が最大のものだけが残り、同じ title に対して複数の community があった場合でも1つにまとめることができる。
3. 重複した community の値が除外され、filtered_community_df としてユニークな community のリストが得られる

エンティティの重複を見て、タイトルが重複していたら COMMUNITY_LEVEL 以下の最大のコミュニティレベルを抽出し、そのコミュニティレベルのレポートを使用する。

コミュニティ階層が深い→クラスタ分割の粒度が細かい→要約の粒度も細かい→細かい質問にも答えられる可能性がある

use_community_summary の指定

use_community_summary=False は、コミュニティの完全なレポート（full_content）を使用することを意味します。True は、コミュニティの短い要約（summary）を使用することを意味します。

データ準備

データセットにわざと「花ケ咲神社は近藤寺と共に応仁の乱の焼失を免れた建造物として有名である。」と入れておいたので、ちゃんと 花ケ咲神社ーー応仁の乱ーー近藤寺 のリレーションができています。

しかし、COMMUNITY_LEVEL=0 のときは、「応仁の乱で焼失を免れた建造物ってなに？」という質問に対して、花ケ咲神社のみしか回答しませんでした。これはレベル 0 のコミュニティレポートの概要（full_content/summary）にこの事実が入っていなかったためです。

あと面白いのが、この実装では Graph DB の中を検索してる訳ではないという点ですね。検索に必要なのは、create_final_community_reports.parquet、create_final_nodes.parquet、create_final_entities.parquet のみとなります。

ローカル検索

ローカル検索は、LLM が抽出したナレッジグラフの関連データと生の文書のテキストチャンクを組み合わせて回答を生成します。この検索手法は、文書に記載された特定のエンティティの理解を必要とする質問に適しています。

入力データ

• コミュニティレポート = "create_final_community_reports"
• エンティティ = "create_final_nodes"
• エンティティの Embeddings = "create_final_entities"
• リレーションシップ = "create_final_relationships"
• 主張 = "create_final_covariates"
• テキストユニット = "create_final_text_units"

デフォルトでは内部で lancedb にエンティティの Embeddings が格納されて、ベクトル類似検索が実行されます。VectorStoreType には azure_ai_search にも対応しています😎

処理の流れ

質問

result = await search_engine.asearch("花ケ咲神社の住所は？")

1. コンテキストの構築（build_context）

ローカル検索プロンプト用のデータコンテキストを構築します。summary_prop で設定された既定の比率を使用して、コミュニティレポートとエンティティ/リレーションシップ/主張テーブル、テキストユニットを組み合わせてコンテキストを構築します。

1.1. クエリに関連するエンティティを抽出（map_query_to_entities）

ユーザーのクエリをエンティティにマッピングする。会話履歴がある場合は、現在のクエリに以前のユーザーの質問を添付する。

クエリとエンティティの記述の Embeddings のセマンティック類似性を利用して、与えられたクエリに一致するエンティティを抽出します。

1.2. 抽出したエンティティに関連する各種テーブルのレコードを抽出

例えばクエリ「花ケ咲神社の住所は？」に対して、以下のようなエンティティがベクトル検索できます。これにより community_ids が特定できるので、コンテキストに含めたいコミュニティレポートの ID は 5 と 1 にすればよいことが分かります。

title='花見小路', type='GEO', description='花ケ咲神社が所在する通り', community_ids=['5'], description_embedding=[...]
title='京都府', type='GEO', description='花ケ咲神社が所在する都道府県', community_ids=['5'], description_embedding=[...]
title='京都市東山区', type='GEO', description='花ケ咲神社が所在する地域', community_ids=['5'], description_embedding=[...]
title='花ケ咲神社', type='ORGANIZATION', description='花ケ咲神社は、京都市東山区花見小路に位置する神社, community_ids=['1'], description_embedding=[...]

2. 構築されたコンテキスト（context_data）

エンティティに関連のあるコミュニティレポート、リレーションシップ、主張テーブル、テキストユニットが統合されます。

id|title|content
5|花ケ咲神社と京都の文化財|"# 花ケ咲神社と京都の文化財
花ケ咲神社は京都市東山区に位置し、桜を守護する神として古くから崇敬されてきた神社です。平安初期に創建され、桜花女神が祀られています。ユネスコの世界遺産「古都京都の文化財」の一部として登録されており、その歴史的および文化的価値が高く評価されています。応仁の乱の焼失を免れた建造物としても有名で、近藤寺と共にその歴史的価値が認められています。桜の名所としても知られ、特に桜の季節には多くの観光客が訪れます。

1|京都市営バスと花ケ咲神社前|"# 京都市営バスと花ケ咲神社前
京都市営バスは京都市内を運行する主要なバスサービスであり、花ケ咲神社前バス停を含む複数のバス路線を提供しています。花ケ咲神社前バス停は1·23·45号系統の路線バスが停車する重要なバス停であり、地域の交通アクセスにおいて重要な役割を果たしています。
...

-----Entities-----
id|entity|description
63|花見小路|花ケ咲神社が所在する通り
62|京都府|花ケ咲神社が所在する都道府県
46|京都市東山区|花ケ咲神社が所在する地域
9|花ケ咲神社|花ケ咲神社は、京都市東山区花見小路に位置する神社で、古くから桜を守護する神として崇敬されてきた。平安初期、桓武天皇の時代に創建され、桜花女神が祀られている。通称「桜の宮」とも呼ばれ、京都の春の風物詩として多くの人々に親しまれている。花ケ咲神社は式内社(名神大社)、山城国一宮の一社であり、旧社格は官幣中社で、現在は神社木庁の別表神社である。また、ユネスコの世界遺産「古都京都の文化財」の1つとして登録されている。
...

-----Relationships-----
id|source|target|description|rank|links
27|京都市|花ケ咲神社|花ケ咲神社は京都市に所在している。|25|1
46|花ケ咲神社|桜参道|桜参道は花ケ咲神社の境内にある参道|25|1
51|花ケ咲神社|京都市営バス|京都市営バスは花ケ咲神社前バス停に停車する|25|2
...

-----claims-----
id|entity|object_id|status|start_date|end_date|description
3|京都市東山区|NONE|TRUE|NONE|NONE|近藤寺は、京都市東山区にある。
94|花ケ咲神社|本殿|TRUE|NONE|NONE|花ケ咲神社の本殿は794年に建造され、国宝に指定されています。
95|花ケ咲神社|京都府京都市東山区花見小路339|TRUE|NONE|NONE|花ケ咲神社の所在地は京都府京都市東山区花見小路339です。
...

-----Sources-----
id|text
38|/wiki/花 ケ咲神社\" -->\n<!-- PageNumber=\"2/3\" -->\n
...

プロンプト

LOCAL_SEARCH_SYSTEM_PROMPT が使用されます。

---役割---

あなたは、提供された表のデータに関する質問に答える、親切なアシスタントです。


---目標---

ユーザーの質問に答え、入力データ表のすべての情報を回答の長さと形式に適した形で要約し、関連する一般的な知識を盛り込んだ、目標の長さと形式の回答を作成します。

答えがわからない場合は、そのように伝えてください。でっちあげてはいけません。

データで裏付けられた事項については、以下のようにデータ参照を記載してください。

「これは複数のデータ参照によって裏付けられた例文です。[データ: <データセット名> (レコードID); <データセット名> (レコードID)]」

1つの参照に5つ以上のレコードIDを記載しないでください。代わりに、最も関連性の高いレコードIDの上位5つを記載し、さらにレコードIDがあることを示すために「+more」を追加してください。

---Data tables---

{context_data}

（省略）

最終回答

# 花ケ咲神社の住所

花ケ咲神社の住所は以下の通りです：

**京都府京都市東山区花見小路339** [Data: Claims (95)].

この神社は京都市東山区に位置し、桜を守護する神として古くから崇敬されてきました。平安初期に創建され、桜花女神が祀られています [Data: Entities (9); Claims (83, 89)].

回答の出典には、[Data: Claims (95)] のように主張 ID: 95 が示されているため、出典の中身を確認します。

entities = result.context_data["claims"]
entities[entities["id"]=="95"]

かなーり大量のデータが投入されましたが、ローカル検索は軽量化などカスタマイズしがいがありますね。

また、非構造化データをメインで扱う場合、Azure AI Search、Azure AI Document Intelligence データ処理パイプラインとの統合が面白そう🤤

Azure-Samples/graphrag-accelerator ではすでに以下のようなアーキテクチャでの実装があります。

アクセラレーター構築手順

以下の記事にまとまっています。

TODO: マルチ LLM

今回は全行程 GPT-4o を使っちゃいましたが、タスクごとにより高精度、低価格、高速な LLM を取捨選択して組み合わせた構成を取りたいですね。Azure AI Studio モデルカタログ から選びましょう！

TODO: UMAP 2D Visualization

umap: enabled: true にすると出力されるノードごとの embeddings を 2D に UMAP 次元削減した座標。これの使い道について。

GitHub

TBD

参考