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

AI Engineer · 14 min · 129 sentences · from YouTube's caption track

Each timecode opens YouTube at the start of that sentence. Line anchors (#s42) are the cue ids in the WebVTT, and every line carries its start and end seconds. All transcripts has every talk, and the whole corpus as one file.

00:00Hi, I'm Tim Angers from The Good Collective and welcome to AI Engineer's presentation, a practitioner's guide to graphs, how to make your AI applications smarter, cheaper, and more reliable.
00:14Graphs have always been a powerful foundation of computer science and they look beautiful.
00:19But sometimes they're genuinely not the right tool for the job.
00:23We've all felt the wonder of a mesmerizing data science graph or ogled the graph view of our Obsidian vault.
00:31It can be tempting to rush into something like GraphRAG or rebuilding our e-commerce shop with a graph database.
00:38But often we don't see the instant payoff we might have expected.
00:42In frustration, many journeys end here in the dust at the bottom of the valley of despair and disillusionment.
00:49What's on the other side of the valley and how do we get there?
00:53That's exactly the question that sparked the idea for this talk.
00:56Have I nailed all of the answers?
00:58Definitely not.
01:00But 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.
01:09Many 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-based problems that are ripe for solving in the AI age.
01:23Now, just a quick disclaimer.
01:25This talk isn't going to go into GraphRAG or agent memory graphs.
01:29Not because I'm throwing shade on those patterns and products, but partly because there'll be many other talks covering each of those single topics.
01:37But 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
01:45AI application.
01:47Today, we're going to speed run the basics of graphs.
01:50Then we'll walk through some tips and tricks for building better graphs to get better results.
01:55And then we'll look at graph native algorithms that leverage a graph and the benefits that they deliver.
02:01At 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.
02:14All right, let's speed run the basics.
02:16What's a graph?
02:18A graph is something that has nodes, also called vertices, and edges, which I sometimes call relationships, that connect the nodes together.
02:26That's it.
02:27That is the most basic definition of a graph.
02:30We can have different types of nodes and edges, which convey more meaning.
02:35Uh we can also put labels on edges and nodes and have properties.
02:40And of course, edges can have direction.
02:44Now that we've speed run that, a really, really important part of getting good value out of graphs is how we build good graphs.
02:53Today, we're going to focus on extracting graphs from unstructured text, cuz that's a pretty common use case and a pretty popular one at the moment.
03:01So, 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.
03:16And we say to our agent, "Hey, go and pull the key information out of this thing as subject, predicate, and object triples.
03:25You figure it out."
03:28And then we give it a wrap pancake recipe.
03:31It's done an all right job.
03:32We've got a graph.
03:34But, we wouldn't get very far with this graph.
03:37It's got some problems, so we'll talk through that next.
03:41One of the key principles about building better graphs is giving the extractor a schema to fill.
03:48In this case, if we say, "Instead of using triples, use a recipe.
03:53And a recipe has ingredients, and ingredients have a quantity.
03:57If we give this to an agent with its structured outputs, what we get back is instantly way more meaningful than the graph we had before, and a lot tidier.
04:10So, the benefit here is that with consistent node and edge types, relationships become meaningful and something that we can interrogate or query.
04:19Let'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.
04:29Now, we've got a graph with structure that's starting to look a bit interesting.
04:34Now that we have a well-defined schema and a nicely structured graph, we need to add detail to our ontology.
04:43The ontology describes how to extract information into our graph, or precisely what to put into that structure.
04:50In 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.
05:04These extra instructions are just as important to the title model as the schema is.
05:09And boom, there we go.
05:11We've got lowercase ingredients and metric units.
05:16We know that the best prompt in the world isn't bulletproof, though.
05:19So, we'll look next at how to make sure we really do standardize our units.
05:24Here's an example where we have a couple of ingredients that probably shouldn't be represented by multiple nodes.
05:30We've got garlic cloves and minced garlic, cumin and cumin seeds, vegetable oil and oil.
05:38We've also got plain old garlic down there as well.
05:42So, 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,
05:54but it also strengthens the relationships between the different recipes that have common ingredients.
05:59We'll explain why this is helpful later.
06:02The problem with this naive approach is that we've applied it retrospectively.
06:08And for this to work well, we'd have to know all of the ingredients ahead of time.
06:12Of course, these days, we have embedding models, which take the pain out of this sort of problem.
06:17And 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.
06:29This is a good example of where graph techniques and AI techniques working in hybrid give us the best result.
06:37So, 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.
06:49Let's start talking about what we can do with our graph.
06:53The very first thing we're going to do is just do a simple query to see which recipes contain the ingredient garlic.
07:01We've got the Cypher or graph database query on top, and the relational SQL query below just for comparison.
07:09Here we can see all the recipes that have garlic and their ingredients, which we print to the if they're fit on the slide.
07:16I 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.
07:27In 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.
07:40Stepping things up a notch, the next graph algorithm we've got is the personalized PageRank algorithm.
07:48This is a variant on vanilla PageRank, which was made famous by a certain Brin and Page back in 1998.
07:55It works by having a little dude run around the graph, and he marks each node as he passes.
08:01After a certain amount of hops around the graph, he'll teleport back to the starting node.
08:07And that's the bit that makes it personalized.
08:09It's personalized to our starting node.
08:12By repeating this process until he's completely worn out, some nodes will emerge with more marks on them than others.
08:19These are the nodes that have a stronger relationship with the starting node than those around them.
08:24A really common and popular reference point for personalized PageRank is the Pinterest Pixie paper.
08:30How's that for some alliteration?
08:32Um that showed how PPR could be used for Pinterest recommendations.
08:38But, an even more contemporary one is Hippo Rag, uh which uses some other cool graph techniques as well to link memories to questions and answers.
08:52In the presentation pack, you'll find links and references to different variants and how they can be used.
09:01So, it looked a bit obvious in that last example.
09:04But, 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.
09:14Another real-world example is taking a real-world US Supreme Court case and being able to find the authoritative landmark cases upon which it relies.
09:25In this example, Miranda v. Arizona is not cited in the Canvas v. Sheba case.
09:30It's purely through the relationships in the citation graph that we are able to find it.
09:35Not 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.
09:46Shortest path algorithm is another good way to look at the relationships between two nodes in a graph.
09:52In 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.
09:59In 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
10:11either the symbols or the text or a summary as context.
10:17In 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.
10:29So, 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.
10:38One 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
10:48symbol and reference lookups and the process of figuring that out for ourselves would have been slow.
10:54In one particular evaluation where we used this technique on a .NET code base, 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.
11:09This is another eShop example.
11:11The 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.
11:23We could specify a node type or a node ID in this query and it would still be a subgraph match.
11:28However, in In 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.
11:41We'll search for a decorator pattern in the eShop example, which is commonly used to enhance an existing class.
11:48So, 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.
12:01Boom.
12:02There we go.
12:04In our eShop code base, we found a catalog view model service and a cached version that calls the same class and implements the same API.
12:14If we knew we were looking for caching classes, we could have searched on that.
12:18But, 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,
12:32sometimes it's really important to be able to look for the shape of something without knowing the specific instance or node details themselves.
12:41The benefits of subgraph matching, where you have the opportunity to use it, I think are are quite unique.
12:46It's not so much an optimization problem as like a big enabling algorithm.
12:52It's something that's just not easy to do uh with other tools.
12:58All right.
12:59So, we've covered a lot of ground.
13:01Thanks for bearing with me.
13:02We've looked at navigating paths, at ranking how important things are, and finding patterns.
13:08We'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.
13:23In the presentation back, we'll also include some notes about some of the things that we couldn't get to today like prediction, similarity, and clustering.
13:32These 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
13:43where things get super interesting as well.
13:46We'll have some references and some pointers in the presentation pack.
13:49Otherwise, you can go and explore some of those things on your own.
13:53So, 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
14:01to help make smarter, cheaper, and more reliable AI applications.
14:06Thank you.