# Theoretical comparison of Relational Concept Analysis (RCA) and Graph-FCA (GCA)

Vanessa Fokou, Peggy Cellier, Xavier Dolques, Sébastien Ferré, Florence Le Ber

► To cite this version:

Vanessa Fokou, Peggy Cellier, Xavier Dolques, Sébastien Ferré, Florence Le Ber. Theoretical comparison of Relational Concept Analysis (RCA) and Graph-FCA (GCA). International Journal of Approximate Reasoning, 2025, 186, pp.109496. 10.1016/j.ijar.2025.109496. hal-05138994

HAL Id: hal-05138994

https://hal.science/hal-05138994v1

Submitted on 2 Jul 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Theoretical Comparison of Relational Concept
Analysis (RCA) and Graph-FCA (GCA)

Vanessa Fokou<sup>a</sup>, Peggy Cellier<sup>b</sup>, Xavier Dolques<sup>a</sup>, Sébastien Ferré<sup>b</sup>,
Florence Le Ber<sup>a</sup>

<sup>a</sup>Université de Strasbourg, ENGEES, CNRS, ICube UMR 7357 Strasbourg, France

<sup>b</sup>Univ Rennes, INSA, CNRS, Inria, IRISA - UMR 6074, Rennes, France

**Abstract**

Relational Concept Analysis (RCA) and Graph-FCA (GCA) are two exten-
sions of Formal Concept Analysis (FCA) introduced in order to allow concept
analysis on multi-relational data. The two methods have different proper-
ties and parameters, but when restricting to binary relationships, existential
quantifier and unary concepts, their outputs look similar. On this basis, a
theoretical comparison of the two methods is conducted, showing that each
RCA concept corresponds to a GCA concept. Furthermore, to allow the com-
parison of concept intensions, a transformation of RCA results into relational
patterns is performed. These results give a sound basis to help interpreting
RCA results and to combine the two approaches for data exploration.

***Keywords:*** Relational Concept Analysis, Graph-FCA, Relational Pattern, Relational Data, Graph Pattern

1. Introduction

In many fields, collected data are not only tabular data but complex re-
lational data that can be represented by graphs. For instance in the environ-
mental domain, graphs are used to represent the social interactions between
animals, or in semantic web, graphs are used to model knowledge. An im-
portant task is then the extraction of structures, or patterns, from relational

Email addresses: vfokou@unistra.fr (Vanessa Fokou), peggy.cellier@irisa.fr (Peggy Cellier), dolques@unistra.fr (Xavier Dolques), Sebastien.Ferre@irisa.fr (Sébastien Ferré), florence.leber@engees.unistra.fr (Florence Le Ber)
data to better understand the underlying concepts in these domains. Formal Concept Analysis (FCA) [1] is a mathematical formalism based on lattice theory and designed to analyze data (called a formal context) by grouping objects with shared properties into formal concepts. It produces a hierarchical structure called a concept lattice representing the generalization ordering between formal concepts. Designed for tabular data, the direct application of FCA on more complex data is limited because it requires the flattening of these data, which results in a loss of structural information.

Several generalizations of FCA have been made to handle multi-relational data such as: Triadic Concept Analysis (TCA) [2], Power Context Families [3], Relational Concept Analysis (RCA) [4], concept lattices of a relational structure [5], Graph-FCA (GCA) [6] and Polyadic Relational Concept Analysis [7]. Other approaches deal with a single relationship, such as Network Formal Contexts [8]. Among them two approaches seem to be very close: RCA and GCA. RCA has been successfully used in a number of fields, e.g. software engineering [9], ontology restructuring [10], the analysis of old Arabic remedies [11]. GCA has been used for different purposes: extraction of linguistic structures from parse trees, extraction of workflow patterns from cooking recipes [12], or addressing the problem of knowledge graph alignment [13]. RCA and GCA seem to be complementary and a few works have addressed questions of comparison or links between both approaches [14, 15, 16]. In [17], an empirical comparison of RCA and GCA has been conducted.

In this paper we propose a theoretical comparison of GCA and RCA based on the same ground, i.e., using the existential quantifier, data with only unary and binary relations, and unary concepts. We first prove that RCA concept extents are included in GCA concept extents and secondly, that RCA concept intents are included in GCA concept intents. However, as RCA and GCA concept intents are defined differently, a common representation is required for the comparison. We thus transform the RCA concept lattice family into relational patterns that are similar to GCA graph patterns.

The paper is organized as follows. Section 2 discusses the related work. Section 3 presents RCA and GCA methods. The extensional comparison of RCA and GCA is described in Sect. 5. Section 6 transforms the family of RCA lattices into relational patterns and Sect. 7 compares the RCA patterns to GCA graph patterns. Section 8 concludes and draws some perspectives.
## 2. Related work

RCA produces as output a family of concept lattices, which can be difficult to interpret when the lattices are large because a concept intent can recursively depend on the intent of another relationally-related concept. Various approaches have been proposed to deal with this complexity (e.g. [18, 19]), some of them propose to transform the lattice family into a hierarchy of graphs, thus moving RCA close to GCA. The work in [14, 20] presents a method to automatically extract directed acyclic graphs from RCA concept intents, starting from one chosen lattice of the lattice family. The resulting graphs are represented within a hierarchy in which each graph represents a navigation path through the lattice family. This method was defined for sequential data, described with a transitive relation. The aim was to explain concept values in the target lattice from the preceding values, encoded in other lattices. In [15], the authors propose a generic graphical representation of RCA outputs that emphasizes the relational patterns. This representation is named hierarchy of concept graphs where, each concept belongs to one concept graph and each concept graph exhibits the relationships between several concepts. This generic representation makes no assumption on the context family and can therefore handle all kinds of relational data.

A practical comparison of TCA (Triadic Concept Analysis), RCA, and GCA for modeling indeterminate values in ternary data has been realized in [16]. Ternary relationships have been directly processed in GCA and TCA. Indeed, GCA extends FCA to *n*-ary relationships and a ternary relationship can be embedded into a TCA scheme i.e., *"an object *g* has the attribute *m* under the condition *b*"*. As RCA is limited to binary relations, the authors propose and compare three different encodings for the ternary relation. Similarities and dissimilarities between RCA and GCA have been studied in [17]. This conducted to the definition of a common ground, where the outputs of the two methods are close to each other. Furthermore, this work explores, and highlights how cycles are processed differently by both approaches. An empirical comparison is carried out suggesting that RCA concept extents are included in GCA concept extents. To our knowledge, a thorough theoretical comparison of the two approaches has not yet been conducted.

## 3. Preliminaries

We here recall the fundamental notions of FCA, RCA and GCA.
### 3.1. Formal Concept Analysis (FCA)

FCA [1] consists of extracting conceptual structures from a set of objects described by attributes, called a formal context. A formal context is a triple $K = (O, A, I)$ where, $O$ and $A$ are sets of objects and attributes respectively and $I$ is a binary relation between $O$ and $A$, i.e., $I \subseteq O \times A$. For instance, tables Animal and Food in Fig. 1 are examples of formal contexts. The incidence relation $I$ induces two mappings (operators), $int: 2^O \to 2^A$ and $ext: 2^A \to 2^O$ such that $int(X) = \{y \in A | \forall x \in X, (x,y) \in I\}$ and $ext(Y) = \{x \in O | \forall y \in Y, (x,y) \in I\}$. A formal concept is then defined as a pair $(X, Y)$ where $X \subseteq O$, $Y \subseteq A$, $int(X) = Y$ and $ext(Y) = X$; $X$ and $Y$ respectively represent the extent and the intent of the formal concept $(X, Y)$. The set of all concepts built from a formal context $K$ is denoted $C_K$. Let $C_1 = (X_1, Y_1)$ and $C_2 = (X_2, Y_2)$ two concepts of $C_K$. The subsumption relation $\subseteq$ is defined by $C_1 \subseteq C_2$ if and only if $X_1 \subseteq X_2$ (or equivalently $Y_2 \subseteq Y_1$). The set $C_K$ provided with the subsumption relation has a lattice structure, and is called the concept lattice associated with $K$.

The FCA result on the Food context is the concept lattice presented in Fig. 2 (right). Each concept is represented by a box that has three compartments representing, from top to bottom, the identifier, the intent and the extent of the concept respectively. Dotted arrows represent the subsumption relation between concepts.

### 3.2. Relational Concept Analysis (RCA)

