A critical examination of node-similarity based graph matching algorithms

G. Zhao, Miltiadis Petridis, G. Sidorov, J. Ma

Research output: Contribution to journalArticlepeer-review


In this paper, we shall critically examine a special class of graph matching algorithms that follow the approach of node-similarity measurement. A high-level algorithm framework, namely node-similarity graph matching framework (NSGM framework), is proposed, from which, many existing graph matching algorithms can be subsumed, including the eigen-decomposition method of Umeyama, the polynomial-transformation method of Almohamad, the hubs and authorities method of Kleinberg, and the kronecker product successive projection methods of Wyk, etc. In addition, improved algorithms can be developed from the NSGM framework with respects to the corresponding results in graph theory. As the observation, it is pointed out that, in general, any algorithm which can be subsumed from NSGM framework fails to work well for graphs with non-trivial auto-isomorphism structure.
Original languageEnglish
Pages (from-to)73-82
Number of pages10
JournalResearch in Computing Science
Publication statusPublished - 1 Jan 2008


  • Graph matching
  • node-similarity


Dive into the research topics of 'A critical examination of node-similarity based graph matching algorithms'. Together they form a unique fingerprint.

Cite this