9 ms·

An Algebra of Graphs

184 points by lambdasquirrel 10y ago

PaulHoule 10y ago
This is a big deal for RDF-based systems because you could merge, intersect, and subtract sets of facts quite efficiently this way.
ajamesm 10y ago
Leave it to a Haskell coder to make an incomprehensible mess of matrices under addition.
- LolWolf 10y ago
  Matrices under addition? I know very little of Haskell, but I think this blog post is quite interesting; it's not obvious to me how you would translate the 'join' operator (->) into a matrix formulation that preserves nice structure (you'd have to be weird about dimensions and such). 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.
  - JadeNB 10y ago
    With an obvious notion of negation of graphs, wouldn't the `connect` operation be \g1 g2 -> not $ (not g1) `overlay` (not g2)? (I've already asked about lattice theory elsewhere (https://news.ycombinator.com/item?id=13125334 https://news.ycombinator.com/item?id=13125334 ); this thought makes me wonder if there's any connection to modal logic https://en.wikipedia.org/wiki/Modal_logic https://en.wikipedia.org/wiki/Modal_logic, where modalities are often defined in these sort of "de Morgan pairs".) 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.
    - LolWolf 10y ago
      I'm afraid I don't quite understand what the negation of a graph is in this case and what you mean by 'overlay,' perhaps elaborate a bit?
      - taejo 10y ago
        overlay or + is the operation from the article; not is the graph with the complementary edge set (i.e. `not (V, E) = (V, E \ (V × V))`)
        JadeNB 10y ago
        Yup, that's what I meant (except that I think your set complement is backwards). Sorry for not replying earlier; I was "submitting too fast."
        taejo 10y ago
        > I think your set complement is backwards It is. Unfortunately I can't fix it now.
    - sn0wleopard 10y ago
      JadeNB: This works but I believe only in the case with undirected graphs and if the graphs being connected do not have common vertices. 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"!)
      - JadeNB 10y ago
        > JadeNB: This works but I believe only in the case with undirected graphs and if the graphs being connected do not have common vertices. 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) https://en.wikipedia.org/wiki/Clique_(graph_theory)
  - ajamesm 10y ago
    It's not really 'extending the dimensions of the matrices' -- we live in a universe with an infinite number of distinct vertices, so the matrices are necessarily of infinite degree. It's only the sake of notation that we project them to finite dimensions. 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 This becomes much less accessible when dressing this up as a novel 'algebra of graphs' and obscuring it in Haskell syntax.
    - LolWolf 10y ago
      That's fine, but then in the 'infinite vertices case' we require an associated numbering scheme and defining an ordering over vertices which requires a bijection from whatever set you're working with into an index labeling (⊆ ℕ), etc, when this could just be abstracted away. In general, I don't think this is any cleaner than the few axioms defined whose structure we can attack with the tools of semirings. 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.'
      - sn0wleopard 10y ago
        LolWolf, thank you very much for 'defending' the algebra much better than I could possibly have defended it myself :-) 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).
  - rjtobin 10y ago
    Just a side note: The join of two graphs does correspond to a reasonably nice matrix operation: take the two adjacency matrices A and B (of dim m and n respectively, say), then form an (n+m)x(n+m) block matrix: 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))
    - LolWolf 10y ago
      Yep, I definitely agree! Nominally, there are plenty of interesting results in spectral graph theory which make use of operations like these (esp. when computing laplacians/spectral partitions, etc), but, like most tools, while we can represent many groups/associated structures as linear-algebraic operations, there are subtle results that emerge from looking at an axiomatic treatment which aren't as clear when working with the linear-algebraic picture.
      - ajamesm 10y ago
        Like what?
        LolWolf 10y ago
        Prove that a topological sort exists for a given graph using only linear algebraic properties of the adjacency matrix or the laplacian. 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?
        ajamesm 10y ago
        https://cs.uwaterloo.ca/journals/JIS/VOL7/Sloane/sloane15.pdf https://cs.uwaterloo.ca/journals/JIS/VOL7/Sloane/sloane15.pd... 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.
