Introducer Concepts in n-Dimensional Contexts
Giacomo Kahn1 and Alexandre Bazin2
1

arXiv:1802.04030v1 [] 12 Feb 2018

2

LIMOS & Université Clermont Auvergne, France
Le2i - Laboratoire Electronique, Informatique et Image, France
giacomo.kahn@isima.fr, contact@alexandrebazin.com

Abstract. Concept lattices are well-known conceptual structures that
organise interesting patterns—the concepts—extracted from data. In
some applications, such as software engineering or data mining, the size
of the lattice can be a problem, as it is often too large to be efficiently
computed, and too complex to be browsed. For this reason, the Galois
Sub-Hierarchy, a restriction of the concept lattice to introducer concepts,
has been introduced as a smaller alternative. In this paper, we generalise
the Galois Sub-Hierarchy to n-lattices, conceptual structures obtained
from multidimensional data in the same way that concept lattices are
obtained from binary relations.
Keywords: Formal Concept Analysis, Polyadic Concept Analysis, Introducer Concept, AOC-poset, Galois Sub-Hierarchy.

1

Introduction

Formal Concept Analysis [1] is a mathematical framework that allows, from a
binary relation, to extract interesting patterns called concepts. Those patterns
form a hierarchy called a concept lattice.
The size of the lattice, potentially exponential in the size of the relation, is
one of the main drawbacks in its use as data representation. In some cases, it is
possible to avoid using the whole lattice, as it contains redundant information [2].
The AOC-poset (or Galois Sub-Hierarchy) is a sub-order of the lattice that
preserves only some of its key elements [3]. Its size is potentially much smaller
than the size of the associated concept lattice [4] and it can be used in place of
the concept lattice to perform certain tasks [5, 6].
The generalisation of FCA to the n-dimensional case, Polyadic Concept Analysis [7], focuses on multidimensional data, i.e. n-ary relations.
In this paper, we generalise the notion of AOC-posets to n-lattices. In Section 2, we provide the definitions and notations that we use throughout the paper. Section 3 is dedicated to the definition of introducer concepts in n-lattices,
and some properties about those concepts. In Section 4, we present an algorithm to compute the introducer sub-order, and study its complexity. Finally,
we conclude and discuss some future works.

2

2

Kahn & Bazin

Definitions and Notations

In this section, we introduce classical definitions and notations from Formal
Concept Analysis and Polyadic Concept Analysis. They can also be found in [1]
and [7].
2.1

Formal Concept Analysis

From now on, we will omit the brackets in the notation for sets when no confusion
is induced by this simplification.
A (formal) context is a triple (S1 , S2 , R) in which S1 and S2 are sets and
R ⊆ S1 × S2 is a binary relation between them. The elements of S1 are called
the (formal) objects and those of S2 the (formal) attributes. A pair (x1 , x2 ) ∈ R
means that “the object x1 has the attribute x2 ”. A context can be represented
as a cross table, as shown in Fig. 1. For instance, object 1 has attributes a and
b, and attribute b is shared by objects 1 and 2.

a b c
1××
2 ××
3× ×

Fig. 1: An example of a context C = (S1 , S2 , R) with S1 = {1, 2, 3} and S2 =
{a, b, c}.

Two derivation operators (·)′ : 2S1 7→ 2S2 and (·)′ : 2S2 7→ 2S1 are defined.
For X1 ⊆ S1 and X2 ⊆ S2 , X1′ = {a | ∀x ∈ X1 , (x, a) ∈ R} and X2′ = {o | ∀y ∈
X2 , (o, y) ∈ R}.
A formal concept is a pair (X1 , X2 ) where X1 ⊆ S1 , X2 ⊆ S2 , X1′ = X2 and
X2′ = X1 . This corresponds to a maximal set of objects that share a maximal
set of attributes and can be viewed as a maximal rectangle full of crosses in the
formal context, up to permutations on the elements of the rows and columns.
X1 is called the extent of the concept, while X2 is called the intent.
The set of all concepts of a context ordered by the inclusion relation on either
one of their components forms a complete lattice. Additionally, every complete
lattice is isomorphic to the concept lattice of some context [1]. The concept
lattice associated with the formal context from Fig. 1 is shown in Fig. 2.
In an application, the size of the concept lattice might be a drawback. For
this reason, Godin et al. [3] introduced a sub-hierarchy of the lattice, the Galois
sub-hierarchy. This sub-hierarchy was introduced and is most often used in the
field of software engineering, but is also used in other fields, such as Relational

