Convergence issues in Relational Concept Analysis based on AOC-posets

Xavier Dolques; Agnès Braud; Alain Gutierrez; Marianne Huchard; Florence Le Ber

cs.LGAug 30, 2026

Convergence issues in Relational Concept Analysis based on AOC-posets

Authors: Xavier Dolques, Agnès Braud, Alain Gutierrez, Marianne Huchard, Florence Le Ber

Organizations: Univ. de Strasbourg, ENGEES, CNRS, ICube UMR 7357, F-67000 Strasbourg, France · LIRMM, Univ. Montpellier, CNRS, Montpellier, France

Abstract

Formal Concept Analysis (FCA) is an approach for conceptual classification building and rule discovery from a binary table describing a set of objects by a set of attributes. Extensions have been proposed to deal with non-binary and more complex data, such as Relational Concept Analysis (RCA) for multi-relational data. RCA aims to highlight groups of objects characterized by their relationships with other groups of objects. The richer and more complex nature of the underlying data allows RCA to produce richer results than FCA, at the expense of higher computational and interpretive complexity. The most commonly used conceptual classification structure in FCA is the concept lattice. However, in many applications, concept lattice substructures, such as AOC-posets, are preferred over the full lattice, either to mitigate combinatorial blow-up or to focus on the most informative parts of the structure. Indeed, in an AOC-poset, only concepts introducing an object or an attribute are represented, which makes AOC-posets smaller and easier to compute and use than concept lattices. Although RCA was originally defined on concept lattices, it can also be instantiated on AOC-posets. RCA is iterative and its convergence is guaranteed in the lattice-based setting, but this guarantee is lost when using AOC-posets. In this paper, we investigate this loss of convergence in detail. We show why convergence is no longer guaranteed in the general case, identify conditions under which it can still be ensured, and discuss how a dataset can be transformed to recover convergence. We also propose a convergent variant of the process, which preserves the AOC-poset structure: relational attributes, once created, are never removed, which guarantees convergence at the price of attributes that may refer to concepts absent from the final structures.

Figures & tables

	herbaceous	bulb	leaves	roots	stems	flowers
camomile	$\times$					$\times$
garlic	$\times$	$\times$				$\times$
laurel			$\times$
angelica	$\times$		$\times$	$\times$
woodruff	$\times$		$\times$		$\times$
borage	$\times$				$\times$	$\times$

Table 1: Formal Context of plants and their used parts (

{\mathcal{K}}_{Plants}

)

Figure 1: Concept Lattice on

{\mathcal{K}}_{\textit{Plants}}

. Each concept is represented in 3 parts: its identifier (top), its intent (middle), and its extent (bottom); only introduced attributes and objects are shown in intents and extents respectively. In the text, C_plants_i is shortened to cp_i .

Figure 2: Formal Context

{\mathcal{K}}_{\textit{Remedies}}

(left) and concept lattice (right) for remedies. In the text, C_remedies_i is shortened to cr_i .

$r_{\mathit{contains}}$	camomile	garlic	laurel	angelica	woodruff	borage	celery
remedy0				$\times$	$\times$		$\times$
remedy1	$\times$			$\times$	$\times$		$\times$
remedy2		$\times$		$\times$	$\times$		$\times$
remedy3	$\times$	$\times$				$\times$

Table 2: Relation

\mathit{r}_{contains}

remedies	$\exists$ r(cp_11)	$\exists$ r(cp_10)	$\exists$ r(cp_3)	$\exists$ r(cp_0)	$\exists$ r(cp_7)	$\exists$ r(cp_9)	$\exists$ r(cp_5)	$\exists$ r(cp_1)	$\exists$ r(cp_4)	$\exists$ r(cp_6)	$\exists$ r(cp_2)	$\exists$ r(cp_8)
remedy0	$\times$	$\times$			$\times$	$\times$	$\times$	$\times$	$\times$	$\times$
remedy1	$\times$	$\times$			$\times$	$\times$	$\times$	$\times$	$\times$	$\times$		$\times$
remedy2	$\times$	$\times$	$\times$		$\times$	$\times$	$\times$	$\times$	$\times$	$\times$		$\times$
remedy3	$\times$	$\times$	$\times$							$\times$	$\times$	$\times$

