Comparing graphs

Question

I am looking for a kick in the right direction. What i am trying to do is to compute "similarity" between two graphs, where I define "similarity" as the number of shared paths.

example:

G1:   
A - B - C - D
 \     /
    G

G2:  
A - G - C - K - B 

G1 and G2 have similarity 3 (A - G - C) What I am interested in are examples for this particular problem. how is it described. how hard it is to compute? if it is NP-hard is there an approximated solution and how is it computed?

Anything that can be interpreted as a kick in the right direction is welcomed.

thank you

Answer 1

I would try to group your paths in such a way that if two paths can equal each other they end up in the same group. A "can-equal" test, if you will, that you can apply in a single pass through the edges of each graph. It's much better to have a bunch of little groups to cross-product compare with each other than to have one big group.

To group them, I don't know if you can compute a hashcode, or if the nodes have coordinates that can be compared, or the edges have slopes that can be compared, or what. But I think the first step is to try to limit the number of items you have to compare with other items. If you are looking at a general-case solution that applies to any graph without knowing anything about the items in that graph, you either have to model a way for the implementation of that graph to specify some sort of ordering or partitioning, or I think you are out of luck.

Hmm... That sounds a lot like "Use a Hash Table." But how? I think "similar" paths must mean edges between "equal" nodes for some definition of "similar" and "equals."

Load the nodes of each graph into a hashtable/set (one pass through each graph). Then pick the smaller hashtable, and for each node see if it has a corresponding node in the other hashtable. You don't need to consider any nodes that fail this test or any edges that touch nodes that fail that test. Now you only have edges that are contained in both graphs and maybe the size of that set is the similarity value you are looking for? Or maybe it's the largest sub-graph of edges meeting this criteria which is your score?

I think you could still be in the case were a tiny part of an enormous problem is still too big to be practically solvable. But in some cases, this may narrow down the problem enough to make it solvable.

This is my first time attempting an answer in this forum, so I hope that it is helpful.

Answer 2

One popular metric is edit distance.

Although for your problem, it seems close to automata intersection. You start with the empty string then accept a word who's symbols match a path in your graph for both G1 and G2.

Their intersection contains only their shared words.

Answer 3

Both of your graphs have longer paths than the 3-path you show, but you seem to only be matching up paths with identical vertex labels. If so, you should mention in your problem formulation that the labels are important (like instead of looking for similarity between 2 graphs, say 2 labelled graphs. And that you are looking for identically-labelled paths... these are not standard terms, though.)

If this is the correct understanding of your problem, then given your two graphs G1 and G2, create a new graph G3 with vertices from the same set of labels (I notice that your G1 has vertex D while your G2 has vertex K ... if these are different nodes and do not count toward your measure of similarity, then my G3 does not need to include any vertices that are not in one of the initial graphs.)

In G3, only create an edge xy if the edge xy exists in G1 and exists in G2. Otherwise, do not add such an edge. Your problem now asks to find a longest (simple?) path in G3.

That might seem easy for you now, but you should know what any algorithm you write-up for finding the longest path in G3 will likely be exponential time (since finding a longest path is NP-hard as it includes the Hamiltonian Path problem).

At least your G3 will have filtered out vertices and edges that are not common to both G1 and G2, and searching in a single graph should make for neater code than to search through two separate graphs simultaneously.