Overview

We will use the concepts of graph similarity, graph distance, and graph matching in the following chapters as they form a basis for the novel approaches we have developed for performing clustering and classification tasks using graphs instead of more restrictive vectors. The purpose of the current chapter is to give a literature survey of the various methods that are used to determine similarity, distance and matchings between graphs as well as introduce the formal notation which will later be necessary to describe our algorithms. These topics are closely related to the topics of inexact graph matching or graph similarity, and several practical applications that utilize graph similarity or graph matching are represented in the literature, many of them in the field of image processing. Haris et al. performed labeling of coronary angiograms with graph matching [HEM ⁺99]. In Ref. [PM99] a method for allocating tasks in multiprocessor systems using graphs and graph matching is described. In Ref. [HH99] Huet and Hancock describe a graph matching method for shape recognition in image databases. Another area where graph similarity and matching is popular is in chemistry, due to the natural representation of chemical structures ( e.g. molecules) as graphs [Gro85][Owo88]. For a recent review of graph matching techniques used in pattern recognition, see Ref. [CFSV04].

In this book we are specifically interested in using graph techniques for dealing with web document content. Traditional learning methods applied to the tasks of text or document classification and categorization, such...