GraphRAG - The Online Movie Quiz
An online quiz with over half a million questions
Two years ago, I was at an AI conference in San Francisco. After explaining what GraphRAG is many, many times, I realised that a card game could be a useful tool for those explanations. So after the show I wrote a blog about a conceptual game based on that idea:
This led to several requests for a real physical version of the game. So I made one, and it was ready a couple of months later.
The problem with the game was that the graph you can fit on a game board, with card-sized nodes, is quite small. And thus the number of questions you could come up with from that graph was quite few. In the end I only came up with 16 questions. So you could play a two-player game and get 8 questions each, and then you knew all the questions in the game.
But recently I realised that I could overcome that by creating an online game where we aren’t limited by a game board. And with a full graph backing the game we don’t have to pre-write the questions, we can generate them on the fly from the graph. Thus we get a quiz with over half a million possible questions.
The Game
The game can be played here:
The game is designed as an analogy for GraphRAG rather than as a literal GraphRAG application. The player takes the role of the LLM and can answer either unaided or with help from RAG or GraphRAG, with the clue cards representing the retrieved context.
Every question takes the following form:
Who in XXX (xxxx) starred in another movie with YYY (born yyyy)?
The goal is to give as many correct answers as possible in a row before giving an incorrect answer. The number of correct answers is your score. If your score is among the top three scores of all time you get on the high score list.
If you think you know the answer you can just give it directly in the answer field. In the game’s analogy, this is you acting like an unaided LLM: you may get the answer right, but you may also confidently guess incorrectly — in other words, hallucinate.
But to help you, you have two types of lifelines, RAG tokens and GraphRAG tokens. You have two of each kind.
Playing a RAG token will reveal the Clue card on the right, i.e. the XXX movie, which shows you the top five credited actors in that movie. So if you didn’t know who acted in that movie you get some help, the answer will be one of those five.
Playing a GraphRAG token will traverse the full path from the XXX movie to the YYY actor and reveal the intermediate steps, except the answer itself. And using the clues for both the XXX movie and the hidden movie in-between, and seeing the list of actors for both, you only have to cross-check which name appears in both and you have your answer.
The data behind the quiz
As mentioned above, every question is generated on the fly from a graph in a Neo4j Aura instance. This graph has a very simple data model:
As you can see we have producers, writers, directors and composers in our graph as well, but for the current version of the game we only use the ACTED_IN relationships.
I had planned to build the graph from IMDb’s publicly available Non-Commercial Datasets. However, IMDb’s terms do not merely require the use to be non-commercial; they require it to be both personal and non-commercial. Although I do not charge anything for the game, it would be difficult to describe the use as personal once the game was made publicly available online.
Instead I imported the data from Wikipedia, using Wikidata. Through Wikidata I was able to extract movies and people, and also the connections between them. See the appendix below for more details on how I created my graph from Wikidata.
I did not import all movies and people found in Wikidata though. According to IMDb statistics there are more than 750,000 movies ever made and around 16 million cast members from all corners of the world working and acting in those. Most of these would be completely unknown to most of us and would make the game extremely hard, instead I only want to include famous movies and actors, and I had to come up with a way to quantify that. The approach I chose was to count the number of Wikipedia language editions containing an article about each movie or person. I classified an entity as famous if it had an English Wikipedia article and articles in at least 25 other languages.
The resulting filtered graph is what is used for the game, hopefully simplifying the questions a bit. A side effect of that is that there could be an answer other than the one the game has in mind, just through a non-famous movie or actor.
The expected answer for Who in Prince of Persia: The Sands of Time (2010) starred in another movie with Isabella Rossellini (born 1952) is Jake Gyllenhaal (in the movie Enemy from 2013), but there is actually another answer as well. Gemma Arterton starred with Isabella Rossellini in Vita & Virginia from 2018. Gemma Arterton met the criteria for being famous, but Vita & Virginia did not and thus is not part of our dataset (it only has a Wikipedia page in 16 languages).
So bear that in mind as you play — and please don’t throw your coffee mug at the monitor while shouting obscenities about graphs if the game rejects Gemma Arterton as your answer to the question above.
Generating the questions
What makes this especially interesting is that the game demonstrates the value of graphs for RAG while also using graph traversal to generate the questions themselves.
Get Christoffer Bergman’s stories in your inbox
Join Medium for free to get updates from this writer.
What we want to find are actor/movie patterns that match this format:
or, expressed in Cypher syntax:
(p1)-[:ACTED_IN]->(m1)<-[:ACTED_IN]-(p2)-[:ACTED_IN]->(m2)And with the variables above our question would be:
Who in m2.title (m2.year) starred in another movie with p1.name (born p1.born)
And p2.name would represent the answer.
The Cypher syntax for finding one such pattern, a random one, would be:
MATCH (p1:Person)-[a1:ACTED_IN]->(m1:Movie)<-[a2:ACTED_IN]-(p2:Person)-[a3:ACTED_IN]->(m2:Movie)
WHERE p1 <> p2 AND m1 <> m2 AND a1.order < 6 AND a2.order < 6 AND a3.order < 6
RETURN * ORDER BY rand() LIMIT 1We have a predicate for order here because we only want to include the top 5 cast of each movie.
Even though I need only one result, ORDER BY rand() requires Neo4j to assign a random value to every candidate and sort the complete result before returning one of them. Still, thanks to the native graph’s ability to traverse relationships, it manages to find all such patterns among all movies and actors and give me a result in less than a second.
The problem is that these questions may have more than one answer, as with the Jake Gyllenhaal, Gemma Arterton and Isabella Rossellini example above. In that example we couldn’t determine that there was more than one answer since we don’t have Vita & Virginia in our database, but at least we want to rule out all those that we can.
We can do that by adding a predicate that makes sure there is no other connection:
MATCH (p1:Person)-[a1:ACTED_IN]->(m1:Movie)<-[a2:ACTED_IN]-(p2:Person)-[a3:ACTED_IN]->(m2:Movie)
WHERE p1 <> p2 AND m1 <> m2 AND a1.order < 6 AND a2.order < 6 AND a3.order < 6
AND NOT EXISTS {
(p1)-[:ACTED_IN]->(:Movie)<-[:ACTED_IN]-(p3:Person)-[:ACTED_IN]->(m2)
WHERE p3 <> p1 AND p3 <> p2
}
RETURN * ORDER BY rand() LIMIT 1But now it gets heavy, even for a graph database. It has to find all those millions of matches for the original query, and for each of them it must traverse all connections to make sure there is no other solution, before giving us a random one out of those that match (which, as already stated, is more than half a million). On our relatively small instance with just one CPU this takes 5 minutes, a bit much for a quiz game.
Fortunately there is a simple solution. We only need it to find all the results of the first query and order them randomly, and then we only need to apply the predicate to avoid multiple solutions until we find a match. This is the sort of thing that a query planner is really good at, and a benefit of a declarative language like Cypher. But in the previous query it cannot do that since we apply the predicate directly on the original match. Instead we need to separate them like this:
MATCH (p1:Person)-[a1:ACTED_IN]->(m1:Movie)<-[a2:ACTED_IN]-(p2:Person)-[a3:ACTED_IN]->(m2:Movie)
WHERE p1 <> p2 AND m1 <> m2 AND a1.order < 6 AND a2.order < 6 AND a3.order < 6
WITH * ORDER BY rand()
WITH * WHERE NOT EXISTS {
(p1)-[:ACTED_IN]->(:Movie)<-[:ACTED_IN]-(p3:Person)-[:ACTED_IN]->(m2)
WHERE p3 <> p1 AND p3 <> p2
}
RETURN * LIMIT 1This query shape lets Neo4j pass the randomly ordered candidates through the uniqueness predicate and stop as soon as LIMIT 1 has been satisfied. It returns a random qualifying path in just a few seconds. Graphs are cool :)
Conclusion
Thanks to the power of graphs we have been able to create a very dynamic quiz game that demonstrates the power of GraphRAG. If you have read this far without actually testing the game, now is the time to do so and see if you can kick me off the high score list:
The full source code of the game (both frontend and backend) can be found here:
Appendix: Creating a graph from Wikidata
Wikidata provides complete data dumps, but they are enormous. I downloaded the compressed .json.bz2 dump without unpacking it into a second, much larger JSON file. Instead, a Java program streamed it through a BZip2 decompressor and read one entity at a time. Since the dump contains one Wikidata entity per line, Jackson could parse each line separately and discard it before continuing.
During the first pass, I selected entities containing property P345, which stores an IMDb identifier. For each match, I saved the IMDb ID, Wikidata QID, and relevant Wikipedia information to a much smaller CSV file. This became the candidate list for the actual import.
Wikipedia coverage came from the entity’s sitelinks. The key enwiki meant that the entity had an English Wikipedia article. Other keys, such as svwiki, dewiki and frwiki, represented the same subject in other language editions. I counted these while counting only Wikipedia language editions and excluding other Wikimedia projects, such as Wikimedia Commons and Wikivoyage. To qualify for the graph, an entity needed an English article and articles in at least 25 other languages.
A Python importer then fetched current information for the candidates from the Wikidata API. For people, I required P31—instance of—to point to Q5, meaning human, and imported their names and birth and death dates. Movies were identified from their Wikidata types, after which I imported their titles and release years.
Connections were read from the movie entities. Properties for cast members and voice actors became ACTED_IN, while director, producer, screenwriter and composer properties became DIRECTED, PRODUCED, WRITTEN and COMPOSED.
For my game I also needed the credit order of the actors, since I only want to include the top 5 credited actors as we saw above. This was taken from qualifier P1545, but it is only available for fewer than 3% of the connections. But investigating those 3% showed that the statement position in Wikidata corresponds fairly well with the actual credit order, and so I used that instead for the other 97%. In the first import I set the order property from the P1545 field and the statement position as altOrder, and then I combined it into one, sorted, order like this:
MATCH (:Person)-[actedIn:ACTED_IN]->(movie:Movie)
WITH movie, actedIn
ORDER BY
movie.id,
coalesce(actedIn.order, actedIn.altOrder),
CASE WHEN actedIn.order IS NULL THEN 1 ELSE 0 END,
actedIn.altOrder,
elementId(actedIn)
WITH movie, collect(actedIn) AS credits
UNWIND range(0, size(credits) - 1) AS creditIndex
WITH credits[creditIndex] AS actedIn, creditIndex
SET actedIn.order = creditIndex + 1
REMOVE actedIn.altOrder
RETURN count(*) AS relationshipsUpdated;Now I had a full graph of famous movies to be used for the game.