RCA [4] extends the purpose of FCA to binary relational data: data represented by several tables and associations between them. In RCA, tables describing objects through attributes are called object-attribute contexts (formal contexts), and those encoding relations between objects are called object-object contexts (relational contexts). RCA input data is called a Relational Context Family (RCF) which is a pair $(\mathbf{K}, \mathbf{R})$ where: $\mathbf{K} = \{\mathcal{K}_i\}_{i=1..n}$ is a set of formal contexts $\mathcal{K}_i = (O_i, A_i, I_i)$, and $\mathbf{R} = \{r_k\}_{k=1..m}$ is a set of relational contexts $r_k$ where $r_k \subseteq \text{dom}(r_k) \times \text{ran}(r_k)$, and $\text{dom}(r_k), \text{ran}(r_k) \in \{O_i\}_{i=1..n}$ are respectively the domain (source) and range (target) of $r_k$. For instance, the three tables in Fig. 1 form an RCF with 2 formal contexts on the left ($\mathbf{K} = \{\text{Animal, Food}\}$) and one relational context on the right ($\mathbf{R} = \{\text{eat}\}$) linking animals to the foods they eat. This means that $\text{dom}(\text{eat}) = O_{\text{Animal}}$ and $\text{ran}(\text{eat}) = O_{\text{Food}}$.

RCA iteratively applies FCA on an RCF using *relational scaling* mechanism to extend initial formal contexts through *relational attributes*. Each
<figure><img src="image_2.png" /><figcaption>Figure 1: Example of an RCF about animals and food (named Animal_Food).</figcaption></figure>

iteration includes 2 steps: (1) applying FCA on each formal context of an RCF, (2) *relational scaling* and extension of formal contexts. The next iteration is based on the results of the previous iteration by applying FCA on the extended formal contexts, and the process ends when the families of lattices of two consecutive steps are isomorphic.

**Definition 1 (Relational attribute).** A relational attribute is an expression $qr(C)$, where $q$ is a scaling quantifier ($\exists, \exists\forall, ...$), $r$ is a relation between two object sets and $C$ is a concept whose extent contains objects from $ran(r)$.

Relational scaling aims to integrate in formal contexts the relational information encoded in relational context by transforming a relation $r_k$ into a set of relational attributes that extends the formal context describing the set of objects in $dom(r_k)$. In the running example, the relation *eat* will be used in association with *Food* concepts, to constitute the set of relational attributes in order to extend *Animal* formal context. Henceforth, these relational attributes will be part of *Animal* concept intents. Using the existential quantifier ($\exists$) - which will be used all along this work - we will obtain relational attributes of the form $\exists \text{eat}(\text{Concept\_food})$ expressing the fact that *an animal eats some food that belongs to a given food concept*.

RCA result on an RCF, written RCA(RCF), is a set of inter-connected lattices through relational attributes, called Concept Lattice Family (CLF), one lattice per formal context of the RCF. For the current RCF, we have a CLF made of two concept lattices as presented in Fig. 2. As we can see, the *Food* concept lattice has no relational attributes because $O_{\text{Food}}$ is not the domain of a relational context like $O_{\text{Animal}}$. The *Animal* concept lattice contains relational attributes connecting *Animal* objects to *Food* concepts. For instance, $\exists \text{eat}(\text{C\_food\_3})$ is a relational attribute linking objects of concept C\_animals\_2 to objects of concept C\_food\_3 and it is interpreted as: $\forall o_i \in \text{Ext}(\text{C\_animals\_2}), \exists o_j \in \text{Ext}(\text{C\_food\_3}), (o_i, o_j) \in \text{eat}$.
<figure><img src="image_3.png" /><figcaption>Figure 2: RCA results on the RCF presented in Fig. 1 – reduced lattice representation.</figcaption></figure>

### 3.3. Graph-FCA (GCA)

GCA [6] was introduced as an extension of FCA where the dataset is a form of hyper-graph instead of a binary table. GCA adopts a graph point of view, seeing objects as *graph nodes*, relationships as *directed edges* between nodes, and attributes as node and edge *labels*. Whereas FCA defines its input data as a formal context which is an incidence relationship between objects and attributes, GCA defines its input data as a *graph context* which is an incidence relationship between *object tuples* and attributes.

**Definition 2 (Graph context).** A graph context is a triple $K = (O, A, I)$, where $O$ is a set of objects, $A$ a set of attributes, and $I \subseteq O^* \times A$ an incidence relation between object tuples $\bar{o} \in O^* = \bigcup_{k \ge 1} O^k$ and attributes $a \in A$.

Figure 3 presents the graph context corresponding to the RCF shown in Fig. 1. In this graph context, each object is represented by a rectangular node where the first compartment identifies the object and the second compartment represents node labels (object features). Links between nodes represent the relations between objects. The set of attributes $A$ contains both unary attributes describing objects and binary attributes applying on tuple of objects to represent the relationships between objects. An incidence $((o), a)$
<figure><img src="image_4.png" /><figcaption>Figure 3: Graph context corresponding to *Animal_Food* RCF shown in Fig. 2.</figcaption></figure>

describes object *o* by attribute *a*, for instance `((a1), herbivore)`. An incidence `((o₁, o₂), a)` relates object `o₁` to object `o₂` through a binary relation *a*, for instance `((a1, f4), eat)`. By generalization, an incidence `((o₁, ..., oₙ), a)` represents an *n*-ary relationship, connecting *n* objects. For more readability, `((o₁, ..., oₙ), a)` is also noted as `a(o₁, ..., oₙ)`. Finally, unary attributes are used to label nodes and *n*-ary attributes are used to label edges connecting *n* nodes.

GCA extends a formal concept into a *graph concept* where the concept extent is a set of *n*-tuples of objects (called *object relation*) and the concept intent is a Projected Graph Pattern (PGP) describing what those *n*-tuples of objects have in common, *n* is the arity of the concept. Unary concepts (*n* = 1) are about sets of objects (like in FCA), while *n*-ary concepts (*n* > 1) are about relations between objects.

**Definition 3 (Projected Graph Pattern - PGP).** A PGP of arity *k* (*k*-PGP) is a pair $Q = (\bar{x}, P)$, where $\bar{x} = (x_1, \dots, x_k) \in \mathcal{V}^k$ is a tuple of *k* projected variables, and $P \subseteq \mathcal{V}^* \times A$ is a graph pattern i.e., an abstraction of a graph context with variables as nodes.

Figure 4 presents the set of graph patterns produced by the GCA tool on the graph context shown in Fig. 3. In this result, the instances of the variables onto the graph context have already been generated (see the third compartment of each node). Formally, the first pattern **P1** (in blue) is written: $\mathbf{P1} = \{\mathbf{carnivore}(a), \mathbf{meat}(b), \mathbf{eat}(a, b)\}$ with variables *a* and *b*. A PGP is simply a graph with focus on one or several nodes. For instance, $Q1a = ((a), \mathbf{P1})$ is a unary PGP with focus on variable *a* in **P1**. Each node in the graph pattern identifies a unary concept and has three horizontal compartments: the first contains the concept id $Qix$, where *i* is the number of
<figure><img src="image_5.png" /><figcaption>Figure 4: Corresponding graph patterns of Animal_Food graph context (Fig. 3).</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Figure 5: Corresponding concept hierarchy of Animal_Food graph patterns (Fig. 4).</figcaption></figure>

the pattern, and $x$ is the lowercase string - generally a single letter - that identifies the concept relative to its pattern. For example, $Q1a$ is the first concept of the first pattern, and $Q3d$ is the fourth concept of the third pattern. The second compartment contains the descriptors of the concept; for instance, $Q1a$ is described as **carnivore**, it is part of the concept intent. The third compartment contains the extent of the concept which represents the instances of the projected variables. For illustration, the extent of $Q1a$ is $\{a3, a2\}$, the instances of the variable $a$.

An object relation is a set $R \subseteq O^k$, for some arity $k$, of object tuples. For illustration, $R = \{(a3, f6), (a3, f5), (a2, f6), (a2, f5)\}$ is a binary object relation (of arity 2) from the current graph context. The description of a tuple of objects $\bar{o}$ is the PGP $Q(\bar{o}) = (\bar{o}, I)$, which uses objects as variables. The intension of a finite non-empty object relation $R$, denoted by $int(R)$ is the intersection of the description of all tuples of objects in $R$.

$$ int(R) = \bigcap_{\bar{o} \in R} Q(\bar{o}) $$

