Multi-Attributed Graph Matching with Multi-Layer Random Walks

Abstract

This paper addresses the multi-attributed graph matching problem considering multiple attributes jointly while preserving the characteristics of each attribute. Since most of conventional graph matching algorithms integrate multiple attributes to construct a single attribute in an oversimplified way, the information from multiple attributes are not often fully exploited. In order to solve this problem, we propose a novel multi-layer graph structure that can preserve the particularities of each attribute in separated layers. Then, we also propose a multi-attributed graph matching algorithm based on the random walk centrality for the proposed multi-layer graph structure. We compare the proposed algorithm with other state-of-the-art graph matching algorithms based on the single-layer structure using synthetic and real datasets, and prove the superior performance of the proposed multi-layer graph structure and matching algorithm.