Flexible Graph Comparison Using HMMs

Abstract

Graphs are powerful means for representing structured data. Graph comparison is consequently an important tool for decision support and several techniques have therefore been proposed for comparing two graphs, including Substructure-based techniques, Matrix-based techniques, Graph Kernels and Graph Neural Networks. In addition to their individual limitations, all these existing techniques do not allow the explicit specification of criteria on which the comparison should rely and which intrinsically determine the result of the comparison. The current paper attempts to attenuate the drawbacks of the existing techniques for graph comparison by proposing a flexible technique based on hidden Markov models (HMMs) that offers the possibility to explicitly precise a finite set of properties that must be considered during the comparison. The proposed approach transforms each graph into a set of Markov chains that is later used for initializing, then for training several HMMs. An interpretable descriptor vector associated with each graph is then extracted from the HMMs. The comparison between two graphs is finally performed through the comparison of their corresponding descriptor vectors by using any existing vector distance. Classification experiments conducted on six graph datasets including two real-world datasets demonstrated that, when the suitable set of properties is selected, the proposed approach outperforms existing techniques with accuracy gains reaching +54.38%.

Keywords

• Graph
• graph comparison
• graph modeling
• hidden Markov models