The extension of a $k$-PGP $Q$ is defined as the set of $k$-tuples of objects whose description contains $Q: ext(Q) = \{\bar{o} \in O^k | Q \subseteq_q Q(\bar{o})\}$. These two derivation operators ($ext, int$) form a Galois connection between two
posets ($2^{O^k}$, $\subseteq$) and ($Q_k$, $\subseteq_q$) – $Q_k$ is the set of K-PGPs. A graph concept is then a pair $(R, Q)$ with $R \subseteq O^k$ and $Q \in Q_k$, for some arity $k$, such that $R = \text{ext}(Q)$ and $Q = \text{int}(R)$ where $R$ is the *extent* and $Q$ is the *intent*. For instance, the binary PGP $((a, b), \{\text{carnivore}(a), \text{meat}(b), \text{eat}(a, b)\})$ has the following extension: $\{(a3, f6), (a3, f5), (a2, f6), (a2, f5)\}$. This PGP identifies the list of *carnivore* animals and the *meat* they eat. Visually, each node $Qnx$ represents a unary concept whose intent is the PGP $((x), Pn)$, and whose extent is listed in the third compartment. For instance, concept $\mathbf{Q3a} = (\{f1, f4\}, ((a), P3))$ is the concept of fruits that are eaten by an herbivore that also eats grass. It has two instances, $\mathbf{f1}$ and $\mathbf{f4}$. The intent of $k$-ary concepts can be read by selecting several nodes, e.g. $\mathbf{Q3(a,c)}$, but their extent cannot be read in the figures.

The GCA tool also provides a lattice view named *concept hierarchy* as an alternative for the pattern view by showing subsomption links between concepts and replacing relational links by textual labels inside concept nodes (second compartment). Figure 5 presents the concept hierarchy of the graph patterns in Fig. 4. In this concept hierarchy, dotted arrows represent the subsumption relation between concepts and the relation *eat* between nodes *a* and *b* in Q1 (Fig. 4) is represented by [*eat_b*] and [*eat a_*] in the description part of Q1a and Q1b respectively (Fig. 5). In general, as in this example, the GCA tool does not display a bottom or top concept if its extent or its intent is empty. This representation of GCA concepts thus appears as a family of concept hierarchies, one for each category of objects, similarly to RCA. Comparing this concept hierarchy (Fig. 5) to the CLF presented in Fig. 2, we can see that the concept Q3d produces by GCA is not produced by RCA. Indeed, GCA automatically considers relationships in both directions and Q3d gathers *food objects eaten by herbivore animals in concept Q3c*.

# 4. Overview

This work investigates a theoretical comparison of GCA and RCA based on the same ground, i.e., using the existential quantifier ($\exists$), data with only unary and binary relations, and unary concepts, leading to the result that *RCA concepts are included in GCA concepts*. We first prove that all RCA concept extents are GCA concept extents (*extensional comparison*) and secondly, that each RCA concept intent is included in some GCA concept intent (*intensional comparison*).
The extensional comparison in Sect. 5 begins by defining a transformation of relational context families into graph contexts, in order to provide a well-founded ground for comparison (Definition 6). Definition 7 introduces how a PGP simulates an RCA concept. This notion of PGP simulating an RCA concept is used in Lemma 1 which states that if a PGP $Q$ simulates an RCA concept $C$, then $ext(Q) = Ext(C)$. Lemma 1 is then used in Theorem 1 to prove that for every RCA concept, there is a GCA concept with the same extent. However, empirical results in a previous work [17] have shown that RCA results get closer to GCA results by adding inverse relations to RCA data as GCA automatically considers inverse relationships in its process. Section 5.4 proves in Theorem 2 that adding inverse relations does not change the previous result stating that all RCA extents are GCA extents.

To achieve the intensional comparison, a common representation is to be found for RCA and GCA concept intents, since they are not directly comparable. Section 6 first presents a transformation of the RCA result (a concept lattice family) into relational patterns including inverse relationships. The translation process begins with the definition of the dependency graph of a concept lattice family (Definition 8) and a concept pattern is then defined as a Strongly Connected Component (SCC) of the dependency graph. Lemmas 3 and 4 respectively introduce the notions of redundant and strongly redundant relational attributes, which form the basis for the definition of the common representation (EAR-pattern, Definition 9) for comparing RCA and GCA intensions. Definition 10 defines the RCA EAR-pattern which is equivalent in term of information to the original concept lattice family. Section 7 then addresses the intensional comparison proper, starting with the definition of GCA EAR-patterns (Definition 12), based on the quotient graphs of GCA graph patterns (Definition 11). Theorem 3 finally states that the union of RCA EAR-patterns is included in the union of GCA EAR-patterns in the sense of labelled subgraphs (Definition 13).

## 5. Extensional Comparison of RCA and GCA

In this section and in the following, we compare RCA and GCA on the same ground, as defined in [17]: considering data with only unary and binary relations, using the existential quantifier ($\exists$) for RCA, computing only unary concepts for GCA. We first compare RCA and GCA on the extensional side because they are directly comparable. Indeed, the objects are the same on both sides, although split in $n$ subsets on the RCA side. As we only consider
unary GCA concepts, as mentioned above, this amounts to compare sets of
extensions, i.e., sets of sets of objects. Given $C_R$ the set of RCA concept
extensions, and $C_G$ the set of GCA concept extensions, we demonstrate that
$C_R \subseteq C_G$, and that the reverse does not hold. Before stating and demonstrat-
ing this result, we need to make some observations regarding RCA concepts
w.r.t. their iterative generation process and also to translate an RCF to a
graph context in order to ground the comparison.

5.1. RCA Concept Rank and Initial Intent

The RCA concept generation process is iterative. On each iteration, new concepts may be formed, and the intent of existing concepts may be extended with new relational attributes derived from new concepts at the previous iteration. A concept is identified by its extent, so a new concept is actually a new extent. The iterative process stops when no new concept is formed, which was proven to happen after a finite number of steps because the set of objects is finite, hence the set of possible extents is also finite.

RCA usually only consider the concepts after the last iteration, i.e. pairs $(X, Y)$ where $Y$ is the final intent. We introduce two new notions: the *rank* of a concept, and the *initial intent* of a concept.

**Definition 4 (Concept rank).** The *rank* of an RCA concept $C = (X, Y)$, written *rank*(C), is the RCA iteration $i \ge 0$ that first generates a concept with extent X.

**Definition 5 (Initial intent).** The *initial intent* of an RCA concept $C = (X, Y)$, written $\hat{\text{Int}}(C)$ or shortly $\hat{Y}$, is the intent of $C$ at iteration *rank*(C), i.e., when extent $X$ was first generated. We therefore have $\hat{Y}' = X$.

By definition of RCA iterations that can only add new relational attributes, we have $\hat{Y} \subseteq Y$. We can also say that the initial intent of a concept $C$ can only refer to concepts $C_i$ (through relational attributes) s.t. $\text{rank}(C_i) < \text{rank}(C)$ because a concept cannot be used before being introduced. Those preliminary results are important because initial intents break the cycles that may exist in the final intents of concepts. This hence establishes a topological ordering among concepts via their rank, while preserving the characterization of extents as $X = \hat{Y}'$.
## 5.2. Translating Relational Context Families to Graph Contexts

In order to have a well-founded ground for comparison, a Relational Context Family (RCF) from the RCA side must first be translated into an equivalent graph context on the GCA side. This is relatively simple when restricting to their common ground because we have multi-relational data on both sides. The main subtlety is about the set of objects that is partitioned in RCA and not in GCA. This leads to the introduction of additional unary attributes to represent the different categories of objects.

**Definition 6.** Let $(K, R)$ be an RCF. The corresponding graph context $K = (O, A, I)$ is defined as follows:

* $O := \cup_{i=1..n} O_i$: the set of objects is the disjoint union of the sets of objects of all object-attribute contexts $K_i \in K$;

* $A = A_1 \cup A_2$: the set of attributes is made of unary attributes ($A_1$) and binary attributes ($A_2$), where:

- $A_1 := \cup_{i=1..n} (\{a_{K_i}\} \cup A_i)$: the set of unary attributes is the disjoint union of the sets of attributes of all object-attribute contexts, extended with the name of the contexts ($a_{K_i}$) as object types;

- $A_2 := \{r_k\}_{k=1..m}$: the set of binary attributes is the set of relation names, one for each object-object context;

* the incidences between tuples of objects and attributes is defined as:

