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?