Measuring similarity of graph nodes by neighbor matching

Abstract

The problem of measuring similarity of graph nodes is important in a range of practical problems. There is a number of proposed measures, usually based on iterative calculation of similarity and the principle that two nodes are as similar as their neighbors are. In our work, we propose one novel method of that sort, with a refined concept of similarity of nodes that involves matching their neighbors. We prove convergence of the proposed method and show that it has some additional desirable properties that, to our knowledge, the existing methods lack. In addition, we construct a measure of similarity of whole graphs based on the similarities of nodes. We illustrate the proposed method on several specific problems and empirically compare it to other methods.