# Relational Concept Analysis: Where Formal Concepts Meet Description Logics

Marianne Huchard

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

To cite this version:

Marianne Huchard. Relational Concept Analysis: Where Formal Concepts Meet Description Logics. Journées Mondiales de la Logique, Christian Rétoré, Jan 2025, Montpellier, France. lirmm-04895826

HAL Id: lirmm-04895826

https://hal-lirmm.ccsd.cnrs.fr/lirmm-04895826v1

Submitted on 18 Jan 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_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Relational Concept Analysis:
Where Formal Concepts Meet Description Logics

Marianne Huchard

Montpellier University, LIRMM, France

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

Journées Mondiales de la Logique 2025
Introduction

Formal Concept Analysis & Propositional Logic

Relational Concept Analysis & Description Logics

RCA -DL opportunities

Concluding remarks
# Agenda

## Introduction

- Formal Concept Analysis & Propositional Logic

- Relational Concept Analysis & Description Logics

- RCA -DL opportunities

- Concluding remarks
Ingredients

**Formal concepts** are “a natural feature of information representation which is as fundamental to hierarchies and object/attribute structures as set theory or relational algebra are for relational databases”.

Uta Priss. 40th Anniv. Vol. of Annual Review of Inf. Sc. and Tech., 2006

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

**Description Logics** are “a family of knowledge representation languages that can be used to represent the knowledge of an application domain in a structured and formally well-understood way. The name description logics is motivated by the fact that [...] the important notions of the domain are described by **concept descriptions**”.

F. Baader, I. Horrocks, U. Sattler. Description Logics, Foundations of Artificial Intelligence, Chap. 3, Vol. 3, Elsevier, 2008

<figure><img src="image_5.png" /></figure>
# Agenda

## Introduction

## Formal Concept Analysis & Propositional Logic

## Relational Concept Analysis & Description Logics

## RCA -DL opportunities

## Concluding remarks
## Galois correspondences in Algebra (1830)

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

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

Wikipedia: Evariste Galois (1811-1932); The last page of its last manuscript; A Duel in the Bois De Boulogne, Near Paris, wood-engraving after G. Durand, Harper's Weekly (Jan. 1875); H. Lecomte, Combat de la rue de Rohan le 29 juillet 1830;

The Galois Fundamental theorem "asserts that given a field extension E/F that is finite and Galois, there is a one-to-one correspondence between its intermediate fields and subgroups of its Galois group." (wikipedia) Ex. of Galois correspondence "Lattice of subfields (left) for $K/Q$ and inverted Lattice of subgroups of $Gal(K/Q)$"(wikipedia)
Galois connection in partial order and lattice theory (1940-1944)

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

Georges David Birkhoff, 1940; Øystein Ore, 1944

A monotone Galois connection between $(A, \leq)$ and $(B, \leq)$ is a pair $(f, g)$
s.t. $f, g$ monotone and $f: A \to B$ and $g: B \to A \forall a \in A, b \in B,$
$a \leq g(b) \Leftrightarrow f(a) \leq b$

$(A, \leq)$
Sets of
integers
ordered by
inclusion

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

$(B, \leq)$
Set of signs
ordered by
inclusion
## Galois lattices in math. & social sciences (1970)

<figure><img src="image_10.png" /><figcaption>Highlighting of the Galois connection associated with a binary relation
Application to qualitative multivariate analysis of questionnaires</figcaption></figure>

<figure><img src="image_11.png" /></figure>
# 1982: Restructuring Lattice Theory (Rudolf Wille)

## RESTRUCTURING LATTICE THEORY:
AN APPROACH BASED ON HIERARCHIES OF CONCEPTS

Rudolf Wille
Fachbereich Mathematik
Technische Hochschule Darmstadt
1800 Darmstadt
Federal Republic of Germany

## ABSTRACT

Lattice theory today reflects the general status of current mathematics: there is a rich production of theoretical concepts, results, and developments, many of which are reached by elaborate mental gymnastics; on the other hand, the connections of the theory to its surroundings are getting weaker and weaker, with the result that the theory and even many of its parts become more isolated. Restructuring lattice theory is an attempt to reinvigorate connections with our general culture by interpreting the theory as coherently as possible, and in this way to promote better communication between lattice theorists and potential users of lattice theory.

