I wrote a blog post on the HNSW vector index design, perhaps the most popular vector index design adopted by databases at this point. The post is based on several lectures I gave in a graduate course at UWaterloo last fall. This is intended for people who are interested in understanding how these indices work internally.
My goal was to explain the intuitions behind HNSW indices as a natural relaxation of two prior indices: kd trees and the (not much appreciated) sa trees.
I also place these three vector indices in a framework that I call the "FES Theorem", which states that any vector index design can provide at most two of the following three properties:
- Fast: returns vectors that are similar to a query vector q quickly.
- Exact: correctly returns the most similar vectors to q (instead of "approximate" indices that can make mistakes)
- Scalable: can index vectors with large number of dimensions, e.g., 1000s of dimensions.
Kd trees, sa trees, and HNSW satisfy each 2 possible combinations of these 3 properties.
Needless to say, I intentionally picked the term "FES Theorem" to sound like the famous "CAP Theorem". Fes (Turkish) or a fez (English), just like cap, is a headdress. You can see a picture in the post.
I hope you find the explanation of HNSW as a sequence of relaxation of kd trees useful.
That's correct though OWL also provides ways to constraint what can be encoded (e.g., the cardinality constraint example I gave). But yes, SHACL is primarily for constraints. I general, there are several other standards than RDFS and OWL I didn't mention in the post. I wanted to give a few example standards to explain to show how RDF + standards forms something more than a regular data model that developers think of.
I wrote a blog post on something that I find is often misunderstood and under-appreciated: Resource Description Framework (RDF). I explain what RDF is, what it is not, when you may need it, and its virtues and vices. RDF is good to know about in our increasingly AI-dominated world, since it has its roots in knowledge representation and reasoning (KRR), which is a field of AI, known as good-old-fashioned symbolic AI.
I explain RDF first as a data model and compare its pros and cons with relational and property graph model. I then explain RDF and the standards around RDF, such as RDFS and OWL, as a "knowledge representation system". I cover RDF's roots in knowledge representation and reasoning (KRR), traditional symbolic AI systems. I also discuss several directions I have seen people pursue to improve LLMs with RDF-based or more broadly KRR-based technology (see especially the link to Doug Lenat's last article (I think) on the subject before he passed on).
It's a bit of a long read but I hope people find it useful to think about RDF.
I think even on the LLMS + KGs space the depth is not very deep. In fact there is more technical depth in the text-to-SQL than anything else I have seen on LLMs. Maybe the COLBERT-like matrix-models is another topic where there is good technical depth.
This is a post that summarizes some reading that I had done in the space of LLMs + Knowledge Graphs with the goal of identifying technically deep and interesting directions. The post cover retrieval augmented generation (RAG) systems that use unstructured data (RAG-U) and the role folks envision knowledge graphs to play in it. Briefly the design spectrum of RAG-U systems have two dimensions:
1) What additional data to put into LLM prompts: such as, documents, or triples extracted from documents.
2) How to store and fetch that data: such as a vector index, gdbms, or both.
The standard RAG-U uses vector embeddings of chunks, which are fetched from a vector index. An envisioned role of knowledge graphs is to improve standard RAG-U by explicitly linking the chunks through the entities they mention. This is a promising idea but one that need to be subjected to rigorous evaluation as done in prominent IR publications, e.g., SIGIR.
The post then discusses the scenario when an enterprise does not have a knowledge graph and discuss the ideal of automatically extracting knowledge graphs from unstructured pdfs and text documents. It covers the recent work that uses LLMs for this task (they're not yet competitive with specialized models) and highlights many interesting open questions.
Hope this is interesting to people who are interested in the area but intimidated because of the flood of activity (but don't be; I think the area is easier to digest than it may look.)
You seem to have done some research already but let me answer briefly: GNNs and what I covered in the blog post, "RAG over structured data", are not connected. They are approaches to solve 2 different problems.
GNNs: Let's forget about LLMs completely. GNN is a term given to a specific ML models where the model layers follow a graph structure. Suppose you have some data that represents real-world entities and you have features, i.e., some vector of floating numbers representing properties of these entities. Then if you want to run some predictive task on these entities, e.g., your entities are customers and products, and you want to predict who could buy a product so you can recommend these products to customers. Then there are a suite of ML tools you can use if you could represent your entities as vectors themselves, e.g., then you can use distances between these vector-representations as indication of closeness/similarity and you could recommend products to a customer A that were bought by customers that are close to A's vector representation. This is what's embedding of these entities in a vector space.
One way to embed your entities is to run the nodes through an ML model that takes their features as input and produces another set of vectors (you could use the features alone as embeddings but they are not really trained and often have higher dimensions compared to the embedded vectors' dimensions). GNNs are a specific versions of such ML models where the entities and relationships between entities are modeled as a graph. And the model's architecture, i.e., the operations that it does on the feature vectors, depends on the structure of this graph. (edited)
In short, GNNs are not deeply connected to LLMs.
GNNs became very popular several years ago because they were the only ML architectures where you could incorporate into the model and training objective not just the features but also connections between features. And they dominated academia until LLMs. In practice, I don't think they're as popular as they are in academia but afaik several major companies, such as Pinterest based their recommendation engines on models that had GNN architecture.
But one can imagine building applications that use a mix of these technologies. You can use GNNs to create embeddings of KGs and the use these embeddings to extract information during retrieval in a RAG system. All these combinations are possible.
This is the first blog post on a series of posts I plan to write on the role graph DBMSs and knowledge graphs play on LLM applications and recent text-to-high-level-query-language work I read up on over the holiday season.
These blogs have two goals:
(i) give an overview of what I learned as an outsider looking for technical depth;
(ii) discuss some venues of work that I ran into that looked important.
This first post is on "Retrieval Augmented Generation using structured data", so private records stored in relational or graph DBMSs. The post is long and full of links to some of the important material I read (given my academic background, many of these are papers) but it should be an easy read especially if you were an outsider intimidated by this fast moving space.
tl;dr for this post:
- I provide an overview of RAG.
- Compared to pre-LLM work, the simplicity and effectiveness of developing a natural language interface over your database using LLMs is impressive.
- There is little work that studies LLMs' ability to generate Cypher or SPARQL. I also hope to see more work on nested, recursive and union-of-join queries.
- Everyone is studying how to prompt LLMs so they generate correct DBMS queries. Here, I hope to see work studying the effects of data modeling (normalization, views, graph modeling) on the accuracy of LLM-generated queries.
My goal was to explain the intuitions behind HNSW indices as a natural relaxation of two prior indices: kd trees and the (not much appreciated) sa trees.
I also place these three vector indices in a framework that I call the "FES Theorem", which states that any vector index design can provide at most two of the following three properties: - Fast: returns vectors that are similar to a query vector q quickly. - Exact: correctly returns the most similar vectors to q (instead of "approximate" indices that can make mistakes) - Scalable: can index vectors with large number of dimensions, e.g., 1000s of dimensions.
Kd trees, sa trees, and HNSW satisfy each 2 possible combinations of these 3 properties.
Needless to say, I intentionally picked the term "FES Theorem" to sound like the famous "CAP Theorem". Fes (Turkish) or a fez (English), just like cap, is a headdress. You can see a picture in the post.
I hope you find the explanation of HNSW as a sequence of relaxation of kd trees useful.
Enjoy!