Database Reference
In-Depth Information
where graph representations have been successfully used include chemical
structure analysis [1], molecular biology [2], software engineering [3], and
database retrieval [4]. In artificial intelligence, graphs have been success-
fully applied to case-based reasoning [5], machine learning [6], planning [7],
knowledge representation [8], and data mining [9]. Also in computer vision
and pattern recognition graphs are widely used. Particular applications
include character recognition [10], graphics recognition [11], shape analysis
[12], and object classification [13].
In many artificial intelligence applications object representations in
terms of feature vectors or lists of attribute-value pairs are used [14]. On the
one hand, graphs have a much higher representational power than feature
vectors and attribute-value lists as they are able to model not only unary,
but higher order relations and dependencies between various entities. On
the other hand, many operations on graphs are computationally much more
costly than equivalent operations on feature vectors and attribute-value
lists. For example, computing the dissimilarity, or distance, of two objects
that are represented through feature vectors is an operation that is linear
in the number of features, but computing the edit distance of two graphs
in exponential in the number of their nodes [15].
In this chapter we focus on a special class of graphs that is character-
ized by a low computational complexity with regard to a number of oper-
ations. Hence this class of graphs offers the high representational power
of graphs together with the low computational complexity typically found
with feature vector representations. The computational eciency of the
graph operations results from constraining the graphs to have unique node
labels. In particular we are concerned with time series of graphs. In such
series, each individual graph represents the state of an object, or a system,
at a particular point of time. The task under consideration is the detection
of abnormal events, i.e. the detection of abnormal change of the state of
the system when going from one point in time to the next.
Data mining is generally concerned with the detection and extraction
of meaningful patterns and rules from large amounts of data [16,17]. Clas-
sification is considered to be one of the main subfields of data mining [18].
The goal of classification is to assign an unknown object to one out of a
given number of classes, or categories. Obviously, the task considered in
the present paper is a particular instance of classification, where the transi-
tions between the individual elements of a given sequence of graphs are to
be classified as normal or abnormal. From the general point of view, such
a classification may serve as the first step of a more complex data mining