Introducer Concepts in n-Dimensional Contexts

3

(123, ∅)

(12, b) (13, a) (23, c)

(1, ab) (2, bc) (3, ac)

(∅, abc)

Fig. 2: Concept lattice associated with C.
Concept Analysis (RCA) [8] and data mining [5]. Additionally, the Galois subhierarchy is integrated in some FCA tools, such as Latviz [9], Galicia [10],
RCAExplore 1 or AOC-poset Builder 2 .
Definition 1 (Introducer concept). An Object-Concept is a concept (o′′ , o′ )
with o ∈ S1 . We say that this concept introduces o.
An Attribute-Concept is a concept (a′ , a′′ ) with a ∈ S2 . We say that this
concept introduces a.
A concept can introduce both attributes and objects, or it can introduce
neither. We call the sub-order restricted to the introducer concepts an AttributeObject-Concept partially ordered set (AOC-poset), or Galois Sub-Hierarchy (GSH).
While a concept lattice can have up to 2min(|S1 |,|S2 |) concepts, the associated
GSH has at most |S1 | + |S2 | elements. Several algorithms exist to compute the
GSH [11–14].
2.2

Polyadic Concept Analysis

Definition 2. An n-context is an (n + 1)-tuple C = (S1 , . . . , Sn , R) in which
Si , i ∈ {1, . . . , n}, is a set called a dimension and R is an n-ary relation between
the dimensions.
An n-context can be represented by a |S1 |×· · ·×|Sn | cross table as illustrated
in Fig. 3.
Definition
Q3. An n-concept of C = (S1 , . . . , Sn , R) is an n-tuple (X1 , . . . , Xn )
such that i∈{1,...,n} Xi ⊆ R and there are no i ∈ {1, . . . , n} and k ∈ Si \ Xi
Q
such that {k} × j∈{1,...,n}\{i} Xj ⊆ R.
1
2

http://dolques.free.fr/rcaexplore/
http://www.lirmm.fr/AOC-poset-Builder/

4

Kahn & Bazin
S2

S1

S3

Fig. 3: Visual representation of a 3-context without its crosses.

An n-concept can be viewed as a maximal n-dimensional box full of crosses
up to permutations on the elements of the dimensions. We denote by T (C) the
set of n-concepts of a n-context C.

a b c a bc
1××
×
2
×
3×
× ×
α
β

Fig. 4: An example of a 2 × 3 × 3 3-context.

In the Fig. 4 example, seven 3-concepts are present: (α, 1, ab), (αβ, 13, a),
(β, 3, ac), (β, 123, a), (αβ, 123, ∅), (αβ, ∅, abc) and (∅, 123, abc).
Definition 4 (From [15]). S = (S, .1 , . . . , .n ) is an n-ordered set if for A ∈ S
and B ∈ S :
1. A ∼i B, ∀i ∈ {1, . . . , n} ⇒ A = B (Uniqueness Condition)
2. A .i B, ∀i ∈ ({1, . . . , n} \ j) ⇒ B .j A (Antiordinal Dependency)
For the Antiordinal Dependency condition to be respected, it is sufficient to
have i, j ∈ {1, . . . , n}, i 6= j such that A .i B and B .j A.
The set of all the n-concepts of an n-context together with the n quasi-orders
.i induced by the inclusion relations on the subsets of each dimension forms an
n-ordered set. Additionally, the existence of some particular joins makes it a
complete n-lattice. Every n-lattice can be associated with some n-context [7].

Introducer Concepts in n-Dimensional Contexts

5

Definition 5. Let x ∈ Si be an element of a dimension i. We denote by Cx the
(n − 1)-context Cx = (S1 , . . . , Si−1 , Si+1 , . . . , Sn , Rx ) where
Rx = {(s1 , . . . , si−1 , si+1 , . . . , sn ) | (s1 , . . . , si−1 , x, si+1 , . . . , sn ) ∈ R}
With the previous definition, Cx is the (n − 1)-context corresponding to
element x, represented by the shaded area in Fig. 5.
x