$$ I := \{a_{K_i}(o) | K_i \in K, o \in O_i\} \\ \cup \{a(o) | o \in O_i, a \in A_i, (o, a) \in I_i\} \\ \cup \{r(o_1, o_2) | r \in R, (o_1, o_2) \in r\} $$

For instance, the graph context corresponding to the RCF presented in Fig. 1 is equal to $K = (O, A, I)$ where:

* $O = O_{Animal} \cup O_{Food}$

* $A = A_1 \cup A_2$ where $A_1 = \{a_{Animal}\} \cup A_{Animal} \cup \{a_{Food}\} \cup A_{Food}$ and $A_2 = \{eat\}$

* $I = \{a_{Animal}(o) | o \in O_{Animal}\} \cup \{a_{Food}(o) | o \in O_{Food}\} \\ \cup \{a(o) | (o, a) \in I_{Animal}\} \cup \{a(o) | (o, a) \in I_{Food}\} \\ \cup \{eat(o_1, o_2) | (o_1, o_2) \in eat\}$
Note that this translation is injective, indeed different RCFs clearly lead to different graph contexts. As a consequence, no information is lost in the process, and the translation can be easily reversed as long as the attributes $a-\mathcal{K}_i$ are distinguished from other unary attributes. However, there is no obvious general translation from graph contexts to RCFs because of the lack of object categories, and because of the possible existence of n-ary relations.

### 5.3. Comparing Sets of Concept Extensions

We prove in the following that all RCA extensions are also GCA extensions. This was conjectured in a previous work [17], where it was also shown through counter-examples that the reverse does not hold. In order to make this proof, we first construct a PGP that simulates the initial intent of an RCA concept, and prove two lemmas about this construction.

**Definition 7 (PGP simulating an RCA concept).** Let $C$ be a concept in an RCA Concept Lattice Family (CLF). Let $\mathcal{C} = \{C_k\}$ be the subset of concepts that participate to the description of $C$ i.e., concepts referred to in relational attributes of the initial intent of $C$, and recursively in the initial intent of those concepts. $\mathcal{C}$ also includes $C$ itself as $C_0$. We define the PGP $Q = (x_0, P_0)$ simulating $C$ by introducing a set of variables $\mathcal{X} = \{x_k\}$, containing a distinct variable for each concept $C_k \in \mathcal{C}$; and by defining a pattern $P_k$ for each concept $C_k$ s.t.:

$$ P_k := \{a_{\mathcal{K}_i}(x_k) | C_k \text{ belongs to the concept lattice of context } \mathcal{K}_i\} \\ \cup \{a(x_k) | a \in \widehat{\text{Int}}(C_k)\} \\ \cup \bigcup \{\{r(x_k, x_l)\} \cup P_l | \exists r C_l \in \widehat{\text{Int}}(C_k)\} $$

We define $Q_k = (x_k, P_k)$ as the PGP that simulates $C_k$, and we note this simulation relationship $Q_k \sim C_k$.

The recursive definition of $P_k$ is well defined because of the rank-based topological ordering of initial intents. The base case is made of concepts at rank 0, which have no relational attributes in their initial intent. For illustration, let us abbreviate `C_animals_1` as $C_{a1}$ and `C_food_1` as $C_{f1}$ in Fig. 2 (left), and define the pattern $P_{a1}$ that simulates $C_{a1}$ given that $\widehat{\text{Int}}(C_{a1}) = \{\text{carnivore}, \exists \text{eat}(C_{f1})\}$. We have $Q_{a1} = (x_{a1}, P_{a1})$ where $P_{a1} = \{a_{\text{Animal}}(x_{a1}), \text{carnivore}(x_{a1}), \text{eat}(x_{a1}, x_{f1}), a_{\text{Food}}(x_{f1}), \text{meat}(x_{f1})\}$.
**Lemma 1.** Under the conditions of Definition 7, we have for all $C_k \in \mathcal{C}$

$$Q_k \sim C_k \implies \mathrm{ext}(Q_k) = \mathrm{Ext}(C_k).$$

**PROOF.** We prove the lemma by recurrence on the rank of concepts in $\mathcal{C}$. In the general case, we consider a concept $C_k$ at rank $n$, belonging to context $\mathcal{K}_i$. We assume the lemma is true for all concepts at a rank lower than $n$, in particular to those occurring in the initial intent $\hat{Y}_k$ of $C_k$.

We first prove that $\mathrm{Ext}(C_k) \subseteq \mathrm{ext}(Q_k)$. Considering some $o_k \in \mathrm{Ext}(C_k)$, we have to prove that $o_k \in \mathrm{ext}(Q_k)$, which is defined by $Q_k \subseteq_q (o_k, I)$, which is true iff there exists a mapping $\phi$ from variables to objects s.t. $\phi(x_k) = o_k$ and $\phi(P_k) \subseteq I$. We have $o_k \in \mathrm{Ext}(C_k) = \hat{Y}'_k = \bigcap_{\alpha \in \hat{Y}} \alpha'$, i.e., $o_k \in \alpha'$ for all elements $\alpha$ of the initial intent. There are two kinds of elements:

* formal attributes ($\alpha = a \in A_i$): $o_k \in \alpha'$ implies that $o_k \in a'$, hence $(o_k, a) \in I_i$.

* relational attributes ($\alpha = \exists r(C_l)$): $o_k \in \alpha'$ here implies that $o_k \in (\exists r(C_l))'$, which implies there exists an object $o_l$ s.t. $(o_k, o_l) \in r$ and $o_l \in \mathrm{Ext}(C_l)$. By applying the recurrence hypothesis, we get $o_l \in \mathrm{ext}(Q_l)$, and hence there exists a mapping $\phi_l$ s.t. $\phi_l(x_l) = o_l$ and $\phi_l(P_l) \subseteq I$.

We define the mapping $\phi := \{x_k \to o_k\} \cup \bigcup_l \phi_l$ as the union of the mappings of each relational attribute plus the mapping from $x_k$ to $o_k$. It therefore remains to show that $\phi(P_k) \subseteq I$. $P_k$ can be decomposed into the following subsets of elements:

* $a_{\mathcal{K}_i}(x_k)$: $o_k$ belongs to context $\mathcal{K}_i$, so we do have $a_{\mathcal{K}_i}(o_k) \in I$ according to the definition of the graph context that corresponds to the RCF.

* $a(x_k)$: by definition of $Q_k$, we have $a \in \hat{Y}_k$, hence as seen above we have $(o_k, a) \in I_i$, hence $a(o_k) \in I$.

* $r(x_k, x_l)$: by definition of $Q_k$, we have $\exists r(C_l) \in \hat{Y}_k$, hence as seen above we have $(o_k, o_l) \in r$, hence $r(o_k, o_l) \in I$.

* $P_l \subseteq P_k$: we have seen above that $\phi_l(P_l) \subseteq I$, hence by definition of $\phi$ that includes $\phi_l$, we also have $\phi(P_l) \subseteq I$.
As all parts of $P_k$ project to parts of I through $\phi$, we get $\phi(P_k) \subseteq I$.

We then prove that $\mathrm{ext}(Q_k) \subseteq \mathrm{Ext}(C_k)$. Considering $o_k \in \mathrm{ext}(Q_k)$, we know it exists a mapping $\phi$ from variables to objects s.t. $\phi(x_k) = o_k$ and $\phi(P_k) \subseteq I$. We have to prove that $o_k \in \mathrm{Ext}(C_k) = \hat{Y}'_k = \bigcap_{\alpha \in \hat{Y}} \alpha'$. Hence we have to prove that $o_k$ belongs to the extension of each element $\alpha$ of the initial intent. We do so for the two kinds of elements:

* $\alpha = a \in A_i$ (formal attribute): by definition of $Q_k$, we know that $a(x_k) \in P_k$. From $\phi(P_k) \subseteq I$ we get $\phi(a(x_k)) \in I$, then from $\phi(x_k) = o_k$ we get $a(o_k) \in I$. Hence we also get $(o_k, a) \in I_i$ through context translation, and therefore, $o_k \in a'$.

* $\alpha = \exists r(C_l)$ (relational attribute): by definition of $Q_k$, we know that $r(x_k, x_l) \in P_k$ and $P_l \subseteq P_k$. From constraints on $\phi$, we can deduce that $r(o_k, o_l) \in I$, with $o_l = \phi(x_l)$, and $\phi(P_l) \subseteq I$. From there, we can conclude that $o_l \in \mathrm{ext}(Q_l)$, by simply projecting $\phi$ on the variables of $P_l$. By applying the recurrence hypothesis, we get $o_l \in \mathrm{Ext}(C_l)$. From $r(o_k, o_l) \in I$, we also get $(o_k, o_l) \in r$ through context translation. We therefore have $o_k \in (\exists rC_l)',$ by definition of the extension of a relational attribute.

