On Walks: A (Brief) Graph Theory Primer For SEOs & AI/LLM Spaces

Walks.

A starting point, a destination — and a path connecting the two.

Every story has a beginning, middle and end and a walk in its simplest form, is the skeleton of a story in and of itself.

We see stories (literally) everywhere – no matter who you are or where you might be reading this, you’re both writing your own story and are a part of others’ stories as your “walk” through life unfolds. Even this post is a mini-story.

As with any story that you’ve read, the skeleton rarely gives you the full depth of any particular story – they don’t tell you about stakes, obstacles, twists and turns and other events that move the story further toward any particular goal or destination.

That’s kind of the fun of the journey, really — the several paths a story can take, each with different probabilities associated with them occurring at each fork or branch in the path.  Exploring different walks  can fill in the holes in the story, allowing you to see the hidden depth that exists in any particular story space.

Some stories are more interesting than others, but ultimately each comes with its own unique walk that can be evaluated when all is said and done.

And like most topics I discuss on this site and the world in general, walks have a basis and root in mathematics.

A (Semi) Formal Intro To Graph Theory & Walks

The scope of this post (and site in general) is far too narrow to explore the intricacies of graph theory in full, but I believe it’s one of the most hidden, useful branches of mathematics – perhaps even moreso these days.

The ideas are simple – terminology we learned in elementary school; walks, paths, trails, loops, trees, forests – all things you already have intuition about from the “real world”, but in graph theory have formal definitions and uses.

A graph, (semi) formally is a collection of vertices and edges. Edges are lines that connect vertices. Two vertices joined by an edge are adjacent vertices (more on this later); non-adjacent (or independent) if not.

A graph can have any number of vertices, all connected as loosely or tightly as defined by their edge connections. The makeup and characteristics of any graph are virtually endless, but the essence is creating a structure that’s defined by a series of any starting point (vertex) connected to an end point (another vertex) by a line (edge).

There’s a beauty in this simplicity (as often in the abstract world).

There are also formal definitions of walks – an “x-y” walk is defined as an alternating sequence of vertices and edges that begins at vertex “x” and ends at vertex “y”, with each edge in the sequence connecting the vertex that precedes it. The number of edges in a walk is called the length of the walk.

In any walk, repeating edges and vertices are allowed – stronger walks – called trails – are walks where no edge is repeated; walks with no vertices repeated (except the starting and ending points) are called paths. Any path is also a trail, intuitively.

We also have important ideas of completion (all pairs of vertices are connected by an edge) and closure (starting and ending vertices are the same – open if not). A closed trail, for example is called a circuit — and a circuit with no repeated vertices is called a cycle (starting and end points are assumed due to closure). If a graph has no cycles it is acyclic.

A graph is called connected if there exists a path between any two vertices (disconnected if not), which brings us to trees (a connected acyclic graph) and forests (an acyclic graph whose components are trees). A forest is a collection of trees as one would expect.

The Adjacency Matrix

Not to present a “whiplash” effect of sorts, but – as with most fields in mathematics – graph theory has overlaps with other fields; in particular linear algebra, vector spaces and matrices.

If you consider an “n x n” matrix, N – where each entry, n_ij, corresponds to a vertex in some graph (G). n_ij is 1 if vertex i is connected to vertex j, 0 if not.

This is something called an adjacency matrix – and it contains all of the information of the structure of a graph in matrix form. This allows us to access the complement of linear algebra machinery to study graphs.

In particular, you can resolve the number of walks of a particular length in any graph, simply by looking at its adjacency matrix.

If You’ve Worked In Search, This Should All Feel (Very) Familiar

Graph theory can be found in a number of fields (there are some really interesting applications in the wild), but if you’ve worked in search this should all feel (really) familiar to you (search and social, really).

If you consider vertices as web pages and links as edges that connect two web pages – voila – you have the graph theory basis to work off of.

Imagining a user navigating from one web page to another through a link (or several links), you now have virtual “walks” that can be defined, each with their own probability weight of occurring – and generates an adjacency matrix of the larger “web”.

If a particular web page has many incoming links – or links from websites with many visitors, you can imagine more walks will occur to that a particular web page.

Modeling Search/AI/LLM Response Outputs As Walks

When looking at responses from search/AI/LLM spaces, it’s not overly intuitive to see a “walk” in the traditional sense.

Take a response and “unroll” it into a one long string, however, it becomes a little easier to imagine it (this is the picture I’ve had in my head for quite some time).

If you imagine each word, entity, brand – whatever is produced by a response in any sequence – as a series of connected vertices with “hidden” edges (or… links) the picture begins to resolve a bit more clearly.

It’s not hard to think of each response representing a complex “walk” across – and through – its internal representation surface (and supported by RAG and other mechanisms), according to some learned graph structure, then, each with its own dynamic adjacency matrix (with probabilities filling the entries) acting as a transition matrix (transitioning from one set of tokens to the next token), defined by the input (prompt/query).

This is obviously an oversimplification (and will ultimately be less rigid in nature than the ones we find on the web) but when you abstract away the engineering particulars, the similarities become obvious.

When you study responses/results, even with the contextuality phenomenon that can drastically change the trajectory of the outputs, it is – in a way – revealing this graph structure (or structure about particular regions, at least) through the “walks” that result. These walks also can reveal a bit about the observer (user), as well – but I digress.

A dynamic web (graph) available at each sequence step in a response – with probabilities assigned to the most likely next candidate tokens as the response is assembled. A recursive search over a representational candidate space of a graph of tokens, more or less.

As more context (and basis) dimensions are included at the time of input, these walks become constrained to more deterministic paths (smaller adjacency/transition matrices).

(Here we find the connections to the non-classical characteristics of these search/AI/LLM spaces I posted earlier this year – transition matrices in quantum measurement – that I’ll have more notes posted soon).

Final Takeaway For SEOs & Marketers

The story of graph theory is rich in practical uses and has much more depth than I can explore in a single post, however after reading this you should have some grounding in some of its use in search/AI/LLMs.

If you’ve made it here, you’ve gone from the opening vertex to (almost) the final vertex – you’ve successfully traversed your own “walk” through my post’s graph of words – hopefully with a few more dots connected in your own internal knowledge graph along the way.

A starting point, a destination — and a path connecting the two.

Walks.