Are there any 'graphical' algebras that can describe the 'shape' of graphs?
Many people have tried to find an algebraic language to describe the shape of a graph.  This question is essentially the one that motivates structural graph theory.

At the heart of this area of discrete mathematics is the study of graph decompositions.  Some of the people working in this area are Neil Robertson, Paul Seymour, Robin Thomas, Maria Chudnovsky, Kristina Vušković, and their collaborators, although this list is biased by my own research interests.

Particular kinds of graph decompositions have led to some of the most general results in graph theory.  For instance, one of the main technical tools developed for the graph minors project, which led to the Robertson-Seymour theorem, is the graph structure theorem.  This shows that classes of graphs that exclude some minor can be built up from simpler graphs.

In the proof of the Strong Perfect Graph theorem a somewhat different decomposition was used.  The key result is: For every Berge graph $G$, either $G$ is basic, or one of $G, \overline{G}$ admits a proper 2-join, or $G$ admits a balanced skew partition.

The decompositions studied to date are in some sense non-algebraic.  My personal intuition is that there are indications that there is no "nice" system such as the one you seek.  Making this glib statement precise would likely require a nontrivial enterprise in finite model theory, but I suspect it could also lead to interesting new results in graph theory (whether successful or not).