Question: Assuming that there are no known complete graph invariants in the spirit of [Harrsion's question](https://mathoverflow.net/questions/11631/complete-graph-invariants) that do not depend on any labelling (see [graph property](http://en.wikipedia.org/wiki/Graph_invariant) 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?

Answer: 
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?
Though painfully slow to compute, I've yet to find a counterexample to the first invariant proposed in [this](http://arxiv.org/abs/math/0503316) 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)