Synthesis of function-described graphs and clustering of attributed graphs

Abstract

Function-Described Graphs (FDGs) have been introduced by the authors as a representation of an ensemble of Attributed Graphs (AGs) for structural pattern recognition alternative to first-order random graphs. Both optimal and approximate algorithms for error-tolerant graph matching, which use a distance measure between AGs and FDGs, have been reported elsewhere. In this paper, both the supervised and the unsupervised synthesis of FDGs from a set of graphs is addressed. First, two procedures are described to synthesize an FDG from a set of commonly labeled AGs or FDGs, respectively. Then, the unsupervised synthesis of FDGs is studied in the context of clustering a set of AGs and obtaining an FDG model for each cluster. Two algorithms based on incremental and hierarchical clustering, respectively, are proposed, which are parameterized by a graph matching method. Some experimental results both on synthetic data and a real 3D-object recognition application show that the proposed algorithms are effective for clustering a set of AGs and synthesizing the FDGs that describe the classes. Moreover, the synthesized FDGs are shown to be useful for pattern recognition thanks to the distance measure and matching algorithm previously reported.