The main goal of the thesis is to compare the distinguishing power of known combinatorial and algebraic graph invariants. Using the language of refinement operators (introduced in [32]) we derive known results relating the Weisfeiler-Leman algorithms and the invertible map tests. The former are a well known family of polynomial time algorithms parametrised by some natural number, each defining an equivalence on graphs which over-approximates graph isomorphism. The latter, introduced in [30], are parametrised by a natural number and a set of prime numbers. By generalising the concept of coherent algebras to an arbitrary field, we show that the invertible map tests can be viewed as a representation theoretic generalisation of the Weisfeiler-Leman algorithms. We also show that the equivalences defined by each invertible map test over the set of all prime numbers can be decided in polynomial time. This motivates an open question which could lead to interesting insights into the nature and computational complexity of graph isomorphism, as well as the descriptive complexity of finite graphs.

We also use refinement operators to bound the expressive power of an infinitary logic with solvability quantifiers so as to study the relative power of the invertible map tests and known proof systems with algebraic rules; namely, bounded degree polynomial calculus, monomial calculus and Nullstellensatz calculus. These are well studied and have been used in the context of graph isomorphism in [14] and [39]. Our results generalise some of the work in the latter two papers and contribute to a deeper understanding of the apparently weaker Nullstellensatz calculus. More precisely, we show that the distinguishing power of Nullstellensatz calculus is essentially the same as that of monomial calculus. Furthermore, in the case of fields of characteristic 0, we show that Nullstellensatz calculus can simulate polynomial calculus in the case of the graph isomorphism problem; hence, combining this with a results by Grohe et al. [39], it follows that over characteristic 0, all three proof systems have similar distinguishing power to the Weisfeiler-Leman algorithms.

Building on recent results by Brachter and Schweitzer [16] we look at the behaviour of the Weisfeiler-Leman algorithms on finite groups. Whilst hinting at potential conditions required to construct families of 2-nilpotent groups with high Weisfeiler-Leman dimension, we also show that the class of 2-nilpotent groups generated by trees has low Weisfeiler-Leman dimension. This naturally leads to the question as to whether classes of graphs with low Weisfeiler-Leman dimension generate classes of 2-nilpotent groups with low Weisfeiler-Leman dimension. Lastly, we show that there is a first-order definable reduction from group isomorphism to the isomorphism problem of Latin square graphs of Cayley tables of groups, and vice-versa. The existence of such a bi-interpretation implies that the Weisfeiler-Leman dimensions of finite groups and Latin square graphs of their Cayley tables have a similar asymptotic behaviour.