Graph isomorphism by invariants

Question

Graph isomorphism is known to be a difficult computational problem. The problem get even worst if we want to find non-isomorphic graphs in a large family of graphs.

Let us call a (numerical) invariant $\alpha$ is good if it is, roughly speaking,

1. simple to compute,
2. fast to compute, and
3. when applied to a family of graphs, say the family $\mathcal{G}_n$ of all graphs of order $\leq n$, the graphs fall into relatively small classes with different $\alpha$-values, that is, $$\lim_{n\ \longmapsto\ \infty}\frac{\max(\text{class sizes})}{\#\mathcal{G}_n}\longrightarrow0.$$

For example, the size of graphs are good invariants as it satisfies the conditions (1), (2), and (3) in the family $\mathcal{G}_n$ of all graphs of order $\leq n$. However, this is not true for the order of graphs in this family. The spectrum can be a candidates in this family, but it is not good in the family of trees.

One technique to overcome the isomorphism problem in large family of graphs is to use good invariants to put graphs into non-isomorphic classes and then try isomorphism check inside each class.

The question is what are best good invariants?

Answer 1

Let me start my answer by noting that this is fundamentally the wrong approach to the problem of reducing a large set of graphs by isomorphism type. The best software (nauty, Bliss, Traces) can put a graph into canonical form in an amount of time similar to what testing two graphs for isomorphism takes. After canonical labelling, you can use a sorting algorithm (or a hash table if it fits in memory) to remove isomorphs quickly. The costly step (canonical labelling) is needed only once per graph, instead of isomorphism testing multiple times per graph.

The advantage of canonical labelling is even more stark if you have a large database of graphs, and you want to determine whether a new graph is already in the database.

Getting back to your question, there is no uniform answer that applies for all classes of graphs. Lorenzo mentioned vertex degrees and you can make that even much stronger by counting the neighbours of each vertex according to their degrees. But as soon as you need to process a large number of regular graphs, this invariant is completely useless. An invariant based on the number of vertices at each distance from each vertex will work well on random regular graphs, but fail completely on strongly regular graphs or incidence geometries. And so on.

There is also the question of how the cost scales. An invariant that takes $n^3$ time to compute might be great when $n=20$, but when $n=10,000$ (well within range of modern programs except for very difficult graph classes) $n^3$ is too much.

The usual use of invariants is not to divide a file of graphs into parts, but to quickly distinguish vertices of each graph from each other as an aid to canonical labelling. But here again there are no known invariants that are efficient and effective for all graph classes.