Dynamic Knowledge Graphs

Speaker 1 [00:00]

So hello everybody, welcome back. You ready for the next talk? So we welcome Jakob with his talk on dynamic knowledge graphs.

Speaker 2 [00:16]

Yeah, thank you very much. Also, a warm welcome from me. Thanks for joining my talk. It's quite nice to see so many people, even though it's after lunch and the third day. And I would like to spend the next 30 minutes talking about data structures for knowledge management and why it's important that now that we have all of these nice AI toolings for inference that we spend some time on discussing on which knowledge sources there are and which they can interact with. So let's start with the motivation. Like I said, third day. I hope all of you have many, many ideas in your head now after these talks, but I hope that there's still some space for a few new ideas. And I think one of the most central concepts that we all work with are knowledge sources. And knowledge sources, they come in many varieties. So let's say in your day-to-day life, depending on your role, I'm sure all of you work with one of these or many of these sources. Let's say you are a scrum master or a product owner, and then you may work with Jira tickets more often where you prioritize and you put new requirements. Say you're more of a developer, you probably work in some Git integration, could be Git labs, GitHub, or we use GITI. Or if you develop APIs, you probably use Swagger or something to put documentation there. And all of these knowledge sources, they have different kinds of schemas and they are disconnected, so it's kind of hard to interact with them at the same time. Probably if you've built some kind of application, maybe some of you have built your own React system, you noticed it's kind of hard to understand holistic information over all of these different systems. And I don't think it's the solution to say we have one system that everybody has to work in, because these different systems, they are quite good at what they try to do. So all of them, they have some use case they cover, and I don't think we should force people to work into one central system, but we should rather try to basically build a data integration pipeline to take the knowledge from different sources and then bring it into some format that is machine readable, such that our infant systems can interact with all of the information that is present. And to set off, I'm sure we have very different people on different knowledge levels. So we have to talk a bit about related work just to make sure everybody can follow these ideas. And like I said, I think most of you are probably familiar with vector stores and maybe you've built your own system. And I think vector stores, they are quite nice because it's especially now very simple to set up. You can use Qtrent or Milius or some kind of vector store. It's also quite cheap to calculate embeddings and it's quite fast to do vector similarity search, especially with advantages in ANN search, it's very quick to find similar vectors or similar documents. But the main limitations that you face in an industry setting are that you're missing these global connections, so it's quite hard using a vector score to answer a query like give me all products for example then the vector store it will return documents and it may be returned many documents but it's quite hard to understand did I get all of something because it's not really what the vector store is trying to do right you just get some but you don't really know have you found all and and you also have a problem with conflicting entity conflicting entries so let's say again you do a query you get five documents and two of them they say one thing one of documents says something else and the other two they are not really relevant you don't know in a global setting like how many other documents support whatever the two said and how many support whatever the one said so which which is actually the truth or which is more reliable information here and there are libraries like graph rag I think that's the most known knowledge graph library it was developed by Microsoft if you haven't heard of graph rag I really recommend it's a really nice blog entry just to read it and and it's I would say kind of easy to set up because they made easy to set up it's just a library and and they do like really powerful community aggregation so the idea is you have clusters of nodes and then you do aggregations before and that's quite nice because then you have this holistic view of your knowledge sources but the main downside here is that it's quite slow to build and it's only static so microsoft there were issues where people requested dynamic features and due to these community aggregations they they basically said we will not do that that's too much complexity and also due to aggregations we lose the traceability to a source document so at some point we don't even know where that information come from so we cannot provide some citation link to a user for example um and yeah it's also quite expensive it takes a long time which isn't bad if you do it from a static version but if you have sources that change all the time you probably want something that's a bit faster and since we will talk about graphs i will just make sure you know which kind of graph we talk about i think there are two like big kinds of graphs we have an rdf that's a resource description framework it's basically triplets of of entities and we have a property graph the property graph is something that was popularized by neo4j i would assume some of you have used neo4j for for some graph stuff i guess it's the most um most popular graph database that there is um and both of these you can you can do basically anything with both of them but we will use the property graph just because it makes it easier to attach complex structures like we would like to attach an embedding for example to a node and that's just easier using a property graph and if you have worked with graphs maybe now you think well isn't that a temporal graph that you're you're talking about if we if we want to have dynamic features and that's pretty good point temporal graphs are a different kind where you basically can go back and forth to time and you always keep like track of changes but i would argue we don't need that capability because i don't see the point to to be like i would like to know how my knowledge graph looked three months ago i just want a current version that is really good and like correct um so we don't support going back and forth that's why this talk isn't called temporal knowledge graphs just dynamic knowledge graphs and but feel free to look into to research on temporal knowledge graphs if you have a use case where you actually need to go back in time to check something out i think for most knowledge like search tasks it's not necessary to go back in time all right and then credit or credit is doing this project started as a cooperation with the tu berlin i supervised the group of five students there for one semester and they basically laid the foundations for this project it was in a lecture by professor tim toibner and then the last like six months i spent every now and then whenever there's time for this nice side project to basically polish it a bit to to um get it ready to then now present it to you all right um next chapter also really doesn't sound interesting if you have been here talk before it was way more visual and way more let's make it interesting but i think to to talk about formal definitions it's really important especially since we now have these powerful li systems that can create fuzzy schemas that you can basically say please please please create me a nice knowledge graph and they will give you something but i think to have a system that you can trust it's very important to make some formal definitions and to to build some kind of structure that you you actually own and that you know how to maintain and so we will talk about four different types of nodes which basically make up this graph and how these nodes are connected so which kind of edges and notes we expect that should be first will be the document node that's basically a source document it could be all kinds of stuff let's say for example it's an html page of your internal wiki and for every document node we save a content hash so you can think of an md5 hash or we use a char 256 hash just to have a more like machine readable thing to interact with the documents and of course you could like hit the same hash i would say will not happen so we are totally fine with just using the hashes to as an identifier and we we save some metadata so like creation date and last verification date and that helps to clean your graph because for us we want to to remove documents that are too old like undocumented was created five years ago even if it still exists in these knowledge sources it's probably outdated it just wasn't deleted by a user um and we generate summaries that's also done through llms and restore embeddings for the summary just to be able to have more search capabilities on a semantic level and you can think of this document node as an anchor for all kinds of information that lives in the graph so basically we build a scaffolding and document nodes they only have outgoing edges which have the type supported by so these documents they basically span the all of the rest of the nodes such that we can always trace back information to a document node and then from the document node we know where the information originated from and can provide a citation and in the further illustration it will just be the small node with the d unit there will be a document node and then we have the entity nodes and entity nodes this is the actual content that we extracted from our documents and here we extract name and a label and the unique identifier then is name and label and we we and we'll talk about it in detail we do a similarity matching to deduplicate the entities when we insert them because our goal would be to have a graph that's really connected to then enable something like neighborhood exploration and to really understand how the different documents talk about the same kind of entity, but maybe in different ways. So we need to make sure that semantically the same kind of entities also get mapped to the same node. Because let's say when we have abbreviations or name shortings, then that should be the same node, not two nodes. They all have a path to a document node, could be direct or indirect. And we see relationships between entity nodes. And we will talk about facts. So every node is dependent on facts. Facts will be the next slide. And again, we store embeddings for the summary to enable more search features. And entity nodes are in this blue. The label is dynamic, right? The label is generated when we process the document. So there's no fixed label, but we will, in the illustration, it will be the e-nodes that's some kind of entity and then there's facts so facts are basically this atomic nuggets of information so let's say i have a have a page in our wiki where i introduce myself and there's like jacob works in the data science team and then some more stuff like where i went to university to and how long i've been in the company and then one nugget would be that i work with the data science team and and we want to split this these nuggets of information to then again merge the same facts and to be able to remove only certain facts because let's say we have a fact that is only supported by one document and then the document gets removed we only remove that fact but maybe the node can stay because there's more facts for the nodes which have been supported by different documents and again we do similarity matching identification just to ensure we have a connected graph at the end. Facts again are extracted by LLM we will see a data prompt example later. And fact nodes are in yellow and have this F. And then lastly, relationships. Relationships are also nodes. I guess if you work with graph, you would expect a relationship to be an edge. But since we want to have again traceability to a source document, we basically take this one edge with the relationship and we just insert a node in the middle such that a document can reference this relationship. But it's just a choice of how we model that. It's basically an edge, but we cannot point an edge to an edge. That's why we insert a node in the middle. And then an edge is very similar to a fact, again, as small as possible, extracted by an LLM, just carries content and will be this darker blue color. So if we take a step back, that's basically the graph schema. document nodes only outgoing edges, which can be connected to very many facts, entities and relationships. And we see that entities and relationship, this is one to one. So every relationship is like between two entities and then facts are connected to entities. And now I invite you, I will stop talking for like 15 seconds, take a deep breath, think about what I said and then we continue just to make it a bit more approachable. Okay let's continue. So now we talk about insertion, deletion and query. So basically the operations that we enable towards the graph such that we can interact with it. And for insertion, we touched on these points during the last few minutes when we talked about the node structures. But basically we have one prompt that goes over the documents and then we do a structured output. These are bidentic classes. I think pretty much all of the state-of-the-art models, they support structured output. And we have the structure, we say produce names, produce labels, summary, and then a list of facts. and the source document gets passed into this prompt and then we just do it again which works surprisingly well like if you just say extracted and then we point like are you sure aren't there more and then sometimes it produces more nodes sometimes it doesn't and if it produces the same node but just with more effects we do a union which is just a strategy you can try and see if it works on your cases work quite well for us and after we extracted the nodes we then provide add to a separate call we say this is the nodes that have been extracted for the document now extract the relationships and again we try it twice to see if we find some more relationships and then we go into this merging phase so after we extracted the nodes and relationship we need to merge them with existing ones before inserting to the graph and for node merging we do basically three steps after each other which are more complex after one another So we try to find matches with a non-complex version and then go to more complex versions. And the easiest would be just an exact match, right? Let's say there's an existing node that's Darmstadt of type place and we extract a new node that's Darmstadt of type place. Great. It's very efficient to find. We can just use it and merge these two nodes. And for merging, it would be that's a cipher. If you're familiar with graph, you know ciphers. If not, just think of SQL, but for graphs and fill in the gaps. and we return this id and then we use the internal id to merge these nodes and the cipher basically just matches a node with the same label and the same name. All right, if that doesn't work we use Jarrow-Winkler matching similar to like Levenstein matching or Jacquard. Jarrow-Winkler is just very good for names because it has, I get values the prefix more than the whole string. So for example if we have something like Darmstadt place and then we have Darmstadt Wissenschaftsstadt maybe if you came here by train that's I think also on the train station just means a science city you can use Jarrow-Winkler and Jarrow-Winkler will give you I think 86 percent for this so quite a good match because it's actually the same and then we use an LLM for verification and if we look at that in the query again we use basically the same kind of idea we've stood for Jarrow-Winkler and we look if this threshold is greater than our given threshold and now you see this faculty b so this is the point we have to tell you which graph database we actually use we don't use neo4j but we use faculty b just because we wanted to experiment with the faculty b if you use neo4j you basically can do the same just the syntax this flex.txt.jarlewinkler would be different then but neo4j also has functions for string similarities and lastly if all of that doesn't work we try to matched embeddings because we have on the descriptions we have embeddings for them so we can try to find a matching node based on the description so let's say in one document again a system one we have visual vest as of type company and then newly extracted it's a vv which is basically an abbreviation that we use quite commonly and it's organization so we have a mismatch but maybe the descriptions are quite similar both of them like talk about a fintech and maybe both of them talk about like this is our company and so it's quite likely that with a semantic embedding we can then find a match and actually still merge these nodes and again for Falco these embeddings are stored directly in the node so it's quite nice we don't need a parallel structure for for searching for embeddings we can find them and again look if the threshold is greater than something and then in the end we merge the nodes if the LLM verification worked and for fact and relationship merging they work pretty similar and we basically we do all of them at the same time and our main priority here is to not change information that's already in the graph because let's say we have a description that is already in the graph and then we change that description and it's kind of impossible to then say well is that then correct for the document that already linked to it so we only try to match new ones to existing ones and then if the new ones can't be matched to existing ones we insert new facts or new relationships and so basically the priority that we already there is to keep the traceability intact and secondly would be to to maximize the connectiveness of the graph um and the idea is just look at the existing facts look at the new facts and then we do some validation afterwards to see that the number of facts didn't change that the existing facts are actually existing and basically that data structured output is correct. For deletion, we will go over a quick example because deletion is now pretty simple when we have that structure and quite fast. So let's assume we want to delete document like on the bottom left. What we would do, we first just delete the document like detach delete with also the edges directly to the document. And then next up, we would delete all facts that don't have an incoming edge from a document anymore. So if you see here, the document also produces an edge to the fact on the right. But when we delete it, the right node down there, it still has an incoming edge. So when we delete facts, we only delete the facts which don't have incoming edges anymore. And then we remove all entities that don't have a path to a document anymore. we remove the relationships that don't form a full relationship anymore and that's basically it we have deleted the document and everything that was only supported by this document is now not in the graph anymore and again here's the cipher it's just one query which detached leads one after another to make sure the graph is then cleaned all right then we are already at the inference and inference is a work in progress so be creative here and these are just ideas because we are still in the process of like using this tooling actually and getting our first experiments but what we started with is a pedantic AI agent you could use Landgraf here you could use small agent like any kind of agentic system you could write your own and we just provided some tools so basically we gave the agent the possibility to query for an embedding. It can query for keywords. So that's like just find a starting node basically and then we have this get neighborhood. So the agent once it has like a starting point can provide the ID and then the tool returns the neighborhood of the node. And that's like how the agent can explore the graph and gather information to answer a user query. And just to point you to some resources the nice thing about this dynamic knowledge graph is that for inference we can just use the same kind of tooling like for normal knowledge graph doesn't matter for inference if it's dynamic or static and so there's a project and also a paper called a reasoning on graphs there's the github link down here and like the illustration i put over there and it's great if you just want to get some ideas of how you can interact with the graph that's also a nice read and yeah to provide this tool that enables us to also get some more structure in we also enable the the agent to just write a cipher itself so it has all the freedom but it could also use the tools to then we have a bit more um a bit more control what the agent is doing let's talk about limitations and our outlook before we end and so cool limitations are that the graph databases they are in-memory databases that's kind of a limitation that you could just solve with using a bigger virtual machine but if you have really really big knowledge sources or if you for example also want to save artifacts into your graph database now or the same machine then you might eventually run out of possibilities here and their vector stores something like pgvector doesn't have these limitations and the insertion times are quite high so since we take a few steps here you need to make a few calls and merging especially for large documents and a large graph can get quite slow so it's about 45 seconds to insert a document not too bad but also if you have like a high throughput you probably want something that's faster than 45 seconds um and of course we also on the development side you need to put more time into development it's more complicated to develop such a tool than a vector store so you should know that if you think no i will build that also it's it's more effort and then the last point i think that's a general problem we have a few examples where we have like a gold standard but it's like 50 examples so we don't have an extensive benchmark set where we can actually say we have a new version and then maybe two documents they produce a better result and one produce a worse result so it's it's quite hard to actually get a quantitative feeling of how good your system is. And for Outlook, something that we are working on, maybe you've been at the talk with the Still Labs, we've worked with them in the past as well, for a small language model training or fine-tuning, and that's a great case because the output is really structured, so we would like to use a small language model here for the node extraction and the relationship extraction, which also provides privacy benefits right if that can run on-prem then you don't have to expose your knowledge sources to some cloud provider and we also want to avoid more weak computation usually in knowledge sources only a small bit of the document changes like in a paragraph maybe a sentence edit but most of the document stays the same so you could apply like aggressive paragraph paragraph-based caching, so then only we could compute small parts of the document. And we do not have like live A-B testing currently deployed, but that would also be very nice to give the employers two options. Basically say these are two responses that have been produced by different versions of the tooling. Pick which one you like better and it could be very nice for us to get an idea of the actual usefulness. That's again a quick overview. I would skip over it due to time and lastly the dynamic social graph I guess that's the standard slide at the end feel free to connect with me or if you're interested you can also check out our job listings and that's it thank you very much and I'm open for questions now

Speaker 1 [25:00]

Yes, so thank you. We got already some questions.

Speaker 2 [25:04]

questions

Speaker 1 [25:05]

The first one would be, why aren't fact nodes presented as entity nodes with relationships between them?

Speaker 2 [25:14]

Fact nodes as entity nodes with relationships between them. I don't know if I get the question. I will try to give the idea about fact nodes. You see the fact nodes the idea is that you always have only linked the fact to an entity that one fact doesn't link to two entities. To again enable flexible deletions because let's say I have a colleague right and in his explanation text he also writes he works with the data science team if then works with the data science team is a fact, and it points to me and the colleague, and then two documents point You know, let's Thank you. Sorry, I don't.

Speaker 1 [27:35]

Depend on each other like in a long chain of thought.

Speaker 2 [27:54]

problem if you have a benchmark Thank you. Time. kind of, three, like, we put labels that I, as yellow. Thank you.