Multi-hop reasoning using KG-RAG

[karthiksoman]

Currently, we can do a 2 hop reasoning using KG-RAG. For example, we can pull off a scenario such as 'What are the common genes associated with DiseaseX and DiseaseY'. This is A->B<-C scenario.
I was thinking if we could take this to the next step i.e. to address questions such as 'Give me the paths between DiseaseX and DiseaseY that are within 4 hops distance'. This is a A->B1->B2->C scenario.
I think such multi-hop graph traversal using natural language would be awesome!
Any ideas?

[namin]

This sounds cool. Do you envision the stitching of the hops to be done by the LLM or by the RAG?

[karthiksoman]

@namin That's a great question! My thought is that if we give sufficient contextual information, LLM should be capable to do the stitching.

For e.g., in the current version of KG-RAG, when we give the prompt "Can you find any genes that are associated with both Lyme disease and Alopecia areata?", the system extracts context that gives information about the respective gene-disease associations of the given 2 diseases. When this is fed to LLM, it finds the intersection and returns the response to the prompt.

Hence for the multi-hop reasoning, I think, the challenge is to dynamically execute multi-hop graph traversal to extract context using natural language.

[namin]

If you do 2-hop, then each hop is directly relevant to the query, but for 4-hop, the intermediary hops are not tied to either end. How will you know what to include?

[karthiksoman]

That's a good argument!
To test that, I just did a simple experiment using gpt-35-turbo.
Here is the prompt that I gave to see if the LLM can decipher a 4 hop path from the context:

Using the context given below, answer the question given. Context: A is associated to B1, A is associated to B2, A is associated to B3,B1 is associated to C1, B1 is associated to C2, B2 is associated to C1, B2 is associated to C3, B3 is associated to C3, C1 is associated to D1, C1 is associated to D3, C2 is associated to D2, C3 is associated to D1, D1 is associated to E, D2 is associated to F Question: Given the context, can you find the connection between A and E? If so, give me the path.

Response from gpt-35-turbo:
Yes, based on the given context, we can find the connection between A and E. The path connecting A and E is as follows:

A -> B2 -> C1 -> D1 -> E

You can try this from terminal:
python -m kg_rag.prompt_based_generation.GPT.text_generation gpt-35-turbo

While this might not conclusively demonstrate the ability of LLMs to stitch heterogeneous associations, it does indicate their capability to traverse through the given context.

[namin]

BTW, just to confirm, llama has no trouble finding the path either!

[karthiksoman]

That's terrific!

[namin]

Interesting! In a real query, how would you know to generate B2 -> C1 and C1 -> D1 among the myriads of things you could put in the context? It sounds like you'd need to do the 4-hop query on the backend side already? In which case, why not make it simpler for the LLM by pre-processing it?

[karthiksoman]

Example prompt was just to show LLM's ability to traverse over the context. Now, the challenge is to generate this context.
To fetch the context for the paths from A to E (ie the example Context), one approach would be to iteratively fetch the first nbr associations starting from the initial node (in this case A) until it touches E (which will give the Context mentioned in the example).
This may not be computationally efficient especially if we encounter 'hub' nodes (ie. nodes with high degree) and the context growth could be exponential. So I guess, we may need a graph algorithmic approach here, maybe shortest path or any other algorithmic approaches to optimize the context extraction.
Any thoughts on that?

[namin]

It sounds like the method to find the context will be computationally expensive and will also already find the paths. So why discard the paths? Why not give the paths to the LLMs instead of just the edges?

However, there could be an interesting dynamic at play by letting the LLM do some work. Do you have a use case in mind?

[karthiksoman]

Sure, one use case could be the following:
'What is the mechanistic relationship between the compound phenylalanine and the disease Phenylketonuria?'

This is a multi-hop reasoning example, where the relationship sequence is as follows:

(phenylalanine)<-[Reaction_CONSUMES_Compound]-(Kegg Reaction R01795)<-[EC_CATALYZES_Reaction]-(phenylalanine 4-monooxygenase)<-[Protein_HAS_EC]-(Phenylalanine 4-hydroxylase)<-[Gene_ENCODES_Protein]-(PAH)<-[Disease_ASSOCIATES_Gene]-(phenylketonuria)

As you can see this is a 5-hop reasoning.

[webyrd]

Hi Karthik! For your multi-hop example, are you restricting the predicates and categories in the query? Or are you finding any 5-hop connection between the disease and the compound?

Do you have a Cypher query that expresses this 5 hop?

Thanks!

[scootermorris]

