 Hello community! A very fast video on a beautiful new mechanism to combine the knowledge of LLMs with the knowledge, the structured knowledge in Knowledge Graph. And this new methodology is called GIF. Now, you know LLMs like OpenEI01 are nothing short and transformative, but today we're not just gonna do a simple knowledge retrieval from the knowledge graph. No, we will have new innovative ways how we combine here the structured knowledge and the intelligent reasoning together. Now, both methodology I'm gonna show you, maybe you know Sync On Graph, T-O-G, we have it now for months, and a brand new GIF methodology by UC Berkeley. Remarkable advancement here in the integration of LLMs and Knowledge Graph. So, let's start and let's explain here the simple one, the old one that we already know, Think on Graph. Responsible reasoning of LLMs on Knowledge Graph. Reference work we have here. Idea Research, University of Southern California, Xiamen University, Hong Kong University, Microsoft. Beautiful. Now what they do? Instead of just fetching here some simple facts and data from a knowledge graph, the LLM in this particular case could actually sink its way through the knowledge graph, exploring here different routes to take, which is beautiful, and it works like a detective gathering the clues. This is exactly what Sync On Graph does here. How does it work here? Well, it couples the LLM with a knowledge graph using here a simple beam search algorithm. So this helps you the LLM to explore multiple possible reasoning paths at once and then choosing the best one. If you want a detailed explanation of beam search, I did this here in my video where I showed you Stanford and OpenAI code and intelligence field because there they used a similar methodology. So this means the LLM doesn't just retrieve facts from the knowledge graph, it makes a dynamic decision doing so. I will show you in a minute a beautiful example and the sync on graph supports also multi-hop reasoning which is beautiful because this is exactly what we need for a more complex task. So simple example, we have a question. What is the majority political party now in the country where Canberra is located? Now, if we have only an LLM and even if you say, hey, chain of thought and whatever, let's think step by step, you know, the model will fail. If we then have here an LLM plus a knowledge graph, and we have here a Sparkle query like we do normally for our RDFs, you see here, this is the response that we get. So we retrieve here. Canberra is located in Australia. Majority party in Australia is however not found here in Sparkle. So we do not have the link that Australia has this political party called whatever. So the prompt now responds here, sorry based on my query result from the knowledge base, I cannot answer your question. Because there was no direct link in the knowledge graph available and now this beautiful new thing is you're looking for triplets related to canberra so on the graph you go here canberra is the capital of and whatever you build a sub graph if you want. And then you kind of think. So you see the most relevant one is Canberra, capital of Australia, looking for dribbles related now to Australia. And on the graph, I look here for a subgraph with a high probability. And I see here in Australia, then for example, the prime minister. Then I do another thinking here. The most relevant one is Australia Prime Minister and this is Anthony. Congratulations. So you see I go step by step thinking and building here whatever I need. And then here the system is able to think hey I know that Anthony is from the Labour Party. This is enough information collected to answer here this particular question. And finally, with Think of Graph, Think on Graph, we succeed. Isn't this beautiful? If you would like to see this in a slightly different way here, we have the same question, of course, and then we have different search depths. we have here again Canberra continent territory capital of part of whatever is our subgraph we have here then the second if object if you want Australia all the subgraph and then we have Anthony again with whatever Anthony is connected with in the knowledge graph and then having here this mighty powerful subgraph, we start to prune it. We look at the most important information, particular in order to answer here the user query. So you see, you prune the graph. Now you look only at the most important probability links, for example. If you have not enough information no problem you look now from canberra to australia you see here the network of australia you prune here and give me a probability and here the pacific query not enough information you go on with anthony and exactly like i just showed you this is just another visualization in the official publication if you would like to have this in a little bit mathematically introduced way this here is a simple introduction beam search for multi-hop reasoning path pruning and traceability and the code of course since it is now month in the making here we have a beautiful github repo this is here the link for you and you see you're just a python main free base or if you want you can go with main wiki base whatever you have you define here your query and your llms and whatever you have and it is simple the code is now after month quite stable to use for your example have fun with this but now knowing this rather month-old model let's look at a brand new model GIF and GIF stands here for a graph inspired veracity extrapolation so the truth let's have a look. While the think-on graph excels in Scenario, where a well-structured knowledge graph exists, give now tackles here a different but equally important challenge. How do we reason here in this dual system way when the knowledge graph is sparse or incomplete. I indicated this here that we have here in yellow here a partial knowledge graph, incomplete, sparse information. How can we use for example here the parametric knowledge of the LLM to build here a knowledge graph that will enable us to answer the human user query and the answer is gif we have here a new publication october 11 2024 university of pennsylvania university of california university of california berkeley uc berkeley beautiful let's have a now a more detailed look here exactly at this one so gif starts here by breaking a query into key concepts. So if the question is, is melatonin effective for insomnia, the model identifies, of course, melatonin and insomnia as key entities. And then in the internal reasoning, GIF now builds group of related concepts. And I will show you an example in a minute. So not just using the knowledge graph, but also leveraging here the parametric internal knowledge of the LLMs. So for melatonin, it might put in all the related ideas like sleep, hormones, supplements, and whatever there is in your LLM. But GIF doesn't just look for known facts. GIF can extrapolate potential relationship, what we've more called here as a hypothetical link, that could exist based on the patterns in the data. But careful, this is not a crazy hypothetical link. This is a link that exists here, but with a lower probability density in our distribution. So hypothetically means more or less not as dominant imprinted here in a knowledge graph but maybe it exists or maybe there's an indirect link and I will show you an example in a minute. And the beauty is and we know that we can improve the reasoning capacity of our systems if we generate counterfactual reasoning examples. So the system doesn't know only 100% yes, yes, yes, yes answers, but it also knows, hey, no, this is the wrong answer. This is a false augmentation. This is the wrong path to argue. So if we have the positive augmentations and the negative augmentations together, we know that our reasoning experience improves significantly. So this approach now of a guided extrapolation, and I will show you this in a minute, allows GIF now to tackle here extreme complex multi-hop reasoning tasks, even when the underlying knowledge graph is incomplete. And you might remember just some days ago, I showed you here that Harvard presents a new knowledge graph agent for medical AI systems. Check out this video. You will find a lot of similar ideas, a lot of implementations that are quite following some similar ideas. So you see it all comes down, it all converges now to a new solution, how to combine NLMs with knowledge graphs. Yeah, here you see Berkeley states here the problem here in the publication. So we have now a new question. Traumatic aortic injury, my goodness, does the anatomy of the aortic arch influence an aortic trauma severity? I have no idea, but just go here with the official example, so chain of thought. And we get here, chain of thought, lacks of internal knowledge. Prompt, let's think step by step, yeah, beautiful, but gives us the wrong answer. If we used here reg, a text-based reg with semantic similarity, you know, the cosine similarity here in the vector store, in the mathematical vector spaces here, they are beautifully semantically similar. The traumatic aortic injury and the aortic arch and the aortic trauma. Beautiful semantic correlated but absolute irrelevant information. So therefore we fail with RAG. So if we have now our sync-on- graph methodology, what do we do? Fail to retrieve here on a sparse knowledge graph. It also gives us here the not correct answer because our knowledge graph is not complete. And it's not complete to an extent that think-on graph simply fails because they are missing links the system is not able to build in a multi hop causal reasoning chain but wait we have now the new idea we have now the new methodology and you're not gonna believe it they give us here exactly this answer what a coincidence no so let me make this one here. So we have here terms. In our questions, we have terms like aortic injury. So we take this aortic injury. And then we have what goes with this here in our knowledge. Injury, poisoning, whatever. Or we have here aortic trauma. Okay. We go here. We have here aortic trauma okay we go here we have here a new group aortic trauma injury poisoning clinical attributes beautiful or we go here with anatomy anatomy abnormalities structure tissue we built here this semantic group or the last one what i missed here i missed here the aortic arch yes this one here so you see you take here all more or less all the elements that you have from the user query and the system tries to understand here the context of everything so we have here all the knowledge graph concepts and we have here one, two, three, four different concepts. And now what they do here with give, it first builds here an entity group for each query concept and then induce inner group connection using its internal knowledge. And then we will use cross group connection contained in the knowledge graph so you see what we do we build here our complete understanding and this is what i meant here with hypothetical links because those links are real but they are not in the knowledge graph for this particular domain augmentation chain so you see an autonomy is part of here and influences this and this affects this one and here we have a location of and the self function goes here is an interrelated functions and you see this system tries to build here new stepstones to be able to have a multi-hop reasoning. And if one of the stepstones, like the cell function, is missing, the system tries to find in the vast knowledge array exactly this stepstone that would connect here in a logical causal reasoning way and build this stepstone for multi-hop reasoning yeah that's if you want to have a look without my things great what made this click is here this single sentence by the authors and they say hey we introduce an additional intermediate node group by picking the multi-step reasoning plans of the LLM that are most helpful for the ultimate questions. So whatever they are missing in their sparse graph, intermediate node groups that are related to the user query, they select this from the LLM's multi-step reasoning plans. And those plans have a multitude of possible pathways forward through the knowledge array. So you see, it is not a hypothetical link, it is just a not yet chosen link here to build these new intermediate node groups. Highly sensitive to your domain knowledge, highly sensitive to the parametric knowledge of the LLM, and of course to the structural information, to the structural data representation in the knowledge graph. Yeah, for my green grasshoppers, short explanation. Now this graph-inspired veracity extrapolation, now you understand it a little bit better, is a knowledge extrapolation framework for structured reasoning of LLMs on sparse knowledge graph and give neither focusy on explicit information retrieval like our RAC nor reliesy on improving the internal reasoning ability of LLMs by a pending triggering statement to the query. No, not at all. I just showed you what we do. Knowledge extrapolation. We build new stepping stones for our multi-hop reasoning. Now it is interesting that those two frameworks, Sync on Graph and GIF, they connect somehow, no? no so first both integrate llms with knowledge graph a new innovative phrase to enhance here complex reasoning both tackle the problem of multi-hop reasoning and while sync on graph achieves this by dynamically searching with the beam through the knowledge graph give does so by extrapolating here this new relationship and filling in the gaps of incomplete knowledge in our sparse knowledge graph. Second, they both aim to reduce the hallucination. This is a common flaw still in our LIMs. TOG achieves this by ensuring traceability and correctness in the reasoning path of our knowledge graph, while GIF adds here, as I showed you, an extra layer of counterfactual reasoning, which increases the overall reasoning capacity. And both frameworks are designed with the idea here that we have smaller LLMs, like JET GPT 3.5, as the author shows, and they, with this new methodology of sync on graph and give can outperform larger models like gpt4 in specialized tasks so this is nice that here our smaller models maybe our open source models are able to outperform with this new methodology how to combine in an innovative way the LLM with the structured knowledge of a knowledge graph, this is really nice. So key insight because it shows that by integrating structured knowledge and reasoning, here we have the knowledge graph, here we have the LLM, we can dramatically improve the model performance without needing to scale up the model size. This is a nice result. But of course, you can use still here the Sync-on graph and give here together or in particular user cases. TOG is ideal when you have a rich, well-populated knowledge graph. You don't need anything else. If your knowledge graph is more or less complete for your particular query on your particular domain and fits in your complexity level, you are good to go. However, on the other hand, if you have a sparse knowledge graph, if you say, wow, the complexity of my queries by the human or by the students is so high, I better go with here a more powerful methodology, especially when your structured data are incomplete and gives us here some real beautiful results. So, both methods create flexible, powerful toolkits for enhancing the LLM reasoning. Independent, if the domain is well-defined, then you go with train on graphs, or the domain is still evolving and sparse, then you go with give. Great. This is the official end, but I want to show you something else. I found out something that amazes me.