Table 3: Existential scaling of the formal context for Remedies based on the relation

r_{contains}

(shortened to

r

in the column headers),

\mathbb{S}_{\exists}(\mathcal{K}_{\textit{Remedies}},\mathit{r_{contains}},\mathcal{C}_{\textit{Plants}})

Figure 3: Concept Lattice on

\mathbb{S}_{\exists}({\mathcal{K}}_{\textit{Remedies}},r_{contains},{\cal C}_{\textit{Plants}})

apposed to

{\mathcal{K}}_{\textit{Remedies}}

Panel of Figure 4 — Figure 4: General overview of the patterns extracted from the concept lattice family built on RP with the existential quantifier and a focus on cr_0 and linked nodes.

Figure 5: AOC-posets of Remedies (left) and Plants (right).

remedies	$\exists$ r(cp_2)	$\exists$ r(cp_0)	$\exists$ r(cp_4)	$\exists$ r(cp_3)	$\exists$ r(cp_5)	$\exists$ r(cp_7)	$\exists$ r(cp_8)	$\exists$ r(cp_1)	$\exists$ r(cp_6)
remedy0		$\times$	$\times$	$\times$	$\times$	$\times$	$\times$
remedy1		$\times$	$\times$	$\times$	$\times$	$\times$	$\times$		$\times$
remedy2	$\times$	$\times$	$\times$	$\times$	$\times$	$\times$	$\times$		$\times$
remedy3	$\times$				$\times$		$\times$	$\times$	$\times$

Table 4: Existential Scaling of Formal Context of Remedies with AOC-poset of Plants

\mathbb{S}_{\exists}(K_{Remedies},r_{\mathit{contains}},{\cal C}_{Plants})

\exists r(\texttt{cp\_i})

abbreviates

\exists{r_{\mathit{contains}}}(\texttt{cp\_i})

remedies	$\exists\forall$ r(cp_2)	$\exists\forall$ r(cp_0)	$\exists\forall$ r(cp_4)	$\exists\forall$ r(cp_3)	$\exists\forall$ r(cp_5)	$\exists\forall$ r(cp_7)	$\exists\forall$ r(cp_8)	$\exists\forall$ r(cp_1)	$\exists\forall$ r(cp_6)
remedy0						$\times$	$\times$
remedy1							$\times$
remedy2							$\times$
remedy3							$\times$		$\times$

Table 5: Strict universal scaling of formal context of Remedies with AOC-poset of Plants

\mathbb{S}_{\exists\forall}(K_{Remedies},r_{\mathit{contains}},{\cal C}_{Plants})

\exists\forall r(\texttt{cp\_i})

abbreviates

\exists\forall{r_{\mathit{contains}}}(\texttt{cp\_i})

Figure 6: AOC-poset for the

K_{Remedies}

formal context extended with the existential scaling on

{\cal C}_{Plants}

	reconcileEntries	withdraw
Ledger	$\times$
BankAccount		$\times$
Customer
Transaction

Table 7: Relational Contexts of the Bank UML fragment. For the sake of simplicity, ownedAttribute is the only relational context for which we consider an inverse ( class ) in this example.

Figure 10: Bank example - AOC-posets at step 0. In the paper, C_Operation_i may be shortened to co_i , C_Parameter_i may be shortened to cpa_i , C_Class_i may be shortened to cc_i , and C_Property_i may be shortened to cpr_i . For each concept, I, E, and Sta denote the intent cardinality, extent cardinality, and stability metric in decimal comma notation, respectively.

Figure 11: Bank example - AOC-posets at step 1.