- JadeNB 10y ago
  > Leave it to a Haskell coder to make an incomprehensible mess of matrices under addition. 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.)
  - pvg 10y ago
    Since we are supposed to explain downvotes 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.
  - ajamesm 10y ago
    Yes, this is matrix addition in a cumbersome disguise. 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.
    - LolWolf 10y ago
      I do agree with the anti-snobbery part, but, again, as someone who totally skipped over the Haskell parts (which were mostly gibberish to me), I still think the article was quite enlightening. 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.
    - 10y ago
- wyager 10y ago
  Ironically, I think you failed to comprehend the article. Adjacency matrices (which you are presumably referring to, but were not mentioned in the article) are neither efficient nor algebraicly convenient. No one represents graphs as matrices in computer science, and graph theorists rarely touch representation theory. It's not that useful when the natural representations are normally much simpler and easier to work with.
  - rjtobin 10y ago
    Not sure it's fair to say that graph theorists rarely use matrices to represent graphs: for many problems in graph theory some of the simplest solution involves representing the graph as a matrix (eg Hoffman-Singleton theorem).
  - ajamesm 10y ago
    Oh, yes, we should definitely draw lessons from academic mathematicians about what is accessible and convenient to understand. THAT's a field that's never had a problem connecting to laymen.
    - Retra 10y ago
      Hard to imagine doing anything interesting if you've got to appeal to laymen with every word.
  - GFK_of_xmaspast 10y ago
    Meanwhile: http://epubs.siam.org/doi/book/10.1137/1.9780898719918 http://epubs.siam.org/doi/book/10.1137/1.9780898719918 https://www.cs.ucsb.edu/~gilbert/talks/GilbertGABB19May2014.pdf https://www.cs.ucsb.edu/~gilbert/talks/GilbertGABB19May2014.... http://graphblas.org/index.php/Graph_BLAS_Forum http://graphblas.org/index.php/Graph_BLAS_Forum http://www.netlib.org/utk/people/JackDongarra/PAPERS/GraphPrimitives-HPEC.pdf http://www.netlib.org/utk/people/JackDongarra/PAPERS/GraphPr... https://people.cs.clemson.edu/~isafro/na13/l12.pdf https://people.cs.clemson.edu/~isafro/na13/l12.pdf
  - JadeNB 10y ago
    > No one represents graphs as matrices in computer science, and graph theorists rarely touch representation theory. 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) 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.
solidangle 10y ago
This is very interesting, but not all that surprising to me. Graphs are closely related to binary relations (on a single set). We can build a binary relation R such that x R y iff there is a directed edge from vertex x to vertex y. It is well known that that the binary relations with the union as the addition, and relational composition (the arrow in the article) as multiplication form an idempotent semiring. If define another unary operation as the reflexive transitive closure of a binary relation (adding a directed edge from a vertex to each reachable vertex) we even form a Kleene algebra, which allows to reason about graphs in terms of regular expressions and regular sets. 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).
- LolWolf 10y ago
  In particular, you can also endow graphs with lattice structures, which yields a bunch of of nice monotonicity/fixed-point/ordering theorems over graphs; computability/hardness of these properties touches some parts of my research areas. 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.
  - solidangle 10y ago
    Yes! Graphs have many interesting algebraic properties. 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-Mathematics/dp/0486485838 https://www.amazon.com/Regular-Algebra-Finite-Machines-Mathe... [2] https://www.cs.cornell.edu/~kozen/papers/ka.pdf https://www.cs.cornell.edu/~kozen/papers/ka.pdf
GFK_of_xmaspast 10y ago
See also : https://en.wikipedia.org/wiki/Graph_operations https://en.wikipedia.org/wiki/Graph_operations
- dbranes 10y ago
  This. The author has discovered the disjoint union and the join. The article looks correct but comes off a little pretentious for describing some rather simple (and well-known) things.
  - deleted 10y ago
    [deleted]
