We investigate ideas from the Geometric Complexity Theory approach to separating complexity classes (Mulmuley & Sohoni, SIAM J. Comput., 2001) in the setting of graph isomorphism. This provides us a playground of finite combinatorial objects on which to explore these techniques. We seek to separate non-isomorphic pairs of graphs using vector spaces of polynomials that are set-wise invariant under permutations (so-called separating modules). We characterize the power of this method for distinguishing graphs under several different complexity measures:
- We show that separating modules of "support-degree" $k$ are equivalent in power to the counts of $O(k)$-vertex subgraphs.
- We show that separating modules of symmetric algebraic circuit size $n^{\Theta(k)}$ are equivalent to $\Theta(k)$-dimensional Weisfeiler-Leman. This generalizes and strengthens the result of Dawar & Wilsenach (CSL '18; ICALP '20; ACM Trans. Comput. Log., 2022; Theory Comput., 2025).
- When considering only the representation-theoretic multiplicities of separating modules, we show that two graphs are separated by multiplicities if and only if their automorphism groups have different multiplicity of cycle types (cycle index).
The latter result is notable in the analogy with GCT, as it is the only result we are aware of in which the multiplicity approach to separating isomorphism types of objects has been given an "intrinsic" characterization in terms of the objects themselves. We show that for graphs, multiplicity obstructions are stronger than occurrence obstructions. We also connect support size (from the study of WL) to complexity measures on $S_n$ (Dafni, Filmus, Lifshitz, Lindzey, & Vinyals, ITCS '21); as well as connections between invariant polynomials, the Graph Reconstruction Conjectures, and Forman's "invariants of finite type" (Adv. Math., 2004).

Updated in response to reviewer feedback. Resolved some open questions from v1.

We introduce an approach to distinguishing isomorphism types of graphs based on vector spaces of polynomials that are set-wise invariant under permutations (“separating modules,” which are representations of the symmetric group), inspired by the Geometric Complexity Theory approach to separating complexity classes (Mulmuley & Sohoni, SIAM J. Comput., 2001). We characterize the power of this method for distinguishing non-isomorphic graphs under several different complexity measures:

- We show that separating modules of "support-degree" $k$ (each monomial touches at most $k$ vertices) are equivalent to the counts of $O(k)$-vertex subgraphs. This is strictly weaker than $O(k)$-dimensional Weisfeiler--Leman (Fürer, ICALP '01).

- We show that separating modules of symmetric circuit size $n^{\Theta(k)}$ are equivalent to $\Theta(k)$-WL. This generalizes and strengthens a result of Dawar & Wilsenach (CSL '18; ICALP '20; ACM Trans. Comput. Log., 2022; Theory Comput., 2025): they proved one direction of this equivalence for invariant polynomials; we generalize to separating modules and prove both directions.

- When considering only the multiplicities of separating modules (as was proposed in GCT by Mulmuley & Sohoni, ibid., rather than the polynomials themselves), we show that two graphs are separated by multiplicities if and only if their automorphism groups have different cycle indices.

The latter result is notable in the analogy with GCT, as it is the only result we are aware of in which the multiplicity approach to separating isomorphism types of objects has been given an "intrinsic" characterization in terms of the objects themselves. We use this to show that for graphs, multiplicity obstructions are stronger than occurrence obstructions. We also connect invariant polynomials to the Graph Reconstruction Conjectures and Forman's “invariants of finite type” (Adv. Math., 2004).