Given a labelled directed graph G, I am interested in a measurement of G that captures how distinguishable arbitrary connected sub graphs of G are. Labels may repeat and as such two or more different vertices or edges may have the same label.
I am considering entropy as a measurement for this. Intuitively, it should take more information to encode a distinct graph (one where all vertices and edges are uniquely labelled) than a less distinct graph (where different vertices or edges share the same label). If we take the scenarios that a sender sends all sub graphs of G to a receiver, some sub graphs will appear to be the same when they are not. We can define the set of all indistinguishable subgraphs $X$, and define a probability distribution over $X$ that a subgraph $x \in X$ will be sent uniformly at random by the receiver by gathering frequentist statistics in this sender/receiver game.
I have implemented this, however, it is highly intractable. This is because it requires finding all connected sub graphs of a graph. Beyond a 30 vertex graph, I cannot compute it. Does anybody know of a graph entropy (or perhaps other measure) that captures this property of graphs and is computable?