S2

S1

S3

Fig. 5: If x is an element of S3 in this 3-context, then Cx is the 2-context resulting
from fixing x.

3

Introducer concepts in n-Lattices

In this section, we define introducer concepts in n-lattices. In the next definitions,
we will call dimension i the height, while all other dimensions are called the
width.
Definition 6. Let x ∈ Si be an element of a dimension i. The concepts with
maximal width such that x is in the height are the introducer concepts of x. The
set of introducer concepts of x is denoted by Ix .
In the Fig. 4 example, we have Iα = {(αβ, 13, a), (α, 1, ab)}.
S
We denote by I(Si ) = x∈S
Si Ix the set of concepts that introduce an element
of dimension i and by I(C) = i∈{1,...,n} I(Si ) the set of all introducer concepts
of a context C.
As in the 2-dimensional case, irreducible elements are introducer concepts.
However, I(C) is not always strictly the set of irreducible elements as some
applications expect the context not to be reduced.

6

Kahn & Bazin

Proposition 1. (I(C), .1 , . . . , .n ) is an n-ordered set.
Proof. Let A and B be in I(C). We recall that Ai ⊆ Bi ⇔ A .i B and that
Ai = Bi ⇔ A ∼i B. Without loss of generality, let A ∈ I(Si ) and B ∈ I(Sj ).
If ∀k ∈ {1, . . . , n}, A ∼k B, then ∀k ∈ {1, . . . , n}, Ak = Bk , so A = B
(Uniqueness Condition).
If A and B are distinct, ∃k ∈ {1, . . . , n} such that A .k B or B .k A. Without loss of generality, suppose A .k B. Suppose that there is no ℓ ∈ {1, . . . , n}
such that B .ℓ A. That implies that all the components of A are included in
the components of B. Then this is in contradiction with the maximality condition implied by A being a concept. Thus ∃j ∈ {1, . . . , n} \ i such that B .j A
(Antiordinal Dependency).
⊓
⊔
As in the 2-dimensional case where concept lattices and GSH are respectively
complete lattices and partially ordered sets, in the n-dimensional case we have
complete n-lattices and n-ordered sets.
Proposition 2. Let x ∈ Si . If (X1 , . . . , Xi−1 , Xi+1 , . . . , Xn ) is an (n − 1)concept of Cx , then (X1 , . . . , {x} ∪ Xi , . . . , Xn ) is an introducer of x.
If (X1 , . . . , {x}∪Xi , . . . , Xn ) is an introducer of x, then there exists an (n−1)concept (X1 , . . . , Xi−1 , Xi+1 , . . . , Xn ) in Cx .
Proof. We suppose, without loss of generality, that x ∈ S1 . The (n − 1)-concepts
of Cx are of the form (X2 , . . . , Xn ). If (x, X2 , . . . , Xn ) is an n-concept of C, then
it is minimum in height and maximal in width and is thus an introducer of x.
If (x, X2 , . . . , Xn ) is not an n-concept of C, as (X2 , . . . , Xn ) is a (n−1)-concept
of Cx , then (x, X2 , . . . , Xn ) can be augmented only on the first dimension. As
such, there exists an n-concept ({x} ∪ X1 , X2 , . . . , Xn ) that is maximal in width
and is thus an introducer of x.
Suppose that there is an X = (X1 , . . . , Xn ) ∈ Ix , x ∈ X1 , that is not obtained
from an (n − 1)-concept of Cx by extending X1 . It means that (X2 , . . . , Xn ) is
not maximal in Cx (else it would be an (n − 1)-concept). Then, there exists an
n-concept Y = (Y1 , Y2 . . . , Yn ) with Y1 ⊆ X1 and Xi ⊆ Yi , for i ∈ {2, . . . , n}.
This is a contradiction with the fact that X is an introducer of x.
⊓
⊔
Proposition 2 states that every (n − 1)-concept of Cx maps to an introducer
of x in C, and that every introducer of x is the image of an (n − 1)-concept of
Cx .

4

Algorithm

In this section, we present an algorithm to compute the introducer concepts in
an n-context.
Algorithm 1 computes the introducers for each element of a dimension i.
For a given element x ∈ Si , we compute T (Cx ). Then, for each (n − 1)-concept

