Clustering of Attributed Graphs and Unsupervised Synthesis of Function-Described Graphs

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. Also, the supervised synthesis of FDGs from a set of graphs with a common labelling has been addressed previously. In this paper, 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. Results on 3D-object recognition show that these algorithms are effective for clustering a set of AGs and synthesising the FDGs that describe the classes