No icon

Multi-attributed Graph Matching with Multi-layer Graph Structure and Multi-layer Random Walks

Multi-attributed Graph Matching with Multi-layer Graph Structure and Multi-layer Random Walks

Abstract:

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

Existing System:

Even though the attributes are integrated using various methods, the information from multiple attributes is not completely utilized in most cases. This is because the existing integration processes are rather simple and do not fully preserve the characteristics of the attributes. Second, the integration methods need to be customized according to the target applications because the applications that are frequently formulated as graph matching problems have diverge characteristics. Actually, designing an appropriate versatile combination of multiple attributes to address various problems is considerably difficult. Moreover, adaptively changing the combination of multiple attributes is also difficult because the integrated attributes cannot be rearranged using conventional integration methods. Third, when using multiple attributes, not all attributes among available attributes are helpful and erroneous or improper attributes should be determined and excluded. In many cases, adopting more attributes for various applications can improve the performance since each attributeĀ  can describe a different aspect of a problem. However, at the same time, it can introduce erroneous or improper attributes and can lead to contradictions between them. In that case, those attributes act as outliers for other attributes.

Proposed System:

We propose a multi-layer graph matching algorithm that jointly considers multiple attributes while preserving the characteristics of each attribute in graph matching.

First, we propose a multi-layer structure to represent multiple attributes, as shown in Fig. 1. The proposed structure consists of multiple layers, in which each layer represents a single attribute, and the layers are closely linked to each other. While a singlelayer structure can lose important information during the multiple attributes integration process, the proposed structure can preserve the characteristics of each attribute in multiple separated layers. Moreover, the proposed structure can redefine the relations between the attributes by adaptively updating inter-layer links during the matching process. Second, we propose a novel multi-attributed graph matching algorithm based on the random walk centrality concept with the proposed multi-layer graph structure. To obtain the centrality values of matching candidates, random walkers traverse the multi-layer association graph according to the transition probability that is derived from pairwise attributes.

Comment As:

Comment (0)