Almost or probably complete graph invariants? Assuming that there are no known complete graph invariants in the spirit of Harrsion's question that do not depend on any labelling (see graph property at Wikipedia), I wonder if there are graph invariants that are


*

*almost complete, i.e. discriminating almost all finite graphs up to isomorphism

*almost complete in a weaker sense, i.e. discriminating all finite graphs except for a small, but finite fraction (the smaller the fraction the greater the invariant's discriminating power)

*probably complete, i.e. not proven to be incomplete yet (e.g. by counterexamples)


Can anyone provide examples or references?
 A: I'm not sure I understand the question well enough to know whether this is a reasonable answer. But a standard observation concerning the graph isomorphism problem is that there is an approach that feels as though it almost works: work out the eigenvalues and eigenvectors of the adjacency matrix. 
There is a small technical problem that you can't do this exactly, and a more fundamental problem that if you have eigenvalues of multiplicity greater than 1 then you don't distinguish all graphs. But I would guess that almost all graphs have adjacency matrices with distinct eigenvalues. Can anyone confirm this? And if that is the case, does it answer your question?
A: Though painfully slow to compute, I've yet to find a counterexample to the first invariant proposed in this paper by Mehendale: a vector of integers counting, for each n, the number of labeled subgraphs of G which are trees on n vertices.
Update: I've since discovered several counterexamples, perhaps the simplest being
S3 U P2 U P2   
and
P4 U P3 U P1
both of which yield the signature (8,5,3,1)
