Formal Concept Analysis takes as input a bigraph known as a formal context. It produces a partially-ordered set of formal concepts which constitutes a complete lattice. This lattice can be represented as a directed acyclic graph, whose vertices are formal concepts and whose arcs connect neighbours in the ordering relation between them. This paper describes a divide-and-conquer technique for discovering and exploiting hierarchical structure in a formal context. Simultaneous hierarchical partitioning of both the context bigraph and the resultant lattice digraph is used to achieve efficient computation and, elsewhere, interactive visualisation of the concept lattice.
Formal Concept Analysis (FCA) derives a multiple-inheritance class hierarchy from a formal context. A formal context consists of a set of objects, a set of attributes, and a binary relation between them. The classes derived by FCA are known as formal concepts. Each consists of a set of objects, called its extent, and a set of attributes, called its intent, such that each object in its extent, and no others, has all attributes in its intent. The set of formal concepts, when partially ordered by set inclusion, forms a complete lattice. This lattice can be efficiently represented as a directed acyclic graph (DAG), whose vertices are formal concepts, and whose adjacency relation is the transitive reduction of the ordering relation.
The number of formal concepts is bounded above by an exponential function of the number of objects and attributes in the context. Scaling FCA to the interactive analysis of large data sets poses two fundamental challenges: the time required to compute the concepts and construct the large lattice digraph; and the difficulty of meaningful and responsive user interaction with this digraph.
The times required to enumerate all formal concepts of a formal context, and to calculate the transitive reduction of the ordering relation between them, are both bounded above by a polynomial function of the number of formal concepts. One class of “divide and conquer” techniques tackles this inherent computational complexity by partitioning the context, performing FCA on each resultant subcontext, and combining the results. FCA is thereby mapped onto multiple independent processors, each performing FCA on a sub-context which is significantly c paper author(s), 2018. Proceedings volume published and copyrighted by its editors.
Paper published in Dmitry I. Ignatov, Lhouari Nourine (Eds.): CLA 2018, pp.
219{230, Department of Computer Science, Palacky University Olomouc, 2018.
Copying permitted only for private and academic purposes.
smaller than the overall context. Several FCA algorithms use this approach for
the enumeration of concepts [
This paper describes the Carve technique for recursively partitioning a
formal context, which produces a corresponding hierarchical partition of the
lattice digraph. Carve exploits structure which we have identified in an empirical
author-publication context for co-authorship analysis, and which Bhatti et al. [
Carve recursively partitions a formal context for analysis by any FCA algorithm which, or algorithms which collectively: enumerates the formal concepts; calculates the transitive reduction of the ordering relation; and returns the corresponding labelled DAG. It further assembles the resultant digraphs into that for the original context. Carve does not compete with existing FCA algorithms; it accelerates their application to formal contexts exhibiting the requisite structure.
This paper is organised as follows. Section 2 introduces relevant aspects of the theories of partial orders, FCA, graphs and graph drawing. Section 3 then establishes the theoretical foundations for the Carve algorithm, after which the algorithm is detailed in Section 4. A brief discussion of related work is presented in Section 5, followed by a summary in Section 6. 2
This section introduces relevant aspects of the theories of partial orders and
FCA, as well as graphs and graph drawing. It assumes relevant knowledge found
in such textbooks as [
Definition 1 A formal context (G, M, I) is a triple consisting of a set G of objects, a set M of attributes and a binary relation I ⊆ G × M such that an object g ∈ G has attribute m ∈ M iff (g, m) ∈ I.
Definition 2 The context bigraph for the formal context (G, M, I) is a bipartite graph having object vertex set G, attribute vertex set M , and edge set I. Definition 3 A connected component of a context bigraph is a maximal subgraph in which a path exists between all pairs of vertices.
The example formal context of Figure 1a is represented in Figure 1b as a context bigraph. Object vertices are drawn with grey fill and attribute vertices white. The context bigraph has three connected components.
Definition 4 The extent operator / : P(M ) → P(G) and intent operator . : P(G) → P(M ) return the maximal sets
B/ = {g ∈ G | (g, m) ∈ I ∀ m ∈ B} A. = {m ∈ M | (g, m) ∈ I ∀ g ∈ A} (1a) (1b) 1 2 X 3 4 X 5 6 7 8 9 X X X X 10 11 X X 12
X X
X
X X X X X X
X X X
J
I
6
X X X (a) Formal context 8
H 1 2 G 12 E 10 5
F
B 11
A 9 C 4 L 3
D (b) Context bigraph
K 7 (2a) (2b) (3a) (3b) B/ = {g ∈ G | g. ⊇ B} A. = {m ∈ M | m/ ⊇ A}
A. = B
B/ = A Definition 5 A formal concept of the context (G, M, I) is an ordered pair (A, B) with extent ∅ ⊆ A ⊆ G and intent ∅ ⊆ B ⊆ M satisfying of objects possessing all attributes in B ⊆ M and attributes possessed by all objects in A ⊆ G.
Here, P(G) and P(M ) denote the powersets – sets of all subsets – of G and M respectively. m/ ≡ {m}/ is the set of objects which have attribute m and g. ≡ {g}. is the set of attributes possessed by object g.
Proposition 1. For A ⊆ G and B ⊆ M Definition 6 A biclique (A, B) in the context bigraph (G, M, I) is a set ∅ ⊂ A ⊆ G of object vertices and a corresponding set ∅ ⊂ B ⊆ M of attribute vertices such that each vertex in A is adjacent to all vertices in B, and vice versa. Definition 7 A biclique (A, B) is maximal if there is no biclique (A0, B0) 6= (A, B) having A0 ⊇ A and B0 ⊇ B.
context (G, M, I) having extent A 6= ∅ and intent B 6= ∅ iff (A, B) is a maximal biclique in the bigraph (G, M, I) having object vertex set A and attribute vertex set B.
The elements of the set B(G, M, I) of formal concepts are partially ordered by defining the relation ≤ between concepts (A, B), (C, D) ∈ B(G, M, I) such that
A ⊆ C ⇐⇒ (A, B) ≤ (C, D) ⇐⇒ B ⊇ D Definition 8 Let hP; ≤i be a finite partially-ordered set, and let a, b ∈ P satisfy a < b – i.e. a ≤ b and a 6= b. If @c ∈ P satisfying a < c < b, then we write a ≺ b. Element a is then called a lower neighbour of b, and conversely b is an upper neighbour of a.
Proposition 3. FCA of the formal context (G, M, I) produces the lattice Definition 9 The concept (A, B) is an attribute concept for each attribute m ∈ μ and an object concept for each object g ∈ γ.
The resultant directed graph is a single-source, single-sink DAG. The source vertex s, corresponding to the infimum, has only outgoing arcs; the sink vertex t, corresponding to the supremum, has only incoming arcs. The extent [intent]1 of any concept is the set of all object [attribute] labels encountered on downward [upward] paths from that concept. Two lattices are order isomorphic iff their lattice digraphs, excluding labels, are isomorphic.
Proposition 4. Let t and s be the sink and source vertices, respectively, of a lattice digraph. Denote by μt and γt the attribute and object label sets of t, and by μs and γs the attribute and object label sets of s. Then μt = G. μs = {m ∈ M |m/ = M /} γt = {g ∈ G|g. = G.} γs = M / 1 Square brackets indicate that a sentence is true both when read without the bracketed terms and when read with each bracketed term substituted for the preceding term.
hB(G, M, I); ≤i = *
C ∪ _ c ∪ ^ c; ≤ c∈C c∈C + where c ranges over the set C of maximal bicliques in (G, M, I).
Thus the global supremum ∨c∈Cc and infimum ∧c∈Cc of the set C of maximal bicliques complete the set B ⊇ C of formal concepts in cases where they have empty intent or extent, and are therefore not already included in C. We refer to the supremum and infimum collectively as the extrema.
The complete lattice hB(G, M, I); ≤i can be efficiently represented as a labeled digraph whose vertices are concepts and whose arcs connect neighbours. Each arc is directed from the lower to the upper neighbour, and concepts are comparable iff there exists a directed path between the corresponding vertices. For each concept (A, B), the corresponding vertex is labelled with attribute set μ ⊆ B and object set γ ⊆ A defined as follows: μ := {m ∈ M |m/ = A} γ := {g ∈ G|g. = B} (4) (5) (6a) (6b) (7)
Proposition 4 indicates that t is labelled with attributes possessed by all objects and with objects possessing only these universal attributes. Similarly, s is labelled with objects possessing all attributes and with attributes possessed only by these universal objects.
A Hasse diagram [
Each biclique of the context bigraph must be entirely contained within a single connected component. The maximal bicliques of (G, M, I) can therefore be enumerated by dividing the bigraph into its connected components and enumerating the maximal bicliques of each component. Separate connected components, and hence also their bicliques, share neither object nor attribute vertices. Proposition 5. If ∨c∈Cc ∈ C or ∧c∈Cc ∈ C then the bigraph (G, M, I) consists of a single connected component. 3.2
For any two concepts, the intent [extent] of their supremum [infimum] is the intersection of their intents [extents].
Proposition 6. For any pair of maximal bicliques drawn from different connected components, their extrema are those of the set C of maximal bicliques. Corollary 1 No arcs exist between vertices of the lattice digraph corresponding to maximal bicliques from different connected components of (G, M, I).
Corollary 1 indicates that partitioning the context bigraph into connected components partitions the vertices of the resultant lattice digraph, excepting the extrema, into disjoint sets between which there are no arcs. From the converse of Proposition 5, if (G, M, I) consists of more than one connected component, then the extrema are not maximal bicliques, and are not covered by Corollary 1.
Figure 3a uses rounded boxes as containers to illustrate this partitioning of the concepts for the example context in Figure 1. The concepts derived from the largest connected component of the context bigraph – with the exception of the J
I 6 8 infimum which does not correspond to a biclique – are in the pink container. These concepts and the ordering relation between them are the same as those in Figure 2b, which resulted from FCA of the largest component in isolation. As expected, there are no edges (arcs) between concepts in different containers.
A context bigraph exhibiting two or more connected components can be partitioned into those components, those components analysed separately to identify their maximal bicliques and compute the transitive reduction of their partial ordering, and the sink [source] vertices of each resultant sub-graph of the lattice digraph connected to the global sink [source] to form the lattice digraph. FCA of the context (G, M, I) is thereby reduced to independent FCA for each of the sub-contexts (Gi, Mi, I ∩ (Gi × Mi)). Some care is required (see Section 3.5) to ensure the proper handling of the extrema of each sub-context. Proposition 7. Let (G0, M 0, I0) be formed from (G, M, I) by removing object set γs, attribute set μt, and all edges incident on either. Then hB(G0, M 0, I0); ≤i is order isomorphic to hB(G, M, I); ≤i.
Proposition 8. Let (G0, M 0, I0) be formed from (G, M, I) by removing object set γt, attribute set μs, and all edges incident on either. Then hB(G0, M 0, I0); ≤i is order isomorphic to hB(G, M, I); ≤i iff the supremum and infimum of B(G, M, I) have more than one lower and upper neighbour respectively.
Propositions 7 and 8 involve the application of row and column reduction
[
H 8 1
G 10
I
J 6
K 3 7 L
B 11
Figure 4a shows the connected components of the bigraph in Figure 2a after removal of the universal attribute G and its incident edges. Object 10 is now isolated, and cannot therefore participate in a biclique. Figure 4b shows the Hasse diagram for this sub-context after removal of both G and 10. As indicated by the shaded containers, the maximal bicliques are partitioned into two sets, corresponding to the two remaining connected components of the bigraph, between which there are no connections. Comparison of Figures 4b and 2b confirms that the lattices before and after extremum reduction are order isomorphic. Since the supremum has more than one lower neighbour, removal of object 10 satisfies the condition of Proposition 8 for lattice isomorphism.
Let (G0, M 0, I0) denote the result of applying Propositions 7 and 8 to (G, M, I). The extrema of this extremum-reduced context are no longer object or attribute concepts, and accordingly have no labels. Whereas the concept lattices for (G, M, I) and (G0, M 0, I0) are order isomorphic, the corresponding lattice digraphs will therefore differ in the labelling of the supremum and infimum. Restoring these labels, which are now stored in γs, μs, γt and μt, converts the lattice digraph for (G0, M 0, I0) into that for (G, M, I). For example, restoring the label sets γt = {10} and μt = {G} to the supremum converts the Hasse diagram in Figure 4b to that in Figure 2b. 3.4
We have seen that the removal of any universal attributes and objects, as per Proposition 7, can disconnect the context bigraph, and thereby pave the way for partitioning of (G, M, I). If (G, M, I) is instead a sub-context resulting from a previous partition, removal of these objects and attributes may facilitate partitioning of that sub-context, and hence recursive partitioning of the global context. J
I 6 8
The execution of a procedure which removes from the context bigraph the objects and attributes identified in Propositions 7 and 8, along with their adjacent edges, identifies the connected components in the remaining context bi-graph, and calls itself to process each of the identified components, is described by its recursion tree. Figure 5 shows this tree superimposed on the context bigraph from Figure 1 using an inclusion tree layout. Each rounded rectangular container corresponds to a vertex in the recursion tree. A container includes another iff the former corresponds to an ancestor of the latter in the recursion tree.
This tree also constitutes a partition tree for the context bigraph, in which the non-leaf nodes are labelled with the objects γt ∪ γs and attributes μt ∪ μs associated with the extrema of the corresponding sub-context. In Figure 5, these objects and attributes appear only in non-leaf containers.
The leaf nodes of this tree correspond to sub-contexts whose lattice digraphs are either trivial – consisting of one or two vertices – or otherwise not amenable to further partitioning. Each non-trivial leaf-node sub-context must be processed by a suitable FCA algorithm which returns the corresponding lattice digraph labelled as per (6). The resultant single-source, single-sink digraphs form the L 3
K 7
B 2
A 11
D 9
C 4
J 6
I 8
H 1
G 10
F 5
E 12 Fig. 5: Context bigraph from Figure 1 with recursion tree superimposed using inclusion tree layout. building blocks which must then be appropriately assembled and interconnected to produce the lattice digraph for the overall context. Importantly, this assembly can be performed progressively in a single pass back up the recursion tree. 3.5
Assembling the lattice digraph for a given sub-context involves either connecting or merging the source (infimum) and sink (supremum) vertices s0, t0 of the digraphs for each of its immediate sub-contexts with their counterparts s, t for the current sub-context. In this section we examine the circumstances under which merging and connection, respectively, are appropriate. μt0 6= ∅ [γs0 6= ∅].
Proposition 9. Let (G0, M 0, I0) be an extremum-reduced context consisting of two or more connected components. Let (A, B) be the supremum [infimum] of one of these connected components, (Gi, Mi, Ii), and let t0 [s0] be the corresponding vertex of the lattice digraph for that sub-context. Then (A, B) ∈ B(G0, M 0, I0) iff
If the supremum [infimum] of (Gi, Mi, Ii) has an attribute [object] label, then an arc is added to connect it to its counterpart in the parent context (G0, M 0, I0). This ensures that each maximal biclique in (Gi, Mi, Ii) has a directed path to the lattice supremum, and from the infimum, of the parent context. If the supremum [infimum] of (Gi, Mi, Ii) does not have an attribute [object] label, it should instead be merged with its counterpart in the parent context. The merge operation replaces two digraph vertices with a single vertex having the unions of their upper neighbours, lower neighbours, attribute labels and object labels. 4
Carve Algorithm 1 lists the Carve algorithm for simultaneous recursive partitioning of a formal context and its corresponding lattice digraph. Carve() takes as input a context bigraph (G, M, I) and returns, by reference to its source and sink vertices, the corresponding lattice digraph, labelled as per (6). The Boolean parameter φ represents the level of recursion, and should be set to zero for the initial call. Carve() invokes the following functions: FindComponents(G0, M 0, I0): Takes as input a context bigraph (G0, M 0, I0) and returns an unordered set of its connected component bigraphs.
FCA(G0, M 0, I0): Takes as input a formal context (G0, M 0, I0) which cannot be
further decomposed by Carve() and returns the resultant lattice digraph.
This function can be implemented using any FCA algorithm (see e.g. [
Lines 2 to 24 of Carve() create and label the source and sink vertices of the sub-lattice digraph, return the lattice digraph in cases where it is trivial, and if not, convert the context (G, M, I) to its extremum-reduced form (G0, M 0, I0). Lines 25 to 29 partition (G0, M 0, I0) into its connected component bigraphs. Lines 30 to 48 calculate the sub-lattice digraph for each of these components and connect or merge it into the source and sink vertices of the lattice digraph for (G, M, I). From the perspective of FCA(), Carve() is a pre-processor which reduces the context to an extremum-reduced, connected bigraph, and a postprocessor which connects the resultant sub-lattice digraph into that for the original context.
Figure 3b uses an inclusion tree layout to illustrates the recursive execution of Carve() when applied to the context of Figure 1. The containers are filled with the same colours as their counterparts in Figure 5, in which the same recursion tree is overlaid on the context bigraph. The single vertex in the yellow container is returned by line 5 of Algorithm 1. Those in the light grey container are generated by a call to FCA() at line 31, and those pairs in the remaining three leaf-node containers are returned by line 22. 5
Berry et al. [
Decomposition using clique minimal separators produces a set of atomic bigraphs which by definition contain no clique minimal separators. FCA of each atomic bigraph produces corresponding lattice digraphs from which the original lattice digraph is reconstructed. In contrast with Carve, the resultant decomposition of the lattice digraph is not hierarchical, and reconstruction is complicated, inter alia, by the fact that edges can be required between constituent digraphs.
Valtchev et al. [11] described a procedure for recursive binary partitioning
of an arbitrary formal context and the assembly of the overall lattice digraph
from the digraphs arising from the sub-contexts. Only the attribute [object] set
is partitioned, so that each sub-context contains all objects [attributes]. Whilst
postulating that an “optimal” partition of the context would be one which
minimised the size of the component digraphs, Valtchev et al. [11] left open the
question of how to choose such a partition. In contrast, Carve discovers and
exploits the structure of amenable contexts to recursively partition both the object
and attribute sets, and significantly simplifies digraph assembly for this special
case.
This paper has established the theoretical foundations of, and then detailed, the
Carve algorithm, a divide-and-conquer technique for discovering and
exploiting hierarchical structure in a formal context. Hierarchical partitioning of both
the formal context and the resultant concept lattice have been used to achieve
efficient computation of the lattice digraph. The discovered structure can be
exploited for improved layout of, and interaction with, the Hasse diagram [