Figure 12: Bank example - Class and Property AOC-posets at step 2 (Operation and Parameter AOC-posets are unchanged).

Figure 13: Bank example - Class and Property AOC-posets at step 3 (Operation and Parameter AOC-posets are unchanged).

Figure 14: Refactoring suggestions for the Bank model. The two new superclasses factor out the notion of owning an administrative identification (in AdminAsset ), and the fact that this identification is a String (in FinancialStructure ), and group coherent classes.

Formal Contexts	Relations
$K_{1}$ o1 o2 $K_{2}$ a1 a2 o3 $\times$ o4 $\times$ $K_{3}$ a3 a4 o5 $\times$ o6 $\times$ $K_{4}$ a5 a6 o7 $\times$ o8 $\times$	$r_{1}$ o3 o4 o1 $\times$ o2 $\times$ $r_{2}$ o1 o2 o7 $\times$ o8 $\times$ $r_{3}$ o7 o8 o5 $\times$ o6 $\times$ $r_{4}$ o5 o6 o7 $\times$ o8 $\times$

Table 8: RCF for the counterexample illustrating divergence using the existential scaling operator (

\exists

) on each relation.

Table 9: AOC-posets obtained from applying RCA-AOC on the RCF from Table 8 using the existential scaling operator (

\exists

) on each relation. For each step, AOC-posets come, from left to right, from

K_{1}

K_{2}

K_{3}

and

K_{4}

Formal Contexts	Relations
$K_{1}$ a1 o1 o2 $K_{2}$ a2 o3 o4 $K_{3}$ a3 o5 o6	$R_{1}$ o5 o6 o1 $\times$ o2 $\times$ $R_{2}$ o5 o6 o3 $\times$ o4 $\times$ $R_{3}$ o1 o2 o5 $\times$ $\times$ o6 $R_{4}$ o3 o4 o5 o6 $\times$ $\times$

Table 10: RCF for the counterexample illustrating divergence using the strict universal scaling operator (

\exists\forall

) on each relation.

Table 11: AOC-posets obtained from applying RCA-AOC on the relational context family from Table 10 using the strict universal scaling operator (

\exists\forall

) on each relation. For each step, AOC-posets come, from left to right, from

K_{1}

K_{2}

and

K_{3}

Figure 15: Dependency graph for RCF in Table 10 .

Figure 16: Example of dependency graph.

Figure 17: Bank example - Concepts created and disappearing along the steps of RCA-AOC: co_8 present only at step 0; cc_17 present at step 1, created from co_8 , and absent at step 2; cpr_22 present at step 2, created from cc_17 , and absent at step 3. In RCA-AOC-conv, co_8 also disappears at step 1, but cc_17 and cpr_22 , being the attribute-concepts of the kept relational attributes built on co_8 and cc_17 respectively, persist from their creation on.

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 18: Illustration of the incremental construction of an AOC-poset by adding an attribute. Each concept is represented with its full intent and extent. The simplified intent and simplified extent elements are circled. Concepts represented with dashed lines are concepts from the lattice that do not belong to the AOC-poset in the pictured cases: the concepts

C^{*}

from cases 3.c and 4.c can never exist in the AOC-poset while the concepts

C_{2}

from cases 4.a and 4.b could belong to the AOC-poset if

\mathit{Extent}_{S}(C)\cap\mathit{Extent}(CA)\neq\emptyset

. Crossed-out concepts are concepts that cannot exist even in the concept lattice.

Formal Contexts
$K_{1}$ a1_1 o1_1 $\times$ o1_2 $\times$ o1_3	$K_{2}$ a2_1 a2_2 o2_1 $\times$ o2_2 $\times$	$K_{3}$ a3_1 a3_2 o3_1 $\times$ o3_2 $\times$	$K_{4}$ a4_1 a4_2 o4_1 $\times$ o4_2 $\times$
Relations
$r1\_2$ o2_1 o2_2 o1_1 $\times$ o1_2 $\times$ o1_3 $\times$	$r3\_1$ o1_1 o1_2 o1_3 o3_1 $\times$ o3_2 $\times$	$r4\_3$ o3_1 o3_2 o4_1 $\times$ o4_2 $\times$	$r3\_4$ o4_1 o4_2 o3_1 $\times$ o3_2 $\times$

