A Practitioner's Guide to Graphs - Tim Ainge, Good Collective

Hi, I'm Tim Ainge from the Good Collective, and welcome to AI Engineers' presentation, "A Practitioner's Guide to Graphs: How to Make Your AI Applications Smarter, Cheaper, and More Reliable." Graphs have always been a powerful foundation of computer science, and they look beautiful, but sometimes they're genuinely not theright tool for the job.

We've all felt the wonder of a mesmerizing data science graph, or ogled to the graph view of our Obsidian vault. It can be tempting to rush into something like GraphRAG or rebuilding our e-commerce shop with a graph database, but often we don't see the instant payoff we might have expected.

In frustration, many journeys end here: in the dust, at the bottom of the valley of despair and disillusionment. What's on the other side of the valley, and how do we get there? That's exactly the question that sparked the idea for this talk.

Have I nailed all of the answers? Definitely not. But what I'm finding is that the more I learn about the fundamentals of graph data structures and algorithms, the more interesting opportunities seem to present themselves. Many of these graph-native use cases, or "good fits for graphs," are also a lovely complement to many of the search, pattern recognition, retrieval, or knowledge base problems that are ripe for solving in the AI age.

Now, just a quick disclaimer: this talk isn't going to go into GraphRAG or agent memory graphs, not because I'm throwing shade on those patents and products, but partly because there'll be many other talks covering each of those single topics.

But more importantly, this talk is for AI builders, and I'd like to focus on the underlying patterns which may just help you come up with your next big graph-powered AI application. Today we're going to speed-run the basics of graphs, then we'll walk through some tips and tricks for building better graphs to get better results, and then we'll look at graph-native algorithms that leverage a graph and the benefits that they deliver.

At each step of the way, we'll open with a principle, look at an easy example and some code, and then finally we'll reference some real-world examples with real-world benefits.

Alright, let's speed-run the basics. What's a graph? A graph is something that has nodes, also called vertices, and edges, which I sometimes call relationships, that connect the nodes together. That's it. That is the most basic definition of a graph.

We can have different types of nodes and edges, which convey more meaning. We can also put labels on edges or nodes and have properties. And of course, edges can have direction. Now that we've speeded around that, a really, really important part of getting good value out of graphs is how we build good graphs.

Today we're going to focus on extracting graphs from unstructured text, because that's a pretty common use case and a pretty popular one at the moment. So in this example, we've defined a very basic data structure for our graph: a triple that has a subject, a predicate, and an object, or a node that somehow relates to another node.

And we say to our agent, "Hey, go and pull the key information out of this thing as subject, predicate, and object triples, you figure it out." And then we give it a bread-and-pancake recipe: "It's done an alright job.

We've got a graph." But we wouldn't get very far with this graph. It's got some problems, and we'll talk through that next.

One of the key principles about building better graphs is giving the extractor a schema to fill. In this case, if we say, "Instead of using triples, use a recipe," and a recipe has ingredients, and ingredients have a quantity.

If we give this to an agent with structured outputs, what we get back is instantly way more meaningful than the graph we had before, and a lot tidier. So the benefit here is that with consistent node and edge times, relationships become meaningful and something that we can interrogate or query.

Let's take this a little bit further to say that a recipe has ingredients, but it also has steps, and each step is the application of a cooking technique. Now we've got a graph with structure that's starting to look a bit interesting.

Now that we have a well-defined schema and a nicely structured graph, we need to add detail to our ontology. The ontology describes how to extract information into our graph, or precisely what to put into that structure. In our case, we want to provide instructions to our agent to standardize the formatting of ingredient names and to standardize units on the metric system to make matching and conversion easier.

These extra instructions are just as important to the target model as the schema is. And boom, there we go, we've got lowercase ingredients and metric units. We know that the best prompt in the world isn't bulletproof, though, so we'll look next at how to make sure we really do standardize our units.

Here's an example where we have a couple of ingredients that probably shouldn't be represented by multiple nodes. We've got garlic cloves and minced garlic, cumin and cumin seeds, vegetable oil, and oil. We've also got plain old garlic down there as well.

So in our first attempt at solving the potato-potato problem, we can see that by taking a naive approach to mapping these, we can eliminate the duplication, which unifies the nodes, but it also strengthens the relationships between the different recipes that have common ingredients.

We'll explain why this is helpful later. The problem with this naive approach is that we've applied it retrospectively, and for this to work well, we'd have to know all of the ingredients ahead of time. Of course, these days we have embedding models which take the pain out of this sort of problem, and by using an embedding model here, we have not only more flexible matching, but we also have the ability to match on terms that we don't need to know in advance.

This is a good example of where graph techniques and AI techniques working in hybrid give us the best result. So now that we have a well-structured graph, we have nicely curated information put into that graph, and we've done extra work to make sure that the nodes are matched or the entities are matched before we create new nodes.

