I am using graphs to represent some structured data. In my case, I have a time series of undirected unweighted graphs with the same topology (i.e. isomorphic graphs with same number of nodes and edges, and same connections). The only thing keeps changing over time are (some of) the node labels. In my case, the node labels are discrete (categorical labels). I want to use some kind of measurement to describe the similarity (or dis-similarity) between two given isomorphic graphs with different node labels. Note that this is fundamentally different from comparing two sequences in the sense that the local similarity at each node not only depends on the matchings of the node label, but also the matchings of the labels of the 1st, 2nd, ... nearest neighbors.
I am looking into graph kernels. In theory, there should be a significant speed-up given the graph topology is fixed, since one can precompute an original kernel and reuse it with different label distributions for different isomorphic graphs. However, I found that all common graph kernels assign the majority of the weight to topological features, which means I will always get very high similarity scores between two isomorphic graphs, even with completely different sets of node labels, which I would expect the similarity to be 0 in this case.
Can anyone suggest a good algorithm that can measure similarity between isomorphic graphs with different node labels? I have been looking for literature related to this, but could not find any. Any suggestion is appreciated.
Edit: note that there can be multiple isomorphisms. For example, as depicted below, $G_1$ and $G_2$ have different node labels at node 1, 3, 4, but they are completely identical, so they should have the highest similarity. This means that any similarity measurement that compares node labels by indices is incorrect.
This paper might be what you're looking for. You can phrase the algorithm as an eigenvalue problem. I remember implementing it, but it's kind of confusing until you look up what the different matrix products mean. Good luck!