Introducer Concepts in n-Dimensional Contexts

7

X ∈ T (Cx ), we build the set Xi needed
Q to extend X into an n-concept. An
element y is added to Xi when y × j6=i Xj ⊆ R, that is if there exists an
(n − 1)-dimensional box full of crosses (but not necessarily maximal) in R, at
level y. The final set Xi always contains at least x.

Algorithm 1: IntroducerDim(C, i)

1
2
3
4
5
6
7
8
9
10
11

Input: C an n-context, i ∈ {1, . . . , n} a dimension
Output: I(Si ) the set of introducer concepts of elements of dimension i
I←∅
foreach x ∈ Si do
C←∅
foreach X = (X1 , . . . , Xi−1 , Xi+1 , . . . , Xn ) ∈ T (Cx ) do
Xi ← ∅
foreach
Q y ∈ Si do
if j6=i Xj × y ⊆ R then
Xi ← Xi ∪ y
C ← C ∪ (X1 , . . . , Xi , . . . , Xn )
I ←I ∪C
return I

Algorithm 2 calls Algorithm 1 on each dimension. This ensure that each element of each dimension will be scanned for its introducer concepts. Algorithm 2
computes the introducer set I(C) for n-context C.

Algorithm 2: Introducers(C)

3

Input: C an n-context
Output: I(C) the set of all introducer concepts for C
R←∅
foreach dimension i do
R ← R ∪ IntroducerDim(C, i)

4

return R

1
2

Algorithm 1 requires the computation of the (n−1)-concepts from an (n−1)context. Several algorithms exist to complete this task [16–18].
Proposition 3. Algorithm 1 ends and returns all the introducer concepts of
elements of the dimension Si .

8

Kahn & Bazin

Proof. The Si are finite. The set of (n−1)-concepts of an (n−1)-context resulting
from fixing an element is also finite. Algorithm 1 passes through each element
x ∈ Si and on each concept of T (Cx ) exactly once. The maximality test on
dimension i looks at the elements of Si , which is finite. Thus, the algorithm
ends.
Proposition 2 ensures that every introducer of x can be computed from the
concepts of Cx . Thus, every introducer of an element of the dimension Si is
returned.
⊓
⊔
At the time of writing, the only
Q known bound for the number of n-concepts of
an n-context (S1 , . . . , Sn , R) is i∈{1,...,n}\k 2|Si | with k = argmaxk∈{1,...,n} |Sk |.
Let Kn be the maximal number of n-concepts in an n-context. Computing Cx
from C is in O(|R|). Building the set Xi that extends
an (n − 1)-concept of Cx
Q
into an introducer of x can be done in O(|Si | × j6=i |Xj |).We denote by T the
complexity of computing T (Cx ) from Cx .
Thus the complexity
C = (S1 , . . . , Sn , R) and

of AlgorithmQ1 for context 
dimension i is O |Si | × T + Kn−1 × j∈{1,...,n} |Sj |
and the complexity of

P


Q
|S
|
.
Algorithm 2 is O
|S
|
×
T
+
K
×
j
i
n−1
j∈{1,...,n}
i∈{1,...,n}

5

Conclusion

In this paper, we introduced the n-dimensional equivalent of Galois Sub-Hierarchies
or AOC-posets. We showed that the set of introducer concepts, together with the
n quasi-orders induced by the inclusion on each dimension, forms an n-ordered
set. We provided an algorithm to compute the set of introducer concepts from
an n-context.
Although our approach was not initially motivated by an applicative problem,
it would be interesting to use the notion of introducer concepts in n-dimensions
to address some specific problems in software engineering or data mining.
It would be interesting to experiment on datasets (real and generated) to
evaluate the gains (in term of number of concepts) of the restriction to introducer
concepts.

Acknowledgements
This research was partially supported by the European Union’s “Fonds Européen
de Développement Régional (FEDER)” program.

References
1. Bernhard Ganter and Rudolf Wille. Formal Concept Analysis - Mathematical
Foundations. Springer, 1999.

Introducer Concepts in n-Dimensional Contexts

9

