semihsalihoglu

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.

Enjoy!

I think having a version with a sample synthetic dataset makes sense.

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.

For entity extraction you can look at SpanMarker: https://tomaarsen.github.io/SpanMarkerNER/. I'm sure other tools exists and others can hopefully point at more.

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.

Hope some find this interesting.

RIP the greatest Colombian artist of all time.

"More than 150 people were involved in efforts to save caver Mark Dickey after he developed stomach problems in the Morca Cave on 2 September.

Organisers say it was one of the largest and most complicated underground rescues ever mounted.

The lowest point of the Morca Cave, in a remote part of the south, reaches nearly 1.3km (0.8 miles) below ground.

Mr Dickey was brought out of the cave at 00:37 local time (21:37 GMT), the Turkish Caving Federation announced on social media. "

Found this interesting article from this news article: https://phys.org/news/2023-07-aftermath-china-survey-chinese...

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've been living in Canada for 8 years and I generally heard people referring to "35M people", which I believe will soon change to "40M" people.

Interesting that there is apparently a population clock that model's Canada's population: https://www150.statcan.gc.ca/n1/pub/71-607-x/71-607-x2018005...

See also the Century Initiative: https://www.centuryinitiative.ca/ to reach 100M by 2100.

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.

I think the sentiment roughly translates to AI, one way or another, replacing whatever it is you were doing for work and making your contribution obsolete. It is surprising that he genuinely seems to worry that even his contributions can be obsolete.

I tend to find the discussion around AI, AGI, ChatGPT doomsday somewhat incoherent and try not to follow them. But, I found Elon Musk's reaction in this interview to the question of "What would be your advice to children in the era of AI?" quite interesting and genuine. At the dawn of every transformative technology many people from all walks of life must have asked the same question and now even Elon Musk seems to be asking this same question to himself.

If you want to listen to a very illuminating episode on law firms hiring based on a handful of firms, how bad this is, I highly recommend this episode of Malcolm Gladwell's podcast: https://www.pushkin.fm/podcasts/revisionist-history/the-tort...

You should start listening around 31m:30s in the podcast, where he interviews someone who has analyzed the correlations between how successful a lawyer will be in different firms and the actual features/statistics of candidates. And one of the biggest conclusions this person says is that one feature that doesn't matter much (close to 0) in predicting how successful a lawyer will be is the school they went to (this is around 34m:35s in the podcast). And that for obvious reasons, this is actually what law firms pay most attention to, which is actually a big mistake. This is in fact a very big market inefficiency and an opportunity for law firms to correct in their recruiting.

I would guess a similar pattern exists in many fields, e.g., software engineering.

Another excellent and illuminating thing to read about recruiting mistakes is Daniel Kahneman's work (he has a chapter on this in his "Thinking Fast and Slow" book (https://en.wikipedia.org/wiki/Thinking,_Fast_and_Slow). This article describes a good summary of Kahneman's advice when recruiting: https://www.inc.com/jessica-stillman/hiring-job-interviews-d....

I hadn't heard for this but this sounds very similar to the definition of polynomial hierarchy: https://en.wikipedia.org/wiki/Polynomial_hierarchy

What has fascinated me (if I'm not mistaken) when I was learning about computational complexity was that P=NP implies that the polynomial hierarchy (so this infinite classes of problem) collapses to P, so all problems in the polynomial hierarchy are solvable in polynomial time.

Dijkstra is a big figure in CS and will be taught on campuses for the foreseeable future. Just ran into this link from ACM's Twitter. The bio contains interesting quotes from him, e.g.:

"The question of whether computers can think is like the question of whether submarines can swim."

or:

"If 10 years from now, when you are doing something quick and dirty, you suddenly visualize that I am looking over your shoulders and say to yourself, Dijkstra would not have liked this, well that would be enough immortality for me."

I recently ran into this seminal 1973 paper again after more than a decade from the first time I had read it, and think it is a very interesting read for people interested in historical CS reading. This is research conducted at IBM in 70s on low-energy computing and shows that in principle it is possible to design computers that perform useful computation, spend some energy doing the computation, compute and output, and then gain back some of the energy with a reverse chemical process. I would doubt it will be relevant for practice for the foreseeable future but it is a great read for fundamental research.

The Wikipedia article explains the core ideas more simply: https://en.wikipedia.org/wiki/Reversible_computing. This part discusses the implication: "...there is at present no fundamental reason to think that this goal cannot eventually be accomplished, allowing us to someday build computers that generate much less than 1 bit's worth of physical entropy (and dissipate much less than kT ln 2 energy to heat) for each useful logical operation that they carry out internally"

I wonder if anyone has studied how the average frequency of personal computer buying, i.e., average number of years for a person to buy a new computer, has changed over time since 80s, 90s, and what factors explain the differences. I think I usually can go about 5 years before I start feeling the need to buy a new one. I wonder if that's frequent or not or average.

We just released Kùzu v0.0.3. One of the main features that comes with the new release is support for Pytorch Geometric's Remote Backend support to train GNNs out of memory. If you want to train a large GNN models on a machine that has limited CPU memory, you can store your graph and node features in Kùzu and scale out of memory. The blog post contains a link to a Codelab Notebook to show how to do this.

Other improvements include: data ingestion from multiple files, improvements to query optimization, a new state-o-art buffer manager, new data types including FIXED-LIST for storing node features, query timeouts and interrupts.

Enjoy!

Of course :) Please feel free to write to me when you'd like to have a meeting. Happy to chat anytime! I'll also check out your graph library.

I think Dean De Leo's work in this space is good. It's certainly the right place to start. This work is on using packed memory arrays (pma) but is focused on in-memory versions of pma. I can recommend these two papers: Teseo: https://dl.acm.org/doi/abs/10.14778/3447689.3447708, and Packed Memory Arrays Rewired: https://ieeexplore.ieee.org/abstract/document/8731468. In Kuzu, I/we will be implementing a pma version of our disk-based CSR-baed join indices, which we also use to store relationship properties, so stay tuned for that!