The base case is for $\mathrm{rank}(C_k) = 0$. The same proof as the general case can be used because the recurrence hypothesis is only used for relational attributes, and concepts at rank 0 have none of them. $\blacksquare$

**Theorem 1.** Let $(K, R)$ be an RCF, and $K$ its corresponding graph context. For every RCA concept, there is a GCA concept with the same extension.

**PROOF.** Consider any concept $C$ in the CLF, and the PGP $Q$ that simulates $C$, i.e., such that $Q \sim C$. As a particular case of previous lemma with $k = 0$, we have $\mathrm{ext}(Q) = \mathrm{Ext}(C)$. In GCA, the pair $(\mathrm{ext}, \mathrm{int})$ is a Galois connection, so $(\mathrm{ext}(Q), \mathrm{int}(\mathrm{ext}(Q)))$ forms a concept, and hence $\mathrm{ext}(Q)$ is the extension of a GCA concept. $\blacksquare$

### 5.4. *Comparison when Adding Inverse Relations to RCA*

Empirical results in a previous work [17] have shown that RCA results get closer to GCA results by adding inverse relations to the RCF. Indeed, GCA automatically considers inverse relationships in its process, due to the graph categorical product used for computing GCA graph patterns. More precisely,
<figure><img src="image_7.png" /><figcaption>Figure 6: RCA results on the Animal_Food RCF that integrates inverse relationships.</figcaption></figure>

for every relation $r \in \mathbf{R}$, a new relation $r^{-} = \{(o_j, o_i) | (o_i, o_j) \in r\}$ is included in the set of relations. We note $\mathbf{R}^{-}$ the set of inverse relations derived from a set of relations $\mathbf{R}$, and the inverse of a relation is named by adding the string “_r” at the end of the relation name. Figure 6 presents RCA results on the Animal_Food RCF with the inverse relation eat_r. We can see that food concepts have relational attributes of the form $\exists eat_r(C_animals_i)$. Also, the addition of this inverse relation creates a new food concept: C_food_5 which corresponds to the GCA concept Q3d (in Fig. 5) missing in the RCA results without inverse relation presented in Fig. 2.

The question we address in this section is whether the previous result stating the inclusion of RCA extensions in GCA extensions remains true or not. We demonstrate that inclusion remains valid by showing that the set of GCA extensions is not affected by the introduction of inverse binary edges.

**Lemma 2.** Let $K = (O, A, I)$ be a graph context, and $K^{-} = (O, A^{-}, I^{-})$ be its extension with inverse relations, i.e. $A^{-} = A \cup R^{-}$, where $R \subseteq A$ is the set of binary attributes in A, and $I^{-} = I \cup \{r^{-}(o_j, o_i) | r(o_i, o_j) \in I\}$. There is a one-to-one correspondence between K-concepts and $K^{-}$-concepts:

$$ (R, Q) \in \text{GCA}(K) \iff (R, Q^{-}) \in \text{GCA}(K^{-}), $$

where, given $Q = (\bar{x}, P)$, we have $Q^{-} = (\bar{x}, P^{-})$ and $P^{-} = P \cup \{r^{-}(y, x) | r(x, y) \in P\}$.
PROOF. The computation of GCA concept intensions boils down to repeated categorical products of the incidence relation. In particular, when the edge $r(x, y)$ belongs to $I \times \dots \times I$ ($n$ times), this means that for all $i \in 1..n$, there is a pair of objects $(u_i, v_i)$ s.t. $r(u_i, v_i) \in I$. Then, by definition of $I^-$, it comes that for all $i \in 1..n$, we also have $r^-(v_i, u_i) \in I^-$. From there, we conclude that the categorical product $I^- \times \dots \times I^-$ contains $r^-(y, x)$ in addition to $r(x, y)$. Indeed, the categorical product defines $x = (u_1, \dots, u_n)$ and $y = (v_1, \dots, v_n)$. The reverse also holds. Whenever $r^-(x, y) \in I^- \times \dots \times I^-$, we have $r(x, y) \in I \times \dots \times I$ because whenever $r^-(v_i, u_i) \in I^-$ holds, $r(u_i, v_i) \in I \subseteq I^-$. ■

This implies that $K^-$-concepts can be derived from $K$-concepts, simply by adding inverse binary edges in patterns along the above definition of $P^-$. The concept extensions are the same. ■

Based on this lemma, previous Theorem 1 can be extended to RCF with inverse relations.

**Theorem 2.** Let $(K, \mathbf{R})$ be an RCF, and $K$ its corresponding graph context. For every RCA concept of the extended RCF $(K, \mathbf{R} \cup \mathbf{R}^-)$, there is a GCA concept of $K$ with the same extension.

PROOF. It is easy to see that if $K$ is the graph context corresponding to the RCF $(K, \mathbf{R})$, then $K^-$ is the graph context corresponding to the RCF extended with inverse relations. Therefore, from Theorem 1, we have that all concept extensions of the extended RCF are concept extensions of $K^-$. Lemma 2 shows that $K$ and $K^-$ have the same concept extensions. Therefore, all concepts extensions of the extended RCF are concept extensions of the non-extended graph context $K$. ■

# 6. From CLF to RCA Relational Patterns

In a concept lattice family, concept intents are defined in term of relational attributes pointing to other concepts while GCA concept intents are defined in term of Projected Graph Pattern. Thus, concept intents of the two approaches are not directly comparable, and a common representation must be found. We choose graphs as the common representation because graphs are natural settings for representing multi-relational data, and there is work in this direction regarding RCA [14, 15]. In order to get as close as possible to GCA, inverse relations will be included in the RCA data [17]. In the following, we detail the process of representing the RCA results into relational patterns similar to GCA graph patterns.
## 6.1. Dependency Graph of a Concept Lattice Family

The transformation of a concept lattice family into a hierarchy of concept graphs was described by [15], based on the Strongly Connected Components (SCC) [21] of a *dependency graph* between concepts. The dependency graph included the relations from each concept in a lattice to its ancestors and to the target concepts of its relational attributes, as defined below.

**Definition 8 (Dependency graph [15])**. Let $\mathbf{L}$ be a CLF. The dependency graph of $\mathbf{L}$ is the directed graph $G_{\mathbf{L}} = (V, E)$ where: $V$ is the set of all concepts of all lattices in $\mathbf{L}$, except bottom concepts, and $E$ is the set of concept dependencies $C_1 \to C_2$, when $C_2$ is a parent concept of $C_1$ ($C_1 \preceq C_2$), or $C_1$ is labeled by a relational attribute $\exists r(C_2)$ i.e., $\exists r(C_2) \in \text{Int}(C_1)$.

For instance, in the CLF presented in Fig. 2, we have $C\_animals\_2 \to C\_animals\_3$ and $C\_animals\_2 \to C\_food\_3$. Figure 7 shows the dependency graph of the RCF presented in Fig. 6 with its 3 SCCs circled. For sake of understanding, edges are represented in two ways: the dotted edges represent the subsumption relation between concepts, while the solid and labelled edges materialize the relational attributes between concepts. For instance, the edge between the concepts $C\_animals\_2$ and $C\_food\_3$ labelled by $\exists \text{eat}$ materializes the fact that $\exists \text{eat}(C\_food\_3) \in \text{Int}(C\_animals\_2)$.

A concept graph (or concept pattern) is defined as an SCC of the dependency graph i.e., a maximal set of concepts where each concept has a dependency path to all other concepts (in the SCC) for the definition of its intent. In these concept patterns, we will only keep the edges corresponding to relational attributes (we know how to reconstruct the edges corresponding to the subsumption relation). There are two difficulties in obtaining GCA-like patterns from these concept patterns. The first difficulty concerns the inter-SCC edges (for instance, the edge $\exists \text{eat}$ between concepts $C\_animals\_1$ and $C\_food\_4$ in Fig. 7), do we lose information on the concept intents by ignoring them? The second difficulty is the presence of inverse relations that are not explicitly represented in the GCA graph patterns. It is worth noting that inter-SCC edges do not have inverse edges, otherwise they would be intra-SCC. Both difficulties are solved in the next section.

## 6.2. Redundant Relational Attributes

