NODES AI 2026: Graph Theory and Games: A Case Study on New York Times Connections

In this talk, Shafiq Qureshi presents an analysis of the New York Times game 'Connections' using graph neural networks and graph-based techniques. He discusses the game's popularity since its launch in 2023, emphasizing that all puzzles are human-crafted and exploring the challenge of abstracting non-obvious relationships in word grouping. Qureshi introduces the concept of framing 'Connections' as an augmented graph coloring problem, where strategies involve quantifying puzzle difficulty through semantic relationships and relational alignment scores. He explains the development of an optimal solver built on graph neural networks and reinforcement learning, aimed at improving the AI's ability to classify words correctly based on human-like understanding and contextual relationships. The presentation concludes with reflections on the limitations of AI in solving human-centric problems and future steps for enhancing the game-solving algorithms.

[music] >> All right. So, I'm going to I'm kicking this off. Welcome. Thank you to my um talk on uh the NYT The New York Times Games Connections and our analysis uh using uh different techniques uh specifically on graph neural networks and uh graph-based techniques to understand the game. Uh My name uh I'm Shafiq Qureshi. Uh my title's out of date. I'm actually a a staff software

engineer at the at The Times. Um and I work on our games platform. Uh I previously worked at Business Insider, the NBA, then the Department of Defense. Um I have a background in machine learning, mobile development, and data science. And I have my LinkedIn and other >> [snorts] >> information here in case you're interested in connecting. So, uh let's get to the actual topic. uh few caveats

that the uh work that I am touching on here uh is going to discuss. This is all my own independent research and experimentation and um not based on our internal user research, which is a different uh part of our research. Um the results of this work are generally preliminary, uh though we have written some articles about it, and uh we are doing additional experimentation. Um the purpose

of this uh work is investigatory, not authoritative. So, there are again uh an evolving understanding and discipline and uh area that we're looking into. So, um just keep that in mind. And um there is third-party research with our games, not only Connections, but I'm not going to be talking about uh those uh at this point. So, um I will I will uh Okay, so someone can't see

me, but I think that's fine. Um, Uh, so, okay, so I just wanted to say one thing quickly. Uh, we don't generate any puzzles with AI. They're all human crafted. Just needed to note that. Um, so we'll talk about the game itself. So, presuming everybody here has possibly has played Connections or people have known what the game is about in general. Um, it was launched in 2023

uh, and uh, it's tested and launched in 2023. Um, the game is edited by Will Shortz, a puzzle editor at The New York Times. Uh, it became one of the most played games um, uh, second to Wordle with hundreds of millions of plays within its first year. And again, as I emphasized, the the puzzles are all human crafted. There's no AI in in creation of the puzzles

themselves. To the right is the actual game itself being uh, launched. So, how Connections work. Each daily puzzle provides 16 words to be grouped. The goal is to form four groups of four related words. Um, each word belongs to only one group. There's no overlap between groups. And uh, players can make up to four incorrect guesses before losing the the difficulty structure of Connections. Now, uh, Connections

uh, I'll get into why we um, wanted to like or or consider AI in the structure of the game itself or the play of the game, but uh, the difficulty structure is as follows. Uh, yellow, there's uh, different uh, colors of categories. Yellow is the more obvious category uh, with things that are like more obviously related together. Uh, they're typically the easier words to find. Uh, green

is a slightly less but still conceptually clear category uh, of words that you know, have are a little harder to relate to each other, but then um, do have still a pretty solvable uh, relationship. Blue is the more trickier, uh, word play based categories where there's new themes and other expressions and idioms possibly involved in the, uh, word base itself for that category. And purple has the

the harder category. So people talk about like solving the purple category, um, where it's easy to to potentially mix, uh, get the wrong word in that purple category. This is generally the, um, uh, the difficulty structure of the game, but, uh, you know, there there are some nuances from game to game and puzzle to puzzle, which I'll I'll talk about briefly. Um, so why is, uh, Connections

an interesting game in relation to AI? Uh, so Connections, um, can channel challenge AI's ability to abstract non-obvious relationships. Uh, the game itself, um, is, uh, has is intentional [clears throat] decoys to kind of test people firstly, but other whether and whether AI has the capability to differentiate, uh, what these decoys are. Um, the solutions require clear explainable categories. Uh, so, um, you know, the, we that

is the structure of like understanding that goes into like a a thing that can be repeatedly solved and tested against. And, um, there are fixed inputs and solutions. There are answers that each game actually has. So it's not ambiguous as what the puzzle should be aiming for. Um, and so, uh, I'll I'll get I the the the visual on the right, um, has, uh, essentially, uh, a

