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.
I might be wrong in the numbers as I just got them from Wikipedia. But to be clear: Istanbul is the name of both the city and the "province" in Turkiye. And I used the larger area number from Wikipedia, which is for the province: https://en.wikipedia.org/wiki/Istanbul
So even when using official numbers, the urban density of Istnabul is > 6000 according to Wikipedia.
ps: I live in Toronto, so I know Toronto is incomparably dense compared to other parts of Ontario. I could have made the same point by comparing Toronto's density to Ontario. Though, I'm curious how much of Ontario is uninhabitable. I thought most of it (say > 50%) seemed habitable.
This is a good point. There must be one though that other cities can look up to. I would guess Singapore does a good job on these problems. I would be curious to hear of the best examples of large cities that have done a better job on housing.
I am also amused that Ontario, which is the most populous province has the following statistics:
Area: 1,076,395 km square
Population: 15.3M
Istanbul, which is the biggest city in my home country Turkiye has these:
Area: 5,343 (so 200x smaller)
Population: 18M (official census is ~16M but even the major cites 18M)
I'm not even comparing the much denser places in the world (e.g., Gaza).
I think this article isn't very stimulating but here's a good summary of the case made by many "realists" about international relations on why Ukraine's entry into NATO and the US-NATO's encouragement of this was destined to lead to a war by one of the most prominent realists, John Mearsheimer: https://www.youtube.com/watch?v=JrMiSQAGOS4&t=2751s.
I remember the Brown prof's demo video, which was about a paralyzed person drawing a circle on the screen. The way it was implemented was by capturing and learning the signals the brain sends (but unable to send to the spine of course) when the person is "thinking of" or "imagining" moving the cursor to the left and right, etc. And then translating those signals to cursor moves. This video explains a similar approach: https://www.youtube.com/watch?v=9oka8hqsOzg
About 15 years ago I had seen a paralyzed man control mouse and computer interfaces (was research from Brown university). This is a new step where the translated brain signals are controlling the spine directly! This is truly amazing, inspiring, and practical (and don't forget to watch the short video!)
The worry is still easy to understand I think. Suppose you are a programmer or a project manager and you have come to think that your skills are valuable, i.e., they are rare and someone will pay for those skills so you find opportunities to participate in the economy. Suppose further you believe that some AI programs will be able to produce the programs you could produce, it makes sense to be worried as you would immediately think will you be laid off and have trouble finding ways to participate. This is the same phenomena every disruptive breakthrough puts communities of people through every so often.
That said, as I said I find the discussions on AI generally incoherent. I do not believe programmers or teachers will be obsolete in the foreseeable future (probably ever) nor is it a bad idea to put certain jobs into the hands of machines; a lot of the jobs are terribly boring and should be replaced. I would guess that whatever the disruption, we are likely open new rooms to develop new skills that we'll see over time.
As a side point yes I agree in some areas, like art, people will always find more value in originality and creativity coming from a human. I'm convinced we will always find what Monet did more beautiful than what some robot can do. But that doesn't apply to other fields like programming, or product management, or cleaning.
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!