Appendix

Table 12: RCF making RCA-AOC diverge when using the existential scaling operator on each relation, and requiring object-concept recomputation in RCA-AOC-conv.

Figure 20: AOC-posets built with RCA-AOC-conv at steps 0 to 2 for Table 12 . The process converges.

Figure 21: AOC-posets built with RCA-AOC-conv at steps 3 to 4 for Table 12 . The process converges.

Figure 22: AOC-posets built with RCA-AOC at steps 2 to 5 for Table 12 . The process diverges.

Formal Concept Analysis

Formal Concept Analysis organizes object–attribute data into concept lattices and uses their structure for reasoning and interpretation.

See all 12 papers

Formal Concept Analysis with Three Types of Negation
Aug 29, 2026Zhenghua PanFormal Concept Analysis
School of Mathematics and Data Science, Jiangnan University, Wuxi 214122, China
Verifiable Knowledge Expansion through Retrieval-Grounded Formal Concept Analysis
Jul 2, 2026Yujin Yang, Heejung LeeKG Construction LLM Grounding
Hanyang University Seoul, Korea
A Variability-Based Framework for Interpretable Naming in Formal and Relational Concept Analysis
Jun 7, 2026Alain Gutierrez, Marianne Huchard, Pierre Martin +2Formal Concept Analysis
LIRMM, Univ. Montpellier, CNRS, Montpellier, France. · CIRAD, UPR AIDA, F-34398, Montpellier, France. · AIDA, CIRAD, Univ. Montpellier, Montpellier, France. +1

Aug 29, 2026J/K move · Enter open · S save

Formal Concept Analysis with Three Types of Negation

Zhenghua Pan

School of Mathematics and Data Science, Jiangnan University, Wuxi 214122, China

Formal Concept Analysis

Open paper AskPDF arXiv

Classic Formal Concept Analysis (FCA) primarily focuses on the positive relationships between objects and attributes and does not have mechanisms for handling negation.To overcome this limitation, we introduce three types of negation concepts (contradictory negation, opposite negation, intermediary negation) into FCA.Based on the set SCOI and logic LCOI+PLCOI with these three types negation, we define formal context, Galois connection operators, formal concept and concept lattice with three types of negation,this leads to the proposal of a FCACOI: Formal Concept Analysis with contradictory negation, opposite negation and intermediary negation.For the reasoning in FCACOI, this paper focuses on attribute implication reasoning. Based on the logic LCOI+PLCOI and its semantics, we introduce the notion of ICOI-entailment as the semantic implication for attribute implication reasoning in FCACOI. Through ICOI-entailment, a connection is established between attribute implication reasoning in FCACOI and inference in the logic LCOI+PLCOI, it indicate that formally proven inference rules (theorems) in LCOI+PLCOI are valid in the attribute implication reasoning of FCACOI, LCOI+PLCOI provides a logical foundation for attribute implication reasoning in FCACOI. To illustrate the capability of attribute implication reasoning in FCACOI, we discuss its application in a concrete example. Moreover, we explore attribute reduction of the formal context in FCACOI, propose two research frameworks for attribute reduction from different perspectives, and compare their characteristics.We believe that, based on richer logic and semantics, FCACOI elevates FCA from a theory that describes affirmations to one that can describe affirmations and its contradiction(either this or that), opposition(extreme negation) and intermediary (transitional states between oppositions).

Abstract

Formal Concept Analysis

Explore similar work

Formal Concept Analysis with Three Types of Negation

Verifiable Knowledge Expansion through Retrieval-Grounded Formal Concept Analysis

A Variability-Based Framework for Interpretable Naming in Formal and Relational Concept Analysis