Once you have found the smallest description of a graph (in your favored scheme), then a philosophically minded person will say, Yes, but how about the smallest description-of-a-description of a graph? And how about the smallest description-of-a-description-of-a-description? Why stop?
These ideas will lead you to the concept of Kolmogorov complexity, where one measures the complexity or information content of a mathematical object by the smallest computational description of it, essentially the size of the smallest program that generates the object. The subject is a part of the emerging theory of computational concepts of randomness, an extremely active current area of research in computability theory. The theory is usually thought of as applied to strings: a string is incompressible if the shortest computational description of it has the same size as itself (thus, the most efficient way to describe it is by explicitly listing it out). Compressible strings, in constrast, have comparatively low information density, since they are describable by a much smaller object. Thus, the graphs you seek to describe are exactly the graphs that are compressible with respect to Kolmogorov complexity.
Thus, I propose that we measure the complexity of a graph on vertices $\{1,2,\ldots,n\}$ by the size of the smallest program able to compute the edge relation. (Let us fix for this purpose a notion of computability, such as Turing machines.) This would correspond to the Kolmogorov complexity, and it will be an extremely robust notion of the measure of the complexity of description of your graph. The class of graphs you have in mind are those that are compressible with respect to this measure, computed by a program that is strictly smaller than the program that simply stores the edge relation in state memory.
There is a small paradox in the subject of computational randomness, since ordinarily one might think of a random string as containing very little information, but in this subject, such strings are incompressible, as it is difficult to describe them exactly except by listing them out explicitly. In this sense, therefore, random strings contain a huge amount of information. Similarly, random graphs are hard to describe in any other way other than by listing the edge relation explicitly.
Because of these ideas, your question (perhaps in extreme form) may ultimately have more to do with logic than with graph theory. Almost any mathematical object can be coded into a graph (in a precise sense, every mathematical structure is interpretable inside a graph), and all such mathematical objects can be ultimately described by strings, to which the Kolmogorv ideas apply. You are asking about are the graphs that are compressible in the sense of Kolmogorov complexity. On cardinality grounds, of course, most graphs are not like this. In general, one should expect Turing noncomputability issues to arise, since the question of whether a given string is compressible is undecidable. Similarly, the question of whether a given finite graph is incompressible is undecidable.
