Why graphs are universal
Graphs and networks are incredibly universal and applicable, you can use them almost everywhere. It sometimes feels like it’s the language of ‘the game’ as described in The Glass Bead Game. If you are long enough in the game you can also notice that different business domains use graphs in almost the same fashion but with a different terminology. As if there could be a dictionary which translates a solution from one domain onto another. For example, finite state machines (seen as graphs) in digital marketing are very similar to LLM state graphs. Logistic optimization on a transport network reminds one of clinical trials procedures/flows. Few people ever step outside their particular domain of expertise and don’t reflect on it on a higher level. In any case, it probably doesn’t make one’s job easier to reflect and step onto a higher level of abstraction.
As a graph consultant I traverse many different domains and sometimes, even within a day, I have to translate multiple times the same concepts in different dialects. Not speaking of the related technologies which also are almost the same, but not quite. Thinking in triples versus property graphs. Thinking in terms of the NetworkX API versus Cypher queries. Using Torch Geometric versus Neo4j’s GDS. Explaining things via the yFiles API versus Linkurious Ogma. This ‘almost the same’ begs the question: why are graphs so universal? How can one express this mapping from one (business) domain to another?
The language to describe all of these (vague) similarities is called category theory and has been around for a long time. In mathematics it originated from the same kinda observations as above: some domains seem to be using very similar concepts and various results seem to be translatable. Like a crucial theorem in, say, topology could be mapped onto a new theorem in number theory. The resulting framework (categories and functors) is, hence, some sort of meta-language describing other languages. It goes much further than that however. Categories can be used to describe programming languages, database schema’s, social interactions…and on top of that also formalize the mapping.
I don’t wish to explain category theory here but to give you a feeling of how it works I want to present a simple example which illustrates nicely the idea.
In the end, the reason why graphs are universal is because a basic triple (A links to B) captures the essence of all we perceive: there are things (A and B) and they interact with or are related to each other in some way. Just like set theory captures the idea of stuff grouped together or group theory capturing the idea of symmetry, graphs capture the idea that everything is connected in some way. Category formalizes this in a very abstract fashion but this is the layman’s version.
Like often, the basic ingredients are deceptively simple:
- a category consists of objects: the stuff or things you want to talk about.
- objects are connected or mapped via morphisms: arrows, the links, edges, relationships, connections…if you prefer.
These two ingredients are augmented with the following assumptions:
Objects and Arrows: In any category, we have objects (nodes) and arrows (edges) that represent relationships between objects. This is exactly what a graph represents—nodes (vertices) and edges between them.
Composition: The edges (morphisms) in a graph can be composed when there are two arrows such that the target of one arrow matches the source of another, which reflects the composition of morphisms in a category.
Associativity: In a category, the composition of morphisms is associative, which aligns with paths in a graph where following multiple edges respects associativity.
Identity Arrows: Each object has an identity morphism (self-loop), which is a trivial path in the graph that starts and ends at the same vertex.
Because graphs naturally encode these structures—objects (nodes), morphisms (arrows), composition, and identity—they can be used to represent categories and, more generally, the relationships between entities in almost any domain. This makes graphs universal as they can model various systems, whether in mathematics, computer science, social networks, or human activities.
If you have two different categories they might represent very different things but are described in the same basic language: things with arrows. That is, a graph. The idea that one set of stuff can be mapped to another bunch is describe by another type of arrow, called a functor. This captures the idea of translating one domain dialect to another.
With this in place, let me give a concrete example of a human activity one can describe with categories:
Consider the activity of social interactions as a category. Here’s how we can model it:
1. Defining the Category: Let’s define a category ( ), where:
- Objects are people.
- Morphisms (arrows) are interactions or relationships between people. For instance, an arrow ( f: A B ) could represent “Person A communicates with Person B”.
We can think of each person as an object in the category, and interactions between them as morphisms. These interactions could be friendship, communication, or transactions.
2. Composition and Identity:
- Composition of morphisms: If Person A communicates with Person B, and Person B communicates with Person C, there is a natural composition of morphisms ( f g: A C ) representing a chain of communication.
- Identity morphisms: Each person has an identity morphism representing their self-relationship. In a social network, this could represent self-reflection or self-communication.
3. Graph Representation:
We can represent this category as a directed graph: - The vertices (nodes) are people. - The edges are interactions between people. - The composition of edges respects the composition of relationships in the category, and the identity edge is simply a loop at each node.
4. Functor: Mapping to a Real-World Domain
Now we define a functor from the category ( ) to a more concrete domain like email communication. Let’s call this functor ( F ).
- Objects in ( ) (people) are mapped to email accounts in the communication network.
- Morphisms (social interactions) are mapped to emails sent between accounts.
Functor ( F ):
- For each person ( A ), the functor ( F ) assigns an email account ( F(A) ).
- For each interaction (morphism) ( f: A B ), the functor ( F ) assigns the sending of an email ( F(f): F(A) F(B) ).
This functor preserves the structure of the category:
- Identity morphisms: The identity interaction for person ( A ) (self-communication) is mapped to the identity email action (e.g., saving a draft).
- Composition of morphisms: If person ( A ) sends a message to ( B ), and ( B ) forwards it to ( C ), the functor preserves the composition of these interactions in the email domain.
This toy-example gives you an idea how categories formalize things, it also shows the typical abstract leap called mathematics.
Returning to the original question, why are graphs universal? Everything and anything fits into a category and any similarity, mapping or transformation fits into a functor. Since category theory is effectively a special kind of (hyper) graph, graphs are universal. Well, that’s the short plain-English version. If you pick up a book on categories you will discover that the theorems and details are highly abstract and deep. Like often in science, simple concepts can lead to highly sophisticated constructions.
One could could construct a category containing property graph databases and one describing triple stores. Cypher would be mapped to SPARQL and one could describe morphisms from properties to ontologies. This would formalize the feeling of similarities but I suspect few people would benefit from it. It won’t boost anyone’s revenue.
Refs:
If you want the ideas without the maths, the illustrated category theory is a wonderful resource. Category theory for the sciences is a wonderful and very approachable text full of easy to grasp examples. The yellow devil by Mac Lane is the real stuff.