TLDR: Defining the similarity between two molecules is an open field of research, but is fundamentally a subjective question which depends on your context. If you are interested in the similarity of molecular structures, then a graph-based measure might be a logical choice. If you're interested in similarities of reactivity, then a measure incorporating the electron density or valence electron density might make sense. Ultimately, only you can know which measure makes the most sense for the problem you are trying to solve.
This is a good question and one which does not (and likely never will) have a definitive answer. That is, there will never be a physically correct way to answer how similar two different molecules should be, or even what type of mathematical object that answer should be (i.e. a number, vector, matrix, etc.). Nonetheless, some measure of the similarity between systems is clearly a useful thing to know about, and it is becoming more practical as machine learning becomes more common in chemistry.
From what I have seen recently, many of the most commonly used similarity measures are derived from a representation of a molecule as a graph. I think there are two main reasons for this. First, most people who are interested in molecular similarity are also interested in machine learning. Hence, they are working with a relatively large dataset. Computing a graph representation of a molecule and performing operations on this graph is almost always significantly cheaper than computing some kind of quantum mechanical property for every molecule in your dataset. Second, machine learning projects in chemistry tend to be very collaborative and there many applied mathematicians and computer scientists that know a lot about graph theory and are hence eager to apply this knowledge in a new context.
I have found a review from 2003 which discusses some more chemically motivated methods of defining molecular similarity and some methods based on a graph representation of the molecule. They also discuss a similarity measure based on the overlap a field. The most natural choice for the field being the electron density, though one could choose something like an electrostatic potential or even some kind of magnetic vector potential. What you choose would just depend on what type of similarity you're thinking of.
As an example, you propose using the electron density due to valence electrons. I would be surprised if this hasn't been done before, but I couldn't find any references where this is done. This would be very natural if one is interested in similarities with regards to reactivity. On the other hand, if you were interested in predicting how similar the x-ray absorption spectra of various compounds would be, then it would be stupid to leave out the core electrons from the density as those are the electrons which are most relevant. This further illustrates that the similarity between two molecules is unanswerable because it is not a well-defined question. That is, this similarity will inevitably be connected to some way in which two molecules produce a similar outcome in some physical situation. If you're interested in predicting a molecule which will behave similarly to some other molecule in a reaction, then valence electron density could be a great descriptor, but this descriptor might be entirely useless if you're actually interested in finding molecules with similar x-ray absorption spectra.
Now, chemists have a serious habit of trying to make a connection between everything a molecule does and the structure of that molecule. Very often, this works out extraordinarily well, so chemists keep doing it. I think this is another reason why graph based measures of similarity have become so popular. Virtually all methods of determining molecular similarity based on a graph begin by computing the adjacency matrix of the molecule based on connectivity along covalent bonds (or maybe hydrogen bonds). Then, some operation is performed on a pair of graphs which results in a number or vector or somethings else which is interpreted as a measure of similarity. Or, an operation is performed on each graph individually, and then some measure of distance is used to define the similarity of these graphs. These operations are usually called kernels. A review of some of the kernels which have been used to define graph similarity can be found here.
There are all sorts of tricks which can be played with the adjacency matrix to give some more physical meaning to the measure of similarity. For instance, you might weight each of the edges by the atom-atom distance defining that connection. You might also weight each of the nodes with an atomic charge or polarizability and incorporate this into the adjacency matrix. You might also choose to do this and then work with the laplacian of the graph rather than the adjacency matrix. Anything at all can be done really. You just have to choose what makes sense for your context.
More recently, people have come up with measures that also incorporate similarities of the subgraphs of two graphs. This seems like it has some potential advantages if functional groups, etc. are important to you.
: Nikolova, N., & Jaworska, J. (2003). Approaches to measure chemical similarity–a review. QSAR & Combinatorial Science, 22(9‐10), 1006-1026.
: Rupp, M., & Schneider, G. (2010). Graph kernels for molecular similarity. Molecular Informatics, 29(4), 266-273.
: Kondor, R., & Pan, H. (2016). The multiscale laplacian graph kernel. In Advances in Neural Information Processing Systems (pp. 2990-2998).