JadeNB 10y ago
The decomposition axiom x \to y \to z = (x \to y) + (x \to z) + (y \to z) looks to me so much like it wants to be an axiom about lattices, like distributivity or modularity or something, in disguise; but I don't know much lattice theory. Is my intuition completely wrong, or could an expert give me the right translation?
- LolWolf 10y ago
  You're actually very much right, in this case, if we choose z to be the preferential element (say, the largest, such that x->y iff x≤y), the addition operation would be the same as 'adding' elements/orderings to the poset in question; this operation does, in fact, form a lattice. 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).
  - JadeNB 10y ago
    Thanks! My question, though, was whether the decomposition axiom is a familiar lattice axiom (such as modularity or distributivity) in disguise.
    - LolWolf 10y ago
      As far as I can tell, I would have to answer that in the negative (see the EDIT in the previous post). In general, the set of graphs is more complicated/general than the set of countable/finite lattices (every lattice can be represented as a DAG by setting a→b iff a∧b=a and b→a iff b∨a=a), which leads me to believe that there is no obvious isomorphism between operations. 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.
  - 10y ago
deleted 10y ago
[deleted]
amelius 10y ago
I was hoping this algebra could have physical significance. For example, you could make a line segment by combining two nodes. You can then combine three such line segments into a triangle. And then you can combine four triangles into a tetrahedron. And you can use techniques from differential geometry. E.g., you could use a "∂" operator to get the boundary of a given structure. And you can transform the graph into an adjacency matrix, and solve differential equations.
- lambdasquirrel 10y ago
  I would love to read even a short post on such applications. One thing I realized while learning abstract math is that abstraction is pretty useless unless you have things to abstract. You don't need to apply any abstractions to what you're doing. Leave that to other people.
  - deleted 10y ago
    [deleted]
- sn0wleopard 10y ago
  I'm the author of the blog post -- thank you for your comment! I was wondering whether anyone would be interested in a different version of the algebra that modells hypergraphs with k-edges. For example, you can change the decomposition axiom to: a.b.c.d = a.b.c + a.b.d + a.c.d + b.c.d, which allows you to have an algebraic structure with nodes, 2-edges (pairs of nodes), and 3-edges (triples of nodes). I can write about this in the following blog post if you are interested. (And I'd love to hear further thoughts from you on the connection to the boundary operator -- do get in touch by email!) EDIT: Used dots (.) for the connect operator not to mess up with formatting.
- LolWolf 10y ago
  These are all well-known things in simplicial geometry [1] which is used everywhere in computational topology and discrete differential geometry. It turns out all of these operations can be done efficiently by considering a matrix over F_2 and considering its several forms. These manipulations lead to a natural (computable!) discretization of differential/topological methods because they're fully constructive and have beautiful theorems. I'd highly recommend looking into it if you're interested. 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. ----- [1] https://en.wikipedia.org/wiki/Simplicial_complex https://en.wikipedia.org/wiki/Simplicial_complex
openasocket 10y ago
Another interesting algebraic structure on graphs is the automorphism group of graphs. For a graph G, the automorphism group is the set of functions f: G -> G such that if (and only if) nodes x and y have an edge between them, f(x) and f(y) have an edge between them. You can think of each such automorphism as a symmetry of the graph. Some very interesting work has been done with this abstraction. In fact, I believe the recent paper claiming to solve the Graph Isomorphism problem in polynomial time makes heavy use of this.
- Chris_Newton 10y ago
  Do you have a reference for that paper about graph isomorphism, please?
  - OJFord 10y ago
    I believe the parent commenter is probably referring to Laszlo Babai's late-2015 paper on quasipoly GI: https://jeremykun.com/2015/11/12/a-quasipolynomial-time-algorithm-for-graph-isomorphism-the-details/ https://jeremykun.com/2015/11/12/a-quasipolynomial-time-algo...
  - openasocket 10y ago
    https://arxiv.org/abs/1512.03547 https://arxiv.org/abs/1512.03547 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.
    - JadeNB 10y ago
      > 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. :-)
egonschiele 10y ago
Super interesting! I'm looking forward to alga being released -- I've been looking for a good graph library for a while.
Chris_Newton 10y ago
These reminds me of the Functional Graph Library[1] in Haskell, which takes similar ideas (edit: about constructing graphs inductively) a lot further. 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 http://hackage.haskell.org/package/fgl [2] http://jelv.is/blog/Generating-Mazes-with-Inductive-Graphs/ http://jelv.is/blog/Generating-Mazes-with-Inductive-Graphs/
eternalban 10y ago
The author's Workcraft work looks very interesting: http://www.workcraft.org/ http://www.workcraft.org/

