Measure similarity between isomorphic graphs with different node labels

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. • You can maybe use a formula of the type : $\sum_{v \in V} \sum_{k = 1...n}|N_k(v)| \alpha_k \phi(v)$ where $\phi(v)$ is equal to $1$ if the labels do not match on $v$, $N_k(v)$ are the $k$-nearest neighbors, $\alpha_k$ is a decreasing function of $k$, and $n$ is fixed to make the computation tractable. Oct 8 '21 at 9:48
• A better one could be $\sum_{v \in V} \sum_{k = 1...n}\sum_{v'\in V}s_k(v') \alpha_k \phi(v)$ where $s_k(v')$ is the number of $k$-paths from $v$ to $v'$. Oct 8 '21 at 9:57
• What would it change? To compute $\phi$, you just need to compare the labels, it does not matter how they are encoded. Oct 8 '21 at 11:10
• As I understand your problem, your graphs always have an isomorphism and you only want to compute the similarity of graphs on exact isomorphisms (no costs on structural dissimilarity). The first step is probably to compute the automorphism group. If the group is relativey small, then you can compute the dissimilarity on all elements of the group (using for example the dissimilarity I proposed, which is a linear one). If it's bigger, then your problem reduce to optimizing hamming distance on a permutation group (assuming your dissimilarity is linear), and it is NP-hard Oct 13 '21 at 8:14
• If I understand right, you have a sort of automorphism group of a toroidal grid, with only the translational symmetry. You may look at the cyclic hamming distance for string (here on 2d), there are interesting results using fourier transform (cs.stackexchange.com/questions/131994/…), which would give a $n^2log(n)|\Sigma|$ complexity I believe. Oct 13 '21 at 9:48