{"id":1101987,"date":"2024-11-15T08:52:47","date_gmt":"2024-11-15T16:52:47","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/?p=1101987"},"modified":"2024-11-15T09:43:53","modified_gmt":"2024-11-15T17:43:53","slug":"graphrag-improving-global-search-via-dynamic-community-selection","status":"publish","type":"post","link":"https:\/\/www.microsoft.com\/en-us\/research\/blog\/graphrag-improving-global-search-via-dynamic-community-selection\/","title":{"rendered":"GraphRAG: Improving global search via dynamic community selection"},"content":{"rendered":"\n
\"The<\/figure>\n\n\n\n

Retrieval-augmented generation (RAG) allows AI systems to provide additional information and context to a large language model (LLM) when generating a response to a user query. However, traditional RAG-based methods can struggle to retrieve information that requires high-level knowledge of the entire dataset, especially with abstract and global questions such as the keywordless query: \u201cCatch me up on the last two weeks of updates.\u201d These types of queries are known as \u201cglobal\u201d queries, as they require holistic understanding of the dataset to answer the question. GraphRAG<\/a> aims to tackle these questions in two main steps: indexing and query. The indexing engine first breaks down a collection of text documents into segments which are then clustered into hierarchical communities with entities and relationships connecting each segment up through higher levels of abstraction. We then use an LLM to generate a summary of each community, known as a community report. The indexing engine thus creates a hierarchical knowledge graph of the dataset, with each level in the hierarchy representing a different level of abstraction and summarization of the original material. In the query step, GraphRAG uses this structured knowledge to provide additional context to the LLM to help answer the question. In this blog post, we show a new method for conducting \u201cglobal\u201d queries that efficiently utilizes the knowledge graph representation and optimizes the performance of global search in GraphRAG. <\/p>\n\n\n\n

Static vs. dynamic global search<\/h2>\n\n\n\n

The global search (opens in new tab)<\/span><\/a> algorithm in GraphRAG aims to answer abstract questions that require knowledge of the entire dataset. It generates answers by searching over communities at a predetermined level in the knowledge graph. Then the LLM combines and summarizes all the community reports at this level of abstraction. Finally, the summary is used as additional context for the LLM to generate the response to the user question. This map-reduce process allows the LLM to select relevant text from all the community reports to generate its final answer. This static approach is expensive and inefficient because it includes many lower-level reports that are not informative to the user query. Since it is unlikely that all community reports, especially at a high level, are relevant in answering the query, an approach that first considers the relevancy of the report prior to the resource-intensive map-reduce operation is highly desirable.  <\/p>\n\n\n\n

Here, we introduce dynamic community selection to the global search algorithm, which leverages the knowledge graph structure of the indexed dataset. Starting from the root of the knowledge graph, we use an LLM to rate how relevant a community report is in answering the user question. If the report is deemed irrelevant, we simply remove it and its nodes (or sub-communities) from the search process. On the other hand, if the report is deemed relevant, we then traverse down its child nodes and repeat the operation. Finally, only relevant reports are passed to the map-reduce operation to generate the response to the user. Figure 1 illustrates the dynamic community selection process in action. <\/p>\n\n\n\n

\"An
Figure 1: Dynamic community selection workflow<\/figcaption><\/figure>\n\n\n\n

The dynamic global search approach has two main benefits. First, it prunes irrelevant reports early on, reducing the total number of community reports to be considered in the map-reduce operation. Second, it enables users to search the entire knowledge graph, instead of predefining a static community level, and can lead to more detailed answers. This allows it to collect information at various levels of abstraction. Moreover, the rating operation is a classification problem, which is considerably easier to perform than summarization and text generation, therefore, a less complex model can be used. In our experiments leveraging OpenAI\u2019s models, a GPT-4o-mini rater achieved a very similar retrieval rate as a GPT-4o rater, while operating at a fraction of both cost and time. Overall, we use the smaller and more cost-effective model, GPT-4o-mini, in the rate operation to prune any irrelevant community reports, then we use GPT-4o to perform the map-reduce operation to generate the final response. <\/p>\n\n\n\n

Dynamic community selection on the AP News dataset<\/h2>\n\n\n\n

To demonstrate the cost saving that dynamic global search brings while maintaining a similar response quality, we evaluated the two methods side by side on a dataset from AP News. We tested static and dynamic search on 50 global questions and assessed the final response quality using an LLM evaluator. Moreover, we compared the total token cost of the two methods. To compare the two methods directly, we constrained the maximum search depth on dynamic global search so that both methods used the same underlying information.<\/p>\n\n\n\n

We use an LLM evaluator to select the best response (i.e. win rate) on 3 key metrics: <\/p>\n\n\n\n