184 points by lambdasquirrel 10y ago

This is a big deal for RDF-based systems because you could merge, intersect, and subtract sets of facts quite efficiently this way.

ajamesm 10y ago

Leave it to a Haskell coder to make an incomprehensible mess of matrices under addition.

LolWolf 10y ago
Matrices under addition? I know very little of Haskell, but I think this blog post is quite interesting; it's not obvious to me how you would translate the 'join' operator (->) into a matrix formulation that preserves nice structure (you'd have to be weird about dimensions and such). 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.
- JadeNB 10y ago
  With an obvious notion of negation of graphs, wouldn't the `connect` operation be \g1 g2 -> not $ (not g1) `overlay` (not g2)? (I've already asked about lattice theory elsewhere (https://news.ycombinator.com/item?id=13125334 https://news.ycombinator.com/item?id=13125334 ); this thought makes me wonder if there's any connection to modal logic https://en.wikipedia.org/wiki/Modal_logic https://en.wikipedia.org/wiki/Modal_logic, where modalities are often defined in these sort of "de Morgan pairs".) 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.
  - LolWolf 10y ago
    I'm afraid I don't quite understand what the negation of a graph is in this case and what you mean by 'overlay,' perhaps elaborate a bit?
    - taejo 10y ago
      overlay or + is the operation from the article; not is the graph with the complementary edge set (i.e. `not (V, E) = (V, E \ (V × V))`)
      - JadeNB 10y ago
        Yup, that's what I meant (except that I think your set complement is backwards). Sorry for not replying earlier; I was "submitting too fast."
        taejo 10y ago
        > I think your set complement is backwards It is. Unfortunately I can't fix it now.
  - sn0wleopard 10y ago
    JadeNB: This works but I believe only in the case with undirected graphs and if the graphs being connected do not have common vertices. 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"!)
    - JadeNB 10y ago
      > JadeNB: This works but I believe only in the case with undirected graphs and if the graphs being connected do not have common vertices. 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) https://en.wikipedia.org/wiki/Clique_(graph_theory)
- ajamesm 10y ago
  It's not really 'extending the dimensions of the matrices' -- we live in a universe with an infinite number of distinct vertices, so the matrices are necessarily of infinite degree. It's only the sake of notation that we project them to finite dimensions. 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 This becomes much less accessible when dressing this up as a novel 'algebra of graphs' and obscuring it in Haskell syntax.
  - LolWolf 10y ago
    That's fine, but then in the 'infinite vertices case' we require an associated numbering scheme and defining an ordering over vertices which requires a bijection from whatever set you're working with into an index labeling (⊆ ℕ), etc, when this could just be abstracted away. In general, I don't think this is any cleaner than the few axioms defined whose structure we can attack with the tools of semirings. 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.'
    - sn0wleopard 10y ago
      LolWolf, thank you very much for 'defending' the algebra much better than I could possibly have defended it myself :-) 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).
- rjtobin 10y ago
  Just a side note: The join of two graphs does correspond to a reasonably nice matrix operation: take the two adjacency matrices A and B (of dim m and n respectively, say), then form an (n+m)x(n+m) block matrix: 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))
  - LolWolf 10y ago
    Yep, I definitely agree! Nominally, there are plenty of interesting results in spectral graph theory which make use of operations like these (esp. when computing laplacians/spectral partitions, etc), but, like most tools, while we can represent many groups/associated structures as linear-algebraic operations, there are subtle results that emerge from looking at an axiomatic treatment which aren't as clear when working with the linear-algebraic picture.
    - ajamesm 10y ago
      Like what?
      - LolWolf 10y ago
        Prove that a topological sort exists for a given graph using only linear algebraic properties of the adjacency matrix or the laplacian. 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?
        ajamesm 10y ago
        https://cs.uwaterloo.ca/journals/JIS/VOL7/Sloane/sloane15.pdf https://cs.uwaterloo.ca/journals/JIS/VOL7/Sloane/sloane15.pd... 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.
JadeNB 10y ago
> Leave it to a Haskell coder to make an incomprehensible mess of matrices under addition. 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.)
- pvg 10y ago
  Since we are supposed to explain downvotes 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.
