Systems and methods for graph-based dynamic information retrieval and synthesis
Disclosed herein are systems and methods for graph-based dynamic information retrieval and synthesis, particularly for enhancing the response generation of chatbot applications using large language models (LLMs). The methods involve receiving a user query, generating a query embedding, and accessing a knowledge graph comprising nodes representing documents with associated document embeddings. A set of documents is retrieved based on similarity scores, and a distance matrix is constructed to calculate shortest-path distances between nodes. Documents are clustered to identify a largest cluster from which content is retrieved to formulate a response. The disclosed embodiments improve upon retrieval augmented generation (RAG) by leveraging the hierarchical relationships of a knowledge graph and node interconnectedness to provide contextually coherent information and mitigate the inclusion of information from irrelevant or superficially related documents in LLM responses.
1. A method comprising:
receiving a user query;
generating a query embedding for the user query using a trained embedding model;
accessing a knowledge graph stored in a graph database, wherein the knowledge graph includes a plurality of nodes representing documents, the plurality of nodes associated with a plurality of document embeddings, wherein each node is associated with a document embedding from the plurality of document embeddings that characterizes content of a document corresponding to the node;
retrieving a set of N documents, where N is a positive integer greater than one, based on a similarity score between the query embedding and the plurality of document embeddings of the plurality of nodes in the knowledge graph;
constructing a distance matrix by calculating a plurality of shortest-path distances between each pair of nodes corresponding to the set of N documents;
clustering the N documents based on the distance matrix to identify a largest cluster of nodes;
retrieving content from the largest cluster of nodes; and
formulating a response to the user query based on the retrieved content, wherein the response is prepared for display on a user interface.
2. The method of claim 1 , the method further comprising:
receiving a document;
generating a document embedding for the received document using the trained embedding model;
adding a new node to the knowledge graph in the graph database, wherein the new node represents the received document and is associated with the generated document embedding;
establishing a plurality of relationships between the new node and existing nodes in the knowledge graph based on a similarity score between the document embedding of the new node and the document embeddings of the existing nodes;
updating the knowledge graph to include the new node and the established relationships.
3. The method of claim 2 , wherein establishing relationships between the new node and existing nodes further comprises extracting one or more substrings from the content of the received document, identifying corresponding nodes in the knowledge graph that satisfy a pre-determined relationship type based on the extracted substrings, and creating edges in the knowledge graph that link the new node to the identified corresponding nodes with the pre-determined relationship type.
4. The method of claim 1 , wherein the knowledge graph is formed by:
receiving a plurality of documents;
generating a document embedding for each document of the plurality of documents using the trained embedding model;
adding a respective node to the knowledge graph in the graph database for each document of the plurality of documents, wherein each respective node is associated with a corresponding document embedding that characterizes content of the document;
establishing relationships between nodes in the knowledge graph based on one or more extracted substrings from the content of the plurality of documents and a pre-determined node schema, wherein the relationships are indicative of content-based associations between the documents; and
updating the knowledge graph to include each respective node and the established relationships.
5. The method of claim 1 , wherein retrieving the set of N documents based on the similarity score between the query embedding and the plurality of document embeddings of the plurality of nodes in the knowledge graph further comprises employing cosine similarity to determine the similarity score.
6. The method of claim 1 , wherein constructing the distance matrix by calculating the plurality of shortest-path distances between each pair of nodes corresponding to the set of N documents further comprises utilizing Dijkstra's algorithm to determine the plurality of shortest-path distances.
7. The method of claim 1 , wherein clustering the N documents based on the distance matrix to identify the largest cluster of nodes further comprises applying a k-means clustering algorithm to group the nodes into clusters.
8. A method comprising:
receiving a user query;
generating a query embedding for the user query using a trained embedding model;
accessing a vector database, wherein the vector database stores a plurality of document embeddings, each document embedding characterizing content of a document and being uniquely associated with a corresponding node in a knowledge graph stored in a graph database, wherein the knowledge graph includes a plurality of nodes representing documents;
retrieving a set of N similar documents based on a similarity score between the query embedding and the plurality of document embeddings stored in the vector database;
constructing an N×N distance matrix by calculating a plurality of shortest-path distances between each pair of nodes corresponding to the set of N similar documents in the knowledge graph;
clustering the N similar documents based on the N×N distance matrix to identify a largest cluster of nodes;
retrieving content from the largest cluster of nodes; and
formulating a response to the user query based on the retrieved content, wherein the response is prepared for display on a user interface.
9. The method of claim 8 , wherein constructing the N×N distance matrix comprises calculating the plurality of shortest-path distances using Dijkstra's algorithm, wherein each shortest-path distance represents a graph distance between a pair of nodes in the knowledge graph, and wherein the graph distance is indicative of a degree of relatedness between content of the documents corresponding to the pair of nodes.
10. The method of claim 9 , wherein clustering the N similar documents based on the N×N distance matrix further comprises employing a k-means clustering algorithm to partition the N similar documents into clusters within an N-dimensional space, wherein the largest cluster of nodes is determined by the cluster having a greatest number of nodes from the set of N similar documents.
11. The method of claim 8 , wherein the shortest-path distances are weighted based on a relevance metric associated with each edge of the knowledge graph.
12. The method of claim 8 , wherein retrieving the set of N similar documents includes selecting documents with a largest cosine similarity to the query embedding.
13. A system for information retrieval in response to a user query, the system comprising:
a memory storing instructions;
a trained embedding model stored in the memory;
a vector database communicably coupled to the memory, wherein the vector database stores a plurality of document embeddings, each document embedding characterizing content of a document and being uniquely associated with a corresponding node in a knowledge graph stored in a graph database, wherein the knowledge graph includes a plurality of nodes representing documents;
a processor communicably coupled to the memory and the vector database, wherein, when executing the instructions, the processor is configured to:
receive a user query;
generate a query embedding for the user query using the trained embedding model;
access the vector database to retrieve a set of N similar documents based on a similarity score between the query embedding and the plurality of document embeddings stored in the vector database;
construct an N×N distance matrix by calculating a plurality of shortest-path distances between each pair of nodes corresponding to the set of N similar documents in the knowledge graph;
cluster the N similar documents based on the N×N distance matrix to identify a largest cluster of nodes;
retrieve content from the largest cluster of nodes; and
a user interface communicably coupled to the processor, wherein the user interface is configured to display a response to the user query based on the retrieved content.
14. The system of claim 13 , wherein, when executing the instructions, the processor is further configured to:
receive a document;
generate a document embedding for the received document using the trained embedding model;
add a new node to the knowledge graph in the graph database, wherein the new node represents the received document and is associated with the generated document embedding;
establish a plurality of relationships between the new node and existing nodes in the knowledge graph based on a similarity score between the document embedding of the new node and the document embeddings of the existing nodes; and
update the knowledge graph to include the new node and the established relationships.
15. The system of claim 14 , wherein establishing relationships between the new node and existing nodes further comprises:
extracting one or more substrings from the content of the received document;
identifying corresponding nodes in the knowledge graph that satisfy a pre-determined relationship type based on the extracted substrings; and
creating edges in the knowledge graph that link the new node to the identified corresponding nodes with the pre-determined relationship type.
16. The system of claim 13 , wherein the knowledge graph is formed by:
receiving a plurality of documents;
generating a document embedding for each document of the plurality of documents using the trained embedding model;
adding a respective node to the knowledge graph in the graph database for each document of the plurality of documents, wherein each respective node is associated with a corresponding document embedding that characterizes content of the document;
establishing relationships between nodes in the knowledge graph based on one or more extracted substrings from the content of the plurality of documents and a pre-determined node schema, wherein the relationships are indicative of content-based associations between the documents; and
updating the knowledge graph to include each respective node and the established relationships.
17. The system of claim 13 , wherein the processor is further configured to update the knowledge graph by adding new nodes and establishing relationships between the new nodes and existing nodes based on a threshold similarity score, wherein the threshold similarity score is determined by a percentile rank within a distribution of similarity scores across the knowledge graph.
18. The system of claim 13 , wherein the processor is further configured to refine the query embedding by incorporating context from a user's previous queries and interactions with the system, based on temporal and topical relevance.
19. The system of claim 13 , wherein the processor is further configured to prioritize retrieval of content from nodes in the largest cluster based on a number of connections to other nodes in the largest cluster.
20. The system of claim 13 , wherein, when executing the instructions, the processor is further configured to:
generate the response to the user query by:
selecting content from the retrieved content of the largest cluster of nodes;
forming a context for the user query based on the selected content;
generating a prompt comprising the context and the user query; and
providing the response to the user interface for display.