2. Robert Godin, Hafedh Mili, Guy W. Mineau, Rokia Missaoui, Amina Arfi, and
Thuy-Tien Chau. Design of Class Hierarchies Based on Concept (Galois) Lattices.
TAPOS, 4(2):117–134, 1998.
3. Robert Godin and Hafedh Mili. Building and Maintaining Analysis-Level Class
Hierarchies Using Galois Lattices. In 8th Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA), pages 394–410, 1993.
4. Jessie Carbonnel, Marianne Huchard, and Alain Gutierrez. Variability Representation in Product Lines using Concept Lattices: Feasibility Study with Descriptions
from Wikipedia’s Product Comparison Matrices. In Proceedings of the International Workshop on Formal Concept Analysis and Applications, FCA&A 2015, colocated with 13th International Conference on Formal Concept Analysis (ICFCA
2015), Nerja, Málaga, Spain, June 23-26, 2015., pages 93–108, 2015.
5. Xavier Dolques, Florence Le Ber, Marianne Huchard, and Corinne Grac.
Performance-Friendly Rule extraction in Large Water Data-sets with AOC Posets
and Relational Concept Analysis. Int. J. General Systems, 45(2):187–210, 2016.
6. Alexandre Bazin, Jessie Carbonnel, and Giacomo Kahn. On-Demand Generation
of AOC-Posets: Reducing the Complexity of Conceptual Navigation. In Foundations of Intelligent Systems - 23rd International Symposium, ISMIS 2017, Warsaw,
Poland, June 26-29, 2017, Proceedings, pages 611–621, 2017.
7. George Voutsadakis. Polyadic Concept Analysis. Order, 19(3):295–304, 2002.
8. Marianne Huchard, Mohamed Rouane Hacene, Cyril Roume, and Petko Valtchev.
Relational Concept Discovery in Structured Datasets. Ann. Math. Artif. Intell.,
49(1-4):39–76, 2007.
9. Mehwish Alam, Thi Nhu Nguyen Le, and Amedeo Napoli. Latviz: A New Practical
Tool for Performing Interactive Exploration over Concept Lattices. In Proceedings
of the Thirteenth International Conference on Concept Lattices and Their Applications, Moscow, Russia, July 18-22, 2016., pages 9–20, 2016.
10. Petko Valtchev, David Grosser, Cyril Roume, and M Rouane Hacene. Galicia: an
open platform for lattices. In Using Conceptual Structures: Contributions to the
11th Intl. Conference on Conceptual Structures (ICCS03), pages 241–254, 2003.
11. Hervé Dicky, Christophe Dony, Marianne Huchard, and Thérèse Libourel. Ares,
Adding a Class and Restructuring Inheritance Hierarchy. In 11èmes Journées
Bases de Données Avancées, pages 25–42, 1995.
12. Marianne Huchard, Hervé Dicky, and Hervé Leblanc. Galois Lattice as a Framework to Specify Building Class Hierarchies Algorithms. ITA, 34(6):521–548, 2000.
13. Gabriela Arévalo, Anne Berry, Marianne Huchard, Guillaume Perrot, and Alain
Sigayret. Performances of Galois Sub-Hierarchy-Building Algorithms. In Formal
Concept Analysis, 5th International Conference, ICFCA 2007, Clermont-Ferrand,
France, February 12-16, 2007, Proceedings, pages 166–180, 2007.
14. Anne Berry, Alain Gutierrez, Marianne Huchard, Amedeo Napoli, and Alain
Sigayret. Hermes: a Simple and Efficient Algorithm for Building the AOC-Poset of
a Binary Relation. Annals of Mathematics and Artificial Intelligence, 72(1-2):45–
71, 2014.
15. George Voutsadakis. Dedekind-Macneille Completion of n -Ordered sets. Order,
24(1):15–29, 2007.
16. Loı̈c Cerf, Jérémy Besson, Céline Robardet, and Jean-François Boulicaut. Closed
Patterns Meet n-ary Relations. TKDD, 3(1):3:1–3:36, 2009.
17. Tatiana Makhalova and Lhouari Nourine. An Incremental Algorithm for Computing n-Concepts.
18. Alexandre Bazin, Giacomo Kahn, and Olivier Raynaud. An Incremental Algorithm
for Computing n-Dimensional Concepts. 2017.