- ajamesm 10y ago
  Yes, this is matrix addition in a cumbersome disguise. 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.
  - LolWolf 10y ago
    I do agree with the anti-snobbery part, but, again, as someone who totally skipped over the Haskell parts (which were mostly gibberish to me), I still think the article was quite enlightening. 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.
  - 10y ago
wyager 10y ago
Ironically, I think you failed to comprehend the article. Adjacency matrices (which you are presumably referring to, but were not mentioned in the article) are neither efficient nor algebraicly convenient. No one represents graphs as matrices in computer science, and graph theorists rarely touch representation theory. It's not that useful when the natural representations are normally much simpler and easier to work with.
- rjtobin 10y ago
  Not sure it's fair to say that graph theorists rarely use matrices to represent graphs: for many problems in graph theory some of the simplest solution involves representing the graph as a matrix (eg Hoffman-Singleton theorem).
- ajamesm 10y ago
  Oh, yes, we should definitely draw lessons from academic mathematicians about what is accessible and convenient to understand. THAT's a field that's never had a problem connecting to laymen.
  - Retra 10y ago
    Hard to imagine doing anything interesting if you've got to appeal to laymen with every word.
- GFK_of_xmaspast 10y ago
  Meanwhile: http://epubs.siam.org/doi/book/10.1137/1.9780898719918 http://epubs.siam.org/doi/book/10.1137/1.9780898719918 https://www.cs.ucsb.edu/~gilbert/talks/GilbertGABB19May2014.pdf https://www.cs.ucsb.edu/~gilbert/talks/GilbertGABB19May2014.... http://graphblas.org/index.php/Graph_BLAS_Forum http://graphblas.org/index.php/Graph_BLAS_Forum http://www.netlib.org/utk/people/JackDongarra/PAPERS/GraphPrimitives-HPEC.pdf http://www.netlib.org/utk/people/JackDongarra/PAPERS/GraphPr... https://people.cs.clemson.edu/~isafro/na13/l12.pdf https://people.cs.clemson.edu/~isafro/na13/l12.pdf
- JadeNB 10y ago
  > No one represents graphs as matrices in computer science, and graph theorists rarely touch representation theory. 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) 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.

solidangle 10y ago

This is very interesting, but not all that surprising to me. Graphs are closely related to binary relations (on a single set). We can build a binary relation R such that x R y iff there is a directed edge from vertex x to vertex y. It is well known that that the binary relations with the union as the addition, and relational composition (the arrow in the article) as multiplication form an idempotent semiring. If define another unary operation as the reflexive transitive closure of a binary relation (adding a directed edge from a vertex to each reachable vertex) we even form a Kleene algebra, which allows to reason about graphs in terms of regular expressions and regular sets. 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).

LolWolf 10y ago
In particular, you can also endow graphs with lattice structures, which yields a bunch of of nice monotonicity/fixed-point/ordering theorems over graphs; computability/hardness of these properties touches some parts of my research areas. 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.
- solidangle 10y ago
  Yes! Graphs have many interesting algebraic properties. 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-Mathematics/dp/0486485838 https://www.amazon.com/Regular-Algebra-Finite-Machines-Mathe... [2] https://www.cs.cornell.edu/~kozen/papers/ka.pdf https://www.cs.cornell.edu/~kozen/papers/ka.pdf

GFK_of_xmaspast 10y ago

See also : https://en.wikipedia.org/wiki/Graph_operations https://en.wikipedia.org/wiki/Graph_operations

dbranes 10y ago
This. The author has discovered the disjoint union and the join. The article looks correct but comes off a little pretentious for describing some rather simple (and well-known) things.
- deleted 10y ago
  [deleted]

JadeNB 10y ago

The decomposition axiom x \to y \to z = (x \to y) + (x \to z) + (y \to z) looks to me so much like it wants to be an axiom about lattices, like distributivity or modularity or something, in disguise; but I don't know much lattice theory. Is my intuition completely wrong, or could an expert give me the right translation?

