I don't know much about graph databases but there is a whole branch of mathematics called algebraic graph theory [1] which allows for the treatment of graphs algebraically. I took intro graph theory in second year so I have only seen combinatorial approaches but from what I gather it's a pretty powerful field.

[1] https://en.wikipedia.org/wiki/Algebraic_graph_theory

There's a recent category-theoretic framework for them:

https://arxiv.org/abs/1909.04881