Understanding how a given pair of graphs align with each other (also known as the graph matching problem) is a critical task in many search, classification, and analysis applications. Unfortunately, the problem of maximum common subgraph isomorphism between two graphs is a well known NP-hard problem, rendering it impractical to search for exact graph alignments. While there are several heuristics, most of these analyze and encode global and local structural information for every node of the graph and then rank pairs of nodes across the two graphs based on their structural similarities. Moreover, many algorithms involve a post-processing (or refinement) step which aims to improve the initial matching accuracy. In this paper1 we note that the expensive refinement phase of graph matching algorithms is not practical in any application where scalability is critical. It is also impractical to seek structural similarity between all pairs of nodes. We argue that a more practical and scalable solution is to seek structural keynodes of the input graphs that can be used to limit the amount of time needed to search for alignments. Naturally, these keynodes need to be selected carefully to prevent any degradations in accuracy during the alignment process. Given this motivation, in this paper, we first present a structural keynode extraction (SKE) algorithm and then use structural keynodes obtained during off-line processing for keynode-driven scalable graph matching (KSGM). Experiments show that the proposed keynode-driven scalable graph matching algorithms produce alignments that are as accurate as (or better than) the state-of-the-art algorithms, with significantly faster online executions.

Original languageEnglish (US)
Title of host publicationCIKM 2015 - Proceedings of the 24th ACM International Conference on Information and Knowledge Management
PublisherAssociation for Computing Machinery
Number of pages10
ISBN (Electronic)9781450337946
StatePublished - Oct 17 2015
Event24th ACM International Conference on Information and Knowledge Management, CIKM 2015 - Melbourne, Australia
Duration: Oct 19 2015Oct 23 2015

Publication series

NameInternational Conference on Information and Knowledge Management, Proceedings


Conference24th ACM International Conference on Information and Knowledge Management, CIKM 2015

ASJC Scopus subject areas

  • General Decision Sciences
  • General Business, Management and Accounting


Dive into the research topics of 'KSGM: Keynode-driven scalable graph matching'. Together they form a unique fingerprint.

Cite this