How to estimate the similarity of two DAGs

Question

Given two DAGs $G_1(V,E_1)$ and $G_2(V,E_2)$ over the same vertex set $V$. Is there any well-studied measures to check the similarity between $G_1$ and $G_2$? I know the definition of similar is too vague and wondered what definitions exist out there.

Answer 1

This answer is from the point of view of a computer scientist, so bear with me :)

If you generalize the DAGs to have labeled edges, there are the concepts of (bi)-simulation.

In this setting the graph is typically called a Kripke Structure or Transition System denoted by $(S,A,\rightarrow)$ where

• S is a finite set of states (like vertices in a graph}
• A is a finite et of actions
• $\rightarrow \subseteq S \times A \times$ is the transition relation (the edges)

In that case:

A bisimulation is a equivalene relation $R$ on $S$ such that whenever $(s,s') \in R$ the following holds:

• If $(s,a,s_1) \in \rightarrow$ then there exists a transition $(s',a,s_1') \in \rightarrow$ such that $(s_1,s_1') \in R$
• If $(s',a,s_1') \in \rightarrow$ then there exists a transition $(s,a,s_1) \in \rightarrow $ such that $(s_1,s_1') \in R$

A simulation would then be one-directional bisimulation (not necessarily an equivalence relation)

It is usually used to make sure that one "system" can at least do what the other system can do.

If you want a (pseudo)-metric between these labeled transition systems you can define that as well. This link describes three simulation distances:

The correctness distance measures how much the specification must be changed in order to be satisfied by the implementation. The coverage distance measures how much the implementation restricts the degrees of freedom offered by the specification. The robustness distance measures how much a system can deviate from the implementation description without violating the specification