Measuring the similarity of labeled graphs

International audienceThis paper proposes a similarity measure to compare cases represented bylabeled graphs. We first define an expressive model of directed labeled graph,allowing multiple labels on vertices and edges. Then we define the similarityproblem as the search of a best mapping, where a mapping is a correspondencebetween vertices of the graphs. A key point of our approach is that thismapping does not have to be univalent, so that a vertex in a graph may beassociated with several vertices of the other graph. Another key point is thatthe quality of the mapping is determined by generic functions, which can betuned in order to implement domain-dependant knowledge. We discuss somecomputational issues related to this problem, and we describe a greedyalgorithm for it. Finally, we show that our approach provides not only aquantitative measure of the similarity, but also qualitative information whichcan prove valuable in the adaptation phase of CBR