Graph matching with type constraints
Catherine Fraikin, Paul Van Dooren · 2007
We consider the problem of comparing two directed graphs with nodes that have been subdivided into classes of different type. The matching process is based on a constrained projection of the nodes of the graphs in a lower dimensional space. This procedure is formulated as a non-convex optimization problem. The objective function uses the two adjacency matrices of the graphs where the nodes are adequately numbered. The constraints on the problem impose the isometry of the so-called projections. An iterative algorithm is proposed to solve the optimization problem. As illustration, we give an example of graph matching for graphs with two types of nodes. Finally, an extension for comparing both groups of nodes in a directed bipartite graph is presented.