=Paper=
{{Paper
|id=Vol-2972/paper3
|storemode=property
|title=FCA Went (Multi-)Relational, But Does It Make Any Difference?
|pdfUrl=https://ceur-ws.org/Vol-2972/paper3.pdf
|volume=Vol-2972
|authors=Mickaël Wajnberg,Petko Valtchev,Mario Lezoche,Alexandre Blondin-Massé,Hervé Panetto
|dblpUrl=https://dblp.org/rec/conf/ijcai/WajnbergVLMP21
}}
==FCA Went (Multi-)Relational, But Does It Make Any Difference?==
https://ceur-ws.org/Vol-2972/paper3.pdf
FCA Went (Multi-)Relational, But Does It
Make Any Difference?
Mickaël Wajnberg1 , Petko Valtchev1 , Mario Lezoche2 , Alexandre
Blondin-Massé1 , and Hervé Panetto2
1
Université du Québec À Montréal, Canada {name.firstname}@uqam.ca
2
Université de Lorraine, France {firstname.name}@univ-lorraine.fr
Abstract. Relational Concept Analysis (RCA) was designed as an ex-
tension of Formal Concept Analysis (FCA) to multi-relational datasets,
such as the ones drawn from Linked Open Data (LOD) by the type-wise
grouping of the resource into data tables. RCA has been successfully
applied to practical problems of AI such as knowledge elicitation, knowl-
edge discovery from data and knowledge structuring. A crucial question,
yet to be answered in a rigorous manner, is to what extent RCA is a true
extension of FCA, i.e. reveals concepts that are beyond the reach of core
FCA even using a suitable encoding of the original data. We show here
that the extension is effective: RCA retrieves all concepts found by FCA
as well as many further ones.
Keywords: Multi-relational Data · Formal Concept Analysis · RDF
· Propositionalization.
1 Introduction
FCA provides the mathematical framework for several Knowledge Discovery in
Databases (KDD) tasks whenever the data is purely, or at least predominantly,
of categorical nature. Indeed, FCA-based association discovery and conceptual
clustering have been applied to knowledge base structuring, ontology learning,
anomaly detection, observation classification, etc. Most real datasets, though,
stray from being purely categorical. FCA thus provides a set of scaling operators
to deal with numerical and otherwise ordered scales. In AI, the majority of
interesting data, such as those compatible with the LOD format, have relational
structure. They can be represented either as graphs (for instance, named graphs
in RDF) or as sets of relational tables. Approaches have been designed for the
former, emphasizing the intra-data object links, e.g. logical FCA [7] and pattern
structures [8], for graph datasets. For the latter, the focus is on inter-object links,
e.g. in datasets structured as a unique RDF graph. In this second trend, more
akin to power-context families [15] and Graph-FCA [6], we focus on the particular
approach of relational concept analysis (RCA). It has already been successfully
applied to a wide range of practical problems such as hydroecology [4], industrial
decision making [12] or biology [1,13]. Rather than in a global graph, RCA shapes
the data as a set of ×-tables, complying to the Entity-Relationship framework [2].
Copyright c 2021 for this paper by its authors. Use permitted under Creative
Commons License Attribution 4.0 International (CC BY 4.0).
Part of the tables have the classical objects × properties format (entity types,
FCA contexts) while the remainder represent objects × objects relations.
A natural question is whether RCA does extend the reach of FCA, knowing
that for single datasets, whatever the level of complexity of the object descrip-
tions (sequences, trees, graphs), the results of an FCA-based processing on those
descriptions can be brought down to FCA on a context made of suitably-chosen
derived attributes. The question is all the more important as prior studies seem
to imply it does not [3] (though, for a reduced version of RCA). We make the
case here for RCA as a true extension of FCA, in the sense that due to its
multi-relational input and fixed point computation, it detects concepts that are
out of reach for FCA while, in turn, retrieving all concepts that FCA is able to
reveal. To that end, we chose some plausible re-encodings of a simple relational
context family (RCF), the hypothesis being that with more complex datasets,
the phenomenon only amplifies.
The remainder of the paper is as follows: Section 2 provides background on
RCA while Section 3 presents our FCA-vs-RCA comparison. Next, Section 4
discusses the comparison outcome and Section 5 concludes.
2 Background
Formal concept analysis [14] is a mathematical method for eliciting the con-
ceptual structure of “object × attribute” datasets. Data are gathered within a
(formal) context, a triple K = (O, A, I) where O is a set of objects, A is a set of
attributes and I ⊆ O × A is the context incidence relation, where (o, a) ∈ I, also
written oIa, means that the object o bears the attribute a. A context induces
two derivation operators: one mapping objects to attributes, and the reciprocal.
The object derivation 0 maps a subset X of objects to the set of attributes shared
by all members of X, 0 : ℘(O) −→ ℘(A) with 0 : X 7→ {a ∈ A | oIa ∀o ∈ X}.
The dual attribute derivation, also denoted by 0 , works the other way around,
0
: ℘(A) −→ ℘(O) with 0 : Y 7→ {o ∈ O | oIa ∀a ∈ Y }. Inside a context K, a
(formal) concept is a pair (X, Y ) ⊆ O × A such that X 0 = Y and Y 0 = X. The
sets X and Y are called extent and intent of the concept (X, Y ), respectively.
FCA extracts conceptual abstractions on objects by factoring out shared at-
tributes. Relational concept analysis [10] extends it by factoring in relational
information, as available in multi-relational datasets [5]. RCA admits multiple
sorts of objects in its input format, each organized as a separate context, plus
a set of binary relations between contexts. The input data structure, called re-
lational context family (RCF), is thus a pair (K, R) where K = {Ki }i=1,...,n
is a set of distinct contexts Ki = (Oi , Ai , Ii ) and R = {rk }k=1,...,m a set
of binary relations rk ⊆ Oi × Oj where the contexts Ki and Kj are the do-
main and range contexts of rk , respectively. Relational tables are also processed
in their own way, as explained below. A cross in the table of relation r for
(domain_objecti , range_objectj ), can be understood as the first order logic
term r(domain_objecti , range_objectj ) being true.
RCA distills the shared relational information (i.e., inter-object links) using
propositionalization [9]: It integrates new attributes into an extended version
of the initial context, say Kd = (Od , Ad , Id ), to further refine the conceptual
structure of the underlying object set. To increase shareability, rather than the
individual objects from the target (range) context, say Kt , the new attributes
refer to abstractions on them. In its most basic version, RCA exploits the natural
conceptual structure provided by the concepts of each context. Indeed, two links
of relation r : d −→ t departing from o1 and o2 from Od and referring to
two distinct objects ō1 and ō2 from Ot , respectively, are distinct information.
However, replacing ō1 and ō2 with a common abstraction, say {ō1 , ō2 }0 , makes the
new information shareable. Relational scaling follows a well-known schema from
description logics: Given a relation r, for each concept ct from the range context
of r, it produces, for Ad , an attribute q r : cr where q is an operator chosen
before-hand from a set Q. RCA admits, among others, standard description
logics restrictions (Q = {∃, ∀, ∀∃, . . .}), which behold their respective semantics
(see [10] for details and example 1 for illustration).
Example 1. Assume a RCF made of contexts on people and cars, and an owner-
ship relation, or pos(sesses), which are given in Tables 1, 3 and 2, respectively.
The cars lattice is shown in Figure 1. Now, an ∃-scaling of the relation pos using
that lattice will add, for each car concept c, a new attribute ∃pos : c to the
person context, e.g. ∃pos : cars_4 and ∃pos : cars_3 that can be rewritten as
∃pos : (cp) and ∃pos : (el, pw), respectively, using intents as IDs.
pos tw t3 zo f 5
Fa ×
KP La × ×
Senior
Adult
Male
Female
I.T.
Sport
Sh × ×
Tr
Table 2: Relation pos
Fa × ×
La × ×× KC el pw cp ch
Sh × ×
tw × ×
Tr ×× ××
t3 × ×
Table 1: Person Context
zo × ×
f5 × × Fig. 1: Car Lattice
Table 3: Car Context
A scaling step results in the related contexts being extended, which, in turn,
may lead to the emergence of new concepts. Thus, as the set of available ab-
stractions increases, a scaling step with the differential set of concepts would
produce further relational attributes and the whole process would go on cycling.
The resulting iterative context refinement necessarily ends at a fixed point [10],
i.e. a set of lattices whose concepts refer to each other via relational attributes.
3 What can RCA do for AI (that FCA can’t) ?
Below, we examine two encoding strategies that bring a multi-relational dataset
to a mono-relational one, i.e. aggregate several contexts into a single data table,
so that they can be fed to classical FCA.
3.1 Encoding multiple contexts into a single one
Assume a simple RCF made of two contexts and a relation (see Figure 2). We
use this simple case for our reasoning, knowing that in more complex cases, i.e.
three or more contexts and several relations, it can be extended appropriately.
Moreover, while there could be a wide range of concrete encoding disciplines [11],
the principle behind them admits only two basic cases, i.e. entity-centric and
relation-centric. In our FCA/RCA perspective this boils down to which sort of
RCF element, i.e. context or relation, is put center-stage.
A1 A2 A1 ρ(A2 )
A1 O2 A2
O1 I1 O1 r O2 I2 O./ O1
Fig. 2: Fictitious RCF
Fig. 3: Semi-join Fig. 4: Aggregation
The first encoding principle we examine below emphasizes the object-to-
object relation as a primary construct and pivotal element of the encoding.
Its member pairs become first-class objects which carry the attributes of both
contexts incident to the relation. Technically speaking, the method is akin to
the (semi-)join operation of relational algebra. The overall encoding schema is
illustrated in Figure 3 whereas Section 3.2 proposes a formal definition thereof.
It also provides a detailed comparison of the results from applying RCA to the
RCF from Figure 2 with those of FCA on the semi-join of the two initial contexts.
A bit closer to the RCA propositionalization spirit, a second encoding princi-
ple emphasizes the context as a main construct and driver of the encoding: The
domain context of the relation is extended with some additional attributes that
translate the relation while following a technique akin to relational scaling. The
main difference here is that the context is the one-shot context extension. The
procedure whose details are discussed in Section 3.3, is schematically illustrated
in Figure 4. Moreover, the asymmetric encoding of the relation and the one-
shot extension amount to processing the range context as if it were aggregated
into the domain one. Therefore, we termed the overall encoding principle the
aggregation and the resulting context the aggregated one.
Finally, please notice that in the detailed investigation of each case (see be-
low), our reasoning follows three steps: 1) We pick an arbitrary formal concept
from the FCA output, 2) we show the RCA output comprises a concept with the
same objects, and 3) we establish the link between the intents of both concepts.
3.2 Semi-join in single relation RCF
We consider here the concurrent case where the FCA is applied on a context
encoding the semi-join of this RCF, as presented in Figure 3. This encoding
consists in creating the objects of O./ as the object pairs (o1 , o2 ) where o1 ∈
O1 ∪ {⊥}, o2 ∈ O2 ∪ {⊥}, according to the RCF modeling of O1 , O2 Figure 2.
The ⊥ object is a fictitious empty object with no attributes used to complete
the semi-join. There are three cases to define the elements of O./ :
– If o1 ∈ O1 , o2 ∈ O2 , then (o1 , o2 ) ∈ O./ if and only if (o1 , o2 ) ∈ r
– If o1 = ⊥, o2 ∈ O2 , then (o1 , o2 ) ∈ O./ if and only if r−1 (o2 ) = ∅, i.e. if there
is no x ∈ O1 such that (x, o2 ) ∈ r
– If o1 ∈ O1 , o2 = ⊥, then (o1 , o2 ) ∈ O./ if and only if r(o1 ) = ∅, i.e. if there
is no x ∈ O2 such that (o1 , x) ∈ r
Example 2. As an illustration of the above modeling, assume an RCF made of
contexts for people (Table 1) and for cars (Table 3) plus an ownership relation
(possession, Table 2). In the first context, Farley, Lane, Shana, and Trudy are
described by being senior or adult, male or female, working in IT, and practicing
a lot of sports. Cars –Twingo, Tesla 3, Zoe, and Fiat 500– can be electrical,
powerful, compact or (not exclusive) cheap. The corresponding semi-join context
is presented in Table 4.
K./ el pw cp ch
Senior
Adult
Male
Female
I.T.
Sport
(Fa,tw) × × × ×
(La,t3) × ×× × ×
(La,f 5) × × × × ×
(Sh,tw) × × × ×
(Sh,f 5) × × × ×
(Tr,⊥) ×× ××
(⊥,zo) × ×
Table 4: Semi-join context of Example 2 RCF
To avoid ambiguity, we consider the derivations in the K1 and K2 contexts
always denoted x0 , while the derivation in the join context is denoted x∇ (and
the double derivation x∇∇ ).
We are first interested in describing a formal concept of the joined context.
Let X ⊆ O./ be a set of objects. So, for all (o1 , o2 ) ∈ X we have o1 ∈ O1 ∪ {⊥}
and o2 ∈ O2 ∪ {⊥}. Thus, by definition, C = (X ∇∇ , X ∇ ) is a formal concept.
Let us now take the projections on the first and second elements of the pairs of
X ∇∇ , i.e. π1 = {o1 | ∃o2 , (o1 , o2 ) ∈ X ∇∇ } and π2 = {o2 | ∃o1 , (o1 , o2 ) ∈ X ∇∇ }.
We start by defining X ∇∇ in terms of these projections.
Lemma 1 We have X ∇∇ = (π1 × π2 ) ∩ O./
Proof. Let (u, v) ∈ X ∇∇ . By definition X ∇∇ ⊆ O./ , so (u, v) ∈ O./ . Moreover,
by construction u ∈ π1 and v ∈ π2 so (u, v) ∈ π1 × π2 . Thus, X ∇∇ ⊆ (π1 × π2 ) ∩
O./ .
Let (u, v) ∈ (π1 × π2 ) ∩ O./ . Since (u, v) ∈ (π1 × π2 ), it exists ũ and ṽ s.t.
(u, ũ) ∈ X ∇∇ and (ṽ, v) ∈ X ∇∇ . But, by construction {(u, ũ), (ṽ, v)}∇ ⊆ u0 ∪ v 0 .
And, since (u, v) ∈ O./ we can write (u, v)∇ = u0 ∪ v 0 . Thus, by derivation
property we have X ∇∇∇ ⊆ {(u, ũ), (ṽ, v)}∇ , by transitivity X ∇∇∇ ⊆ (u, v)∇ .
Thus, by deriving this expression we obtain (u, v)∇∇ ⊆ X ∇∇∇∇ . Finally, as
(u, v) ∈ (u, v)∇∇ and X ∇∇∇∇ = X ∇∇ we have (u, v) ∈ X ∇∇ . t
u
We first study the particular cases containing the object ⊥ by starting with
the case where this element appears in both projections.
Proposition 1 If ⊥ ∈ π1 and ⊥ ∈ π2 then X ∇ = ∅ and X ∇∇ = O./
Proof. Suppose ⊥ ∈ π1 and ⊥ ∈ π2 then by definition of ⊥ we have X ∇ ∩ A1 = ∅
and X ∇ ∩ A2 = ∅ and therefore X ∇ = ∅. By definition of the derivation we have
∅∇ = O./ therefore X ∇∇ = O./ .The second assertion holds by symmetry. t
u
In the case described by the lemma 1, it is immediate to show that we can
construct (X ∇∇ , X ∇ ). We show that the same is true when only one of the
components π1 or π2 contains ⊥ by first describing X ∇ then X ∇∇ in the lemmas
2 and 3.
Lemma 2 If ⊥ ∈ π1 and ⊥ 6∈ π2 , X ∇ = π20 . If ⊥ ∈ π2 and ⊥ 6∈ π1 , X ∇ = π10 .
Proof. Let us suppose ⊥ ∈ π1 and ⊥ 6∈ π2 . We have a ∈ X ∇ iff X ∇∇ ⊆ a∇ . Yet,
since ⊥ ∈ π1 we have construction X ∇ ∩ A1 = ∅. thus, we have a ∈ A2 .therefore,
we have a ∈ X ∇ iff for all (o1 , o2 ) ∈ X ∇∇ o2 carries the attribute a, i.e. a ∈ π20 .
Since we have a ∈ X ∇ iff a ∈ π20 , we have X ∇ = π20 . We show the second
assertion symmetrically. t
u
Lemma 3 If ⊥ ∈ π1 and ⊥ 6∈ π2 , X ∇∇ = (O1 ∪ {⊥} × π2 ) ∩ O./ . If ⊥ ∈ π2 and
⊥ 6∈ π1 , X ∇∇ = (π1 × O2 ∪ {⊥}) ∩ O./ .
Proof. Let us suppose ⊥ ∈ π1 and ⊥ 6∈ π2 . Let v ∈ π2 . Any pair (u, v) ∈ O./
verifies π20 ⊆ (u, v)∇ . Since, by the lemma 2, we have X ∇ = π20 , we can write
X ∇ ⊆ (u, v)∇ and thus, by derivation (u, v)∇∇ ⊆ X ∇∇ . Finally, for any u ∈
O1 ∪ {⊥}, we have (u, v) ∈ X ∇∇ donc X ∇∇ = (O1 ∪ {⊥} × π2 ) ∩ O./ . We show
the second assertion symmetrically. t
u
The lemmas 2 and 3 allow us to determine that in cases where only one of
the projections contains ⊥ we can write a formal concept of K./ only with the
other projection. Let us now study a formal concept based on this projection
determined by RCA.
Lemma 4 If ⊥ ∈ π1 and ⊥ 6∈ π2 , there exists a concept C2 = (π2 , π20 ) on K2 .
If ⊥ ∈ π2 and ⊥ 6∈ π1 , there exists a concept C1 = (π1 , π10 ) on K1 .
Proof. Let us suppose ⊥ ∈ π1 and ⊥ 6∈ π2 . Since π2 ⊆ O2 , (π200 , π20 ) is a concept
son K2 . It is therefore sufficient to show that π200 = π2 , or more simply π200 ⊆ π2 .
Let o ∈ π200 . By construction at least one couple (ō, o) ∈ O./ and o0 ⊆ (ō, o)∇ .
Now, we have o ∈ π200 so by derivation, π20 ⊆ o0 . Moreover, by the lemma 2, we
have X ∇ = π20 . Thus, X ∇ ⊆ (ō, o)∇ so by derivation, (ō, o) ∈ X ∇∇ . Finally, by
definition of the projections o ∈ π2 . The second assertion holds by symmetry. t u
The following proposition gathers the previous lemmas. It emphasizes that,
in the case where only one of the two projections contains ⊥, any concept of
K./ can be expressed with the other projection. Moreover, there exists a con-
cept generated by RCA, of the same intent and whose extent corresponds to a
projection of the extent of the concept generated by FCA.
Proposition 2 Let C = (X ∇∇ , X ∇ ). If ⊥ ∈ π1 and ⊥ 6∈ π2 , C = ((O1 ∪ {⊥} ×
π2 ) ∩ O./ , π20 ) and there exists a corresponding concept C2 = (π2 , π20 ) on K2 .
If ⊥ ∈ π2 and ⊥ 6∈ π1 , C = ((π1 × O2 ∪ {⊥}) ∩ O./ , π10 ) and there exists a
corresponding concept C1 = (π1 , π10 ) on K1 .
Proof. Follows from the lemmas 2, 3 and 4. t
u
There remains a specific case, described by the lemma 5, to complete the
exhaustive description of a formal concept on the join table.
Lemma 5 For any X ⊆ O1 × O2 we have X ∇ = π10 ∪ π20 and X ∇∇ = {(o1 , o2 ) |
π10 ⊆ o01 ∧ π20 ⊆ o02 }
Proof. Let us show X ∇ = π10 ∪ π20 by double inclusion.
(i) X ∇ ⊆ π10 ∪ π20 .
The RCF modeling assures us that A1 ∩ A2 = ∅. Thus, an attribute a ∈ X ∇
is either in A1 or in A2 . If a ∈ X ∇ ∩ A1 , it must be shared by all the elements
of π1 ; and so a is in π10 . Similarly, if a is in X ∇ ∩ A2 , a ∈ π20 . We deduce that
X ∇ ⊆ π10 ∪ π20 .
(ii) π10 ∪ π20 ⊆ X ∇ .
On the other hand, if an attribute a is in π10 , then any pair of X ∇∇ has a first
component that carries the attribute a. Since this property is true for any pair
of X ∇∇ and X ⊆ X ∇∇ , then any pair of X carries the attribute a. Therefore,
we have a ∈ X ∇ . In the same way, we show that if a ∈ π20 , then a ∈ X ∇ . thus,
we have π10 ⊆ X ∇ and π20 ⊆ X ∇ . We can therefore affirm that π10 ∪ π20 ⊆ X ∇ .
Finally, by (i) and (ii) we have X ∇ = π10 ∪ π20 . As X ∇∇ describes exactly the
set of couples (o1 , o2 ) having the attributes of π10 ∪ π20 , by construction of the
join table we have π10 ⊆ o01 and π20 ⊆ o02 . t
u
The cases described by the lemmas 1 and 2 allow for the immediate selection
of concepts from the RCA process corresponding in terms of extent to a concept
in the join table. The proposition 3 relies on the lemma 5 to state the main result
of this subsection, dealing with non-degenerate cases (without ⊥ element).
Proposition 3 Let X ⊆ O1 ×O2 . There exists by RCA on K1 a concept (X1 , Y1 )
such that X1 = π1 and π10 ⊆ Y1 and there exists on K2 a concept (X2 , Y2 ) such
that X2 = π2 and π20 ⊆ Y2 .
Proof. As π10 ⊆ A1 and π20 ⊆ A2 , C1 = (π100 , π10 ) and C2 = (π200 , π20 ) are formal
concepts on their respective contexts computed at step 0 of RCA.
Let us consider the contexts K1 and K2 after graduation by the operator
∃ on the relations r and r−1 . We then have the attributes ∃r : C2 in K1 and
∃r−1 : C1 in K2 . We define the sets of attributes Y1 = π10 ∪ {∃r : C2 } and
Y2 = π20 ∪ {∃r−1 : C1 } as well as the concepts C3 = (Y10 , Y100 ) and C4 = (Y20 , Y200 )
(it is possible that C1 = C3 or C2 = C4 ). We have Y10 = π100 ∩ {∃r : C2 }0 , let us
show that Y10 = π1 by double inclusion.
Let o ∈ π1 , we have o ∈ π100 . Moreover, by construction, any pair of (o, ō) ∈
X ∇∇
verifies (o, ō) ∈ r with ō ∈ π2 and, by hypothesis, ō 6= ⊥. Thus, since
π2 ⊆ π200 , o carries the attribute ∃r : C2 . Thus, we have π1 ⊆ Y10 .
Let o ∈ Y10 . We have π10 ∪ {∃r : C2 } ⊆ o0 . Since {∃r : C2 } ⊆ o0 , there exists
ō ∈ π200 such that (o, ō) ∈ r and thus (o, ō) ∈ O./ . Moreover, since ō ∈ π200 , we have
π20 ⊆ ō0 . Since π20 ⊆ ō0 , π10 ⊆ o0 and that by the lemma 5 we have X ∇ = π10 ∪ π20 ,
we can affirm X ∇ ⊆ (o, ō)∇ . Finally (o, ō)∇∇ ⊆ X ∇∇ and by definition of π1 ,
on a o ∈ π1 (In a completely analogous way, we show π2 = Y20 ).
Finally, we have shown the existence of C3 = (Y10 , Y100 ) such that Y10 = π1 and
π1 ⊆ Y100 as well as of C4 = (Y20 , Y200 ) such that Y20 = π2 and π2 ⊆ Y200 . t
u
In conclusion, the propositions 1, 2 and 3 show that for any concept C =
(X ∇∇ , X ∇ ) we find on K1 a concept (X1 , Y1 ) such that X1 = π1 and π10 ⊆ Y1
and there exists on K2 a concept (X2 , Y2 ) such that X2 = π2 and π20 ⊆ Y2 . It
is to note that if ⊥ ∈ π1 (respectively π2 ) we have π1 = {x | ∃y, (x, y) ∈ O./ }
(respectively π2 = {x | ∃x, (x, y) ∈ O./ }). Example 3 illustrates these properties.
Example 3. Let us consider the relational family as well as the semi-join context
defined in the Example 2.
On the joined context, we find the concept C = ({(La, t3), (La, f 5)}, {Adult,
Female, IT, pw}). Here, π1 = {La} and π2 = {t3, f 5}. We check that there exists
on KP a concept (π1 , π10 ), namely the concept C1 = ({La}, {Adult, F emale,
IT }), and on KC a concept (π2 , π20 ), the concept C2 = ({t3, f 5}, {pw}). After an
iteration, RCA extends these concepts’ intents to {Adult, F emale, IT, ∃pos : C2 }
and {pw, ∃pos−1 : C1 }, respectively.
3.3 Aggregation operation in mono-relational case
Assume again the RCF in Figure 2 and let us consider FCA is applied on the
context schematically visualized in Figure 4. Intuitively, this amounts to extend-
ing the domain context of the relation by appending some new attributes. These
are derived from the range context attributes by a technique akin to relational
scaling, i.e. one basically simulating a one-shot RCA-like context refinement.
Formally speaking, we design the context Kl = (Ol , Al , Il ) where Ol =
O1 , Al = A1 ∪ρ(A2 ), and ρ(A2 ) are the attributes resulting from the application
of the scaling operator ρ to the attribute concept of a ∈ A2 . We will denote such
an attribute ρr : a to avoid confusion with RCA’s own relational attributes. No-
tice that A1 ∩ ρ(A2 ) = ∅ holds. Next, we introduce Constraint(ρ, r, op , (X, Y )),
a predicate verifying whether op and (X, Y ), from the domain and the range of r,
respectively, jointly comply to the semantic of ρ. Thus, Constraint(∀, r, op , (X, Y ))
is true iff r(op ) ⊆ X. The predicate is a compact expression of the incidence Il :
– if ap ∈ A1 then (op , ap ) ∈ Il iff (op , ap ) ∈ I1 ,
– if ap ∈ ρ(A2 ) then (op , ap ) ∈ Il iff Constraint(ρ, r, op , (a0p , a00p )) is true.
Example 4 illustrates the ∀∃ case (reasoning with other operators is similar).
For the O2 perspective, it is enough to swap K1 and K2 and replace r by r−1 .
Example 4. Consider again the RCF in Example 2. We aggregate the family via
∀∃: For an o ∈ OP and a ∈ AC s.t. ∀∃pos : a ∈ ρ(AC ) it holds (o, ∀∃pos : a) ∈ I
iff 1) ∃oC ∈ OC s.t. (o, oC ) ∈ pos and 2) ∀oC ∈ OC , (o, oC ) ∈ pos entails ov ∈ a0
(there is at least one image of o by pos and all such images carry a. Table 5
depicts the resulting aggregated context Kl .
Kl
Senior
Adult
Male
Female
I.T.
Sport
∀∃pos : el
∀∃pos : pw
∀∃pos : cp
∀∃pos : ch
Kl
Senior
Adult
Male
Female
I.T.
Sport
∃pos : el
∃pos : pw
∃pos : cp
∃pos : ch
Fa × × × × Fa × × × ×
La × ×× × La × ×× × × ×
Sh × × × Sh × × × × ×
Tr ×× ×× Tr ×× ××
Table 5: Kl for Example 4 Table 6: Kl for Example 6
To define a formal concept on the aggregated table, we first identify the
component of the intent on the part ρ(A2 ). Again, we denote the derivations in
K1 and K2 by 0 , and in the aggregated context by ∇ .
Definition 1. The relational deviation of X ⊆ Ol , denoted δ(X), is the set of
its attributes from ρ(A2 ), i.e. δ(X) = X ∇ ∩ ρ(A2 ).
Proposition 4 Given a X ⊆ Ol , δ(X) = ∩o∈X {ρr : a | Constraint(ρ, r, o, (a0 , a00 ))}.
Proof. Let o ∈ X. By construction, for any ρr : a ∈ ρ(A2 ), holds ρr : a ∈ o∇
(a0 , a00 )). Thus o∇ ∩ ρ(A2 ) = {ρrT: a | Constraint(ρ, r, o,
iff Constraint(ρ, r, o,T
(a , a ))}. As X = o∈X o0 , we have X 0 ∩ ρ(A2 ) = o∈X o∇ ∩ ρ(A2 ), hence
0 00 0
δ(X) = ∩o∈X {ρr : a | Constraint(ρ, r, o, (a0 , a00 ))}. t
u
A formal concept on the aggregated context is then characterized by:
Proposition 5 Let X ⊆ Ol , then the concept C = (X ∇∇ , X ∇ ) of the aggre-
gated context satisfies X ∇ = X 0 ∪ δ(X) and X ∇∇ = X 00 ∩ {o | δ(X) ⊆ o∇ }.
Proof. By definition, we have Al = A1 ∪ ρ(A2 ) and A1 ∩ ρ(A2 ) = ∅. Thus we
can write X ∇ = (X ∇ ∩ A1 ) ∪ (X ∇ ∩ ρ(A2 )), that is X ∇ = X 0 ∪ δ(X).
By deriving X ∇ , we determine that X ∇∇ = {o | o ∈ O1 ∧ X 0 ⊆ o∇ ∧ δ(X) ⊆
o }. Now, as X 0 ⊆ A1 , we have X 0 ⊆ o∇ iff X 0 ⊆ o∇ ∩ A1 , that is X 0 ⊆ o0 .
∇
Finally, X ∇∇ = X 00 ∩ {o | δ(X) ⊆ o∇ }. t
u
Now, let us assume we have the result of RCA using the same relational
scaling with ρ along r on the simple RCF in Figure 2. Let X be the extent of
a concept from Kl . The set δ(X) is well-defined, hence we can denote its i-th
member by ρr : aδ,i (where aδ,i ∈ A2 ). As every concept Cδ(X),i = (a0δ,i , a00δ,i ) is
well defined on K2 , in RCA, K1 will be refined with all the attributes ρr : Cδ(X),i
at the first relational scaling step. Let Yδ = X 0 ∪i∈1..|δ(X)| ρr : Cδ(X),i , we claim
that C = (X ∇∇ , X ∇ ) and Cδ = (Yδ0 , Yδ00 ) have the same extent:
Proposition 6 Yδ0 = X ∇∇ .
Proof. Yδ0 ⊆ X ∇∇ : Let o ∈ Yδ0 . First, o carries all the attributes of X 0 , thus
X 0 ⊆ o∇ . Moreover, for each attribute ρr : aδ,i ∈ δ(X) a concept Ci = (a0δ,i , a00δ,i )
exists such that o carries the attribute ρr : Ci (for which Constraint(ρ, r, o, Ci )
is true). Since aδ,i is in the intent of Ci , we can verify that ρr : aδ,i ∈ o∇ . Since for
all i, we have ρr : aδ,i ∈ o∇ , then we have δ(X) ⊆ o∇ . Finally, since δ(X) ⊆ o∇
and X 0 ⊆ o∇ , we have X ∇ ⊆ o∇ . By derivation, we have o∇∇ ⊆ X ∇∇ . Finally,
Yδ0 ⊆ X ∇∇ . t
u
Yδ0 ⊇ X ∇∇ : The 1st relational scaling step will necessarily produce ρr :
(a0δ,i , a00δ,i ) for each ρr : aδ,i ∈ δ(X). Let o ∈ X ∇∇ , then o carries all the attributes
of X 0 . Moreover, after the scaling step, o gets incident to each attribute ρr : aδ,i ∈
δ(X) (Constraint(ρ, r, o, (a0δ,i , a00δ,i )) is necessarily satisfied). Thus, we have Yδ ⊆
o0 and therefore o00 ⊆ Yδ0 . Finally, since o ∈ o00 we conclude that X ∇∇ ⊆ Yδ0 . t u
Proposition 6 states that for any concept from the aggregated context, an
RCA concept with the same extent exists. Definition 2 introduces the notion of
relational weakening (illustrated by Example 5) to enable the mapping between
both intents. The latter is given by proposition 7.
Definition 2. Let a concept C be produced by RCA and let Yr be the set of
S intent of C. We call relational weakening of C, noted
relational attributes of the
Ω(C), the set Ω(C) = ρr:(U,V )∈Yr {ρr : v | v ∈ V }
Example 5. Assume the contexts of Example 2: Context KC gives rise to the
concepts C1 = ({t3}, {el, pw}), C2 = ({f 5}, {pw, cp}), C3 = ({t3, zo}, {el})
and C4 = ({zo, f 5}, {cp}). After a scaling with ∃, KP yields the concept C =
({La}, {Adult, F emale, I.T., ∃pos : C1 , ∃pos : C2 , ∃pos : C3 , ∃pos : C4 , ∃pos :
>}). Then Ω(C) = {∃pos : el, ∃pos : pu, ∃pos : cp}.
Proposition 7 δ(X) ⊆ Ω(Cδ )
Proof. Let’s denote by Yr the set of relational attributes in the intent of Cδ . Let
ρr : a ∈ δ(X), then by scaling and construction of Cδ , it holds ρr : (a0 , a00 ) ∈ Yr
and as a ∈ a00 , one concludes δ(X) ⊆ Ω(Cδ ). t
u
While we’ve just shown that the extents of C and Cδ are equal, their intents
might differ: As proposition 7 states, the intent of the aggregate table concept
is a subset of the weakening of the RCA concept with the same extent (see
Example 6 below). In this sense, we see the RCA concept as more informative.
Example 6. Assume the relational family defined by Example 2 with the ∃ op-
erator. The aggregated context is presented in table 6. Now, after one iteration,
RCA discovers the concept ({F a}, {Senior, M ale, ∃pos : (cp, ch)}) whereas FCA
finds ({F a}, {Senior, M ale, ∃pos : (cp), ∃pos : (nd))}). While ∃pos : (cp, ch) im-
plies ∃pos : (cp) and ∃pos : (ch), the reverse does not hold.
4 Discussion
We’ve shown that for any FCA concept from an encoded context, RCA would
reveal a counterpart concept, or a pair of such, conveying the same semantics
(equal extent). Moreover, the syntactic expression of the RCA concept(s) is
clearer than the FCA one, whatever the encoding. With semi-join, since separate
RCA concepts map to the 1st and 2nd projections of a FCA concept, the clarity
gain is immediate. Indeed, no confusion is ever possible as to which attribute of
the semi-join intent is incident to which object. Moreover, redundancy in FCA
concepts, e.g. shared 1st or 2nd projection, is avoided in RCA.
With aggregation, RCA trivially produces a concept of the same extent, yet
it is more precise: The FCA counterpart is readily obtained by relational weak-
ening. Here, higher-order encoding schemata are conceivable that mimic RCA
iterations by nesting the scaling operators. Yet the maximal depth of these nest-
ings in the resulting (pseudo-)relational attributes must be fixed beforehand.
This is a serous limitation since we know of no simple way to determine the
number of iterations required till the fixed point for a given RCA task, i.e. a
RCF and a vector of scaling operators. This means that, at least in the realistic
cases, RCA will be revealing concepts that FCA –over the aggregated context
with all possible nestings of a depth up till the limit– will miss. A relevant
question here is whether knowing the fixed point contexts in RCA, there is an
equivalent aggregation context that comprises only nested operator attributes
referring exclusively to attribute concepts. This would mean that a static en-
coding, i.e. without the need for explicitly composing RCA concepts popping at
iterations 2+, exists. The cost of constructing such an encoding is, though, a
separate concern.
5 Conclusion
We tackled here the question of whether RCA brings some effective scope ex-
tension to the realm of FCA, given that FCA is at its core. We’ve examined two
complementary principles of encoding a relation into a single augmented context
and compared FCA output on each of the contexts to the output of RCA on the
original RCF. It was shown that in both cases, RCA is able to find counterpart
concepts (same extent) to those found by FCA, while the RCA intents at its 1st
iteration are at least as expressive as the FCA ones.
A more systematic study should allow us to demonstrate similar results in
the more complex cases of multiple relations in the RCF as well as multiple
relations between the same pair of contexts.
References
1. M. Alam et al. Lattice based data access: An approach for organizing and accessing
linked open data in biology. In DMoLD@ECML/PKDD. Springer, 2013.
2. P. Chen. The Entity-Relationship Model - Toward a Unified View of Data. ACM
Transactions on Database Systems, 1(1):9–36, 1976.
3. X. Dolques et al. RCA as a data transforming method: a comparison with propo-
sitionalisation. In ICFCA, pages 112–127. Springer, 2014.
4. X. Dolques et al. Performance-friendly rule extraction in large water data-sets with
aoc posets and relational concept analysis. Intl. J-l of General Syst., 2016.
5. S. Džeroski. Multi-relational data mining: an introduction. ACM SIGKDD Explo-
rations Newsletter, 5(1):1–16, 2003.
6. S. Ferré and P. Cellier. Graph-fca: An extension of formal concept analysis to
knowledge graphs. Discrete Applied Mathematics, 273:81–102, 2020.
7. S. Ferré and O. Ridoux. A logical generalization of formal concept analysis. In
ICCS, pages 371–384. Springer, 2000.
8. B. Ganter and S. Kuznetsov. Pattern structures and their projections. In ICCS,
pages 129–142, 2001.
9. S. Kramer et al. Propositionalization approaches to relational data mining. In
Relational Data Mining, pages 262–291. Springer, 2001.
10. M. Rouane-Hacene et al. Relational concept analysis: mining concept lattices from
multi-relational data. AMAI, 67(1):81–108, 2013.
11. E. Spyropoulou and T. De Bie. Interesting multi-relational patterns. In ICDM,
pages 675–684. IEEE, 2011.
12. M. Wajnberg et al. Mining process factor causality links with multi-relational
associations. In K-Cap, pages 263–266, 2019.
13. M. Wajnberg et al. Mining heterogeneous associations from pediatric cancer data
by relational concept analysis. In MSDM@ICDM. IEEE, 2020.
14. R. Wille. Restructuring Lattice Theory: An Approach Based on Hierarchies of
Concepts, pages 445–470. Springer Netherlands, Dordrecht, 1982.
15. R. Wille. Conceptual graphs and formal concept analysis. In ICCS, pages 290–303.
Springer, 1997.