Graph matching and clustering using kernel attributes

Abstract

In this paper, we exploit graph kernels for graph matching and clustering. Firstly, we analyze different kinds of graph kernels in order to extract from them attributes to be used as a similarity measure between nodes of non-attributed graphs. Next, such attributes are embedded in a graph-matching cost function, through a probabilistic framework, and we evaluate their performance within a graph-matching algorithm. Secondly, we propose a method for obtaining a representative prototype from a set of graphs, which relies on obtaining all the pairwise matchings between the input graphs, and uses the information provided by graph kernels in order to select the matchings that will be considered for obtaining the prototype. Nodes and edges in such a prototype graph register their frequency of occurrence, so that it can be considered a first-order generative model. The proposed method for building prototypes is efficiently integrated into a central clustering algorithm, which allows us to unsupervisedly learn the class-structure of a given set of graphs, and the prototypes representing each class, thus obtaining a central graph clustering algorithm with the same computational cost than a pairwise one. We successfully apply the proposed methods to structural recognition problems.