A naive interpretation of a concept intent takes into account all its relational attributes, some of which do not provide new features about the
<figure><img src="image_8.png" /><figcaption>Figure 7: Dependency graph of Animal_Food CLF presented in Fig. 6 with its 3 SCCs.</figcaption></figure>

description of the concept. For example, the intension of C_animals_2 (Fig. 6) contains the relational attributes $∃ eat(C_foo\_2)$, $∃ eat(C_foo\_3)$, $∃ eat(C_foo\_5)$ and $∃ eat(C_foo\_4)$. The two first relational attributes are sufficient for its description while $∃ eat(C_foo\_5)$ and $∃ eat(C_foo\_4)$ are redundant. In fact, these two last attributes do not provide any new information (w.r.t $∃ eat(C_foo\_2)$ and $∃ eat(C_foo\_3)$). Lemma 3 introduces the notion of redundancy of relational attributes as defined in [14].

**Lemma 3.** Let $C_1$ and $C_2$ be two concepts such that $C_1 \preceq C_2$. If a concept C is such that $∃r(C_1) \in Int(C)$, then we also have $∃r(C_2) \in Int(C)$. For this reason, $∃r(C_2)$ is considered redundant for the description of C.

**PROOF.** Let $C_1 = (X_1, Y_1)$ and $C_2 = (X_2, Y_2)$. $∃r(C_1) \in Int(C) \iff ∀o \in Ext(C), r(o) \cap X_1 \neq \emptyset$. Since $C_1 \preceq C_2$, $X_1 \subseteq X_2$ and thus, $r(o) \cap X_2 \neq \emptyset \iff ∃r(C_2) \in Int(C)$. Hence, the relational attributes are ordered and $∃r(C_2)$ is redundant in the interpretation of C.

This lemma makes it possible to reduce redundancy and describe a concept by its most specific intent. However, looking further to the example
of concept C_animals_2, we can differentiate the two redundant attributes
∃eat(C_food_5) and ∃eat(C_food_4). The first one points at the direct
subsumer of only the two concepts (C_food_2) and (C_food_3) while the
last one points at concept (C_food_4) that also covers (C_food_1), thus
adding some kind of noise to the description of concept C_animals_2. Ac-
cordingly, there is no inverse relational attribute pointing from C_food_4 to
C_animals_2. This type of attribute will be called strongly redundant as
defined in the following lemma.

**Lemma 4.** Let $C = (X, Y)$ and $C_1 = (X_1, Y_1)$ be two formal concepts. If $∃r(C_1) ∈ Y$ and $∃r^-(C) ∉ Y_1$ then, there exists a concept $C_2 = (X_2, Y_2) ⊑ C_1$ such as $∃r(C_2) ∈ Y$ and $∃r^-(C) ∈ Y_2$ with $X_2 = X_1 ∩ ⋃\{r(o) | o ∈ X\}$. We then say that $∃r(C_1)$ is strongly redundant for the description of C.

PROOF. We have to prove that: (1) $X_2 \subseteq X_1$, which is trivial by definition of $X_2$, (2) $∃r^-(C) ∈ Y_2$, and (3) $∃r(C_2) ∈ Y$.

To prove $∃r^-(C) ∈ Y_2$, we start from what it implies to be an element of $X_2$: $∀o_j ∈ X_2 : o_j ∈ ∪\{r(o) | o ∈ X\}$, by definition of $X_2$
⇒ $∀o_j ∈ X_2 : ∃o_i ∈ X : (o_i, o_j) ∈ r$, by definition of $r(o_i)$
⇒ $∀o_j ∈ X_2 : ∃o_i ∈ X : (o_j, o_i) ∈ r^-$, by definition of inverse relation
⇒ $∃r^-(C) ∈ Y_2$, by definition of relational attributes in the intension.

To prove $∃r(C_2) ∈ Y$, we start from $∃r(C_1) ∈ Y$, which implies
$∀o_i ∈ X : ∃o_j ∈ X_1 : (o_i, o_j) ∈ r$
⇒ $∀o_i ∈ X : ∃o_j ∈ X_1 : (o_i, o_j) ∈ r$ hence $o_j ∈ ∪\{r(o_i) | o_i ∈ X\}$
⇒ $∀o_i ∈ X : ∃o_j ∈ X_2 : (o_i, o_j) ∈ r$, by definition of $X_2$
⇒ $∃r(C_2) ∈ Y$, by definition of relational attributes in intension. ■

Lemma 4 states that a relational attribute that has no reciprocal rela-
tional attribute is strongly redundant, which is the case of inter-SCC edges.
Thus, ignoring inter-SCC edges does not lead to a loss of information in the
interpretation of concept intents. This addresses the first difficulty mentioned
in the previous section about inter-SCC edges. After deleting strongly re-
dundant relational attributes, all remaining relational attribute between two
concepts have an inverse relational attribute. This means that the edges
induced by inverse relationships can be ignored (by convention), as in the
case of GCA graph patterns. This addresses the second difficulty concerning
inverse relational attributes.
### 6.3. RCA Relational Pattern (RCA EAR-Pattern)

A relational pattern is induced for each SCC of the RCA dependency graph. This section first defines such a relational pattern as an *extension-attribute-relation pattern (EAR-pattern)*, which will serve as a common representation to compare RCA intensions and GCA intensions. It then defines the EAR-patterns of RCA based on the above i.e., using only intra-SCC relational edges, and ignoring inverse edges given their redundancy.

**Definition 9 (EAR-pattern).** Let $O$ be a set of objects, $A$ a set of attributes, and $R$ a set of binary relationships. An *extent-attribute-relation pattern* (EAR-pattern) is a labelled directed graph $P = (V, E, L_V, L_E)$ where:

* the nodes $V \subseteq 2^O$ are concept extensions, i.e. sets of objects;

* $E \subseteq V \times V$ is a set of directed edges relating extensions;

* $L_V : V \to 2^A$ is a labelling function from nodes to sets of attributes;

* $L_E : E \to 2^R$ is a labelling function from edges to sets of relations.

**Definition 10 (RCA EAR-pattern).** Let $S$ be an SCC of a dependency graph $G_L$. The *RCA EAR-pattern* induced by $S$ is the EAR-pattern $P_S = (V, E, L_V, L_E)$ where:

* $V = \{Ext(C) | C \in S\}$: the extensions of the concepts of $S$;

* $E = \{(Ext(C_1), Ext(C_2)) | C_1, C_2 \in S, \exists r(C_2) \in Int(C_1)\}$: edges correspond to the relational attributes in concept intensions;

* $L_V(Ext(C)) = \{a \in A | a \in Int(C)\}$: extension labels are the unary attributes in the intension;

* $L_E((Ext(C_1), Ext(C_2))) = \{r \in R | \exists r(C_2) \in C_1\}$: edge labels are the relations of relational attributes from $C_1$ to $C_2$.

For instance, Fig. 8 presents the set of RCA EAR-patterns obtained from the CLF on *Animal_Food* RCF shown in Fig. 6. As we can see, this set of RCA EAR-patterns corresponds to the set of GCA graph patterns (Fig. 4) obtained on the same example.
<figure><img src="image_9.png" /><figcaption>Figure 8: RCA EAR-patterns of the *Animal_Food* CLF presented in Fig.6.</figcaption></figure>

To sum up, for a CLF obtained on a given RCF (with inverse relations), the corresponding set of RCA EAR-patterns is obtained as follows: (1) dependency graph of the CLF, (2) SCCs of the dependency graph, (3) removal of the edges of the subsumption relation, (4) removal of redundant relational attributes, and (5) removal of relational attributes induced by inverse relationships. It should be noted that these positive results are achieved thanks to inverse relationships which play an important role for the computation of SCCs. The representation of RCA results as EAR-patterns, close to GCA graph patterns, makes it possible to compare the concept intensions of the two approaches, as done below.

# 7. Intensional Comparison of RCA and GCA Concepts

This section compares a set of RCA EAR-patterns to a set of GCA graph patterns computed on the same data. However, they are not directly comparable because GCA graph patterns are not exactly EAR-patterns, and because they may have several nodes corresponding to the same concept, the so-called automorphic concepts. We therefore start by transforming GCA graph patterns into EAR-patterns.

## 7.1. *From Graph Patterns to EAR-Patterns*

