A concept (or Galois) lattice is built on a binary relation; this relation can be represented by a bipartite graph. We explain how we can use the graph tool of clique minimal separator decomposition to decompose some bipartite graphs into subgraphs in linear time; each subgraph corresponds to a subrelation. We show that the lattices of these subrelations easily yield the lattice of the global relation. We also illustrate how this decomposition is a tool to help displaying the lattice.
In many algorithms dealing with hard problems, a divide-and-conquer approach is helpful in practical applications. Computing the set of concepts associated with a given context (or the set of maximal rectangles associated with a binary relation) is time-consuming, as there may be an exponential number of concepts. It would be interesting to decompose the lattice into smaller sublattices. What we propose here is to decompose the relation into smaller subrelations, compute the lattice of each subrelation, and then use these lattices to reconstruct the lattice of the global relation.
For this, we use a graph decomposition, called "clique separator
decomposition", introduced by Tarjan [
In a previous work [
It turns out upon investigation that the subgraphs obtained divide not only the graph, but in a very similar fashion divide the matrix of the relation, the set of concepts and the lattice. When the relation has a clique separator of size two, the lattice, as we will explain further on, is divided along a vertical axis by an atom and a co-atom which correspond to the two vertices of the separator. Thus not only can the concepts be computed on the subrelations, but the Hasse diagram of the lattice can be drawn better, as no edge need cross this vertical line.
Moreover, in a bipartite graph, this decomposition can be implemented with
a better worse-case time complexity than in the general case, as the clique
separators can be of size one (in this case they are called articulation points) or of
size two. In both cases, the entire decomposition can be computed in linear time,
i.e. in the size of the relation, thanks to the works of [
The paper is organized as follows: we will rst give some more preliminaries in Section 2. In Section 3, we explain how a bipartite graph is decomposed. In Section 4, we show how to reconstruct the global lattice from the concepts obtained on the subrelations. In Section 5, we discuss using vertical decomposition as a tool for layout help. Finally, in Section 6, we conclude with some general remarks. 2
We will rst recall essential de nitions and properties.
All the graphs will be undirected and nite. For a graph G = (V; E), V is the vertex set and E is the edge set. For xy 2 E; x 6= y, x and y are said to be adjacent ; we say that x sees y. A graph is connected if, for every pair fx; yg of vertices, there is a path from x to y. When a graph is not connected, the maximal connected subgraphs are called the connected components. For C V , G(C) denotes the subgraph induced by C. In a graph G = (V; E), the neighborhood of a vertex x 2 V is the set NG(x) = fy 2 V; x 6= yjxy 2 Eg. NG(x) is denoted N (x) when there is no ambiguity.
A clique is set of vertices which induces a complete graph, i.e. with all possible edges.
A bipartite graph G = (X + Y; E), where + stands for disjoint union, is built on two vertex sets, X and Y , with no edge between vertices of X and no edge between vertices of Y . A maximal biclique of a bipartite graph G = (X + Y; E) is a subgraph G(X0 + Y 0) with all possible edges between the vertices of X0 and the vertices of Y 0.
A relation R O A on a set O of objects and a set A of attributes is associated with a bipartite graph G=(O + A; E), which we will denote Bip(R); thus, for x 2 O and y 2 A, (x; y) is in R i xy is an edge of G. The maximal rectangles of the relation correspond exactly to the maximal bicliques (maximal complete bipartite subgraphs) of Bip(R) and to the elements (the concepts) of concept lattice L(R) associated with context (O; A; R). If O1 A1 and O2 A2 are concepts of L(R) then O1 A1 O2 A2 i O1 O2 i A1 A2; the corresponding bicliques on vertex sets O1 + A1 and O2 + A2 of Bip(R) are comparable the same way.
An atom (resp. co-atom) of L(R) is a concept covering the minimum element (resp. covered by the maximum element). In the bipartite graph Bip(R), the neighborhoods are de ned as follows: for x 2 O, N (x) = R(x) = fy 2 Aj(x; y) 2 Rg, and for x 2 A, N (x) = R 1(x) = fy 2 Oj(y; x) 2 Rg.
A separator in a connected graph is a set of vertices, the removal of which
disconnects the graph. A clique separator is a separator which is a clique. Clique
separator decomposition [
In the rest of the paper, we will use the bipartite graph Bip(R) de ned by a relation R O A. Figure 1 shows an example of a relation with the corresponding bipartite graph. In this section, we will rst discuss connectivity issues, then illustrate and give our process to decompose the bipartite graph.
When the bipartite graph Bip(R) is not connected, our process can be applied separately (or in parallel) to each connected component. The lattice obtained is characteristic: when the top and bottom elements are removed from the Hasse diagram, the resulting diagram is a set of disjoint lattices, with a one-to-one correspondence between the connected components of Bip(R) and the lattices obtained.
Note that trivially, if a connected component has only one vertex, this means that the corresponding row or column of the relation is empty: such a component corresponds to a lattice with only one element.
In the rest of the paper, we will consider only relations whose bipartite graph is connected. In order to make the process we use as clear as possible, we will rst describe what happens when one decomposition step is applied for each of the two decompositions involved (using clique separators of size one or of size two).
It is important to understand, however, that to ensure a good (linear) time complexity, each of the two decompositions is computed globally in a single linear-time pass.
The removal of an articulation point fxg in a connected bipartite graph G results in components C1, ..., Ck, which correspond to a partition V = C1 + ::: + Ck + fxg of Bip(R). After a decomposition step using fxg, x is preserved, with its local neighborhood, in each component, so that G is replaced by k subgraphs G(C1 [ fxg), ..., G(Ck [ fxg).
Example 1. In the input graph of Figure 3, vertex 1 de nes an articulation point that induces two connected components f2; 3; a; b; cg and f4; d; eg. The decomposition step results into subgraphs G(f1; 2; 3; a; b; cg) and G(f1; 4; d; eg).
When the removal of a clique minimal separator fx; yg in a connected bipartite graph G results into components C1,..., Ck, corresponding to a partition V = C1 +:::+Ck +fx; yg. The decomposition step replaces G with G(C1 [fx; yg), ..., G(Ck [ fx; yg).
Example 2. In the input graph of Figure 4, f2; bg is a clique minimal separator of size two that induces two connected components f1; 2; 3; a; b; c; f g and f2; 5; 6; b; g; hg. A clique minimal separator of size two may include an articulation point. Thus it is important to complete the decomposition by the articulation points rst, and then go on to decompose the obtained subgraphs using their clique separators of size two.
Example 3. In the input graph of Figure 5, f2g is an articulation point included in clique minimal separator f2; bg. The decomposition will begin with f2g, inducing components f2; ig and f1; 2; 3; 5; 6; a; b; c; f; g; hg. As there remains no articulation point in these resulting components, the second component will be then decomposed by f2; bg into f1; 2; 3; a; b; c; f g and f2; 5; 6; b; g; hg. After the bipartite graph decomposition is completed, we will obtain subgraphs with no remaining clique minimal separator, and the corresponding subrelations with their associated lattices.
Example 4. Figure 6 shows that the input graph of Figure 1 is decomposable into four bipartite subgraphs: G1 = G(f1; 2; ig), G2 = G(f2; 5; 6; b; g; hg), G3 = G(f1; 2; 3; a; b; c; f g) and G4 = G(f1; 4; d; eg).
Note that in the general case all subgraphs obtained have at least two vertices, since at least one vertex of a separator is copied into a component which has at least one vertex. To obtain the entire decomposition of a connected bipartite graph, we will thus rst decompose the graph using all articulation points, and then decompose each of the subgraphs obtained using all its clique separators of size 2.
The articulation points (clique minimal separators of size one) can be found
by a simple depth- rst search [
The search for clique separators of size two corresponds to a more complicated
algorithm, described in [
Once this list of separators is obtained, it is easy to check which are joined by an edge. The desired decomposition can then be obtained easily.
In both cases, the set of clique separators is output.
Both algorithms run in linear time, so the global complexity is in O(jRj) to obtain both the set of subgraphs and the set of clique separators of the original graph. When the clique separators involved do not overlap and each de nes exactly two connected components, this decomposition of the bipartite graph partitions the graph and the underlying relation. This results in a signi cant pattern of their binary matrix. As the components obtained are pairwise disconnected, the matrix can be reorganized in such a way that zeroes are gathered into blocks. Two components may appear as consecutive blocks, linked by a row corresponding to the articulation point that has been used to split them, or linked by one cell giving the edge between the two vertices of a size two clique minimal separator.
In the general case, this pattern can occur in only some parts of the matrix, and di erent patterns can be de ned according to the di erent separators which the user chooses to represent.
Example 5. The rst of the two matrices below corresponds to our running
example from Figure 1 and has been reorganized, following the decomposition,
which results in the second matrix. Notice how f1g is an articulation point, so
row 1 is shared by blocs 231 bacf and 14 de; and how f2; bg is a clique
separator of size two, so cell [2; b] is the intersection of blocs 562 ghb and 231 bacf .
[2; i] is not integrated into the pattern, because separator f2; bg of Bip(R) de nes
3 connected components: f2; 5; 6; b; g; hg, fig and f1; 3; 4; a; c; d; e; f g.
We will now describe a process to organize the lines and columns of the
matrix with such patterns. We will construct a meta-graph (introduced in [
Example 6. Figure 7 gives the meta-graph for our running example from Figure 1. Chordless path (f2; 5; 6; b; g; hg; f1; 2; 3; a; b; c; g; f1; 4; d; eg) was chosen for the patterning. Another possible chordless path would be (f2; ig; f1; 2; 3; a; b; c; g; f1; 4; d; eg). Finding a chordless path in a graph can be done in linear time; the meta-graph has less than min(jAj; jOj) elements, so nding such a path costs less than (min(jAj; jOj))2. We will now examine how the set of concepts is modi ed and partitioned into the subgraphs obtained. As clique minimal separators are copied in all the components induced, most of the concepts will be preserved by the decomposition. Furthermore, only initial concepts including a vertex of a clique minimal separator may be a ected by the decomposition.
De nition 1. We will say that a maximal biclique is a star maximal biclique if it contains either exactly one object or exactly one attribute. This single object or attribute will be called the center of the star.
Lemma 1. A star maximal biclique fxg [ N (x) of Bip(R) is an atomic concept of L(R) (atom or co-atom), unless x is universal in Bip(R). More precisely, fxg N (x) is a atom if x 2 O and N (x) 6= A, or N (x) fxg is a co-atom if x 2 A and N (x) 6= O.
Proof. Let fxg [ N (x) be a star maximal biclique of Bip(R). As a maximal biclique, it corresponds to a concept of L(R). Suppose the star has x 2 O as center . As a star, it contains no other element of O; as a biclique, it includes all N (x) A, and no other element of A by maximality. The corresponding concept is fxg N (x) which is obviously the rst concept from bottom to top including x. As the biclique is maximal, and as x is not universal, this concept cannot be the bottom of L(R) but only an atom. A similar proof holds for x 2 A and co-atomicity.
We will now give the property which describes how the maximal bicliques are dispatched or modi ed by the decomposition. In the next Section, we will give a general theorem and its proof, from which these properties can be deduced. Property 1. Let G = (X + Y; E) be a bipartite graph, let S be a clique minimal separator of G which decomposes G into subgraphs G1, ..., Gk. Then: 1. 8x 2 S, fxg [ NG(x) is a star maximal biclique of G. 2. 8x 2 S, fxg [ NG(x) is not a maximal biclique of any Gi. 3. 8x 2 S, fxg [ NGi (x) is a biclique of Gi, but it is maximal in Gi i it is not strictly contained in any other biclique of Gi. 4. All the maximal bicliques of G which are not star bicliques with any x 2 S as a center are partitioned into the corresponding subgraphs.
With the help of Lemma 1, this property may be translated in terms of lattices. Given a relation R, its associated graph G, its lattice L(R), and a decomposition step of G into some Gis by articulation point fxg:
If x 2 O (resp. 2 A) is an articulation point of G, fxg NG(x) (resp. NG(x) fxg) is a concept of L(R). After the decomposition step, in each subgraph Gi of G, either this concept becomes fxg NGi (x), or this concept disappears from Gi; this latter case occurs when there is in Gi some x0 2 O, the introducer of which appears after the introducer of x in L(R), from bottom to top (resp. from top to bottom if x; x0 2 A). Every other concept will appear unchanged in exactly one lattice associated with a subgraph Gi.
The same holds for each vertex of a size two clique minimal separator. Example 7. Figure 8 illustrates a decomposition step with articulation point f1g using the graph from Figure 3. Concept f1; 4g fd; eg disappears from the rst component f1; 2; 3; a; b; cg, but remains in the second component f1; 4; d; eg. Example 8. Figure 9 illustrates a decomposition step with clique separator f2; bg using the graph from Figure 4. Concept f2g N (2) is duplicated into components f2; 5; 6; b; g; hg and f1; 2; 3; a; b; c; f g; concept N (b) fbg will appear as f2; 6g fbg in the rst component, but not in the second one, as f2; 3; bg is a biclique included in maximal biclique f2; 3; b; f g of G.
Remark 1. The smaller lattices obtained can not be called sublattices of the initial lattice as some of their elements may not be the same: for example, in Figure 9, f2g fb; c; f g is an element of the third smaller lattice L(G3) but is not an element of the initial lattice L(G). 4
We will now explain how, given the subgraphs obtained by clique decomposition, as well as the corresponding subrelations and subsets of concepts, we can reconstruct the set of concepts of the global input bipartite graph. We will then go on to explain how to obtain the Hasse diagram of the reconstructed lattice. We will use the following Theorem, which describes the concepts of the global lattice.
Theorem 1. Let G = (X + Y; E) be a bipartite graph, let = fs1; :::shg be the set of all the vertices which belong to a clique separator of G, let G1; :::Gk be the set of subgraphs obtained by the complete corresponding clique separator decomposition. Then: 1. For every s 2 , fsg [ NG(s) is a star maximal biclique of G. 2. Any maximal biclique of a subgraph Gi which is not a star with a vertex of as center is also a maximal biclique of G. 3. There are no other maximal bicliques in G: 8s 2 , no other star maximal biclique of Gi with center s is a star maximal biclique of G, and these are the only maximal bicliques of some graph Gi which are not also maximal bicliques in G.
Proof. 1. For every s 2 , fsg [ NG(s) is a star maximal biclique of G: Case 1: s is an articulation point, let Gi, Gj be two graphs which s belongs to; s must be adjacent to some vertex yi in Gi and to some vertex yj in Gj . Suppose fsg [ NG(s) is not a maximal biclique: there must be a vertex z in G which sees yi and yj , but then fsg cannot separate yi from yj , a contradiction.
Case 2: s is not an articulation point, let s0 be a vertex of S such that fs; s0g is a clique separator of G, separating Gi from Gj . s must as above see some vertex yi in Gi and some vertex yj in Gj . Suppose fsg [ NG(s) is not maximal: there must be some vertex w in G which sees all of NG(s), but w must see yi and yj , so fs; s0g cannot separate Gi from Gj . 2. Let B be a non-star maximal biclique of Gi, containing o1; o2 2 O and a1; a2 2 A. Suppose B is not maximal in G: there must be a vertex y in G B which augments B. Let y be in Gj , wlog y 2 A: y must see o1 and o2. Since Gi is a maximal subgraph with no clique separator, Gi + fyg must have a clique separator. Therefore N (y) must be a clique separator of this subgraph, but this is impossible, since y sees two non-adjacent vertices of Gi. 3. Any star maximal biclique B of Gi whose center is not in is also a star maximal biclique of G: suppose we can augment B in G.
Case 1: v sees an extra vertex w; Gi + fwg contains as above a clique separator, which is impossible since N (w) = v and v 62 S.
Case 2: A vertex z of Gj is adjacent to all of N (v): again, G + fzg contains a clique separator, so N (z) is a clique separator, but that is impossible since N (z) contains at least two non-adjacent vertices. 4. For s 2 , no star maximal biclique of Gi is a star maximal biclique of G: let B be a star maximal biclique of Gi, with s 2 as center. s 2 , so s belongs to some clique separator which separates Gi from some graph Gj . s must see a vertex yj in Gj , so B + fyj g is a larger star including B: B cannot be maximal in G.
Example 9. We illustrate Theorem 1 using graph G from Figure 6, whose decomposition yields subgraphs G1, ..., G4, with G1 = G(f1; 2; ig), G2 = G(f2; 5; 6; b; g; hg), G3 = G(f1; 2; 3; a; b; c; f g) and G4 = G(f1; 4; d; eg). Finally, = f1; 2; bg. The corresponding lattices are shown in Figure 10, and their concepts are presented in the table below. In this table, braces have been omitted; symbol ) represents a concept of the considered subgraph Gi which is identical to a concept of G (there can be only one ) per row); the other concepts of the subgraphs will not be preserved in G while recomposing.
L(G1) L(G2) According to Theorem 1, the steps to reconstruct the maximal concepts of the global lattice from the concepts of the smaller lattices are: 1. Compute , the set of attributes and objects involved in a clique minimal separator. (In our example, = f1; 2; bg.) 2. Compute the maximal star bicliques for all the elements of . (In our example, we will compute star maximal bicliques 1 acde, 2 bcf hi and 26 b.) 3. For each smaller lattice, remove from the set of concepts the atoms or coatoms corresponding to elements of ; maintain all the other concepts as concepts of the global lattice. (In our example, for L(G3), we will remove 1 ac and 2 bcf , and maintain 3 abf; 13 a; 12 c and 23 bf as concepts of L(G).)
Step 1 requires O(jRj) time. Step 2 can be done while computing the smaller lattices; Step 3 costs constant time per concept. Thus the overall complexity of the reconstruction is in O(jRj) time. 4.2
According to Theorem 1, the maximal bicliques which are not star maximal bicliques with a vertex of as center are preserved; therefore, the corresponding edges between the elements of the lattice are also preserved. In the process in 5 described below, we will refer to labels in the lattice as being the 'reduced' labels, such as the ones used in our lattice gures throuhout this paper.
To de ne the edges of the Hasse diagram of lattice L(G), we will, for each smaller lattice L(Gi): { nd each atom (or co-atom) which corresponds to an element of (such as 2 or b for L(G3) in our example). { If shares its label with some non-elements of , remove all elements of from the label. (In our example for L(G3), bf becomes f ). If does not share its label with some non-elements of , remove the atom or co-atom. (In our example for L(G3), remove element 2). { Maintain the remaining edges as edges of L(G). { Compute the neighborhood in L(G) of each atom or co-atom which corresponds to an element of .
All this can be done in polynomial time: there are at most jAj + jOj vertices , and the corresponding edges can be added in O((jAj + jOj)2jRj).
When there is a size two clique separator in the bipartite graph which divides the graph into two components, the concepts which are not involved in the separator can be displayed on the two sides of the separator, thus helping to minimize the number of line crossings in the Hasse diagram.
(a) (b)
To illustrate this, we have used our running example with 'Concept Explorer'
[
Figure 11 shows the lattice as proposed by Concept Explorer, and then redrawn with insight on the clique separators of the bipartite graph.
The same technique of course also applies when there is a succession of such clique separators.
Let us add that if moreover both lattices are planar, as discussed in [
When there is no clique separator in the bipartite graph, it could be interesting to investigate restricting the relation to a subgraph or partial subgraph which does have one.
We leave open the question of characterizing, without computing the relation, the lattices whose underlying bipartite graph has a clique minimal separator.
The authors sincerely thank all the referees for their useful suggestions and questions.