ADD LLM TO Knowledge-Graph: NEW GIVE Method (Berkeley)
Graph Inspired Veracity Extrapolation (GIVE) is a novel reasoning framework designed to enhance the performance of large language models (LLMs) in knowledge-intensive tasks by integrating sparse external knowledge graphs (KGs) with the LLM's internal knowledge. 

The main insight of GIVE is that even when working with incomplete or limited KGs, it's possible to improve the reasoning capabilities of LLMs by using the structure of the KG to inspire the model to infer and extrapolate potential relationships between concepts. This approach facilitates a more logical, step-by-step reasoning process akin to expert problem-solving, rather than relying solely on direct fact retrieval from dense knowledge bases.

The GIVE framework operates in several key steps. First, it prompts the LLM to decompose the query into crucial concepts and attributes, extracting key entities and relations relevant to the question. It then constructs entity groups by retrieving entities from the KG that are semantically similar to these key concepts. Within these groups, GIVE induces intra-group connections using the LLM's internal knowledge to explore relationships among similar entities. For inter-group reasoning, it identifies potential relationships between entities across different groups by considering both the relations mentioned in the query and those present in the KG. 

Additionally, GIVE introduces intermediate node groups to facilitate multi-hop reasoning necessary for complex questions, effectively bridging gaps in sparse KGs. By prompting the LLM to assess and reason about these possible relationships—including counterfactual reasoning where the model considers both the presence and absence of certain relations—GIVE builds an augmented reasoning chain. This chain combines factual knowledge from the KG with extrapolated inferences from the LLM, enabling the generation of more accurate and faithful responses even when the available external knowledge is limited.

Great insights by @UCBerkeley  and @penn 

00:00 Integrate LLM and Knowledge Graphs
01:06 Think on Graph (ToG)
05:58 ToG GitHub code repo
06:30 GIVE Graph Inspired Veracity Extrapolation
09:33 GIVE vs Harvard Knowledge Graph Agent 
10:33 Why RAG fails in Knowledge Graphs
11:40 Example of GIVE in detail
16:16 Compare ToG to GIVE 



All rights w/ authors:
THINK-ON-GRAPH: DEEP AND RESPONSIBLE REASON-
ING OF LARGE LANGUAGE MODEL ON KNOWLEDGE GRAPH
https://arxiv.org/pdf/2307.07697

GIVE: STRUCTURED REASONING WITH KNOWLEDGE
GRAPH INSPIRED VERACITY EXTRAPOLATION
https://arxiv.org/pdf/2410.08475v1

Towards Trustworthy Knowledge Graph Reasoning:
An Uncertainty Aware Perspective
https://arxiv.org/pdf/2410.08985

#airesearch 
#aiagents 
#harvarduniversity 
#berkeley 
#knowledge 
#llm