How are communities grouped?

[natoverse]

Copying from #841

@FatemaD1577 asks:

I am trying to understand implementation of graph rag. I have gone through the documentation available and also through the git repo to understand the global query part. My understanding of the implementation is as follows:

1. We first create a graph based on the entities and relationships extracted.
2. Communities are then created by grouping closely related entities
3. At the next level community reports are created.
4. Whenever user query comes we shuffle the community reports randomly and group them
5. An intermediate response is generated for each group and a score is assigned to these groups based on the relevance of the answer to the user query
6. Responses with 0 score are filtered out and the remaining are passed on to the LLM for final response generation

Below are some of the doubts still not cleared:

1. Are community reports created at different levels to incrementally cover larger amount of information?
2. On what basis are the communities reports grouped? Is there any parameter to control number of community reports that will be included in one group?
3. Only responses with 0 score are filtered out or is there a threshold below which the responses will not be considered for final response generation?
4. On what basis are we scoring the intermediate response in relevance to user query? Is it using similarity search or any other method to determine the score?

Having an answer to these doubts will help me have more clarity on the process of the global querying part.

Thank you in advance.

[natoverse]

1. The community structure is first created from hierarchical Leiden communities. As the tree depth increases, communities are smaller and more closely connected. This gives us flexibility for how we fill the context window as we roll them up for summaries (for example, root level communities are likely too large to fit in a single context window, so if we start with the leaves we can recursively summarize everything).
2. We use the hierarchical Leiden algorithm as implemented in graspologic, which operates on the largest connected component (LCC). We do not expose any tuning parameters. To group communities for global search summarization, as you note we randomly shuffle them during the map stage. We fill the context window until we meet a defined max token limit (max_tokens in the global search context_builder_params).
3. Responses with 0 are filtered out. We will also stop including communities once the context window is full.
4. We ask the LLM to provide a relevance score for each point in the intermediate response so we have flexibility in which points to include. It is not using similarity/vector search.

[FatemaD1577]

Thank you for the response. This seems to be helpful to understand the process in depth. Will crosscheck once with reference to these points and revert back in case of more clarification if required.