The duplication of concepts in GCA output is sometimes required to properly represent the graph patterns that exhibit symmetries or capture some structures such as cycles. We refer to these duplicated concepts as
<figure><img src="image_10.png" /><figcaption>Figure 9: Graph context made of cycles of length 2-4.</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>Figure 10: Graph patterns for the graph context in Fig. 9.</figcaption></figure>

automorphic concepts which are interchangeable nodes in a pattern. For illustration, let us use the example on cycles of length 2-4 presented in [17]. The graph context is made of two cycles of length 2 and 4 as shown in Fig. 9. The graph patterns are presented in Fig. 10 where, patterns Q2 (red), Q3 (lime-green) and Q4 (green) all contain automorphic concepts. For instance, Q2a and Q2b are automorphic concepts. However, RCA does not produce automorphic concepts. Our idea is then to merge the occurrences of automorphic concepts in GCA graph patterns. Given P a graph pattern, merging its automorphic concepts is equivalent to computing its quotient graph with respect to the concept extents, i.e., two nodes belong to the same class if they have the same extent.

**Definition 11 (Quotient graph ([22], P.110)).** Let $G$ be a graph and let $\mathcal{P} = V_1, \dots, V_k$ be a partition of the vertex set of $G$ into non-empty classes. The quotient $G/\mathcal{P}$ of $G$ by $\mathcal{P}$ is the graph whose vertices are the sets $V_1, \dots, V_k$ and whose edges are the pairs $(V_i, V_j)$, $i \neq j$, such that there exists $u_i \in V_i, u_j \in V_j$ s.t. $(u_i, u_j) \in E(G)$.

Figure 11 presents the quotient graphs of the graph patterns shown in Fig. 10. Pattern Q1 (blue) does not change because it has no automorphic concepts. The automorphic concepts of patterns Q2, Q3, Q4 have been merged. Figure 12 presents the corresponding RCA EAR-patterns. GCA produces two more patterns (Q1, Q2) than RCA, as explained in [17].

In a *quotient pattern* $P \subseteq V^* \times A$ of a graph pattern, $A$ contains unary attributes which label nodes and $n$-ary attributes/relations which label edges. If $P$ is limited to binary relations as it is the case in this work, $A$ can be
<figure><img src="image_12.png" /><figcaption>Figure 11: Quotient graphs of the GCA graph patterns in Fig. 10.</figcaption></figure>

<caption>Figure 12: RCA patterns for the example in Fig. 9.</caption>

partitioned into two sets: unary attributes ($A_1$) and binary attributes, also called relations ($A_2$). Pattern $P$ can thus be equivalently represented as an EAR-pattern along the following definition.

**Definition 12 (GCA EAR-pattern).** Let $P \subseteq V^* \times A$ be the quotient graph of a GCA graph pattern. Let $A = A_1 \cup A_2$, with $A_1$ the set of (unary) attributes and $A_2$ the set of relations (binary attributes). The EAR-pattern of $P$ is written $P_G = (V, E, L_V, L_E)$ where:

$$ \bullet V = \{v \mid ((..., v, ...), a) \in P\}, $$

$$ \bullet E = \{(v_1, v_2) \mid ((v_1, v_2), a) \in P\}, $$

$$ \bullet L_V(v) = \{a \in A_1 \mid ((v), a) \in P\}, $$

$$ \bullet L_E((v_1, v_2)) = \{r \in A_2 \mid ((v_1, v_2), r) \in P\}. $$

## 7.2. Comparing RCA and GCA EAR-Patterns

Let $(K, R)$ be an RCF, $K$ the corresponding graph context, and $F = (K, R \cup R^{-})$ the extended RCA with inverse relations. Let $S = \cup\{S_1, S_2, ..., S_m\} = (V_S, E_S, L_{V_S}, L_{E_S})$ be the disjoint<fnref n="1" /> union of RCA EAR-patterns of $F$ and $P = \cup\{P_1, P_2, ..., P_n\} = (V_P, E_P, L_{V_P}, L_{E_P})$ be the disjoint

<footnote n="1">¹Because every concept belongs to one and only one pattern.</footnote>
union of the GCA EAR-patterns of K. In the following, we prove that every
RCA EAR-pattern is a *subgraph* of a GCA EAR-pattern, which is equivalent
to *S* being a *labelled subgraph* of *P* in the sense of Definition 13.

**Definition 13 (Labelled subgraph).** Let $G_1 = (V_1, E_1, L_{V1}, L_{E1})$ and $G_2 = (V_2, E_2, L_{V2}, L_{E2})$ be labelled graphs. $G_2$ is a labelled subgraph of $G_1$ ($G_2 \subseteq G_1$) iff $V_2 \subseteq V_1$, $E_2 \subseteq E_1$, $\forall v \in V_2 : L_{V2}(v) = L_{V1}(v)$ and $\forall (v_1, v_2) \in E_2 : L_{E2}((v_1, v_2)) = L_{E1}((v_1, v_2))$.

**Theorem 3.** Let $F = (\mathbf{K}, \mathbf{R} \cup \mathbf{R}^-)$ be an RCF extended with inverse relations and $K$ the corresponding graph context of the RCF $(\mathbf{K}, \mathbf{R})$. Let $S = \bigcup_i S_i$ be the union of RCA EAR-patterns of $F$ and $P = \bigcup_j P_j$ the union of GCA EAR-patterns of $K$. We have $S \subseteq P$, and so $\forall S_i : \exists P_j : S_i \subseteq P_j$.

**PROOF.** Let $C_R$ be the set of RCA concept extents for $F$ and $C_G$ the set of GCA concept extents for $K$. Based on $C_R \subseteq C_G$ (Theorem 2), we want to prove that $S \subseteq P$ by proving that: (1) $\forall (v_1, v_2) \in E_S : (v_1, v_2) \in E_P, L_{E_S}((v_1, v_2)) = L_{EP}((v_1, v_2))$ and (2) $\forall v_i \in V_S : v_i \in V_P, L_{V_S}(v_i) = L_{VP}(v_i)$.

(1) Let $(v_1, v_2) \in E_S$ be an edge, and $r \in L_{E_S}(v_1, v_2)$ a relation in its label, where $v_1, v_2$ correspond to the extents of concepts $C_1, C_2$. This implies that $\exists r(C_2) \in Int(C_1)$ and $\exists r^{-}(C_1) \in Int(C_2)$, by definition of RCA EAR-patterns. Then $\forall o_1 \in v_1 : \exists o_2 \in v_2 : (o_1, o_2) \in r$ and $\forall o_2 \in v_2 : \exists o_1 \in v_1 : (o_2, o_1) \in r^{-}$, hence $(o_1, o_2) \in r^{-}$ ($*$), by the definition of relational attributes.

Let $R_{12} = \{(o_1, o_2) | o_1 \in v_1, o_2 \in v_2, (o_1, o_2) \in r\}$ (object relation of
arity 2). We have $\pi_1(R_{12}) = \{\pi_1(o_1, o_2) | (o_1, o_2) \in R_{12}\} = v_1$ and $\pi_2(R_{12}) =$
$\{\pi_2(o_1, o_2) | (o_1, o_2) \in R_{12}\} = v_2^2$, according to ($*$).

Let $Q_{12} = \text{int}(R_{12}) = \bigcap_q \{Q((o_1, o_2))\}_{(o_1, o_2) \in R_{12}} = ((y_1, y_2), P_{12})$, for some pattern $P_{12}$, by definition of the intension of an object relation of arity 2. This implies that $r(y_1, y_2) \in P_{12}$, by the definition of $R_{12}$.

Let us prove that $\text{ext}(((y_1), P_{12})) = v_1$ and $\text{ext}(((y_2), P_{12})) = v_2$, i.e., that the nodes $y_1, y_2$ in the GCA EAR-pattern correspond to the nodes $v_1, v_2$ in the RCA EAR-pattern.

$$
\begin{align*}
\text{ext}(((y_1), P_{12})) \\
&= \text{ext}(\pi_1(Q_{12})), \text{ because } \pi_1((y_1, y_2)) = y_1
\end{align*}
$$

<footnote>$^2\pi_1$ and $\pi_2$ respectively represent the projection on the first and second component of a tuple or set of tuples.</footnote>
$$
\begin{align*}
&= \mathrm{ext}(\pi_1(\mathrm{int}(R_{12}))) \text{, because } Q_{12} \text{ is the intent of } R_{12} \\
&= \mathrm{ext}(\mathrm{int}(\pi_1(R_{12}))) \text{, because of Lemma 24 in [6] } (\pi(\mathrm{int}(R)) = \mathrm{int}(\pi(R))) \\
&= \mathrm{ext}(\mathrm{int}(v_1)) \text{, since } \pi_1(R_{12}) = v_1 \\
&= v_1 \text{, because } v_1 \in C_R \subseteq C_G \text{, so } v_1 \text{ is closed as a concept extent.}
\end{align*}
$$