Let's start talking about what we can do with our graph. The very first thing we're going to do is just do a simple query to see which recipes contain the ingredient garlic. We've got the cipher or graph database query on top, and the relational SQL query below, just for comparison.

Here we can see all the recipes that have garlic and their ingredients, which we print so that they fit on the slide. I think if you look at this example, you can see how out of hand the SQL query might get if we wanted to traverse 5, 10, 20 edges to find the nodes that we're looking for.

In a graph query, not only is it a little bit easier and more natural to write, but traversing relationships like that is where the graph data structures start to inherently excel.

Stepping things up a notch, the next graph algorithm we've got is the personalized PageRank algorithm. This is a variant on vanilla PageRank, which was made famous by a certain Bryn & Page back in 1998. It works by having a little dude run around the graph, and he marks each node as he passes.

After a certain amount of hops around the graph, he'll teleport back to the starting node, and that's the bit that makes it personalized. It's personalized to our starting node. By repeating this process until he's completely worn out, some nodes will emerge with more marks on them than others.

These are the nodes that have a stronger relationship with the starting node than those around them. A really common and popular reference point for personalized PageRank is the Pinterest Pixie paper—how's that for some alliteration—that showed how PPR could be used for Pinterest recommendations.

But an even more contemporary one is HIPORAG, which uses some other cool graph techniques as well to link memories to questions and answers. In the presentation pack, you'll find links and references to different variants and how they can be used.

So it looked a bit obvious in that last example, but algorithms like this really shine when we have dense clusters of nodes and relationships, and it isn't that easy to infer which ones are the most important. Another real-world example is taking a real-world U.S.

Supreme Court case and being able to find the authoritative landmark cases upon which it relies. In this example, Miranda v. Arizona is not cited in the campus v. Sheba case. It's purely through the relationships in the citation graph that we are able to find it.

Not only to find it, but to be able to return a string of citations that show how it is related to this existing case through another. Shortest path algorithm is another good way to look at the relationships between two nodes in a graph.

In this case, where we know both nodes in advance and we don't understand the relationships, we can look at the most direct route between them. In this case, if we say, "The checkout code broke after we changed the basket constructor, but I have no idea why," we can traverse the edges between those two nodes in the code graph and return either the symbols or the text or a summary as context.

In this case, the shortest path is highly useful, but we might want the k-shortest paths, or the shortest path that passes through a particular node, or the cheapest path if the edges are weighted. So there are multiple variants, and they're all very useful at telling us what nodes and edges might help explain the relationship between two other nodes on the graph.

One of the benefits of this, being able to retrieve a subgraph as context, is that we wouldn't have found these intermediate nodes by doing vector search, or even by doing individual symbol and reference lookups, and the process of figuring that out for ourselves would have been slow.

In one particular evaluation where we used this technique on a .NET codebase, we saw a 40% reduction in tool calls for code search, where we used techniques like this to identify the context we needed to give the agent.

This is another e-shop example. And one thing I like about this particular example is that instead of starting with a node or a set of nodes and navigating our way through the graph, we're querying entirely on relationships. We could specify a node type or a node ID in this query, and it would still be a subgraph match.

However, in this case, we're searching for code in a certain shape, not knowing anything specific about the code we're looking for or any symbols up front. We'll search for a decorator pattern in the e-shop example, which is commonly used to enhance an existing class.

So what we're looking for is a class that wraps its target class or consumes methods from its target class, where both the wrapper and the target class implement the same interface. Boom, there we go. In our e-shop codebase, we found a catalog view model service and a cached version that calls the same class and implements the same API.

If we knew we were looking for caching classes, we could have searched on that. But if we're looking for a specific pattern, or if we were looking for an anti-pattern, or a particular type of security issue, a malicious transaction pattern, or legal arguments in a big corpus, sometimes it's really important to be able to look for the shape of something without knowing the specific instance or node details themselves.

The benefits of subgraph matching, where you have the opportunity to use it, I think, are quite unique. It's not so much an optimization problem as a big enabling algorithm. It's something that's just not easy to do with other tools.

Allright, so we've covered a lot of ground. Thanks for bearing with me. We've looked at navigating paths, at ranking how important things are, and finding patterns. We've skipped over some of the traditional flow and cost and search algorithms that you might find often used in modeling dependencies or networks, and there's heaps of use cases of those, but I think probably a little bit more run-of-the-mill.

In the presentation pack, we'll also include some notes about some of the things that we couldn't get to today, like prediction, similarity, and clustering. These are now edging into some of the Graph RAG, building dynamic graphs, or schema-less graph kind of territory that we deliberately didn't want to go into today, but it is also where things get super interesting as well.

We'll have some references and some pointers in the presentation pack. Otherwise, you can go and explore some of those things on your own. So I hope that some of these concepts will have given you some insight or inspired you, and that you can take them and either use graph-native algorithms or hybrid algorithms to help make smarter, cheaper, and more reliable AI applications.

Thank you.