LolWolf 10y ago
You're actually very much right, in this case, if we choose z to be the preferential element (say, the largest, such that x->y iff x≤y), the addition operation would be the same as 'adding' elements/orderings to the poset in question; this operation does, in fact, form a lattice. 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).
- JadeNB 10y ago
  Thanks! My question, though, was whether the decomposition axiom is a familiar lattice axiom (such as modularity or distributivity) in disguise.
  - LolWolf 10y ago
    As far as I can tell, I would have to answer that in the negative (see the EDIT in the previous post). In general, the set of graphs is more complicated/general than the set of countable/finite lattices (every lattice can be represented as a DAG by setting a→b iff a∧b=a and b→a iff b∨a=a), which leads me to believe that there is no obvious isomorphism between operations. 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.
- 10y ago

deleted 10y ago

[deleted]

amelius 10y ago

I was hoping this algebra could have physical significance. For example, you could make a line segment by combining two nodes. You can then combine three such line segments into a triangle. And then you can combine four triangles into a tetrahedron. And you can use techniques from differential geometry. E.g., you could use a "∂" operator to get the boundary of a given structure. And you can transform the graph into an adjacency matrix, and solve differential equations.

lambdasquirrel 10y ago
I would love to read even a short post on such applications. One thing I realized while learning abstract math is that abstraction is pretty useless unless you have things to abstract. You don't need to apply any abstractions to what you're doing. Leave that to other people.
- deleted 10y ago
  [deleted]
sn0wleopard 10y ago
I'm the author of the blog post -- thank you for your comment! I was wondering whether anyone would be interested in a different version of the algebra that modells hypergraphs with k-edges. For example, you can change the decomposition axiom to: a.b.c.d = a.b.c + a.b.d + a.c.d + b.c.d, which allows you to have an algebraic structure with nodes, 2-edges (pairs of nodes), and 3-edges (triples of nodes). I can write about this in the following blog post if you are interested. (And I'd love to hear further thoughts from you on the connection to the boundary operator -- do get in touch by email!) EDIT: Used dots (.) for the connect operator not to mess up with formatting.
LolWolf 10y ago
These are all well-known things in simplicial geometry [1] which is used everywhere in computational topology and discrete differential geometry. It turns out all of these operations can be done efficiently by considering a matrix over F_2 and considering its several forms. These manipulations lead to a natural (computable!) discretization of differential/topological methods because they're fully constructive and have beautiful theorems. I'd highly recommend looking into it if you're interested. 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. ----- [1] https://en.wikipedia.org/wiki/Simplicial_complex https://en.wikipedia.org/wiki/Simplicial_complex

openasocket 10y ago

Another interesting algebraic structure on graphs is the automorphism group of graphs. For a graph G, the automorphism group is the set of functions f: G -> G such that if (and only if) nodes x and y have an edge between them, f(x) and f(y) have an edge between them. You can think of each such automorphism as a symmetry of the graph. Some very interesting work has been done with this abstraction. In fact, I believe the recent paper claiming to solve the Graph Isomorphism problem in polynomial time makes heavy use of this.

Chris_Newton 10y ago
Do you have a reference for that paper about graph isomorphism, please?
- OJFord 10y ago
  I believe the parent commenter is probably referring to Laszlo Babai's late-2015 paper on quasipoly GI: https://jeremykun.com/2015/11/12/a-quasipolynomial-time-algorithm-for-graph-isomorphism-the-details/ https://jeremykun.com/2015/11/12/a-quasipolynomial-time-algo...
- openasocket 10y ago
  https://arxiv.org/abs/1512.03547 https://arxiv.org/abs/1512.03547 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.
  - JadeNB 10y ago
    > 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. :-)

egonschiele 10y ago

Super interesting! I'm looking forward to alga being released -- I've been looking for a good graph library for a while.

Chris_Newton 10y ago

These reminds me of the Functional Graph Library[1] in Haskell, which takes similar ideas (edit: about constructing graphs inductively) a lot further. 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 http://hackage.haskell.org/package/fgl [2] http://jelv.is/blog/Generating-Mazes-with-Inductive-Graphs/ http://jelv.is/blog/Generating-Mazes-with-Inductive-Graphs/

eternalban 10y ago

The author's Workcraft work looks very interesting: http://www.workcraft.org/ http://www.workcraft.org/