much older screen cap, uh, uh, a Connections puzzle, uh, you know, being, uh, solved by attempted to be solved by AI and then AI struggling. Now at this point in time I that the models have advanced pretty far that, um, that no longer is the case that most AI can solve most advanced AI systems can solve Connections boards, but, um, there was quite a a lot a

quite a leap in order for that to occur. Uh it structurally and semantically it it took quite a bit of time. uh that's one thing we wanted to highlight that there was there was a challenge. And then in 2025 is where the you know, it took all the way up to that point since the building of the AI where it became um more feasible for AI to

do this or more complex AI systems to do this on a regular. So, uh just getting into a little bit of the thinking structure before we get into the graph structure, game structure is um how do uh humans solve connections? So, there's the idea of system one versus system two thinking. Um this is a little bit of a spectrum, so it's not exactly um you know, uh

all 100% uh you know, delineated by one or the other, but essentially one type of thinking is sort of fast thinking um uh versus uh more slow thinking uh where you're more deliberately considering things. So, uh either quick decision-making versus um you know, more uh more uh again, deliberate decision-making uh or more reasoning-based uh thinking. And so, uh usually when people are solving a problem, uh they're

using both approaches to suss out a solution. So, that's how essentially how you'd approach a Connections board. You'd activate uh some combination of the two types of thinking in your mind to um uh it assess the board. And depending on the difficulty, you may have to employ one type of thinking reasoning more so than uh if the board wasn't as difficult. And so, again, there's different error

cases. If you made a system one error or a system two error, it depends you were thinking too hard about something or not thinking enough about something that is usually leads to in games like Connections leads to people solving the wrong categories. So, there are benchmarks in Connections. I just want to note that that they do exist. People have attempted to benchmark um that against AI and

in uh got against people solving. So, this is This is known and it's been known for a while. Um in AI in general, there's also benchmarks, but like the benchmark's important because then uh you can persistently test against a particular system to see if it's effective or not at solving the game. And again, older systems have been fed groups of boards have been fed to LLMs make

them more you know trained against being able to solve these puzzles. And this is again 2025 is when the the end of 2025 is when you know the version of this one out. And then there's more going into it for more advanced games and other things that are being worked on but it was it's even even the best system still can trip up very difficult board. So

that's something to note. So quickly a little bit on the theory of the game. Let's talk about just basic structure. So chance there's certain chances of winning connections if you if you play the game and you are thinking about it. If you're totally guessing randomly, your your total chance of winning is one in 63 million. If you like really have no no like structured way that you're

thinking about solving the game. If you uh Let's see. Sorry. One second. If you you know guess one category and the other three categories are random, you still have it's still be about a one in 5000 one in 6000 ish chance in solving which is very low. And then after if you guess two categories correctly, actually your chances of winning if you completely lost in the next

two categories is about almost 3%. So that's where the that's sort of the natural difficulty scaling if we are operating with you know little information from solving each category. I'm presuming here people have heard of the graph coloring problem. If you you know you've basic problem in computer science but the graph coloring problem is essentially a it's a using a you know node-based graph structure which is

you know what this conference is about and what we're here to talk about. It involves assigning colors to vertices of a graph so no adjacent vertices share the same color. There's different versions of the problem as well, but this is this is a core way of approaching structurally before we add additional thrills to this problem to Common algorithms for solving graph problems including include the backtracking algorithms,

greedy coloring, there's other algorithms but they're basic computer science algorithms too and the graph coloring problem has applications all over the spectrum of technology from scheduling, frequency assignment in wireless networks, register allocation in compilers all over the it is very common problem. So, we start off and this is just a start of the you know approach. We start off by framing connections as an augmented graph coloring

problem. So, that means each of the 16 words in the puzzles represented by node or vertex. There's four hidden categories which are the words that haven't been solved yet represented by four distinct colors. The goal is to color each word with one of the four categories of colors such that all four words belong to the same category receive the same color and then the edge can be

thought of as exist a relationship existing between two words that are in the same category. So, that's the basic we haven't gone into any of the nuance or semantic structure of the game, but that's for example if we're building a solver to solve we can back solve using this kind of structure. now let's talk about puzzle difficulty because that's where you know the the light of the

game actually shines. So, we quantify we need to quantify first puzzle difficulty before we can get too deep down you know what is the what is what is the difficulty in the game versus easy parts of the game. So, first of all, the game heavily relies on semantic relationships between words. So, categorization is, you know, where do certain words form in different categories? And so, there could