So the Cypher is easy MATCH (c:Compound {name:phenylalanine})-[]-(d:Disease {name: phenulketonuria}). The real problem is the computational cost, particularly with something the size of SPOKE. We could limit the depth of the query (i.e. [..5]) or use a shortest path algorithm, as was already mentioned.

I think there are also some other challenges. In you example above, I think what people are more likely going to put in is: "Why does phenylaline cause phenylketonuria?" or perhaps "How does phenylaline cause phenylketonuria?". So the name-entity recognition is going to be somewhat more challenging, but certainly tractable. There may need to be a dialog loop to resolve ambiguity: "Are you asking about the compound phenylalinine?", etc.

[karthiksoman]

@webyrd Yes, for the example I showed, the path is constrained on the specific predicates. As @scootermorris mentioned, cypher is straightforward here as he showed and I want to resonate what @scootermorris mentioned i.e. the computational complexity that we may encounter as 'n' increases in the n-hop reasoning.

So, I think the options can be:

1. An exhaustive approach: After recognizing entities A and B from the prompt, iteratively do graph traversal from A until it reaches B (preferably constraining the search for a 'max-hop'). This could explore all the paths that connect A and B (within 'max-hop') and give that as context to the LLM and LLM further stitches the paths and generates the text based on that. But, I think this would induce a longer latency to respond to the user prompt.

2. A heuristic approach: After recognizing entities A and B from the prompt, do a path analysis beforehand (shortest path/degree weighted path count/embedding methods) and give that estimated path as the context to the LLM. This may not find all paths that connect A and B, but maybe efficient in terms of latency.

Maybe I might have missed other good options here, please feel free to chime in and include them as well :)

@scootermorris I like the idea of 'dialogue loop'! I think that would help us to resolve the ambiguity of duplicate names for different node types.

[MadhumitaSushil]

Maybe of interest: https://arxiv.org/abs/2308.14321

[karthiksoman]

Thanks @MadhumitaSushil, will check this out.

[karthiksoman]

@MadhumitaSushil The paper that you shared is an interesting one! I liked the idea of an iterative graph traversal. I think, this stems primarily from the nature of the problem addressed in that paper, i.e. to predict diagnosis using the concepts extracted from the notes.
The problem formulation in our case is different though. For e.g. we may address the question, with a template of, "How is A and B related?", i.e. unlike their case, we know our source and target. In such cases, we need to find the optimal paths that connect A and B. This could be a one-hop or multi-hop problem.
Albeit the fundamental problem formulation differs between the mentioned paper and ours, I guess we could still mull over some notions such as ranking paths based on attention scores.
In addition to that, it was really interesting to see how the knowledge path enhanced the diagnosis summarization performance in both T5 and GPT cases. It indeed underscores and complements the proposition that we presented in our paper!
Overall, this was a good resource for conducting a critical analysis to guide the development of our roadmap aimed at achieving the goal of multi-hop reasoning using KG-RAG. Thank you for sharing this paper!
Please don't hesitate to share your thoughts and let's keep this fruitful conversation going. I really appreciate your input!

[webyrd]

https://arxiv.org/abs/2305.14625

…

On Thu, Dec 7, 2023 at 6:12 PM karthik-soman ***@***.***> wrote: Thanks @MadhumitaSushil <https://github.com/MadhumitaSushil>, will check this out. — Reply to this email directly, view it on GitHub <#8 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAI5HBBR2JME4E4KP5DQKNLYIJEPRAVCNFSM6AAAAABAGYTUL2VHI2DSMVQWIX3LMV43SRDJONRXK43TNFXW4Q3PNVWWK3TUHM3TOOJUGU4DQ> . You are receiving this because you were mentioned.Message ID: ***@***.***>

[karthiksoman]

Thanks @webyrd for sharing this!
It is actually interesting to see how interpolation-based retrieval processes could easily get off track. I guess interpolation-based methodology (like kNN-LM) could be pragmatic on relatively smaller LMs like GPT2. But the possibility for an increased entropy in the next-token retrieval distribution for longer text generation is a bottleneck.
But, with larger LMs like Llama or GPT3+, they are shown to have better in-context learning. Our approach is based on capitalizing this in-context learning ability of these larger LMs and this way we don't have to deal with the retrieval next-token distribution and its associated entropy.

[karthiksoman]

Also, one important distinction is that, in kNN-LM, as I understand, the retrieval is based on the similarity between generated text and documents. this could lead to the entropy issue as mentioned.
but in our case, we do similarity check with the prompt, not with the generated text.
it is a nice paper for a comparative analysis. thanks @webyrd for sharing this.