Distance measures between Attributed Graphs and Function-Described Graphs relaxing 2 nd order constraints

Abstract. The aim of this article is to purpose a distance measure between At-tributed Graphs (AGs) and Second-Order Random Graphs (SORGs) for recog-nition and classification proposes. The basic feature of SORGs is that they in-clude both marginal probability functions and joint probability functions of graph elements (vertices or arcs). This allows a more precise description of both the structural and semantic information contents in a set (or cluster) of AGs and, consequently, an expected improvement in graph matching and object rec-ognition. The distance measure is derived from the probability of instantiating a SORG into an AG. SORGs are shown to improve the performance of other random graph models such as FORGs and FDGs and also the direct AG-to-AG matching in two ex-perimental recognition tasks.