be different word forms, word meanings, there could be combinations of word forms and word meanings, which have their own category of semantic understanding. So, for example, you'll have something like phonology or answers that like that have a silent w. So, the for example, words that fall in a phonology, same phonologistic category are the word answer, two, wrist, and wrong. So, that could conceivably be a connections category,

right? Or orthographic relationships and anagram relationships. Evil, live, avail, and vile could also be related. That would be a probably a pretty simple one. But again, you have more complex categories as well, which like for example, polysemy, words that could mean a mole can mean have multiple meanings, right? So, this is really the structure of the difficulty of the game. So, we start by looking at a

relational alignment scores to see where the game complexity can be quantified. And relational alignment means that the categories, how how related are words in a particular category. So, the words meaningfully connected within a in a conversation, they will have like similarity scores associated with them, which is also in some texts called coherence. Like do they go to work do groups of words coherently fall into a category?

So, if two words are highly aligned relationally, they the model or anything anything that is reading those words can comprehend those words more easily. There's different types of scores. There's some basic ones like Levenshtein distance or cosine similarity. They're mostly evaluated using natural language processing uh word embeddings, topic modeling, uh other techniques in NLP um which help allow these scores to be quantified. And um they have

uh there's different components uh which I'll get into the next slide of semantic similarity. So, there's not just one score that says these two things are related because again, there's multiple dimensions of uh alignment between words. So, uh comparing relational alignment and scoring between puzzles, the reason why we have this number is so that we can um validate uh difficulty uh of a puzzle. So, here's an

example of an easy puzzle. And with the easy puzzle, there's a high coherence score between the words um versus a harder puzzle which has a lower coherence score. Again, this is what we're tending to. Um the there's there's much more nuance in those alignments, but we'll we'll continue down the path. And then um over time, you can see that there's the difficulty of puzzles changes in terms

of coherence uh because you can see that there's a graph mapping the coherence in each of the categories. Um so, over over like several days for instance or several weeks or several months. So, this is an example. This dip here is just because the puzzle was missing. So, that's it's just kind of a funny thing, but the the key thing is that you can see a fluctuation.

Um So, again, because we're talking in a multi-dimensional world, we have multi-dimensional relational alignments we need to consider. Um so, we have categories of scores. So, this is a radar chart if you're familiar. And um essentially different alignment scores um will show distinct uh distinct um representations or strengths in particular axes as you can see. So, some uh words that have a functional relationship in one category

may be very strong versus another category in the functional relation may be weaker, but some other relationship like domain-specific knowledge might be stronger. Um and so, the again, this is the way of uh ex- understanding the multiple relational alignments that are needed to kind of figure out how tricky a graph is to a system or how tricky a connections board is to a system. And so again,

there's different distributions of the relational alignment scores which you can compute against different boards. This is a tool I built to do that just so I can have sort of like an understanding of like where word difficulty is because using something like this we can then condition a model to to have a similar under in theory condition a model to have a similar understanding of word distribution

difficulty for categories like in connections. So um Now, how do we build a better solver or an optimal solver? An optimal solver that's kind of tricky because we already have solvers that perform pretty well. But the way that I approach solving is from a graph perspective and the reason I did this will sort of become clear. We build a conceptual we start off with a conceptual semantic

graph of the words. So we already have a graph relationship from the coloring problem. We convert it to something that has more of a human understanding of the relationship So if you're familiar with WordNet or ConceptNet, I don't know how many people have seen that before, but WordNet and ConceptNet are the those are two different ontological databases of relationships between words. So for example, WordNet will have

things that are like in the same category like hypernyms or hyponyms or any of those taxonomic relationships that I showed you earlier and ConceptNet will have the relationship between these two words. So for example, milk is related to a cat in a certain way, dog is related to a cat in a certain way, a mouse hunts a mouse is hunted by a cat so there's a relationship

there. A cat is a you know a part of a cat is a claw, a cat can be used for a pet. So, these relationships are crucial to having the machine have more nuanced understanding of how to um you know, to to how to parse categorical relationships and sort the words into the correct categories for the game. And so, we use also convert these to word embeddings

for the machine to understand. So, um we talk about the property graph. I'm not going to go too deep into the property graph itself, but the reason for creating the property graph is to essentially have these have those relationships created uh into properties that can be magnified by the relational alignments that we were just talking about. So, when you have these graph distributions, you can see that

there's a strength between different categories and including the mis- the misdirection categories or misdirected words because some words again are meant to throw people off. Um and you might not be sure if what cat a word belongs to one category or another. So, building this as the in this property graph with the graph topology could help a machine that's trying to understand uh know the difference between

