For a given list of combined graph properties, is there some general strategy of proving that these properties don’t define a graph up to isomorphism?
For example, let’s call $S(G) = (P, D)$ a signature of a graph $G$ with $P$ being the sequence of the shortest distances between each pair of vertices in $G$ and $D$ - the degree sequence of $G$. I want to show that $\forall G_i \forall G_j (S(G_i)=S(G_j) \Leftrightarrow G_i \cong G_j)$ is false.
I can do that by constructing a counterexample. In this particular case it wasn’t difficult but if I include, say, spectrum in the signature, I’ll have to start over.
Is there a more fundamental way to show that a signature is insufficient to define an isomorphic class?
I suppose we cannot consider all possible signatures but perhaps there’s some clever way of reasoning through, for example, information density in a signature being less than $2n^2logn$ bits required for adjacency matrix or some algebraic trick that would allow cutting off certain signatures immediately.
In general, the efficiently-computable combinatorial properties of a graph are insufficient to solve GI. The Weisfeiler--Leman algorithm captures the combinatorial properties of a graph. Precisely, it is equivalent to first-order logic with counting quantifiers.
Cai, Furer, and Immerman (https://people.cs.umass.edu/~immerman/pub/opt.pdf) have a family of counter-examples showing that $\Omega(n)$-dimensional Weisfeiler--Leman is necessary to solve GI. Their examples all have bounded degree, and so are solvable by the group-theoretic methods of Babai & Luks.
It's probably worth looking at the CFI graphs as a test bed.
Also, more recently, Neuen & Schweitzer showed that the individualize and refine paradigm also fails quite badly to resolve GI (https://dl.acm.org/doi/10.1145/3188745.3188900).