Comparing two graph structures with the same number of vertices and edges to see if they are equivalent would be the graph isomorphism problem. The graph isomorphism problem is known to be **NP** in complexity, but it is not known if it is NP-complete nor is it known to be solvable in polynomial time.

Comparing two graph structures with different numbers of edges and vertices would be a slightly bigger problem. Call the graph with the smaller number of vertices $G_1$ and the graph with the larger number of vertices $G_2$. Now you have to search to see if $G_1$ is isomorphic or similar to a subset of $G_2$. Depending on the relative sizes of the graphs, this could take a long time to evaluate.

If you already has a *similarity metric* defined for two graphs with the same number of vertices, e.g. $d(G_a,G_b)$, where $|V_a|=|V_b|$, then you could proceed as follows.

One way to attack the problem is to take the smaller graph as the template and see if you can overlay it onto the larger graph by taking a subset of the vertices of $G_2$, call it $H_n$ where $n$ can be one of the $\binom{|V_2|}{|V_1|}$ ways of picking a subgraph of $G_2$ with the same number of vertices as $G_1$. $|V_1|$= the number of vertices in $G_1$, and $|V_2|$= the number of vertices in $G_2$ in this case.

One similarity metric to use to compare two graphs with the same number of vertices would be to apply a mapping between vertices between $G_1$ and $G_2$, e.g. {$m: V_{1,a} \to V_{2,b}$}.

Then add up the number of coincident edges: for each edge in $G_1$ which connects $V_{1,i}$ and $V_{1,j}$, find the two corresponding vertices in $G_2$ , $V_{2,m(a)}$ and $V_{2,m(b)} $,and see if there is a corresponding edge is $G_2$ between these corresponding vertices.

onegood measure of similarity for graphs. Whatever measures you can come up with will depend on which application you have in mind. – Thierry Zell Sep 11 '10 at 0:22