By analogy, we also have $ext(((y_2), P_{12})) = v_2$. Those results imply that $r(y_1, y_2) \in P_{12}$, then, from the definition of GCA EAR-patterns, $(v_1, v_2)$ is an edge in $P$, and $r$ is one of its labels.

Moreover, if $r$ is a label of $(v_1, v_2)$ in $P$, then $r(y_1, y_2) \in P_{12}$, then $r(o_1, o_2)$ for all $(o_1, o_2) \in ext(Q_{12})$. Hence, for all $o_1 \in \pi_1(ext(Q_{12})) = v_1$, there is $o_2 \in \pi_2(ext(Q_{12})) = v_2$ s.t. $(o_1, o_2) \in r$. As a consequence, we have $\exists r(C_2) \in Int(C_1)$. Similarly, we have $\exists r^{-}(C_1) \in Int(C_2)$. Therefore, $r$ is a label of the edge $(v_1, v_2)$ in $S$.

(2) Let $v \in V_S$ be a node and $a \in L_{v_S}(v)$ be a label attribute, where $v$ corresponds to the extent of concept $C$. This implies that $a \in Int(C)$ by definition of RCA EAR-patterns, hence $\forall o \in v : a(o)$.

Let $Q = int(v) = ((y), P)$ for some pattern $P$. We have $a(y) \in P$ because $Q$ generalizes all objects in $v$, all of which have attribute $a$. Moreover, $ext(Q) = ext(int(v)) = v$ because $v \in C_R \subseteq C_G$. Then, from the definition of GCA EAR-patterns, $v$ is a node of $P$, and $a$ is one of its labels.

Moreover, if $a$ is a label of $v$, then $a(y) \in P$, then $a(o)$ for all $o \in v$, hence $a \in Int(C)$, and finally $a$ is a label of $v$ in $S$. ■

Theorem 3 covers three configurations. Firstly, we can have $S = P$ where all patterns are the same. An example is the **Animal_Food** context presented in Fig. 3. Secondly, we can have a one-to-one matching between patterns but there exists at least one pair of different patterns $S_i, P_j$, where $S_i \subset P_j$. An example is given in [17], where GCA produces one more concept than RCA. The third configuration is when there exists a pattern $P_j$ that cannot be matched with any pattern $S_i$. An example is the cycle shown in Fig. 9.

## 8. Conclusion

In this paper, we have conducted a theoretical comparison between RCA and GCA based on their common ground namely, unary concepts, existential quantifier, data with only unary and binary relations and integration of inverse relationships into RCA input data. The extensional comparison provides the theoretical proof that the set of RCA concept extents is included in the set of GCA concept extents. To perform the intensional comparison, we
transform RCA output - the concept lattice family - into RCA EAR-patterns where relational attributes are represented as labeled edges between concept extensions. We then proved that the RCA EAR-patterns are subgraphs of the GCA EAR-patterns, which are quotient graphs of GCA graph patterns. These two comparisons allow us to conclude that the results of RCA are included in the results of GCA. Therefore, GCA is more expressive than RCA in this setting. This is to explore further, considering a maximal version of RCA, as suggested by [23].

As future work, we will investigate the formalization of RCA EAR-patterns for lattice families with quantifiers other than the existential quantifier ($\exists\forall$, $\supset$, or with percentages). This will lead to representations with richer and more meaningful relations/edges, that will be useful to help the interpretation of lattice families. The notion of *n*-ary concepts which is one of the specificities of GCA is based on graph patterns. It would be interesting to compute *n*-ary concepts from RCA EAR-patterns to take advantage of RCA quantifiers.

*Acknowledgments*. This research is supported by ANR project SmartFCA (ANR-21-CE23-0023).

## References

[1] B. Ganter, R. Wille, Formal Concept Analysis: Mathematical Foundations, Springer, 1999.

[2] F. Lehmann, R. Wille, A triadic approach to formal concept analysis, in: Conceptual Structures: ICCS'95, Proc., Springer, 1995, pp. 32–43.

[3] R. Wille, Conceptual graphs and formal concept analysis, in: Conceptual Structures: ICCS'97, Proc., Springer, 1997, pp. 290–303.

[4] M. Rouane-Hacene, M. Huchard, A. Napoli, P. Valtchev, Relational concept analysis: mining concept lattices from multi-relational data, Annals of Mathematics and Artificial Intelligence 67 (2013) 81–108.

[5] J. Kötters, Concept lattices of a relational structure, in: Conceptual Structures: ICCS 2013, Proc., Springer, 2013, pp. 301–310.

[6] S. Ferré, P. Cellier, Graph-FCA: An extension of formal concept analysis to knowledge graphs, Discrete applied mathematics 273 (2020) 81–102.
[7] A. Bazin, J. Galasso, G. Kahn, Polyadic relational concept analysis, International Journal of Approximate Reasoning 164 (2024) 109067.

[8] M. Yan, J. Li, Knowledge discovery and updating under the evolution of network formal contexts based on three-way decision, Information Sciences 601 (2022) 18–38.

[9] N. Hlad, B. Lemoine, M. Huchard, A.-D. Serial, Leveraging relational concept analysis for automated feature location in software product lines, in: Proc. of the 20th ACM SIGPLAN Int. Conf. on Generative Programming: Concepts and Experiences, 2021, pp. 170–183.

[10] L. Shi, Y. Toussaint, A. Napoli, A. Blansché, Mining for reengineering: An application to semantic wikis using formal and relational concept analysis, in: ESWC Conference, Springer, 2011, pp. 421–435.

[11] V. Fokou, K. El Haff, A. Braud, X. Dolques, F. Le Ber, V. Pitchon, Exploring Old Arabic Remedies with Formal and Relational Concept Analysis, in: Int. Joint Conf. Concepts 24, Springer, 2024, pp. 302–318.

[12] S. Ferré, P. Cellier, Graph-FCA in practice, in: ICCS 2016, LNCS vol 9717, Springer, 2016, pp. 107–121.

[13] S. Ferré, Exploring the application of graph-FCA to the problem of knowledge graph alignment, in: CLA 2022, 2022, pp. 1–12.

[14] C. Nica, A. Braud, X. Dolques, M. Huchard, F. Le Ber, Extracting Hierarchies of Closed Partially-Ordered Patterns using Relational Concept Analysis, in: ICCS 2016, LNCS vol 9717, Springer, 2016, pp. 17–30.

[15] S. Ferré, P. Cellier, How Hierarchies of Concept Graphs Can Facilitate the Interpretation of RCA Lattices?, in: CLA 2018, Vol. 2123 of CEUR-WS Proc., 2018.

[16] P. Keip, S. Ferré, A. Gutierrez, M. Huchard, P. Silvie, P. Martin, Practical comparison of FCA extensions to model indeterminate value of ternary data, in: CLA 2020, Vol. 2668 of CEUR-WS Proc., 2020.

[17] V. Fokou, P. Cellier, X. Dolques, S. Ferré, F. Le Ber, Comparing Relational Concept Analysis and Graph-FCA on their Common Ground, in: Int. Joint Conf. Concepts 24, 2024, pp. 63–79.
[18] A. Ouzerdine, A. Braud, X. Dolques, M. Huchard, F. Le Ber, Adjusting the Exploration Flow in Relational Concept Analysis, in: AKDM, SCI Vol 1004, Springer, 2022, pp. 175–198.

[19] M. Huchard, P. Martin, E. Muller, P. Poncelet, V. Raveneau, A. Sal-laberry, RCAviz: Exploratory search in multi-relational datasets represented using relational concept analysis, IJAR 166 (2024) 109123.

[20] C. Nica, A. Braud, F. Le Ber, RCA-SEQ: an original approach for enhancing the analysis of sequential data based on hierarchies of multilevel closed partially-ordered patterns, DAM 273 (2020) 232–251.

[21] S. Even, Graph algorithms, Cambridge University Press, 2011.

[22] G. Hahn, C. Tardif, Graph homomorphisms: structure and symmetry, in: Graph symmetry: Algebraic Methods and Applications.

[23] J. Euzenat, Stepwise functional refoundation of relational concept analysis (2024). arXiv:2310.06441.