A context graph of a one-valued context is a graph which has formal objects as its vertices, and whose edges connect the objects in such a way that concept extents form connected subgraphs of this graph. This allows to retrieve objects similar to a given object by a recursive traversal of that objects neighborhood. The approach has been introduced in [1] and is considered as a potential model for information retrieval. In this paper, context graphs for many-valued contexts are introduced. The de nition bases on descriptions, which were introduced in [2], and basically allows to construct context graphs without transforming the many-valued context into a one-valued context. It is examined how the structure of the context graph, which is based on similarity of objects, can be used to nd objects in the graph based on a particular description. Finally, scale graphs are proposed as a method to incorporate knowledge about an attribute domain into the structure of the context graph.
The concept lattices of Formal Concept Analysis (FCA) [3] have been studied and utilized as structural models for information retrieval (IR) by a number of researchers. The advantage concept lattices have to o er is that they support the combination of two principal ways of user interaction with an information retrieval system: querying and browsing. The most basic idea of such an application, described e.g. in [4], is that a subset of the attributes of a formal context is understood as a query by the system. The corresponding result set is the concept extent generated by the attributes in the query. This way, every query positions the user in a concept node of the lattices Hasse diagram, and the system can then present an option to the user to move to a lower or upper neighbor of the current node. Such a step in the diagram corresponds to a minimal re nement or extension of the result set, and this is how browsing is realized.
The complexity of the Hasse diagram sets a natural limit to the size of formal contexts for which the Hasse diagram can be realistically computed. More recent publications present ways how these limits can be advanced, in addition to presenting more sophisticated user interfaces [5{7]. In [1] we have introduced a graph representation of a formal context that we call a context graph, and have motivated them as a potential alternative to the concept lattice in IR applications and beyond. The nodes of a context graph are objects of a formal context, and these are connected by edges in such a way that every concept extent is a connected subgraph within the context graph. We will generally assume that the graph has no more edges than necessary for this property to hold. The rationale of this approach is that, in an IR application, as soon as one object matching a given query is found, all other matches can be retrieved by recursively traversing that objects neighborhood. Moreover, the conceptual hierarchy of the lattice is contained in the context graph as a system of subgraphs, which means that navigating in the lattice (aka \browsing\) can be simulated in the graph (although some search may be involved). An example context graph for the \Living Beings and Water" context (Fig. 3) is shown on the left of Fig. 4.
So far context graphs and the algorithm for their construction in [1] have only been de ned for contexts with one-valued attributes. In a practical scenario however, objects that one might want to nd in an IR system are more likely to be described by many-valued attributes (e.g. price or location). In FCA, the classic approach of dealing with many-valued attributes is to translate a manyvalued context into a one-valued context by means of conceptual scaling [3], but other ways of generating a lattice from a many-valued context have been proposed (see e.g. [2, 8]). In this paper we will follow the approach of Gugisch using descriptions [2]. In Sect. 3, the de nition of context graphs and the pivotal notion of a compliant path are reformulated in terms of descriptions and we show that the resulting context graphs are equivalent to what we would obtain by conceptual scales. Thus we provide a true generalization of context graphs into the setting of many-valued attributes. An adaptation of the construction algorithm from [1] is straightforward and will not be discussed here.
A context graph could be likened to a kind of semantic map, where objects are distributed according to their similarity. This leads to believe that it may be possible to nd an object in the graph that matches a given description by starting in some arbitrary vertex and following along a path of subsequently better matches. This will be examined in Sect. 4, using the notions developed in Sect. 3.
Finally, in Sect. 5 we brie y present the idea of scale graphs. Scale graphs are context graphs of a scale and therefore express similarity between attribute values. The proposed idea is that attribute domains can be intuitively modeled by drawing a graph and then de ning an appropriate scale which has this graph as a context graph. The scale graph will then be re ected in the structure of any context graph created with the corresponding scale. 2 2.1
Basic Notions
A formal context is a triple (G; M; I) consisting of two sets G and M and a relation I G M . The members of G and M are called objects and attributes, respectively. We say that an object g 2 G has an attribute m 2 M if (g; m) 2 I.
Let K := (G; M; I) be a formal context. The set of attributes of an object g 2 G is
attK(g) := fm 2 M j gImg : We extend the de nition to sets of objects: The set of attributes shared by all objects of a subset A G is The set of objects which have all attributes of a subset B
M is attK(A) := \ attK(g) : g2A objK(B) := fg 2 G j B attK(g)g :
A pair (A; B) with A G and B M is called a formal concept of K if A = objK(B) and B = attK(A). In this case A is called the extent and B the intent of the formal concept (A; B). We write B(K) for the set of all formal concepts of K.
The smallest concept extent which contains a set A G of objects is given by
AK := objK(attK(A)) for A
G : We will also use the abbreviations ghK := fg; hgK and gAK := fgg [ AK for g; h 2 G and A G. The smallest concept intent which contains a set B M of attributes is given by We can characterize the set of all concepts in the following ways: BK := attK(objK(B)) for B
B(K) = f(AK; attK(A)) j A B(K) = f(objK(B); BK) j B
M :
Gg ;
M g :
(
The extents and intents of two concepts (A(
A(
A(
B(
An undirected graph is a pair K = (VK ; EK ), where VK is a nite set and EK is a subset of ffx; yg VK j x 6= yg. The members of VK are called the vertices, and the members of EK the edges of K. Given two vertices x; y 2 VK , we say that x and y are joined by an edge if fx; yg 2 EK . In this case, we call x and y neighbors and we may alternatively write x y.
A sequence (v(
A graph (V; E) with V VK and E EK is called a subgraph of K. The induced subgraph on a set V VK of vertices is the subgraph K[V ] := (V; EK \ P(V )), where P(V ) denotes the power set of V . 2.3
a formal context K = (G; M; I) is a triple (G; E; f ) where (CG1) K := (G; E) is an undirected graph on the set of objects, (CG2) E is an arbitrary set of edges such that every induced subgraph
K[objK(B)], B M , is connected, (CG3) f is a labeling function on the vertex set with f (g) = attK(g) for g 2 G. It has been shown in [1] how a context graph with a minimum number of edges can be constructed.
called compliant if x(i) 2 x(
Condition (CG2) for context graphs is equivalent to the statement that there
exists a compliant path between every two vertices x; y 2 G. This follows from
(
AK =
[ x;y2AK xyK : (9) This has already been shown in [1], where we have used a slightly di erent, but equivalent de nition of compliant paths. 3 3.1
Context Graphs for Many-Valued Contexts
We use attributes like e.g. size, price, date or color to describe the objects that surround us. It is usually the value of such an attribute that we are interested in, not just the fact that the attribute applies to an object. We will call these attributes many-valued attributes, in contrast to one-valued attributes which simply do or do not apply to an object.
If we want to use Formal Concept Analysis on objects with many-valued attributes, we have to translate the many-valued attributes into one-valued attributes. As an example, \is big", \is cheap", \before yesterday" and \is black" may be some of the one-valued attributes which are used instead of size, price, date and color. This process is called conceptual scaling, and we will cover in this article the simplest variant, which is also described in [3].
The rst step is to select a formal context called a scale for each attribute. The objects of the scale are the possible values of the many-valued attribute. We can consider the extents of the scale to be the meaningful subsets of values. For example, consider an attribute "rating\ with possible values in f1 = excellent; 2 = good; 3 = average; 4 = badg. This could be something like the user ratings for books and compact disks that you can nd on Amazon.com, for example. We reason that this attribute could be scaled by the ordinal scale in Fig. 1: 1 2 3 2 3 4
1 2 3 The extents of the ordinal scale are f g 1 , f1; 2g, f1; 2; 3g and f1; 2; 3; 4g. If someone is interested in an item that is rated good, they would probably also accept an excellent item, so the extents of the ordinary scale are possible descriptions of what one might be looking for. The one-valued attributes of the scale are used to identify these subsets of values. In our example, one attribute is su cient for each of the sets (e.g. " 3" for f1; 2; 3g).
There are situations where somebody may be interested in bad items exclusively. The interval scale (see also Fig. 1) provides a more ne-grained description of integer value sets: The extents are all intervals [a; b] with a; b 2 f1; 2; 3; 4g, including the interval [4; 4] that we just mentioned. To sum up, we can say that the scale chosen for an attribute determines which subsets of values are considered for the formation of concepts.
Figure 2 shows an example of how objects with many-valued attributes can be represented in a formal context. In this example, we have only three objects o1, o2 and o3 which are described by a 5-tuple of attribute values each. We have scaled the rst three attributes using the interval scale, dichotomic scale and ordinal scale of Fig. 1, respectively. The fourth attribute has not been scaled at all; this is possible as it only takes the values \true" or \false". The last attribute has been scaled by the color scale in Fig. 6.
The formal context obtained in this way is called the derived context w.r.t. plain scaling. We will formalize the process of conceptual scaling in the next section, taking a slightly di erent approach than that in [3].
Derived Context Example o1:(2,true,3,false,blue) o2:(1,true,4,true,red) o3:(4,false,1,false,yellow)
1 2 3 2 3 4 treu lfsea 1 2 3 treu --roy --goy --gyb --gpb --rbp --rop We start with the de nition of a precontext, which is a formal representation of the set of many-valued attributes that we initially have:
ing of n 1 nonempty sets W1; : : : ; Wn and a set G W1 Wn. We call a set Wi an attribute domain, and the members of Wi are called values. The members of G are called objects, and we say that an object (x1; : : : ; xn) 2 G has a value of w 2 Wi in an attribute i 2 f1; : : : ; ng if and only if w = xi.
Precontexts are less general than many-valued contexts (see [3]) in two respects: 1. The condition G W1 Wn means that objects are identi ed with the tuple of their attribute values. That is, objects with identical values in each attribute are considered the same. 2. The attributes are modeled by the projection functions i, i = 1; : : : ; n. That is, the i-th attribute of an object x = (x1; : : : ; xn) is given by i(x) = xi. In particular, the attributes are total functions, whereas the attributes of a many-valued context may be partial functions.
The rst of these points is not an actual restriction if we want to navigate in context graphs, since objects with identical descriptions can be represented by the same vertex. The second point is a restriction: The current paper does not deal with the case where attribute values are unknown or unde ned.
With this in mind, we can understand a precontext (G; W1; : : : ; Wn) as an alternative representation for the many-valued context (G; f i j 1 i ng; Sin=1 Wi; I) with I = f(x; i; i(x)) j x 2 G; 1 i ng.
(G; S1; : : : ; Sn) such that every Si is a formal context (Wi; Mi; Ii), and (G; W1; : : : ; Wn) is a precontext. The contexts Si are called scales.
A precontext with scales (G; S1; : : : ; Sn), with Si = (Wi; Mi; Ii) for i = 1; : : : ; n, and the corresponding derived context K = (G; M; I) are related by the equations : :
M = M1 [ : : : [ Mn ; 8x 2 G : attK(x) \ Mi = attSi ( i(x)) : Theorem 1. Let (G; ~S) be a precontext with scales and K the derived context w.r.t. plain scaling. Then
AK = G \ i(A)
Si n i=1 holds for all A
AK (4=)(
Si :
The theorem provides a description of the extents of the derived context as products of value sets. We formalize this notion of description in the following de nition (descriptions have been explored in [2] already, although the de nition given there is not exactly the same). h 2 W1 De nition 5 (Description). Let M be a precontext with scales Si = (Wi; Mi; Ii), i = 1; : : : ; n. A description in M is a set D = D1 Dn W1 Wn such that Di is an extent of Si for all i = 1; : : : ; n. We write D(M) for the set of all descriptions in M.
An object description is a description D 2 D(M) with Di = hiSi for some Wn, and we shall also write D = h for convenience. (12) (13)
tu n i=1 dscM(A) := i(A)
Si ; objM(D) := G \ D ;
AM := objM(dscM(A)) ; DM := dscM(objM(D)) :
AK = AM : for A
G and D 2 D(M). Now we can state Theorem 1 in the shorter form We write B(M) for the set of all pairs (A; D) with A = objM(D) and D = dscM(A) and state without proof that
In analogy to (
Gg ;
B(M) = f(objM(D); DM) j D 2 D(M)g : Note that A
AM, but D
DM. Moreover,
A(
A(
D(
In this section we de ne the context graph for a precontext with scales: De nition 6 (Context Graph of a Precontext with Scales). Let M = (G; ~S) be a precontext with scales. An undirected graph K = (G; E) is called a context graph of M, if K[objM(D)] is connected for all descriptions D in M. The sets objM(D), D 2 D(M), are precisely the extents AM ((19) and (20)). Because of (18) this means that we essentially get the same context graphs that we would get by rst creating the derived context K and then using De nition 1. However, the attributes of an object do not have to be explicitly encoded by onevalued attributes, which is an advantage of this de nition.
As in Sect. 2.3 we call a path between x; y 2 G compliant if it lies in xyM and obtain the following characterization: Lemma 1. Let M = (G; S1; : : : ; Sn) be a precontext with scales. An undirected graph K = (G; E) is a context graph of M if and only if there is a compliant path between all x; y 2 G. A path (x; : : : ; y) is compliant if and only if 8i : zi 2 xiyiSi holds for all z on the path.
Approximating Objects by Description The following de nition captures the idea of how close a vertex x matches a given description D = D1 Dn:
~uD(x) = (x1D1S1 ; : : : ; xnDnSn ) : The vector contains, in every component, the smallest scale extent that contains fxig[Di. This could be compared with a neighborhood of the set Di in topology.
We write ~uD(x) ~uD(y) if x matches D better than y does: ~uD(x) ~uD(y) :, 8i : xiDiSi yiDiSi : (22) (23)
of M and D 2 D(M). A path (x(
~uD(x(
> ~uD(x(k)) :
For a given description D 2 D(M) we are interested in the objects which best match the description, i.e. the vertices y 2 G for which ~uD(y) is minimal. We will see that from every vertex x 2 G there exists a nonincreasing path to some minimum. We will also prove conditions under which there exist nonincreasing paths to all minima beneath x, and conditions under which these nonincreasing paths are actually decreasing. The conditions depend on the scales chosen for the precontext.
De nition 8 (Scale Properties). The following are properties which may be true or not for a given scale S = (W; M; I): (P1) w 2 uT S; v 2 uwS ) w 2 vT S for all u; v; w 2 W and T (P2) v 2 uwS; v 6= u; v 6= w ) vwS uwS for all u; v; w 2 W W The given properties express what one would probably expect if the scale extents are seen as some kind of intervals, where uwS is the set of all values \between" u and w. Property (P2) then says that the interval vw generated by the inner point v and the end point w is strictly smaller. In the same fashion (P1) would mean that whenever w is between u and T and v is between u and w, then w must be between v and T .
The following lemma will give rst results: Lemma 2. Let (G; E) be a context graph of M, D 2 D(M) and x; y 2 G. Let further (x; : : : ; y) be a compliant path between x and y. The following holds for all z on the path: 1. ~uD(x)
~uD(z),
~uD(z) ~uD(y).
Proof. Because z lies on a compliant path between x and y, we obtain xiDiSi ) yi 2 xiDiSi ) xiyiSi ()24) zi 2 xiDiSi ) ziDiSi
xiDiSi
xiDiSi :
The last inclusion shows that ~uD(x) ~uD(z). If all scales of M satisfy (P1),
we obtain ~uD(z) ~uD(y) by setting u := xi, w := yi, v := zi and T := Di in
De nition 8.
tu
Now let us have a closer look at the Lemma. We interpret x as an arbitrary
vertex and y as a minimum beneath x. In a context graph there must be a
compliant path p from x to y, and we write p = (z(
The left side of Fig. 4 shows a context graph of the one-valued context in Fig. 3. Every one-valued context can be represented as a precontext with scales, using a scale Sid(f0; 1g; fag; f(1; a)g) for each attribute a. This is easily veri ed showing that the derived context, de ned by (10) and (11), is the original context again. The objects are then encoded by n-tuples of attributes in the obvious way (consider the right graph in Fig. 4 for this). The corresponding precontext with scales is therefore (f0; 1gn; Sid; : : : ; Sid). The extents of Sid are f0; 1g and f1g. We now want to nd a best match for the description D = (f0; 1g; f0; 1g; f1g; f0; 1g; f1g; f0; 1g; f0; 1g; f1g; f1g), which happens to be an object description (the corresponding object is (0; 0; 1; 0; 1; 0; 0; 1; 1), which does not exist in the context). We start the search in the \Leech\ vertex, which is represented by the tuple (1; 1; 0; 0; 0; 0; 1; 0; 0). We could now use the de nition in (23) to describe how closely the current vertex matches the description, but it is clear that we can equivalently use the set of shared attributes as a measure instead (the unmodi ed de nition of ~u is better reserved for theoretical considerations). The attributes of the leech are given by fa; b; gg, and the object description translates to the set fc; e; h; ig. There are two best matches in the graph: the dog vertex and the bean vertex. Both lie below the leech vertex, and both can be reached via exactly one compliant path. But in the frog vertex, which lies two vertices down the path, the bean vertex does no longer lie beneath the frog vertex. So only the dog vertex can be reached via a nonincreasing path. In fact it can be seen that Sid does not satisfy (P1).
The next lemma states that every nonincreasing path is in fact a decreasing path if all scales satisfy (P2) and the description is an object description. Lemma 3. Let (G; E) be a context graph of a precontext with scales M. If all scales satisfy (P2), then
x 6= y ) ~uh(x) 6= ~uh(y) holds for all x; y 2 G and all object descriptions h 2 D(M).
Proof. Suppose that x 6= y and ~uh(x) = ~uh(y). Then for some i 2 f1; : : : ; ng we have xi 6= yi, wlog xi 6= hi, and xihiSi = yihiSi . The latter implies xi 2 yihi , Si and from (P2) we obtain (setting v := xi, u := yi and w := hi) that xihiSi yihiSi , contradiction! tu The property (P2) is satis ed by the dichotomic scale and the interval scale. The right of Fig. 4 shows a context graph for the "Living Beings and Water\ context where the precontext with scales is as above, but the scales Sid have been replaced by dichotomic scales. The corresponding derived context is shown in Fig. 5. Consider as a second example that we want to search this graph for Living Beings and Water a b c d e f g h i :a :b :c :d :e :f :g :h :i Leech Bream Frog Dog Spike{weed Reed Bean Maize the object d := (1; 0; 1; 0; 0; 0; 1; 1; 1), which happens to be the dog. The function ~ud can be replaced by the Hamming distance hd(x) :=
X 1 jxij6=jdij as we have ~ud(x) ~ud(y) , hd(x) hd(y). The context graph shows the Hamming distance to the dog object next to each of the nodes. We can verify that the dog vertex can be reached from every other vertex via a decreasing path. As a concluding remark we want to note that the edge-minimal context graph on the right side is unique. More generally, the following proposition can be shown: Proposition 1. Let M = (G; S1; : : : ; Sn) be a precontext with scales such that all Si satisfy (P2). Then there is a unique edge-minimal context graph of M, and the edges of this graph are given by x y , 8z 2 G : ~ux(y) ~ux(z) :
Scale Graphs In this section we brie y present an idea how knowledge about domain of attribute values, or an individual perspective on such a domain, can be fed into a context graph. The idea is to rst draw a graph which represents similarity among attribute values and then de ne a scale which has this graph as its context graph. We have no general method for this and just provide two examples, one de ning a graph for an attribute "color\ and one de ning a graph for an attribute "location\. The graphs are shown in Figs. 6 and 7. The extents have been chosen in a way that (P2) is satis ed, i.e. the extent generated by two objects is the set of all values "between\ these objects. The extents can be read o from the scales which are shown next to the graphs. It can also be checked that the graphs are indeed context graphs of the given scales and that all edges are necessary. This means that if these scales are used for a precontext with scales M, the structure of the scale graphs is re ected in any context graph K of M. This approach allows to model the neighborhoods of a vertex in K. It would also be interesting to investigate the idea of embedding a context graph into a product of scale graphs, comparable to the subdirect product of lattices.
Colors red orange yellow green blue purple
--roy --ogy --gyb --gbp --rbp --rop
Fig. 7. Cities in Australia
Conclusion In this article, we have transferred the de nition of context graphs into the more general setting where objects are described by many-valued attributes, using descriptions instead of attributes. Descriptions can be interpreted as queries of a user, although the queries could actually be formulated in some other language that the user is more comfortable with. In Sect. 4, we have investigated to what degree the structure of a context graph supports nding objects by their description. If the result set for a given query is nonempty, it may be preferrable to look up matching objects in a database and to use the graph structure for examining similar objects or result sets only. However, if the result set for a query is empty, it has been shown that best matches can be found by navigating through the graph. This may be an interesting starting point for interactive querying. Some search in the graph is unavoidable unless a decreasing path leads to a best match for a given query, which can only be guaranteed if a condition is met which comes at the price of further edges in the graph. Generally, navigation in the graph makes only sense if the number of edges is not too large. While a context graph can always be constructed in polynomial time [1], the capacity of the graph seems to be the limitation that applies to context graphs. We believe that the results presented in this paper provide an interesting point of reference but an evaluation of the theory within some real application scenario will be necessary.