# Graph matching with apriori information about the matches?

Given two graphs with n vertices each, where apriori information regarding the similarity of each pair of vertices (between the source and target nodes) is given, is there a known concept for finding the (sub) optimal matching problem?

A "good" solution will match neighbor source vertices to neighbor targets (similarly to the QAP problem), but will also try to maximize the summed source-target similarity of the graph match solution.

• If the similarity between two vertices is modelled with a weight on the edge between these two vertices, and the problem is solved as a maximum weight matching. Is it what you are looking for? Aug 15 at 12:21
• Not quite, there are the edges representing each individual graph and the "theoretical" edges between the graphs, with the weights being the similarity metric. The problem is to find the bipartite matching (between the graphs, like the Hungarian algorithm), but with another constraint, that neighbor source nodes should be matched to neighbor target nodes. Aug 15 at 18:34
• So you have tWo sets of weights on each edge linking both graphs ? Aug 15 at 20:15
• So basically, you want to find a matching in which the source and target nodes are paired. Is that right? Aug 16 at 23:20
• Correct, but the initial knowledge about source-target node similarity should be a constraint, and not only a "seed assumption" about the pairing. Aug 17 at 5:52