=Paper=
{{Paper
|id=None
|storemode=property
|title=Links between Modular Decomposition of Concept Lattice and Bimodular Decomposition of a Context
|pdfUrl=https://ceur-ws.org/Vol-959/paper27.pdf
|volume=Vol-959
|dblpUrl=https://dblp.org/rec/conf/cla/Gely11
}}
==Links between Modular Decomposition of Concept Lattice and Bimodular Decomposition of a Context==
https://ceur-ws.org/Vol-959/paper27.pdf
Links between modular decomposition of
concept lattice and bimodular decomposition of
a context
Alain Gély
LITA, Ile du Saulcy, 57045 Metz Cedex 1
Université de Metz, France
gely@univ-metz.fr
Abstract. This paper is a preliminary attempt to study how modular
and bimodular decomposition, used in graph theory, can be used on
contexts and concept lattices in formal concept analysis (FCA).
In a graph, a module is a set of vertices defined in term of behaviour
with respect to the outside of the module: All vertices in the module act
with no distinction and can be replaced by a unique vertex, which is a
representation of the module. This definition may be applied to concepts
of lattices, with slighty modifications (using order relation instead of
adjacency).
One can note that modular decomposition is not well suited for bipar-
tite graphs. For example, every bipartite graph corresponding to a clar-
ified context is trivially prime (not decomposable w.r.t modules). In [4],
authors have introduced a decomposition dedicaced to bipartite graph,
called the bimodular decomposition. In this paper, we show how modu-
lar decomposition of lattices and bimodular decomposition of contexts
interact. These results may be used to improve readability of a Hasse
diagram.
1 Introduction
Concept lattices are well suited to deal with knowledge representation and clas-
sification, but when the number of concepts grows, it is not very convenient
to visualize the Hasse diagram. To avoid this problem, some approaches keep
only part of the concepts (Iceberg lattice [9] , usage of Galois sub-hierarchy [3],
concepts with high stability score [7, 8] or any combinaison of these techniques);
Others approaches try to obtain a more readable lattice by usage of a threeshold,
as for α-galois lattices [10]. Another solution is to use decompositions to improve
readability (see all chapter 4 of [5] and particularly nested diagrams).
There is a lot of works in graph theory about decomposition of a graph. A
classical and well studied decomposition is the modular decomposition (see for
example [6]). This decomposition has great properties: possibility of replacing a
set of vertices by a single representant, so that visualization of the graph is better
understandable; recursive approach, so that one can go from generalities to finer
detail levels (useful for knowledge representation); nice theoretical properties,
as the existence of a decomposition tree or closure properties for the family of
modules.
Modular decomposition of graphs may be adapted to lattices with only little
changes: In a graph, this is the adjacency relation which is fundamental, but it
is the order relation for lattices.
Moreover, concept lattices are usually computed from a context, which can
be considerated as a bipartite graph. So, there are two structures which can be
decomposed: the concept lattice and the bipartite graph.
Unfortunately, bipartite graphs are not good candidates for modular decom-
position: except for twin vertices (vertices with the same neighbourghood) or con-
nected components, there are no modules (except trivial one’s) in such graphs.
To improve the decomposition of bipartite graph, the notion of bimodule is in-
troduced in [4].
Goal of this paper is to study how bimodules of a bipartite graph interact
with modules of the concept lattice of this context, and to see how it can be
used to help the visualisation of information contained in lattices.
The next section is dedicaced to definitions. Section 2.2 introduces modules
of a graph and transposes the definition to lattice (modules of a lattice). Section
3 is about bimodules of a bipartite graph (context) and the links that exist
with the corresponding concept lattice. After some discussion in section 4, we
conclude the paper in section 5.
2 Preliminaries
2.1 Definitions
In this paper, all discrete structures are finites and all graphs are simples (no
loops neither multi-edges). Since this paper is about usages of graph theory
results, a formal context will be considerated as a bipartite graph B = (O, A, I)
with O (objects) and A (attributes) being two stable sets of vertices, and I
(incidence relation between objects and attributes) the set of edges of B.
For a vertex v, v ′ denotes the neighbourghood of v (vertices adjacents to
v). For a subset V of vertices, V ′ denotes the common neighbourhood (vertices
which are adjacent to every vertices of V ). With this notation, the classical
definition of galois connections follows immediately.
Definition 1 (Galois connections). For a set X ⊂ O, Y ⊆ A we define
X ′ = {y ∈ O | xIy for all x ∈ X},
Y ′ = {x ∈ A | xIy for all y ∈ Y }.
A clarified context is a context such that x′ = y ′ implie x = y for any vertices
of O ∪ A. A clarified context is reduced if no vertex v is such that v ′ = V ′ with
V ⊆ O ∪ A, v ̸∈ V .
A complete lattice L = (P, ≤, ∨, ∧) is a poset such that for all X ⊆ P , there
exist a supremum and an infimum in P . j ∈ P is ∨-irreducible element if x∨y = j
implies x = j or y = j. m ∈ P is a ∧-irreducible element if x ∧ y = m implies
x = m or y = m. j covers a unique element j∗ (j∗ ≺ j), m is covered by a unique
element m∗ (m ≺ m∗ ). We denote J the set of ∨-irreducible elements and M
the set of ∧-irreducible elements.
For a formal context C = (O, A, I) a formal concept is a pair (X, Y ), X ⊆ O,
X ⊆ A and X ′ = Y and Y ′ = X. X is called the extent of the concept and Y is
called the intent. The set of formal concepts ordered by inclusion on the intents
is the concept lattice of C.
For every finite lattice L = (P, ≤, ∨, ∧) there is, up to isomorphism, a unique
reduced context C = (J, M, ≤). In the following of this paper, we will consider
only reduced contexts, i.e. contexts such that O = J, the set of ∨-irreducible
elements and A = M the set of ∧-irreducible elements of L.
2.2 Modules of graphs and lattices
We denote a graph G with G = (V, E). V is the set of vertices and E a set of
edges. Let X ⊂ V and s ∈ V \X. Then s distinguishes X if s′ ∩ X ̸= ∅ and
s′ ∩ X ̸= X. That is, s is adjacent with some vertices of X and not adjacent
with some others vertices of X. So, if no vertex distinguishes a set X, then for
the outside of X and relation of adjacency, every vertex is similar and X can be
viewed as a unique vertex.
Definition 2 (Module, graph theory). A module in a graph is a subset of
vertices that no vertex distinguishes.
The graph which is obtained by the replacement of a module by a single
vertex is called a quotient graph. It is a simplification of the original one (see
Fig. 1). As no vertex distinguishes X (elements in dashed line), there exist only
two possibilities for a vertex v not in X: either v is adjacent to every vertex of X
(then there exists an edge between v and the representant of X) or v is adjacent
with no vertex of X (then, there is no edge between v and the representant of
X).
For a graph G = (V, E), the set V and singletons x ∈ V are trivial modules.
A graph without non trivial module is called a prime graph (for the modular
decomposition). Two modules A and B overlap if no one is a subset of the other
and A ∩ B ̸= ∅. A module which does not overlap another module is a strong
module.
Modules and strong modules are central in several decomposition processes
and their properties have been well studied. In the first definitions, modules
where defined with respect to the adjacency relation, but decompositions have
been generalized (for example in [1]) for others properties of graphs.
For a lattice, it is more natural to consider the order relation than an adja-
cency relation, so a natural definition follows immediately:
(a) (b)
Fig. 1. (a) A module in a graph and (b) the quotient graph
Definition 3. For a lattice L = (P, ≤, ∨, ∧), a lattice module is a set of elements
X ⊆ P such that, for every y ∈ P \X, one of the three following statements is
true:
– ∀x ∈ X, x < y;
– or ∀x ∈ X, x > y;
– or ∀x ∈ X, x||y.
It is clear with this definition that a module in a lattice L is equivalent to a
module (with respect to adjacency) in the graph obtained by transitive closure
of the Hasse Diagram of L.
⊤
f g h M1 M2
a b c d e
⊥
(a) (b)
Fig. 2. Two strong modules of lattice (a) and the quotient lattice (b). Since no vertex
outside the module distinguishes vertices inside the module, it can be collapsed to a
single vertex which is the representant of the module. Note that M2 can be recursively
decomposed in two other modules {h} (trivial) and {d, e}.
Let X ⊆ P be a subset of elements of a lattice L, with A = min(X) and
B = max(X) the sets of minimal (resp. maximal) elements of X. X is a convex
set iff for all y ∈ P such that a < y < b, a ∈ A, b ∈ B, then y ∈ X. If A and B
are reduced to singletons, X is an interval. [A, B] denotes the convex set defined
by the two sets A and B.
Lemma 1. Modules in lattices are convex sets.
Proof. Suppose it is not, then there exists y ∈ P \X with a < y < b and so, y
distinguishes a and b. It follows that X is not a module.
From now, since lattices modules are convex sets, we will use the notation
X = [A, B] to speak of a module X.
Lemma 2. For a lattice module [A, B]:
1. if |A| > 1 then A ⊆ J,
2. if |B| > 1 then B ⊆ M .
Proof. Suppose |A| > 1, and let A = a1 , a2 , . . . , an .
Suppose ai ̸∈ J, then, since ai ||aj there exists at least one ∨-irreducible element
j such that j < ai and j ̸< aj , which is a contradiction with the fact that [A, B]
is a module.
Dually proof applies for elements of B.
Note that when |A| = 1 (dually for B) the maximal element of the module
is not necessary an irreducible one (See Fig. 3).
M1 M6
b b
M2 c d M5
a a
M3 M4
(a) (b)
Fig. 3. (a) Module M2 is a convex set [A, B], with A = {a} ̸⊂ J and B = {b} ̸⊂ M .
M1 , M2 and M3 overlap: there are not strong modules. (b) M4 , M5 and M6 are strong
modules but are not intervals. M5 = [A, B], with A = {b, c} ⊂ J and B = {b, c} ⊂ M .
Lemma 3. For a lattice module [A, B]:
∧
1. if |A| > 2, ∨ A = ai ∧ aj for all ai , aj ∈ A.
2. if |B| > 2, B = bi ∨ bj for all bi , bj ∈ B.
Proof. Clearly, suppose |A| > 2 and there exist ai , aj , ak ∈ A such that x1 =
ai ∧ aj ̸= aj ∧ ak = x2 . w.l.o.g suppose x1 ̸< x2 . Then x1 < aj and x1 ̸< ak . It
follows that x1 distinguishes [A, B].
3 Modules of lattices and bimodules of contexts
As a preliminary remark, we recall that all considered contexts are reduced, and
so, clarified. The clarification of a context is the fact to keep only one object o
for all objects oi such that o′i = o′j (dually for attribute). It is clear that the set
{o1 , . . . , on } is a module in the bipartite graph and this process is equivalent to
replace twin vertices by a representant.
Modules are not well situed for bipartite graphs. Twin vertices and connected
components are the only modules for these graphs which are poorly decompos-
able. In goal to improve the decomposition, Fouquet and all have introduced
bimodule, an analog of module for bipartite graphs.
Definition 4 (Bimodule). Let C = (O, A, I) be a bipartite graph, and (X, Y ) ⊂
(O, A), then (X, Y ) is a bimodule if no x ∈ O\X distinguishes A and no y ∈ A\Y
distinguishes O.
Example of bimodule is given in Fig. 4: b and c are not distinguished with
respect to vertices 4 (none of them are adjacent) or 3 (each of them is adjacent).
Similarly, 1 and 2 are not distinguished by a (each of them is adjacent) and d
(none of them is adjacent).
1 2 3 4
a b c d
Fig. 4. Example of bimodules
The whole bipartite (O, A), all vertices and pairs (j, m), j ∈ J, m ∈ M
are trivial modules. In the following, we consider only non trivial bimodules, i.e
bimodules with at least 3 elements.
Proposition 1. To any non trivial module X of lattice corresponds a bimodule
of reduced context.
Proof. By definition of a lattice module, no elements inside the modules are dis-
tinguished by elements outside. It follows directly that no ∨-irreducible element
outside the module distinguishes ∧-irreducible elements inside, and conversely.
Now, we want to know how a bimodule on the context may be interpretated
in the concept lattice. First, we define a set in the lattice L from a bimodule X.
From a bimodule X = (J1 , M1 ) ⊆ (J, M ), we build a subset C of concepts
in L such that:
– attributes concepts of X are in C,
– objects concepts of X are in C,
– C = [A, B] is a convex set, with A being maximal elements of C and B being
minimal elements of C.
As previously seen, a lattice module corresponds to a context bimodule but,
with the previous construction, the converse may be false: There exist bimodules
of a context such that [A, B] does not correspond to a module in the lattice. As
an example, Fig. 5 shows the lattice for the bipartite graph in Fig. 4. The set
[A, B] is bounded by a dashed line.
Nevertheless, we can observe that, even if [A, B] is not a module, there exists
a possibility of simplification, replacing a set of elements by two vertices and an
edge.
(abcd, ∅) (abcd, ∅)
(ab, 1) (ac, 2) (bcd, 3) 12 (bcd, 3)
(a, 12) (b, 13) (c, 23) (d, 34) (a, 12) bc (d, 34)
(∅, 1234) (∅, 1234)
Fig. 5. (a) lattice for bipartite graph in Fig. 4.a and (b) simplified lattice
In the following, we show that when [A, B] is not a module, the shape of the
set [A, B] is very constrained.
Proposition 2. Let [A, B] be a convex set built from a non trivial bimodule X.
If [A, B] is not a module, then
1. | |[A, B] ∩ M | − |[A, B] ∩ J| | ≤ 1
2. if |[A, B] ∩ M | = |[A, B] ∩ J|, then∨A ⊆ J and B ⊆ M
3. if |max([A, B] ∩ J)| > 1, a+ = ai , ai ∈ max([A, B] ∩ J) is such that
ai ≺ a+ ∧
4. if |min([A, B] ∩ M )| > 1, b− = bi , bi ∈ min([A, B] ∩ M ) is such that
b− ≺ bi
Proof. First, we show that | |[A, B] ∩ M | − |[A, B] ∩ J| | ≤ 1:
Suppose that [A, B] is not a module of the concept lattice, then there exists
an element x ̸∈ [A, B] which distinguishes [A, B]. Without lost of generality, we
can consider that x ∈ J and there exist y ∈ [A, B] such that x < y. We denote P1
the set of elements of [A, B] which are greater than x and P2 = [A, B]\P1 . Since
x is a ∨-irreducible element, it does not distinguish any ∧-irreducible elements
in [A, B]. It follows that all ∧-irreducible elements in [A, B] are in P1 and none
of them in P2 (or conversely).
In a finite lattice, every element e is ∧-dense, i.e. equal to the infimum of
∧-irreducible elements greater than e.
All ∨-irreducible elements in P2 cannot be distinguished by ∧-irreducible
elements outside [A, ∧B]. One unique ∨-irreducible element jmax of P2 may be
defined by jmax = mi , . . . , mj , with mi , . . . , mj ̸∈ P1 . All other ∨-irreducible
elements in P2 are distinguished by ∧-irreducible elements in P1 (and only by
these elements). So P2 ∩ J = X ∪ {jmax } (jmax may not exist).
Suppose |X| < |[A, B] ∩ M |, then there exist m1 , m2 ∈ [A, B] ∩ M , j1 ∈ X
such that j1 < m1 , j1 < m2 , m1 ||m2 . It follows that j1 < m1 ∧ m2 , which is
impossible since j1 ∈ P2 and elements in P2 are not comparable to x.
Similarly, suppose |X| > |[A, B] ∩ M |, At least one ∨-irreducible element j
of X is smaller than two ∧-irreducible elements m1 and m2 of P1 , with m1 ||m2 .
This is impossible, so |X| = |[A, B] ∩ M | and | |[A, B] ∩ M | − |[A, B] ∩ J| | ≤ 1.
A ⊆ J and B ⊆ M follow directly of the fact that, by construction A and
B contain irreducible elements and for each ∧-irreducible element m ∈ [A, B],
there exists a ∨-irreducible element j ∈ [A, B] such that j < m.
It remains
∨ to prove that, when max([A, B]∩J) contains at least two elements,
a+ = ai , ai ∈ max([A, B]∩J) is such that ai ≺ a+ (and dually for b− ). Suppose
it is not the case, then exist at least two elements x1 and x2 smaller than a+
and such that x1 and x2 distinguish elements in A. It follows that one can find a
∧-irreducible element which distinguishes ∨-irreducible elements in A and that
is a contradiction.
It follows from this proposition that even if a set [A, B] is not a module, it
can be collapsed into two vertices j and m such that j < m (but maybe not
j ≺ m). j is a representant for the set [A, B] ∩ J and m a representant for the
set [A, B] ∩ M . Moreover, j ≺ a+ and b+ ≺ m.
4 Discussion
4.1 Algorithmic Aspects
It is known that the family of modules of a graph (and so, of a lattice) and
the family of bimodules of a bipartite graph are closed by intersection. Since
the whole graph is a (trivial) module, it defines a lattice. So, for any set S of
vertices, it is possible to use a closure operator to compute the smallest module
which contains S. Algorithm 1 adds all vertices which distinguish respectively
X and Y and the same process is repeated until no more vertex can be added.
Usually, bimodules decomposition does not produce all possible modules,
but an inclusion tree such that all possible bimodules can be deduced from this
tree. The root represents the whole graph and the leaves are vertices (trivial
Input: (O, A, I) a bipartite graph, (X, Y ) ⊂ (O, A)
Output: (Xc , Yc ), smallest bimodule containing (X, Y )
begin
continue ← true;
(Xc , Yc ) ← (X, Y );
while continue do
continue ← f alse;
forall the x ∈ J\Xc do
if x distinguishes Yc then
Xc ← Xc ∪ x;
continue ← true;
end
end
forall the y ∈ M \Yc do
if y distinguishes Xc then
Yc ← Yc ∪ y;
continue ← true;
end
end
end
return (Xc , Yc )
end
Algorithm 1: Computation of the smallest bimodule which contains (X, Y )
bimodules). It follows that the size of the tree is O(n), with n = |O| + |A|. In
[1], authors propose a O(n3 ) algorithm to compute a such tree.
4.2 Decomposition and Real Data
In Fig. 6, an example of bimodule is shown on the “Living Beings and Water”
concept lattice [5]. g is the attribute for “can move around” and h is the one for
“has limbs”. These two attributes are equivalent (cannot be distinguished) from
the outside of the bimodule. So, on the lattice in Fig. 6.c these two attributes
are collapsed, as well as objects 1 (Leech) and 2 (Bream). Further work must be
done on real data to see what bimodules can enlight for practical cases.
5 Conclusion
First, we have seen that modules defined on a lattice have natural links with
bimodules of the bipartite graph (context) of this lattice. Modules of a lattice
can be used the same way as modules of a graph are used: to produce a quo-
tient lattice, which is a simplification of the original one. Recursive definition of
modules allows to consider several details levels in the lattice.
All results in modular decomposition may be transposed immediatly to con-
cept lattice and associated context to improve the readibility of the lattice.
b c d e f g h i
1 × ×
2 × ××
3 ×× ××
4 × ×××
5 × × ×
6 ××× ×
7 ×××
8 ×× ×
(a)
c b
g
h d
f
1
2 5
8
4 i 3 e 7 6
(b)
c b
gh
d
f
12
5
8
4 i 3 e 7 6
(c)
Fig. 6. (a) “Living Beings and Water ” Context [5], (b) Concept lattice for “living
Beings and Water” and (c) the same concept lattice with a bimodule collapsed.
Second, investigation of bimodules properties shows that a bimodule may not
correspond to a module of the lattice. Nevertheless, it remains possible to use it
to produce a simplification of the original lattice. In such a case, the bimodule
is collapsed in two elements a and b which represent ∨-irreducible elements and
∧-irreducible elements of the bimodule.
This last case is a particular case of another decomposition proposed for
inheritance hierarchies [2], called the block decomposition (with a different def-
inition of block that the one in [5]): a block is an interval [a, b] such that only a
and b can be distinguished of other vertices from the outside of the block. As a
perspective behaviour of this decomposition for lattices and associated properties
on the context can be investigated.
References
1. m. Bui Xuan, B., Habib, M., Limouzy, V., Montgolfier, F.D.: Homogeneity vs. adja-
cency: generalising some graph decomposition algorithms. In: In 32nd International
Workshop on Graph-Theoretic Concepts in Computer Science (WG), volume 4271
of LNCS (2006)
2. Capelle, C.: Block decomposition of inheritance hierarchies. In: WG. pp. 118–131
(1997)
3. Encheva, S.: Galois sub-hierarchy and orderings. In: Proceedings of the 10th
WSEAS international conference on Artificial intelligence, knowledge engineer-
ing and data bases. pp. 168–171. AIKED’11, World Scientific and Engineer-
ing Academy and Society (WSEAS), Stevens Point, Wisconsin, USA (2011),
http://portal.acm.org/citation.cfm?id=1959485.1959517
4. Fouquet, J., Habib, M., de Montgolfier, F., Vanherpe, J.: Bimodular decomposi-
tion of bipartite graphs. In: Graph-Theoretic Concepts in Computer Science 30th
International Workshop, WG 2004, Bad Honnef, Germany, June 21-23 (2004)
5. Ganter, B., Wille, R.: Formal Concept Analysis, Mathematical Foundations.
Springer-Verlag Berlin (1996)
6. Habib, M., Paul, C.: A survey of the algorithmic aspects of modular decomposition.
Computer Science Review 4, 41–59 (2010)
7. Jay, N., Kohler, F., Napoli, A.: Analysis of social communities with iceberg and
stability-based concept lattices. In: Proceedings of the 6th international confer-
ence on Formal concept analysis. pp. 258–272. ICFCA’08, Springer-Verlag, Berlin,
Heidelberg (2008), http://portal.acm.org/citation.cfm?id=1787746.1787765
8. Klimushkin, M., Obiedkov, S., Roth, C.: Approaches to the selection of relevant
concepts in the case of noisy data. In: Kwuida, L., Sertkaya, B. (eds.) Proc. 8th
Intl. Conf. Formal Concept Analysis. LNCS/LNAI, vol. 5986, pp. 255–266. Springer
(2010)
9. Stumme, G., Taouil, R., Bastide, Y., Lakhal, L.: Conceptual clustering with iceberg
concept lattices. In: In: Proc. of GI-Fachgruppentreffen Maschinelles Lernen’01,
Universität Dortmund (2001)
10. Ventos, V., Soldano, H.: Alpha galois lattices: an overview. In: In: International
Conference in Formal Concept Analysis (ICFCA05), LNCS. pp. 298–313. Springer
(2005)