We describe a technique for user interaction with the interim results of Formal Concept Analysis which we hypothesise will expedite user comprehension of the resultant concept lattice. Given any algorithm which enumerates the concepts of a formal context, this technique incrementally updates the set of formal concepts generated so far, the transitive reduction of the ordering relation between them, and the corresponding labelled Hasse diagram. User interaction with this Hasse diagram should prioritise the generation of missing concepts relevant to the user's selection. We brie y describe a prototype implementation of this technique, including the modi cation of a concept enumeration algorithm to respond to such prioritisation, and the incremental updating of both the transitive reduction and labelled Hasse diagram.
Formal Concept Analysis (FCA) takes as input a formal context consisting of a
set of attributes, a set of objects, and a binary relation indicating which objects
have which attributes. It produces a partially-ordered set, or poset, of formal
concepts, the size of which is, in the worst case, exponential in the number of
objects and attributes in the formal context [
A number of algorithms exist which e ciently enumerate the formal concepts of a formal context [3{6]. In this paper, we describe an approach which incrementally updates and presents the partial order amongst the formal concepts generated so far. In particular, it: incrementally updates the transitive reduction of the interim partial order as each new concept is generated; incrementally updates the layout of the Hasse diagram; and animates the resultant changes to the Hasse diagram to assist the user in maintaining their mental model. This approach enables user exploration and interrogation of the interim partial order in order to expedite their comprehension of the resultant complete lattice of concepts. It applies equally to any other partial order, the enumeration of whose elements is computationally intensive.
We also describe how this interaction can prioritise the generation and
display of those missing concepts which are most relevant to the user's current
exploratory focus. By addressing the scalability challenge of visual analytics [
Incremental algorithms exist for updating the set of formal concepts and the transitive reduction of the ordering relation following the addition of a new object to the formal context [9{11]. A new object can give rise to multiple additional concepts which must be inserted in the existing complete lattice to produce an updated lattice which is also complete. In contrast, the technique described in this paper involves the addition of a single element at a time to a partially ordered set which is not in general a complete lattice.
Ceglar and Pattison [
A nite poset hP ; <i consists of a nite set P and an irre exive, antisymmetric, transitive binary relation < between its elements. Two elements a; b 2 P are said to be comparable if a < b or b < a, and incomparable otherwise. hP ; <i can be represented as an acyclic directed graph, or digraph, in which each element of the set P is a vertex and an arc connects each pair of comparable elements. The direction of each arc is \upward" in the sense of the relation <, from the lesser to the greater element.
The greater the number of comparable pairs, the greater the number of arcs,
and hence the harder it is for a user to interpret a drawing of this digraph.
The transitive reduction [
A layered drawing of the resultant digraph, in which the vertical component of each arc is upwards on the page, is known as a Hasse diagram of the partial order. This direction convention reduces clutter by avoiding the need to explicitly represent the direction of the arcs. An example Hasse diagram is shown in Fig. 1a. The black vertices in Fig. 1b are comparable because a monotonically upward path, via the light-grey vertices, exists between them. The more elements there are in P , and the more arcs there are in the transitive reduction of <, the harder the visual task of tracing paths in the Hasse diagram to determine comparability. An upper [respectively lower]1 bound on a given set S P is an element u 2 P [l 2 P ] satisfying 8s 2 S, s < u [l < s]. If S consists of a single element a 2 P , the set of upper [lower] bounds on S is called an upset [downset], and can be identi ed by tracing all upward [downward] paths from a in the Hasse diagram. In Fig. 1c, the vertices in the upset [downset] of the black vertex are light [dark] grey. The union of a with its upset and downset gives the set of elements of P which are comparable with a. If S consists of two or more elements of P , then the set US P [DS P ] of its upper [lower] bounds is the intersection of the upsets [downsets] of its elements. In Fig. 1d, the sets of upper and lower bounds on the pair of black vertices are encompassed by the shaded areas. The visual task of identifying and intersecting these upsets [downsets] is demanding for small partial orders, and rapidly becomes intractable as the size jP j of P increases.
If there exists an a 2 US such that a 6 a for all upper bounds a 2 US on S, then a is called the least upper bound (LUB); if there exists a b 2 DS 1 Square brackets are used throughout this paper to indicate that a sentence is true both when read without the bracketed terms and when read with each bracketed term substituted for the term which precedes it. such that b 6 b for all lower bounds b 2 DS on S, then b is called the greatest lower bound (GLB). In Fig. 1d, the least upper and greatest lower bounds on the pair of black vertices are the upper and lower shaded vertices respectively. By de nition, the LUB and GLB are unique whenever they exist, since equality corresponds to identity. In addition to the challenge of identifying the set of upper [lower] bounds on S, the visual task of establishing the existence and identity of the LUB [GLB] from this set also becomes intractable for large jP j.
If the LUB and GLB exist for all pairs of elements in P , then hP ; <i is called a lattice. If the LUB and GLB exist for all S P , then hP ; <i is called a complete lattice, and the LUB [GLB] on P is known as the supremum [in mum]. 2.3
In the previous section, we identi ed a number of operations on posets which a user can perform visually by tracing paths in the Hasse diagram, but which become intractable as jP j increases. To support the user in these tasks, the computer should calculate the results of these operations and display them by highlighting elements of the Hasse diagram. In particular: 1. Comparability between selected elements of P can be determined computationally and all identi ed paths between them highlighted in the Hasse diagram. 2. The set of elements comparable with a selected element can be determined by calculating and highlighting the members of its upset and downset. 3. The set of upper [lower] bounds on a set S of elements can be determined by calculating the upsets [downsets] of each, and highlighting the members of their intersection. 4. The existence and identity of the LUB [GLB] on a selected subset S can be determined computationally from the result of 3. The identi ed element of P , if any, should be highlighted. 3
So far we have assumed that the elements of hP ; <i are known a priori, so that the transitive reduction can be computed and the Hasse diagram laid out before being presented to the user. Consider now the case where the user's request for the Hasse diagram triggers the on-demand enumeration of the elements of P . If this enumeration is computationally intensive, the user may experience excessive delay before the results are presented. Rather than waiting for the generation of all elements, the user may wish to commence interaction with the Hasse diagram for the elements generated so far, and have this diagram evolve to incorporate each new element as it is added. We hypothesise that user exploration of, and familiarisation with, the evolving hQ P ; <i will facilitate and expedite comprehension of hP ; <i.
In order to examine the feasibility of user interaction with the Hasse diagram of hQ; <i as a proxy for that of hP ; <i, the subsequent sections address the following four key questions: 1. What information about hP ; <i can and cannot be ascertained through inspection of hQ; <i? 2. Should the response to user interrogation of hQ; <i be expressed in terms of hP ; <i ? 3. Can hQ; <i be incrementally updated to incorporate each new element of P as it is generated? 4. How should these updates be presented so as to minimise disruption to the user's mental model of hQ; <i? 3.1
Two elements which are comparable in hP ; <i are comparable in any hQ P ; <i in which they both exist. The upset [downset] of an element in hP ; <i is a (possibly improper) superset of its counterpart in hQ; <i. Accordingly, the set of upper [lower] bounds on S Q in hP ; <i is also a superset of its counterpart in hQ; <i. Importantly, the LUB [GLB] on S Q may not be present in hQ; <i, even if it is in hP ; <i. 3.2
User interaction could be de ned to implement the same computer-assisted operations on hQ; <i as were de ned above on hP ; <i. However, since the user's objective is to nd out about hP ; <i, interaction with hQ; <i should also prioritise the generation of the requisite elements of P .
The selection of two elements a and b in order to determine their comparability might con rm comparability by not only highlighting the elements x 2 Q which lie between a and b, but also prioritise the generation of all such x 2 P . Selection of an element might not only display its upset and downset in hQ; <i, but also prioritise the completion of these sets by the process which generates the elements of P . Similarly, the selection of a set S Q of elements in the interim partial order may not only result in the display of the corresponding upper and lower bound sets, but also prioritise the completion of these sets. And nally, if the user requests the LUB [GLB] on a set S Q of elements, then the computer could prioritise the generation of the corresponding result in hP ; <i. If the requested bound exists, the corresponding element of P could be added, if not already present, and highlighted in the Hasse diagram; otherwise a null result should be signalled to the user. 3.3
As each new element e of P is generated and added to hQ; <i to form hQ [ feg; <i, both the element set and the transitive reduction of < must be updated. Updating the transitive reduction involves identifying the upper and lower neighbours of e, adding the requisite arcs, and deleting any arcs from the lower to the upper neighbours.
The set N u := minfu 2 Q : e < ug N l := maxfl 2 Q : l < eg of upper [lower] neighbours can be identi ed through a top-down [bottom-up] search of hQ; <i starting from each of the maximal [minimal] elements of Q. Each downward [upward] path from each maximal [minimal] element can be pruned from the point at which an element is encountered which is not greater [less] than e. An element in fu 2 Q : e < ug [fl 2 Q : l < eg] is also in N u [N l] i it has no lower [upper] neighbour greater [less] than e.
Once the sets N u and N l have been identi ed, the neighbour relation should be updated as follows. In hQ [ feg; <i, e for each 2 N u and e for each 2 N l. To maintain as the transitive reduction of <, any arcs in N l N u must also be removed. Note that either or both of the sets N u and N l can be empty; the element e is maximal in hQ [ feg; <i i N u = ;, and minimal i N l = ;. 3.4
The layout of the Hasse diagram for hQ [ feg; <i will necessarily di er from that
of hQ; <i. The addition of the new vertex e will require either its accommodation
within an existing layer or the creation of a new layer. The deletion of some
existing arcs and the creation of new ones may also worsen the aesthetic criteria,
such as number of edge crossings, which the chosen layout algorithm seeks to
optimise [
The addition of the new vertex and its incident arcs, the deletion of superseded arcs, and any changes in layout, must be presented to the user in a way which minimises disruption of the user's mental model of hQ; <i. The sequential animation of each step in this process is a logical solution to this problem. By also minimising and localising any changes to the layout necessitated by the addition of a new vertex, the number of vertices and edges whose movement the user must visually track can be minimised.
Figure 2 illustrates the process of adding a new element to hQ; <i in Fig. 2a. The upper (light grey) and lower (dark grey) neighbours of the new element are identi ed, and the edges between them (bold) slated for deletion. The vertical separation between the top and bottom layers is increased to make room for a new layer, which is required to accommodate the new vertex. Finally, the new vertex is inserted and attached to its upper and lower neighbours. Placement of the new vertex near its upper and lower neighbours helps localise the resultant changes to the Hasse diagram. 4 4.1
FCA takes as input a bigraph consisting of a set G of objects, a set M of attributes, and a binary relation R G M between them. FCA produces a complete lattice of formal concepts. Each formal concept consists of a set E G, (a) Identify neighbours and superceded edges (b) Make room for, insert and connect new vertex known as the extent, and a set I M , known as the intent, such that E I R. Each object in E has all attributes in I and each attribute in I is possessed by all objects in E. The extent and intent are maximal in the sense that adding elements to either set necessarily entails removing elements from the other. The relation < between concepts is the subset relation between their extents. The upset [downset] of a concept consists of concepts whose intents [extents] are subsets of those of the nominated concept. The concept whose extent is the set of objects possessing attribute i is referred to as the attribute concept for i; the concept whose intent is the set of attributes possessed by object j is known as the object concept for j. In the Hasse diagram for the complete lattice of formal concepts, an attribute [object] concept is labelled with the corresponding attribute [object]. The intent of a concept can be inferred from the set of attribute labels on vertices in its upset, while its extent can be inferred from the set of object labels on vertices in its downset.
This reduced labelling scheme works for the interim partial order hQ; <i provided that all object and attribute concepts are present ab initio. The algorithm which generates the formal concepts should be chosen or modi ed so as to produce these rst, and rendering of the Hasse diagram deferred until they are included in Q. It will be seen in Sect. 4.6 that this deferral also has bene ts for the layout of the Hasse diagram. In FCA, the intent of the LUB on a set of concepts is the intersection of their intents, while the extent of the GLB is the intersection of their extents. Thus, the LUB [GLB] indicates the set of attributes [objects] which they have in common. Since the partial order amongst the full set of formal concepts for a formal context is a complete lattice, the LUB and GLB are guaranteed to exist; they may however be absent from hQ; <i, and will in general require computation on demand.
Notably, the LUB and GLB on the full set P of formal concepts may not be present in hQ; <i. A concept enumeration algorithm should be chosen or modi ed to produce these rst. In addition to improving the resemblance between hQ; <i and the resultant complete lattice hP ; <i, the existence of the LUB [GLB] ab initio provides a single, consistent starting point for the top-down [bottom-up] search of the transitive reduction of hQ; <i for the upper [lower] neighbours of each new concept. This process is described in Sect. 4.4.
Selection of a set A of concepts could trigger the generation, display and highlighting of all concepts x 2 P satisfying A < x < A . Here A and A denote the GLB and LUB on the set A in the complete lattice hP ; <i of formal concepts. A and A constitute the GLB and LUB on the complete lattice of elements whose generation is to be prioritised. Their generation is given the highest priority in order to bound this poset. The elements of A are all mutually comparable i at least one directed path from A to A passes through all of these elements. In this case, A 2 A and A 2 A; in the special case of jAj = 2, this is a necessary and su cient condition for comparability. 4.4
As described in Sect. 3.3, the upper [lower] neighbours of the new concept can be identi ed in hQ; <i using a top-down [bottom-up] directed search. The search commences from the LUB [GLB] on P , which by design is present in Q ab initio. The current vertex is marked as having been visited, and any lower [upper] neighbour whose intent [extent] is a subset of that of the new concept is queued for subsequent traversal. If the current concept has no such neighbours, then it is an upper [lower] neighbour of the new concept. 4.5
The poset hQ; <i is presented to the user as a layered drawing of the corresponding directed acyclic graph. In order to maintain the direction convention of upward arcs in this Hasse diagram, each new concept must be assigned to a layer which is separated from the in mum [supremum] by at least the maximum length of all directed paths between them in the transitive reduction of hQ; <i. If no existing layer satis es both constraints, one must be added. If only one such layer exists, the new concept is assigned to that layer. If more than one existing layer satis es both constraints, the choice amongst them is arbitrary.
Even if at least one layer satis es both constraints on path length, it is still possible for the new concept to have upper and lower neighbours in adjacent layers. Adding an intervening layer in this case would create room for the new concept, and would not require the revision of any previous layer assignments. However, given that there are already su cient layers to accommodate the new concept, a more space-e cient strategy would be to instead promote the lowest upper neighbours to the next highest layer or demote the highest lower neighbours to the next lowest layer. To make room for either change, it may also be necessary to promote additional members of the upset or demote additional members of the downset of the new concept.
In our preliminary implementation of layer assignment, we: assign a vertex to the uppermost layer, if any, satisfying the dual path length constraints; attempt to demote elements of the downset in order to make room to insert a new concept between upper and lower neighbours which are in adjacent layers; and insert a new layer, if required, which has path length two from the in mum to make room for this demotion. The reason for the choice of path length two will become apparent in Sect. 4.6. This layering strategy is illustrated later in Sect. 4.8.
The chosen strategy requires that concepts be allowed to migrate between layers following initial presentation to the user, which has the potential to disrupt the user's mental model. On the other hand, creating more layers than are required results in ine cient use of the vertical space available for drawing the Hasse diagram, making it harder for the user to maintain simultaneous focus and context as jQj increases. 4.6
For the reason given in Sect. 4.3, the concept enumeration algorithm should rst generate the LUB and GLB of the poset hP ; <i of concepts. These should be placed at the centre top and centre bottom of the canvas. For the reason given in Sect. 4.2, all (remaining) attribute and object concepts should be generated next. In this section, we prioritise from amongst these the generation of the lower neighbours of the supremum, which are called atoms, and the upper neighbours of the in mum, which are called co-atoms. We describe a scheme whereby their relative ordering within their respective layers is chosen so as to improve the aesthetics of the resultant Hasse diagram. The horizontal placement of all subsequent concepts, including the remaining attribute and object concepts, is dependent on this ordering.
The supremum and in mum, along with all atoms and co-atoms, are generated and laid out before the Hasse diagram is rst presented to the user. The atoms and co-atoms are ordered within their respective layers so as to minimise edge crossings in the relation R. As subsequent concepts are discovered and added, each edge morphs into one or more directed paths in the transitive reduction of hQ; <i. Provided care is taken in the placement of the remaining concepts on these paths, the e ort invested in minimising edge crossings in R might therefore be repaid with fewer arc crossings, and potentially also shorter paths, in the Hasse diagram.
For each newly-discovered concept, the horizontal barycentre [
The creation of a new layer may be required to separate vertically, by at least one layer, the upper and lower neighbours of a new concept. That new layer is created immediately above the layer of co-atoms, and elements of the downset of the new concept are demoted as required. Note that demotion beyond this layer would violate the constraint on path length from the in mum. Since each new concept is placed in the uppermost layer satisfying the constraint on path length to the supremum, and new layers are only ever added with path length two from the in mum, concepts will either remain in the layer to which they are originally assigned, or migrate downward. 4.7
We have so far assumed that algorithms for the enumeration of formal concepts
could be modi ed to prioritise the generation of concepts relevant to the user's
current selection. To demonstrate that this is possible, we brie y describe a
modi cation of the algorithm of Choi and Huang [
Choi and Huang enumerate the concepts of a formal context in top-down,
breadth- rst order, extending the intent of each concept generated so far using
attributes not currently in its intent. Ceglar and Pattison [
E cient FCA algorithms employ various strategies for preventing the
repeated generation of the same concept, typically by traversing a trie structure
[
Figure 3 shows mockups of a prototype interface for the incremental construction of a poset of formal concepts. The example formal context consists of people and their physical attributes. Figure 3a depicts the state of the Hasse diagram rst presented to the user. By this stage, all of the attribute and object concepts have been generated by the concept enumeration algorithm, labelled, and laid out to establish the framework for insertion of subsequent concepts. WhiteHair Beard
Moustache BrownHair BlackHair BrownSkin RedHair
Kyle Andy Justin Jon Jake Joshua Megan Sarah Wiliam Tyler Daniel (a) Initial diagram (b) Multiple selection (c) Insertion This paper has described a technique for the incremental construction of the Hasse diagram of a poset. We hypothesise that user interaction with this evolving diagram will expedite user comprehension of the partial order. When applied to FCA, this technique incrementally updates the transitive reduction, and the labelled Hasse diagram, of the partial order amongst the set of concepts generated so far. User interaction with the Hasse diagram prioritises the generation of missing concepts relevant to the user's selection. A prototype implementation, including the modi cation of a concept enumeration algorithm to respond to downset prioritisation, has also been described through which the hypothesis will be tested in future work. Scalable mechanisms for interactive concept deletion should also be explored to allow the exclusion from the interim partial order of concepts which are no longer of interest to the user.