The approach reported here goes back to the origin of the lattice concept in nineteenth-century attempts to formalise logic, where a fundamental step was the reduction of a concept to its "extent". We propose to make the reduction less abstract by retaining in some measure the "intent" of a concept. This can be done by starting with a fixed object which in defined as a triple $(G, \mathcal{M}, \mathcal{R})$ where $G$ is a set of objects, $\mathcal{M}$ is a set of attributes, and $\mathcal{R}$ is a binary relation between $G$ and $\mathcal{N}$ Indicating by $\mathcal{glm}$ that the object $\mathcal{G}$ has the attribute $\mathcal{R}$. There is a natural Galois connection between $\mathcal{G}$ and $\mathcal{N}$ defined by $\mathcal{A}^* = \{\mathcal{M} \mid \mathcal{glm} \text{ for all } \mathcal{G} \in \mathcal{G} \text{ and } \mathcal{R}^* \in \mathcal{R}^* \text{ for all } \mathcal{M} \in \mathcal{M}\}$. A concept of the context $(G, \mathcal{M}, \mathcal{R})$ is introduced as a pair $(\mathcal{A}, \mathcal{R})$ with $\mathcal{A} \in \mathcal{G}$, $\mathcal{R} \in \mathcal{M}$, $\mathcal{A}^* = \mathcal{R}^*$, and $\mathcal{R}^* \in \mathcal{R}$, where $\mathcal{R}$ is called the ambient and $\mathcal{A}$ the (ambient) of the concept $(\mathcal{A}, \mathcal{R})$. The hierarchy of concepts given by the relation subconcept-supercConcept is captured by the definition $(\mathcal{A}_1, \mathcal{R}_1) = (\mathcal{A}_2, \mathcal{R}_2) = \dots = \mathcal{A}_i \in \mathcal{A}^*(\mathcal{M}_1, \mathcal{R}_1) = \dots = \mathcal{A}_i \in \mathcal{A}^*(\mathcal{M}_n, \mathcal{R}_n)$ for concepts $(\mathcal{A}_1, \mathcal{R}_1)$, $(\mathcal{A}_2, \mathcal{R}_2)$, \dots of $(\mathcal{A}_n, \mathcal{R}_n)$. Let $\mathcal{L}(\mathcal{G}, \mathcal{M}, \mathcal{R})$ be the

<figure><img src="image_12.png" /></figure>
<figure><img src="image_13.png" /><figcaption>Bernhard Ganter & Rudolf Wille, Seminal book 1999</figcaption></figure>

* Philosophical perspective, Spirit of Port-Royal terminology (Arnauld et Nicole, 1683)

* Terminology: Formal concepts, Extension/Intension (extent/intent), Concept lattice

* Many theoretical tools including the logical perspective

* Opening towards applications
Simple but powerful basics

• Formal Context

• Galois connection

• Concept Lattice

• Connections with propositional logic
Formal Context = Triple (*O*, *A*, *R*)

*O* is a finite set of objects, *A* is a finite set of attributes

*R* ⊆ *O* × *A* is a binary relation

$(o, a) \in R$ means that object *o* owns attribute *a*.

<table><thead><tr><th>Ingredient</th><th>vege</th><th>vegan</th><th>spring</th><th>summer</th><th>autumn</th></tr></thead><tbody><tr><td>goatcheese</td><td>×</td><td></td><td></td><td>×</td><td></td></tr><tr><td>burrata</td><td>×</td><td></td><td>×</td><td></td><td></td></tr><tr><td>scallop</td><td></td><td></td><td>×</td><td></td><td></td></tr><tr><td>tomato</td><td>×</td><td>×</td><td></td><td>×</td><td></td></tr><tr><td>shallot</td><td>×</td><td>×</td><td></td><td></td><td>×</td></tr><tr><td>mushroom</td><td>×</td><td>×</td><td></td><td></td><td>×</td></tr><tr><td>eggplant</td><td>×</td><td>×</td><td></td><td>×</td><td></td></tr></tbody></table>
Two operators, both denoted by ', connect the powerset of objects, $2^0$ and the powerset of attributes $2^A$ as follows:

$$ \begin{aligned} \text{': } 2^0 \to 2^A, \quad & X' = \{a \in A \mid \forall o \in X, (o, a) \in R\} \\ \text{': } 2^A \to 2^0, \quad & Y' = \{o \in O \mid \forall a \in Y, (o, a) \in R\} \end{aligned} $$

The pair of ' operators induces a Galois connection between $2^0$ and $2^A$

A pair $(X, Y)$ where $X \in 2^0$, $Y \in 2^A$, $X = Y'$, and $Y = X'$, is a (formal) concept, with $X$ as extent and $Y$ as intent.
Formal Concept = Pair (Extent, Intent)

Extent = Maximal set of owner objects

Intent = Maximal set of their shared attributes

<table><thead><tr><th>Ingredient</th><th>vege</th><th>vegan</th><th>spring</th><th>summer</th><th>autumn</th></tr></thead><tbody><tr><td>goatcheese</td><td>×</td><td></td><td></td><td>×</td><td></td></tr><tr><td>burrata</td><td>×</td><td></td><td>×</td><td></td><td></td></tr><tr><td>scallop</td><td></td><td></td><td>×</td><td></td><td></td></tr><tr><td>tomato</td><td>×</td><td>×</td><td></td><td>×</td><td></td></tr><tr><td>shallot</td><td>×</td><td>×</td><td></td><td></td><td>×</td></tr><tr><td>mushroom</td><td>×</td><td>×</td><td></td><td></td><td>×</td></tr><tr><td>eggplant</td><td>×</td><td>×</td><td></td><td>×</td><td></td></tr></tbody></table>
The set $\mathcal{C}_K$ of all concepts extracted from $K$ ordered by extent inclusion forms a complete lattice, $\mathcal{L}_K = \langle \mathcal{C}_K, \le_K \rangle$, called the *concept lattice* of the context (or the *Galois lattice* of the binary relation $R$)
Concept Lattice

<figure><img src="image_14.png" /></figure>
Another view of concept building

<figure><img src="image_15.png" /><figcaption>Links between objects and attributes</figcaption></figure>
Another view of concept building

Links between objects and attributes vege / vegan

<figure><img src="image_16.png" /></figure>
Another view of concept building

Concept of vegan ingredients

<figure><img src="image_17.png" /></figure>
Connections with propositional logic

"One of the aspects of FCA thus is **attribute logic**, the study of possible attribute combinations. Most of the time, this will be very elementary. Those with a background in Mathematical Logic might say that attribute logic is just Propositional Calculus, and thus Boolean Logic, or even a fragment of this. Historically, the name Propositional Logic is misleading: Boole himself used the intuition of attributes (signs) rather than of propositions. So in fact, attribute logic goes back to Boole. But our style is different from that of logicians. Our logic is contextual, which means that **we are interested in the logical structure of concrete data (of the context)**. Of course, the general rules of mathematical logic are important for this and will be utilized." B. Ganter.

https://www.kde.cs.uni-kassel.de/lehre/ss2005/formale_begriffsanalyse/skript/chapter1_2.pdf

* Constraints

* Implications, association rules
Logical Constraints: Mutual exclusion

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

Intersection of C14 and C11 extents is empty

$$ \neg (spring \land vegan) $$
<figure><img src="image_19.png" /></figure>

Extent of C9 is covered by extents of C14 and C10
(possibly non disjoint)

Ingredients verify: spring ∨ vege
<figure><img src="image_20.png" /></figure>

Extents of C14, C17 and C16 form a partition of C9 Extent
Ingredients verify: spring ⊕ autumn ⊕ summer
Implication rules Prem $\Rightarrow$ Conc of K = (O, A, R)

Pair (Prem, Conc) $\subseteq A \times A$ s.t. $g(Prem) \subseteq g(Conc)$

all the **objects** that own the **attributes** of Prem (premise) also own
the **attributes** of Conc (conclusion)

vegan $\Rightarrow$ vege
Implication rules

Criteria for an implication set

* Sound: any implication of the set holds

* Complete: any other implication can be obtained from the set

* Basis: sound and complete

* Minimal cardinality

* Direct: any attribute closed set can be obtained in one iteration

* No redundancy between rules and inside rules
Diverse approaches

* Minimal non-redundant set of binary implications

* Basis of Duquennes-Guigues [Guigues, 1986] (For a systematic study, see [Bertet&Monjardet, 2010])

* Left-minimal direct basis of implications [Cordero 2013]

* Basis of proper premises [Reppe, 2008; Ryssel, 2014]

* and others ...
Duquenne-Guigues Basis of Implications (DGBI)

"What we can remember and gather from the
data forgetting the objects" V. Duquenne, 1987

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

Cardinality minimal set of non redundant implications

<support> implication

support = number of objects that hold the implication

<2> autumn => vege,vegan

<3> summer => vege

<4> vegan => vege

<0> vege,spring,summer => vegan,autumn

<0> vege,vegan,summer,autumn => spring

<0> vege,vegan,spring => summer,autumn

Nota: redundancy can occur in a premise or in a conclusion
<table><thead><tr><th>Ingredient</th><th>vege</th><th>vegan</th><th>spring</th><th>summer</th><th>autumn</th></tr></thead><tbody><tr><td>goatcheese</td><td>x</td><td></td><td></td><td></td><td></td></tr><tr><td>burrata</td><td>x</td><td></td><td>x</td><td></td><td></td></tr><tr><td>scallop</td><td></td><td></td><td>x</td><td></td><td></td></tr><tr><td>tomato</td><td>x</td><td>x</td><td></td><td>x</td><td></td></tr><tr><td>shallot</td><td>x</td><td>x</td><td></td><td></td><td>x</td></tr><tr><td>mushroom</td><td>x</td><td>x</td><td></td><td></td><td>x</td></tr><tr><td>eggplant</td><td>x</td><td>x</td><td></td><td></td><td>x</td></tr></tbody></table>

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

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

<2> autumn => vege, vegan

<3> summer => vege

<4> vegan => vege

<0> vege, spring, summer => vegan, autumn

<0> vege, vegan, summer, autumn => spring

<0> vege, vegan, spring => summer, autumn

The magic triangle of FCA
Limits and developments

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

Non tabular
data

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

Imperfect data

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

Deluge of
patterns

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

Huge lattice

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

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

"what kind of
alien really
reads Figure
3 concept
lattice..."
* **Multi-valued attributes**: integers, double, terms, structures, symbolic objects, etc. (Ganter et Wille, Diday, Polaillon, ...)

* **Fuzzy** (Belohlavek et al., Cabrera, Cordero, Enciso, Mora, López-Rodríguez, Ojeda-Aciego et al., Cornejo, Medina et al., Yahia et al., Dubois, Prade ...)

* **Value taxonomies** (Godin et al., Carpineto et Romano, ...)

* **Logical description** (Chaudron et al., Ferré et al., ...)

* **Graphs** (Ganter and Kuznetsov, Liquière, Prediger et Wille, Kötters et al., Graph-FCA Ferré et al....)

* **Multi-relational, RCA** (Priss, Rouane et al., ...); **RCA+Fuzzy** (Boffa et al.)

* **Polyadic** (Sacarea, Tronca et al.)

* **Sequences** (Boukhetta, Demko, Bertet et al., Buzmakov et al.)

* **Temporal data** (Wolff et al., Nica, Braud, Dolques, Le Ber et al., Boukhetta, Demko, Bertet et al.)

* **Pattern Structures** (Ganter et al., Kuznetsov et al., Napoli et al., Buzmakov et al.)
# Agenda

Introduction

Formal Concept Analysis & Propositional Logic

Relational Concept Analysis & Description Logics

RCA -DL opportunities

Concluding remarks
Principles

* Extends the purpose of FCA for taking into account object categories and links between objects

* Main principles:

* A relational model based on the entity-relationship model (restricted to unidirectional binary relationships)

* *relational attributes* integrate relations in formal contexts between objects

* Various operators (*quantifiers*) inspired by description logics

* Iterative and tunable process

* RCA provides a *set of interconnected lattices*

* Translation in the Description logics framework

M. Huchard, M. A. Rouane-Hacène, C. Roume, P. Valtchev: Relational concept discovery in structured datasets. . Ann. Math. Artif. Intell. 2007

M. A. Rouane-Hacène, M. Huchard, A. Napoli, P. Valtchev: Relational concept analysis: mining concept lattices from multi-relational data. . Ann. Math. Artif. Intell. 2013

<figure><img src="image_30.png" /></figure>
Relational Context Family (RCF)

* Set of Formal contexts (object-attribute)

* Represent classes/instances

* Set of Relational contexts (object-object)

* Represent Unidirectional binary associations/links

<figure><img src="image_31.png" /></figure>
Relational Context Family (RCF)

A relational context family $\mathcal{R}$ is a pair $(\mathcal{K}, \mathcal{R})$, where:

* $\mathcal{K}$ denotes the set of formal contexts $\mathcal{K}_i = (O_i, A_i, I_i)$,

* $\mathcal{R}$ denotes the set of relational contexts $r_k \subseteq O_i \times O_j$, where $O_i$ and $O_j$ are the object sets of formal contexts $\mathcal{K}_i$ and $\mathcal{K}_j$.
Relational Context Family Pizzerias

<table><thead><tr><th>Pizzeria</th><th>ldHappizzy</th><th>ldEatalicy</th><th>ldLafelicita</th><th>ldSmallitaly</th></tr></thead><tbody><tr><th>happizzy</th><td>x</td><td></td><td></td><td></td></tr><tr><th>eataly</th><td></td><td>x</td><td></td><td></td></tr><tr><th>lafelicita</th><td></td><td></td><td>x</td><td></td></tr><tr><th>smallitaly</th><td></td><td></td><td>x</td><td></td></tr></tbody></table>

<table><thead><tr><th>Pizza</th><th>ldCabri</th><th>ldForest</th><th>ldViolent</th><th>ldStjacques</th></tr></thead><tbody><tr><th>cabri</th><td>x</td><td></td><td></td><td></td></tr><tr><th>forest</th><td></td><td>x</td><td></td><td></td></tr><tr><th>violet</th><td></td><td></td><td>x</td><td></td></tr><tr><th>stjacques</th><td></td><td></td><td>x</td><td></td></tr></tbody></table>

<table><thead><tr><th>Ingredient</th><th>vege</th><th>vegan</th><th>spring</th><th>summer</th><th>autumn</th></tr></thead><tbody><tr><th>goatcheese</th><td>x</td><td></td><td></td><td>x</td><td></td></tr><tr><th>burrata</th><td>x</td><td></td><td>x</td><td></td><td></td></tr><tr><th>scallop</th><td></td><td></td><td></td><td></td><td></td></tr><tr><th>tomato</th><td>x</td><td>x</td><td></td><td>x</td><td></td></tr><tr><th>shallot</th><td>x</td><td>x</td><td></td><td></td><td>x</td></tr><tr><th>mushroom</th><td>x</td><td>x</td><td></td><td></td><td>x</td></tr><tr><th>eggplant</th><td>x</td><td>x</td><td></td><td>x</td><td></td></tr></tbody></table>

<table><thead><tr><th>contains</th><th>goatcheese</th><th>burrata</th><th>scallop</th><th>tomato</th><th>shallot</th><th>mushroom</th><th>eggplant</th></tr></thead><tbody><tr><th>cabri</th><td>x</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><th>forest</th><td></td><td></td><td></td><td>x</td><td>x</td><td>x</td><td></td></tr><tr><th>violet</th><td></td><td></td><td>x</td><td></td><td></td><td></td><td>x</td></tr><tr><th>stjacques</th><td></td><td>x</td><td>x</td><td></td><td></td><td></td><td></td></tr></tbody></table>

<table><thead><tr><th>serves</th><th>cabri</th><th>forest</th><th>violet</th><th>stjacques</th></tr></thead><tbody><tr><th>happizzy</th><td>x</td><td>x</td><td></td><td></td></tr><tr><th>eataly</th><td></td><td>x</td><td>x</td><td></td></tr><tr><th>lafelicita</th><td></td><td></td><td>x</td><td></td></tr><tr><th>smallitaly</th><td>x</td><td></td><td></td><td>x</td></tr></tbody></table>
<figure><img src="image_32.png" /></figure>

serves

contains
# Vegan ingredients

Concept of vegan ingredients

<figure><img src="image_33.png" /></figure>
Concept building: relational attribute introduction

Concept pizzas that have all their ingredients in concept vegan ingredients

forest and violet share: $\exists\forall contains (Vegan)$

<figure><img src="image_34.png" /></figure>
Objective: consistently introduce in FCA framework abstractions similar to the role restrictions $\forall r.C$ or $\exists r.C$ in DL

Role restrictions provide summaries of object links:

* $\exists r.C$ expresses that for any object satisfying the restriction, at least one of its "r links" points to instances of C.

* $\forall r.C$ expresses that for any object satisfying the restriction, all its "r links" point to instances of C.

* $\exists \forall r.C$ expresses that for any object satisfying the restriction, at least one and all its "r links" point to instances of C.
Concept building

Concept pizzerias that have at least one pizza in concept pizzas that have all their ingredients in concept vegan ingredients

happizzy, eataly and lafelicita share:

$$ \exists \text{ serves} (\exists \forall \text{contains} (\text{Vegan})) $$

<figure><img src="image_35.png" /></figure>
* Initialization

* Build the concept lattice associated with each formal context

* Iteration until a fix point is reached

* Scaling: Extend each formal context FC with the relational attributes associated with all relations that have FC as domain, for chosen quantifiers.

* Build the concept lattice associated with each extended formal context

INPUT: relational context family

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

OUTPUT: Concept Lattice Family

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

Credits X. Dolques
Interconnected concept lattices

<figure><img src="image_38.png" /></figure>
Concept building

Concept pizzerias that have all their pizzas in concept pizzas that have all their ingredients in concept vegan ingredients

eataly and lafelicita share:

<figure><img src="image_39.png" /></figure>
Interconnected concept lattices

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

C_Pizzeria_34

∃∀serves(C_Pizza_31)

C_Pizza_31

∃∀contains(C_Ingredient_11)

C_Ingredient_11

Vegan
## Cyclic models
(including cyclic data)

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

## Complex models

<figure><img src="image_42.png" /><figcaption>Credits P. Martin</figcaption></figure>

## A variety of quantifiers (excerpt)

<table><thead><tr><th>Operator</th><th>Attribute form</th><th>Condition</th></tr></thead><tbody><tr><td>Universal (narrow)</td><td>∀ r.c</td><td>r(o) ⊆ Ext(c)</td></tr><tr><td>Universal strict</td><td>∃ r.c</td><td>r(o) ⊆ Ext(c) and r(o) ≠ ∅</td></tr><tr><td>Universal-percent</td><td>∀∃ ≥ n% r.c</td><td>|r(o) ∩ Extent(c)| ≥ n|r(o)|/100</td></tr><tr><td>Covers</td><td>≥ r.c</td><td>r(o) ≥ Ext(c)</td></tr><tr><td>Covers-percent</td><td>≥ ∃ n% r.c</td><td>|r(o) ∩ Extent(c)| ≥ n|Extent(c)|/100</td></tr><tr><td>Existential (wide)</td><td>∃ r.c</td><td>r(o) ∩ Ext(c) ≠ ∅</td></tr><tr><td>Universal strict</td><td>∃ r.c</td><td>r(o) ⊆ Ext(c) and r(o) ≠ ∅</td></tr><tr><td>Qualif. card. restriction</td><td>≥ n r.c</td><td>r(o) ⊆ Ext(c) and r(o) ≥ n</td></tr><tr><td>Card. restriction</td><td>≥ n r.⊥</td><td>|r(o)| ≥ n</td></tr></tbody></table>
Family of knowledge representation formalisms, where an
application domain is described in terms of concepts, roles and
individuals

Knowledge basis:

* TBox (terms: concepts and relations)

* ABox (assertions)

Syntax excerpt:

<table><thead><tr><th>syntax</th><th>constructor</th><th>syntax</th><th>constructor</th></tr></thead><tbody><tr><td>⊤</td><td>universal</td><td>⊥</td><td>absurd</td></tr><tr><td>c1 ∩ c2</td><td>conjunction</td><td>c1 ∪ c2</td><td>disjunction</td></tr><tr><td>c1 ⊑ c2</td><td>concept subsumption</td><td>r1 ⊑ r2</td><td>role subsomption</td></tr><tr><td>∀r.c</td><td>universal restriction</td><td>∃r.c</td><td>existential restriction</td></tr><tr><td>(≥ n r)</td><td>cardinality sup restriction</td><td>(≤ n r)</td><td>cardinality inf restriction</td></tr><tr><td>¬ c1</td><td>concept negation</td><td>r1 ∧ r2</td><td>role composition</td></tr></tbody></table>

F. Baader, D. Calvanese, D. L. McGuinness, D. Nardi, P. F. Patel-Schneider: The Description Logic Handbook: Theory, Implementation, Applications. Cambridge University Press, Cambridge, UK, 2003.
Connection RCA - DL ($FLE^+$)

A bijective mapping $\alpha$ associates a DL construct, of TBox and ABox ($T(T_C, T_R)$, $A$) in $FLE^+$: conjunction, universal and existential restrictions to each RCA entity

Construction of the TBox

<table><thead><tr><th>Source rca entity</th><th>Notation</th><th>Target dl element</th><th>Rule</th></tr></thead><tbody><tr><td>context</td><td>$\mathcal{K} \in \mathcal{K}$</td><td>primitive concept</td><td>$\alpha[\mathcal{K}] \in \mathcal{T}_C$</td></tr><tr><td>atomic attribute</td><td>$a \in A_i$</td><td>primitive concept</td><td>$\alpha[a] \in \mathcal{T}_C$</td></tr><tr><td>relation</td><td>$r \in \mathbf{R}$</td><td>primitive role</td><td>$\alpha[r] \in \mathcal{T}_R$</td></tr><tr><td>relational attribute (narrow)</td><td>$\forall r(c) \in A_i^\infty$</td><td>value restriction</td><td>$\forall \alpha[r].\alpha[c] \in \mathcal{T}$</td></tr><tr><td>relational attribute (wide)</td><td>$\exists r(c) \in A_i^\infty$</td><td>existential role quantification</td><td>$\exists \alpha[r].\alpha[c] \in \mathcal{T}$</td></tr><tr><td rowspan="3">concept</td><td>$c \in \mathcal{L}_i^\infty$</td><td>defined concept</td><td>$\alpha[c] \in \text{definitions}(\mathcal{T})$</td></tr><tr><td>$c \neq \mathcal{T}\mathcal{L}_i^\infty$</td><td>concept definition</td><td>$(\alpha[c] \equiv \bigcap_{a_j \in \text{int}(c)} \alpha[a_j]) \in \mathcal{T}$</td></tr><tr><td></td><td>inclusion axiom</td><td>$(\alpha[c] \sqsubseteq \alpha[K_i]) \in \mathcal{T}$</td></tr><tr><td>sub-concept link</td><td>$c_1 \leq_{\mathcal{L}_i^\infty} c_2$</td><td>inclusion axiom</td><td>$(\alpha[c_1] \sqsubseteq \alpha[c_2]) \in \mathcal{T}$</td></tr></tbody></table>
Connection RCA - DL

A bijective mapping $\alpha$ associates a DL construct to each RCA entity

Construction of the TBox (examples)

Primitive concepts

* Ingredient, Pizza, Pizzeria, Vege, Vegan, ..., Autumn

Primitive roles

* serves, contains

Defined concepts

* C_Pizzeria_34 ≡ ∃∀serves (C_Pizza_31)

* C_Pizza_31 ≡ ∃∀serves(C_Ingredient_11)

* C_Ingredient_11 ≡ Ingredient ⊓ Vegan

* C_Ingredient_17 ≡ Ingredient ⊓ Vegan ⊓ Autumn
Connection RCA - DL

A bijective mapping $\alpha$ associates a DL construct to each RCA entity

Construction of the ABox

<table><thead><tr><th>Source rca entity</th><th>Notation</th><th>Target dl element</th><th>Rule</th></tr></thead><tbody><tr><td rowspan="2">objects</td><td rowspan="2">o &isin; O<sub>i</sub></td><td>individual</td><td>&alpha;[o] &isin; individuals(A)</td></tr><tr><td>primitive concept<br/>instantiation</td><td>&alpha;[K<sub>i</sub>](&alpha;[o]) &isin; A</td></tr><tr><td>object-to-attribute<br/>incidence</td><td>(o, a) &isin; I<sub>j</sub><sup>0</sup></td><td>primitive concept<br/>instantiation</td><td>&alpha;[a](&alpha;[o]) &isin; A</td></tr><tr><td>relational link</td><td>r(o<sub>1</sub>, o<sub>2</sub>), r<sub>i</sub> &isin; R</td><td>role instance</td><td>&alpha;[r](&alpha;[o<sub>1</sub>], &alpha;[o<sub>2</sub>]) &isin; A</td></tr><tr><td>object-to-concept<br/>incidence</td><td>c &isin; L<sub>i</sub><sup>&infin;</sup>, o &isin; ext(c)</td><td>defined concept<br/>instantiation</td><td>&alpha;[c](&alpha;[o]) &isin; A</td></tr></tbody></table>
Connection RCA - DL

A bijective mapping $\alpha$ associates a DL construct to each RCA entity

Construction of the ABox (examples)

* Individuals: eataly, violet, shallot, eggplant

* Primitive concept instantiation: Vegan(shallot)

* Role instances: serves(eataly,violet), contains(violet,eggplant)

* Defined concept instanciation: C_Pizzeria_34(eataly), C_Pizza_31(violet), C_Ingredient_11(shallot), C_Ingredient_17(shallot)
Connection RCA - DL

Each extended formal context has its associated implications.
E.g. for RCA with ∃serves, ∃∀contains setting, a few implications
for pizzerias:

$$
\begin{align*}
\langle 2 \rangle \quad & \exists \ \text{serves}(\text{IdViolet} \& \exists \ \text{contains}(\text{/I/vege\&vegan\&summer})), \exists \\
& \text{serves}(\exists \ \text{contains}(\text{summer})), \exists \ \text{serves}(\exists \ \text{contains}(\text{vege})) \\
\Rightarrow & \exists \ \text{serves}(\exists \ \text{contains}(\text{vegan}))
\end{align*}
$$

$$
\begin{align*}
\langle 2 \rangle \quad & \exists \ \text{serves}(\text{IdForest} \& \exists \ \text{contains}(\text{autumn})), \exists \\
& \text{serves}(\exists \ \text{contains}(\text{summer})), \exists \ \text{serves}(\exists \ \text{contains}(\text{vege})) \\
\Rightarrow & \exists \ \text{serves}(\exists \ \text{contains}(\text{vegan}))
\end{align*}
$$

$$
\langle 4 \rangle \Rightarrow \exists \text{ serves}(\exists \forall \text{ contains}(\text{summer})), \\
\phantom{\langle 4 \rangle \Rightarrow \exists \text{ serves}(\exists \forall \text{ contains}(\text{summer}))} \exists \text{ serves}(\exists \forall \text{ contains}(\text{vege}))
$$
# Agenda

Introduction

Formal Concept Analysis & Propositional Logic

Relational Concept Analysis & Description Logics

RCA -DL opportunities

Concluding remarks
* Ontology building

* Microbiology (Rokia Bendaoud, Amedeo Napoli, Yannick Toussaint. A Proposal for an Interactive Ontology Design Process based on Formal Concept Analysis. FOIS 2008)

* Astronomy (Bendaoud, Rokia, Rouane-Hacene, Mohamed, Toussaint, Yannick, Delecroix, Bertrand, Napoli, Amedeo. Construction d'une ontologie à partir d'un corpus de textes avec l'ACF. IC 2007)

* Reasoning (FaCT++, RACER, DLP, Pellet, KAON2)

* Knowledge discovery through populated ontology exploration or implication exploration
<figure><img src="image_43.png" /></figure>

https://www.knomana.org/en

* Find alternatives to chemical pesticides and antibiotics, with local plants

* Understanding relations between therapeutic plants, pests (bioagressors), and affected organisms

* Intensive collection of ≥ 48.000 descriptions of plant use in the scientific literature (Pierre Silvie, Pierre Martin and a community of thematic researchers)

* Beyond queries: find or hypothesize solutions in phytotherapy by knowledge exploration (Pierre Silvie, Pierre Martin, Marianne Huchard and a group of computer scientists)

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

(1) Mature larva of beet armyworm, Spodoptera exigua (Hübner). Photograph by John Capinera, University of Florida. (2) Adult beet armyworm, Spodoptera exigua (Hübner). Photograph by Lyle J. Buss, University of Florida. (3) Aspergillus fumigata
https://commons.wikimedia.org/wiki/File:Aspergillus.jpg?uselang=fr
## Knomana: Populated ontology exploration

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

https://rcaviz.lirmm.fr/

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

**Expert:** "I need to control Fusarium oxysporum in Burkina Faso. May I find a protection system with these requirements or with close requirements?"

**By exploration:** "Lantana camara is used in Burkina Faso to control Fusarium solani. It is very likely that Lantana Camara can be also used in Burkina Faso, and this time, to control Fusarium Oxysporum"

Marianne Huchard, Pierre Martin, Emile Muller, Pascal Poncelet, Vincent Raveneau, Arnaud Sallaberry:
RCAviz: Exploratory search in multi-relational datasets represented using relational concept analysis. Int. J. Approx. Reason. 166: 109123 (2024)
## Knomana: Implication exploration

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

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

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

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

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

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

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

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

https://fcavizir.lirmmm.fr/

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

### Excerpt from Knomana

P1 (Protection System in the field) developed in Namibia (Country): Cinnamomum zeylanicum (Plant) is used to control Aspergillus flavus (Pest)

A protection system indicates a plant usage to control a pest (bioagressor) in a given country

Lola Musslin, Alexandre Bazin, Marianne Huchard, Pierre Martin, Pascal Ponculet, Vincent Raveneau, Arnaud Sallaberry: FCAvizIR: Exploring Relational Data Set's Implications Using Metrics and Topics. CONCEPTS 2024: 132-148
# Knomana: Implication exploration

A few implications of the Duquenne-Guigues base of implications:

∃PS2Pest(aspergillus),∃PS2Plant(lauraceae&comestible&applicOil),
∃PS2Plant(aromatic&evergreen)
⇒ field,∃PS2Pest(attacksCheese),∃PS2Country(australAfrica)

∃PS2Pest(aspergillus),∃PS2Country(westernAfrica),∃PS2Plant(aromatic&evergreen)
⇒ lab,∃PS2Pest(attacksPeanuts),
∃PS2Plant(asteraceae&toxic&applicEssentialOil&applicExtract)

∃PS2Pest(attacksPeanuts),∃PS2Pest(aspergillus),∃PS2Plant(aromatic&evergreen)
⇒ lab,∃PS2Country(westernAfrica),
∃PS2Plant(asteraceae&toxic&applicEssentialOil&applicExtract)

(...)

Nota: concepts id are recursively rewritten using their simplified intent (introduced attributes) for the sake of readability by domain experts
## Knomana: Implication exploration

https://fcavizir.lirmm.fr/

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

### Principles:

* **Filtering** with various **metrics** to rapidly localize implications with certain values of these metrics

* **Clustering** based on **common elements** (relations or attributes) in their premise or conclusion.

* **Estimating** the quantity of implications in the formed groups.

* **Navigating** among **topic-based** implication groups by refining/enlarging the selection step-by-step.
## Knomana: Implication exploration

https://fcavizir.lirmm.fr/

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

**After successive selections:**
support ≥ 2 ; relations ∃PS2Pest × {∃PS2Pest, ∃PS2Plant, ∃PS2Country} ; attributes aspergillus × attacksCheese, attacksCheese × {field, australAfrica} ; premise ∃PS2Pest(attacksCheese)

**Resulting Implication:**

∃PS2Pest(attacksCheese), ∃PS2Pest(aspergillus), ∃PS2Plant(aromatic&evergreen) ⇒ field, ∃PS2Country(australia)
# Agenda

Introduction

Formal Concept Analysis & Propositional Logic

Relational Concept Analysis & Description Logics

RCA -DL opportunities

Concluding remarks
* FCA, RCA: frameworks with dual graphical and logical views

* Transcription in DL frameworks of some RCA settings

* Opportunities for:

* Ontology building or completion

* Reasoning

* Knowledge discovery in a controlled formalism
Conceptual exploration extended to RCA:

* Knowledge elicitation by formal context completion asking implications of a base in a suitable ordering

* FCA framework: Conceptual Exploration, Bernhard Ganter, Sergei Obiedkov, Springer Nature, 2016

* Ask: "Is it true that for all protection systems: ∃PS2Pest(attacksCheese), ∃PS2Pest(aspergillus), ∃PS2Plant(aromatic&evergreen) ⇒ field, ∃PS2Country(australAfrica)"

* If Yes → the system goes to the next implication

* If No → the expert proposes a new protection system which is added to the relational context family
Future work for efficient use

LLM-assisted RCA output reading (implications, concepts, concept lattices)

E.g. with an Implication

* Explain to the LLM the context, syntax, ... meaning of the relations.

* "Can you write an interpretation in English of the following implication? "

exists_PS2Pest(attacksPeanuts),exists_PS2Pest(aspergillus), exists_PS2Plant(aromatic&evergreen) => lab,exists_PS2Country(westernAfrica), exists_PS2Plant(asteraceae&toxic&applicEssentialOil&applicExtract)

* ChatGPT 4o 2024/01/11:

"Here's an interpretation of the implication in English, designed for domain experts: (...) If there exists a protection system (PS) that satisfies all of the following conditions: The PS controls a pest that attacks peanuts. The PS controls a pest associated with Aspergillus (a genus of fungi). The PS uses a plant that is both aromatic and evergreen. Then, the following must also hold true: The protection system involves laboratory analysis or has been observed to involve laboratory settings. The protection system has been observed in Western Africa. The protection system uses a plant from the Asteraceae family that is both toxic and is applied in the form of essential oil or extract.(...)
Future work for efficient use

LLM-assisted Grounding problem:

* "Connect abstract symbols and representations to their real-world meanings and referents."

* Ask variants of: "what is the term for (SCOPE) which is (ATR1) and (ATR2)...., as (OBJ1), (OBJ2), (OBJ3), ...., but exclude to (CEX1), nor (CEX2), nor ....?"

* E.g. / ChatGPT 4o, 2024/01/12:

Question: "what is the term for (`C_Pizza_31`) which is (`Pizza,existForall contains(autumn),existForall contains(vegan)`)?"

Answer: "Here are some suggestions for naming the concept described by (Pizza, ∃∀contains(autumn) ∨∃contains(vegan)) in English:

AutumnVeganPizza: A straightforward and clear name highlighting the key attributes (autumn and vegan). SeasonalVeganPizza: Emphasizes the seasonal nature (autumn) and vegan characteristic. AutumnPlantBasedPizza: If "plant-based" resonates better than "vegan" in the context. (...)

If you're working within an ontology, AutumnVeganPizza or VeganAutumnPizza would balance clarity and simplicity well. Let me know if you'd like further refinements!"

* G.A. Aranda-Corral and A. Bundy and J. Borrego-Díaz and P.Y. Chan. Grounding problem in Formal Concept Analysis by means of Large Language Models, Ws. Late Breaking Advances on Conceptual Structures Concepts 2024
¡Thank you!

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

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

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

https://rcaviz.lirmm.fr/
https://www.lirmm.fr/fca4j/
https://fcavizir.lirmm.fr/

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

ANR Program Investments for the Future
Grant ANR-16-CONV-0004 anr*

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

ANR SmartFCA project
Grant ANR-21-CE23-0023 anr*