what could be a red herring versus not. So, um next we'll just quickly touch on reinforcement learning. Um I know I'm going through a lot of different topics, but in order no one said that you know, this kind of AI stuff is even for a easy thing like connections is is easy. So, that's just something to uh keep in mind. So, reinforcement learning is basically uh uh

a paradigm in AI where a system learns by interacting with its environment. So, over time the a machine can start off pretty bad at a particular task and then over repetitive interactions it can get better at that task. Um and so, there's a lot of factors that go into reinforcement learning, but what the visual on the right that you see that I constructed is the so-called cart

and pole problem where there's a AI driven cart that's trying to balance a pole and it gets better over time, but it fails a lot in the beginning, similar to how a car is driving on a racetrack. It needs many iterations if it's AI-driven before it can get the curve of the track correct. Now, why that's important is because that's essentially how we needed to approach solving

connections as the game. So, um first, before we uh since this is a machine learning problem, uh we went down going uh building a training and test set. So, building a training and test set required making sure that uh we go to various training test paradigms, which include stratified sampling, uh putting uh categories into putting uh boards into tiers of categories and having um some easy puzzles,

medium puzzles, and difficult puzzles separated out so that the puzzle strategy that the AI would take would be smart enough um to figure out which strategy to uh which which brain to switch to, so to speak. So, that's the idea of a test and training. And then, to build an optimal solver, we needed to uh essentially uh try to build uh go towards since we are representing

and this is a graph problem, um using graph networks and Neo4j, etc., we uh use a custom graph neural network, which I call it RGCNN with reinforcement learning to evaluate and rank similarity metrics. So, what happens is the the This is a neural network specific model. We train the AI to select word groupings based on dynamic coherence signals, and then the AI again goes through the training

process and eventually updates its understanding, uh and that's the typical um uh back propagation that many people who are familiar with neural networks understand, but this is from a graph neural network particular perspective. And then, we check the evolution of the graph over time. I'm not going to go through the details of the system itself, but this is a kind of how the system structure is at

the higher level, um including the persistence layers and feedback loops and other things that go into building this on agent that we built out to test process. again, system diagram piece uh but I essentially this is the visualization of the cluster formulation of the words. So basically the graph neural network essentially tries to group the based on these scores that we talked about relational alignment scores that

learns the best alignments and tries to group the structures into different categories. There's five here. There should be four for each category, but the fifth one represents unknown information that's still to be evaluated. So that's this kind of how the morphology of the system evolves over time as the neural network is learning. Uh the graph network is learning. And so the dynamic updates of the graph structure

is based on the feedbacks incorrect versus incorrect guesses that the machine does over time reinforcement learning process. Um and again, sort of the the there's a blown up view or a hyper dimensional view of how what occurs here is that different clusters are sort of learned and then the agent tries to perform on each of these clusters for particular puzzle. And so the the same again, these

are based on the the difficulty groups in the connections board. And so the ball represents the learning process and the optimal RL process in the space. Um uh for the machine to actually get the to more like best fitted state to solve the particular board. Um so there are some scores and again, this is different than the LLM version of the solving strategy. Um but again, we're

evolving this and experimenting with this for more general cases and trying to understand more about how a system like this evolves for different things other than connections. Um we have performance ways of evaluating performance which includes some standard metrics like grouping accuracy which an example is an NMI score. Um and the whole point is these are supposed to get better over time to reduce uncertainty of the

system. Um, and again, why do all this? Um, LLM is essentially a black box. Uh, you know, they they're great agents are great. Agents can solve a lot of things, but we essentially wanted to build an understandable system grounded in human principles to be able to solve this game. So, using a graph neural network structure, we are able to ground this more in human ontological knowledge to

help it solve the game more as we would and using our own vocabulary and understanding. Um, also that uh, games like this are like, you know, uh, are similar to benchmarks that are uh, being built like are the AGI benchmarks and other benchmarks to actually determine how human that AI intelligence evolves because uh, intelligence uh, is it it it still has limits and those are all grounded

in uh, something called Moravec's paradox. But, here's some of the work by one of the first article is by myself which I've written and then there's some benchmarks and other articles out there which you can take a look at. And if you're familiar with Moravec's paradox, that's where I leave you where the AIs are great at doing certain things and amazing, but they're very they're challenged at

doing simple things that humans can do. Um, so that's um, an example of that. And so, we have some next steps, but I'm at time. So, uh, I will leave the open for questions any if there are any leave this presentation. >> [music]