1
$\begingroup$

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 similarity not only depends on the matchings of the node labels, but also the matchings of the labels of the 1st, 2nd, ... nearest neighbors of each node.

I am looking into graph kernels, especially spectral graph kernels, but they all assign the majority of the weight to topological features, which means I will always get very high similarity scores between two isomorphic graphs.

Can anyone suggest a good algorithm that can measure similarity between isomorphic graphs with different node labels? I have been looking for literatures related to this, but could not find any.

Improve this question
$\endgroup$
2
  • $\begingroup$ There can be more than one isomorphism. Are you considering a fixed isomorphism, an average over isomorphisms, the isomorphism giving the best matching, or something else? $\endgroup$
    – Brendan McKay
    Commented Oct 8, 2021 at 14:25
  • $\begingroup$ @BrendanMcKay If there are multiple isomorphisms, then the similarity should average over the similarity w.r.t. each isomorphism $\endgroup$
    – Shaun Han
    Commented Oct 8, 2021 at 15:07

0

Reset to default

You must log in to answer this question.