An Algebra of Graphs
blogs.ncl.ac.uk
blogs.ncl.ac.uk
Another interesting way to represent directed graphs is using matrices over boolean matrices (also forming an idempotent semiring). Matrices over min, + algebra (also a Kleene algebra) allow us to represent direct graphs with weighted edges and allow us to derive many interesting algorithms, such as the Floyd-Warshall (if we replace the min, + algebra by regular sets we get Kleene's algorithm instead).
I do have a bit of a problem representing arbitrary graphs as matrices since it requires that each graph you're working with be a subgraph of some 'parent graph,' which is where I think this algebra shines since you're allowed to construct arbitrary graphs without much mathematical yoga.[1]
Do you have any references/articles you find particularly interesting in the subjects you mentioned? I'd love to have a bit more in my reading list about it.
------
[1] That isn't to say that I'm discounting super useful things like Smith Normal form, etc.; just that they serve a different purpose than what I believe this article is trying to get at.
I'm not aware of articles treating graphs as Kleene algebras (I haven't looked for them though). Conway's "Regular Algebra and Finite Machines" [1] and Kozen's "A Completeness Theorem for Kleene Algebras and the Algebra of Regular Events" [2] are interesting texts to read on Kleene algebra.
[1] https://www.amazon.com/Regular-Algebra-Finite-Machines-Mathe...
Why do I need the decomposition axiom? I haven't actually provided a motivation for it (or why I defined overlay and connect the way I did). So, here it is: just like LolWolf, I wanted to represent arbitrary graphs and only graphs using expressions, so expression x -> y -> z should be just a graph, and therefore I should be able to construct it from smaller pieces. But what should these pieces be? We can't make it equal to x -> y + y -> z because then our definition of -> would be partial, since it's not always possible to find 'the last node' (in this case y) that we need to connect to z (e.g. the left-hand side may be a cycle). The only choice that seems to work is to connect all vertices on the left-hand side to all vertices on the right hand side, which leads directly to the decomposition axiom.
Note it was actually Quasipolynomial time, not true polynomial time. It's also a pretty recent paper, so it could turn out to have flaws.
On the other hand, it's Babai, so it doesn't. :-)
There is also an article by Tikhon Jelvis[2] that provides a nice and relatively informal introduction to using those ideas in practice.
[1] http://hackage.haskell.org/package/fgl
[2] http://jelv.is/blog/Generating-Mazes-with-Inductive-Graphs/
EDIT: Used dots (.) for the connect operator not to mess up with formatting.
There may even be a nice way of taking elements from the algebra and extending these definitions to fit this idea of '∂' or closure or interior, etc; but I have little intuition for what the algebra might look like and whether it would admit nice expressions of this (personally, I was more motivated by the possible connection to computability theory and languages). Once I have some time, I may sit down and toy around with the idea.
-----
EDIT: I'd like to say this algebra is more general since in the lattice sense, any undirected graph is just equivalent to a poset in which all of the elements are equal (e.g. since x->y+y->x ≅ {x}, where x=y), but there's obviously more interesting structure than that within the graph. In general, there's only truly interesting structure within the graph when the graph has a topological sort (anything else gives elements which are equal under the partial order).
There may be some weirdness where we can take subsets of vertices/edges of graphs and then endow those subsets with lattice structure, which is somehow isomorphic to the original graph, but this is again, not obvious to me how it would be done.
Sure, the 'add' operation is nice (+) since it's just an OR over F_2 (e.g. 0+0=0, 1+0=0+1=1+1=1 [1]) in the matrix representation, but even this involves some bending-over-backwards by noting that you still have to extend the dimensions of the matrices in question in order to even make sense (think about, say (1->2) + (3->4)).
I think the minimal axioms are quite elegant if you ask me.
------
[1] Over F_2, this isn't quite the same addition; I define
a+b ≡ a⊕b + a·b
where ⊕ is XOR and · is AND, which are the usual, defined operations.
EDIT: I guess I didn't mean to say it's not obvious to do these things per se, but rather, a simplistic approach without defining a universe of possible vertices and a mapping from these into indices can't really be done in the linear-algebraic picture.
EDIT: I originally typo'd and proposed the above as a definition of the `overlay` operation, which would be both a pointless circularity and wrong.
It is. Unfortunately I can't fix it now.
So, indeed there is a sort of de Morgan law:
a -- b = !(!a + !b) where ! is the graph edge-complement, a and b do not have common vertices, and -- is a commutative version of ->.
(Responding so late, because I was also "submitting too fast"!)
Agreed; I thought that your `overlay` was the "(forced) disjoint union". I had missed that "(vertex x) `overlay` (vertex y)" was not isomorphic to "(vertex x) `overlay` (vertex x)". I don't even know what negation would mean for directed graphs.
(By the way, your code doesn't seem to give any way of producing inhabitants of `Vertex g`. Since the displayed code only ever uses `Vertex g` in order to promote it immediately to `Graph g`, does it make sense just to have them as a separate type? (Maybe I'm misreading; it's been a while since I've Haskell'd.) Also, am I wrong to read `vertex` as a kind of `return`? (I hope that I am not wrong to think that graphs should serve as just as good instances of monads as lists, if not better.))
While we're talking: thanks for this article; I enjoyed it a lot. My one suggestion is that I think that what you call a "clique" is usually called a "complete graph", with "clique" (implicitly, in G) reserved for subgraphs of G that happen to be complete. https://en.wikipedia.org/wiki/Clique_(graph_theory)
In fully polymorphic code (like clique) you indeed can't produce new inhabitants, or do anything else with the values of type `Vertex g`. However, if you know something about `Vertex g` then you can do certain things. For example, if we know that the type of vertices has `Ord` instance then we can compare them (as we do in `Relation`). And in very concrete code, e.g. operating on `Basic Int` values, you can create new inhabitants freely -- any number will do.
> Also, am I wrong to read `vertex` as a kind of `return`?
It is indeed very much like `return` or `pure`! We use it to inject a type into a sort of container type, in this case, into a graph type.
> I hope that I am not wrong to think that graphs should serve as just as good instances of monads as lists, if not better
Many `Graph` instances are `Monad`s. For example, `Basic` is a `Monad` (and many other things too). But on the other hand `Relation` is not a `Monad`, because it imposes the `Ord` constraint on the underlying type (and Haskell monads are not allowed that).
> While we're talking: thanks for this article; I enjoyed it a lot.
Thank you! I didn't expect so much interest to it, so I'm a bit overwhelmed to be honest :)
> My one suggestion is that I think that what you call a "clique" is usually called a "complete graph", with "clique" (implicitly, in G) reserved for subgraphs of G that happen to be complete.
Thanks, indeed "clique" may be not the best name... I decided to use it, because I would like to reserve "complete graph" to mean something like `clique [1..]` i.e. the complete graph on the whole universe. If we look from this perspective then something like `clique [1..10]` may look like a clique within some bigger graph. Anyway, I admit this may be confusing.
Indeed, I did say that it was a monad and not a `Monad`; math doesn't suffer from these implementation constraints. :-)
> Thanks, indeed "clique" may be not the best name... I decided to use it, because I would like to reserve "complete graph" to mean something like `clique [1..]` i.e. the complete graph on the whole universe. If we look from this perspective then something like `clique [1..10]` may look like a clique within some bigger graph. Anyway, I admit this may be confusing.
Oh, that makes more sense. Maybe it's worth even making just a throwaway remark to that effect?
Ah, I see :-) Indeed, from the mathematical standpoint we can both inject a vertex into the graph type with `vertex`, and flatten a graph whose nodes are graphs (the monad `join`, not to be confused with graph `join` operation that I'm using). I haven't given this much thought before, thanks for noticing this.
> Oh, that makes more sense. Maybe it's worth even making just a throwaway remark to that effect?
I've added the following remark: "we will call such cliques covering the whole universe complete graphs". Hopefully this helps to clarify the naming convention.
A: x x x B: y y y
x x x y y y
x x x y y y
A join B:
x x x 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 x x x 1 1 1
x x x 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 x x x 1 1 1
x x x 0 0 0 + 0 0 0 0 0 0 + 0 0 0 1 1 1 = x x x 1 1 1
0 0 0 0 0 0 0 0 0 y y y 1 1 1 0 0 0 1 1 1 y y y
0 0 0 0 0 0 0 0 0 y y y 1 1 1 0 0 0 1 1 1 y y y
0 0 0 0 0 0 0 0 0 y y y 1 1 1 0 0 0 1 1 1 y y y
Overall, I think both cases have their uses; matrices in the area of computation and abstract algebras where manipulations are straightforward. In particular, I'm interested here since the axioms can be written as a language and operations can be done over finite sets which may yield some nice computability results over this 'language of graphs.'
Just to add: I don't understand why we should compare the algebra and the matrix encoding suggested above. The latter is just one possible implementation (a model) of the former. It's a good, useful model. But the point of having an algebra is that we can abstract of details of particular implementation and instead focus on the laws that all such implementations satisfy. Sometimes these laws can be interesting by themselves (at least they are interesting to me).
Anyways, thanks for the interesting blog post!
But from a design and theory standpoint, I prefer to work independent of the representation as much as possible, and only switch in the matrix language as an implementation of a type in already working code. (Sometimes, this isnt quite possible and you need to, eg, reorder operations to make it efficient to calculate in your representation.)
So I would say that linear algebra is a big deal for implementations, if not as much of one theoretically. (Mostly cause my computer has really fast linear algebra chips/code, and not so much for random graph traversal.)
There's no debate on the merits of computational tractability by converting problems to linear algebra ones; I was speaking from a purely graph-theoretic standpoint.
I would argue that having to drag around the notion of everything being indices + projection tuples constructed from a universal, infinite dimension matrix to be needlessly complex compared to the presented version.
This only seems to get worse when you generalize to multiple edges between a pair of vertices, with your rank 3 infinite tensor being n x n x m, and requiring a canonical way to index edges.
A J
J B
where J is the all one matrix (of the appropriate sizes to make the above matrix square).
Further aside: this block form might seem unnatural, but it pops up all the time in adjacency matrices of graphs. For example, bipartite graphs are exactly those that can be written in the form
0 A
B 0
(Where B = transpose(A))
Or even, give a proof that a graph is a DAG iff there exists a topological sort using only linear algebraic operations on the adjacency matrix.
The point is, I'm sure you can do this; in some sense, we can perform every operation on a graph as we can its adjacency matrix, but why make it so complicated when there are easier pictures to work with?
Why perform surgery with a chainsaw when a scalpel will do without such a mess?
I get that lin alg maybe isn't your picture of elegance, but you can't say that proof is laborious or esoteric. Any intro-level LA course is enough to grok it.
There are plenty of interesting results where linear algebra shines and is beautiful (Kirchoff's theorems for counting trees, random walks on lattices as electrical networks, harmonic functions on graphs, topological data analysis) but there's plenty of statements where linear algebra is a hammer that's wholly unnecessary---statements that are already simple or elegant using other descriptions of graphs.
Though: interesting paper you linked to, thanks for that.
For example, in the algebra I described, you can do 1 -> (1 + 2) and this represents a graph with vertices {1,2} and two edges (1,1) and (1,2). How would that work with your matrix join?
Note that both involve relabelling vertices. Many graph theorists do this freely (it's the same graph), but perhaps you have some application in mind where you don't want to do this.
Since we are supposed to explain downvotes: this seems to me like useless anti-snobbery. Even a minor variation like "Although I believe that I understand matrix addition well, I had difficulty understanding the translation into Haskell" seems more constructive. (On the other hand, CTRL+Fing the article, which I haven't yet read, doesn't show any mention of addition. Are you pointing out that this is matrix addition in a cumbersome disguise? That, too, would have been more useful, without even having to make any linguistic slurs.)
We aren't. If anything, we're encouraged not to talk about vote meta stuff. You can just reply if you want to reply and vote however you want (or not at all), independently of that.
Haskell is a fine language, it's the authors I can't stand. I'm anti-snobbery because snobbery keeps people from understanding stuff. Programming languages are about building a standard and a foundation for common understanding -- Haskell articles are all CV-fodder about byzantine type algebras.
Of course, it's also a matter of the audience you're picking, I wouldn't talk about optimization algorithms, convexity, and computational hardness to an audience of 10-year-olds first learning to program (even though it underlies everything they will do in any first programming class which can be done efficiently), but I also wouldn't discuss introductory programming topics and the definition of a Turing machine to an audience of theoretical computer scientists, even if that's what we end up talking about in a very abstracted sense.
Haskell is certainly not essential to understand or explain the algebra, but having an implementation (in any language!) helps to play with the algebra and experiment with possible models. I am a beginner in Haskell, and that's my current language of choice, as I'm keen to get better at it.
To respond to your comment about matrices: I'm pretty sure one can come up with a matrix-based model (instance) of the algebra. So, no arguments here. In fact, I'd be very interested to see such an instance, to add it to other instances I've found.
What I dislike is the bait-and-switch, wherein the lede implies a digression on an math topic, then the bulk of the content is going over mundane Haskell code.
I don't care if Haskell coders want to get together and code golf their homomorphisms all day, but I find it exploitative to package that up as an excursion into algebra. As someone who's interested in math, but honestly couldn't care less about Haskell, these posts are all noise to me.
Sometimes I find that code works as a clear notation for math. Maybe you just have something against Haskell, but all of this could have been written in any other modern language without too much effort, and I find Haskell to be more on the mathy end. (By the way, I can't tell if you're against Haskell or homomorphisms!)
And I think this really is an excursion into algebra, more on the general algebraic structures end of things. One might say that this describes an algebraic theory of graphs, where your matrix representation is a particular construction which satisfies the theory. The very end, the "Basic" type, feels quite a lot like reading a book on general algebraic structures.
I have some questions about this algebra, like how decompositions work, and maybe I'll think about them sometime.
Are you conflating linear algebra and representation theory, or did you really mean to refer to representation theory in particular? The notion of a quiver (https://en.wikipedia.org/wiki/Quiver_(mathematics) ) seems to me to be a unification of the two fields; I'm not a graph theorist, but I have a hard time imagining that they don't at least consider these structures.