Graph matching using random walks

In this paper we propose a graph matching algorithm which uses random walks to compute topological features for each node, in order to identify candidate pairs of corresponding nodes in the two graphs. The algorithm automatically adapts the number of topological features required to determine the exact match among the nodes. Even if the proposed technique is not guaranteed to provide an exact solution for all graphs, the experiments on a benchmark dataset show that it can outperform other state of the art algorithms with respect to the computational requirements. In fact, the proposed algorithm is polynomial in the number of graph nodes.