Many graph matching algorithms follow the approach of node-similarity measurement, that is, matching graphs by means of comparing the corresponding pairs of nodes of the graphs. Based on this idea, the authors propose a high-level schema for node-to-node graph matching, namely N2N graph matching algorithm schema. The chapter shows that such a N2N graph matching algorithm schema is versatile enough to subsume most of the representative node-to-node based graph matching algorithms. It is also shown that improved algorithms can be derived from this N2N graph matching schema, compared with various corresponding algorithms. In addition, the authors point out the limitation and constraints of the propose algorithm schema and suggest some possible treatments.
TopBackground
In 1987, Umeyama proposed an eigen-decomposition based graph matching algorithm (EDGM) for matching both undirected and directed weighted graphs. The EDGM algorithm is critical examined in (Zhao et al., 2007) that EDGM algorithm only works for graphs with single eigenvalues, and improved as meta-basis based graph matching algorithm MBGM, which can be applied for more general cases.
In 1991, Almohamod presented a symmetric polynomial transform based graph matching algorithm (SPGM), where the node similarity of two graphs is constructed by the coefficient of the polynomial transform of the weights of the edges.
In 1999, Kleinberg proposed a hubs and authorities graph matching algorithm (HAGM) for internet searching, where the node similarity is based on the idea that two nodes are similarity if their adjacent nodes are similar. An iterative algorithm is provided to calculate such node similarity. This algorithm has been revised in (Zager & Verghese, 2008).
In 2003, van Wyk & van Wyk presented several Kronecker product successive projection based graph matching algorithms. The graph matching problem is transferred into the Kronecker Product Graph Matching formulation, based on which several approaches are derived, such as the least squares Kronecker product graph matching (LSKPGM) algorithm, the interpolator-based Kronecker product graph matching (IBKPGM) algorithm, the gradient-based Kronecker product graph matching (GBKPGM) algorithm and the orthonormal kernel Kronecker product graph matching (OKKPGM) algorithm.
Although these methods are derived from different theories, they are using the same idea to matching graphs by node similarity. These methods are mostly only applicable for certain kinds of graphs, but they can be easily implemented, analyzed and improved. In addition, most of the node similarity based graph matching algorithms have low computational complexities and are consequently applicable to large size graphs.