Source-linked AI summary
Convergence issues in Relational Concept Analysis based on AOC-posets
Xavier Dolques, Agnès Braud, Alain Gutierrez, Marianne Huchard, Florence Le Ber
TL;DR
RCA-AOC replaces full concept lattices with compact AOC-posets, but this can remove the convergence guarantee of lattice-based RCA. The paper analyzes divergence, identifies convergence conditions, and proposes a convergent variant that preserves AOC-posets while retaining relational attributes once created.
Problem
Using AOC-posets in RCA can lose the convergence guarantee of lattice-based RCA, creating divergence and interpretive difficulties.
Method
The paper analyzes divergent RCA-AOC examples, derives data and process conditions for convergence, and proposes the RCA-AOC-conv variant.
Results
The paper shows that RCA-AOC can diverge, identifies properties that prevent divergence, and proposes a convergent variant that builds genuine AOC-posets.
Takeaways & Limitations
RCA-AOC-conv preserves the AOC-poset structure by never removing created relational attributes, while some attributes may refer to concepts absent from final structures.
Takeaways & Limitations
RCA-AOC can lose step-to-step inclusion because concepts that become non-introducers may disappear from later concept-posets.
Abstract
from arXiv · showhide
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.
1. Introduction
RCA extends FCA to multi-relational data by iteratively connecting concept structures, while AOC-posets offer a smaller representation focused on object- and attribute-concepts. This compactness motivates RCA-AOC, but using AOC-posets can lose RCA’s convergence guarantee and introduce divergence.
- RCA applies FCA iteratively to relational data, computing concept lattices connected by links that abstract relationships between objects.
- RCA uses multiple scaling operators to extract richer relational patterns, but relationships at any distance can cause combinatorial explosion and difficult pattern selection.
- AOC-posets were adopted because they produced reasonable numbers of concepts and relevant rules in environmental datasets, while focusing on outputs useful for particular applications.
- In software-engineering refactoring, attribute-concepts can guide generalized classes and object-concepts can help preserve the initial classes.
- RCA-AOC can diverge, creating a need to understand when divergence occurs and how to eliminate it or reliably use results produced in its presence.
- The paper presents three divergence examples, identifies properties that prevent divergence in most cases, and proposes a terminating variant that builds genuine AOC-posets.
2. Introduction to Relational Concept Analysis
RCA extends FCA by representing relational connections between objects through relational attributes and iteratively building interconnected concept lattices. Its scaling operators determine which source objects receive attributes referring to target concepts.
- FCA foundations: FCA extracts formal concepts from objects and attributes, organizing them in a concept lattice ordered by extent inclusion.A formal concept pairs an extent of objects with the attributes shared by those objects.
- FCA foundations: A formal context is a triple K = (G, M, I), with finite object and attribute sets connected by an incidence relation.The derivation operators identify attributes shared by objects and objects owning specified attributes.
- RCA foundations: RCA extends FCA to multiple object categories described by attributes and relations, linking concepts formed in one category to concepts in another.These datasets are represented as Relational Context Families containing contexts and relations.
- Scaling operators: RCA assigns scaling operators to relations, creating relational attributes that describe whether related objects intersect, remain within, or strictly occupy a target concept extent.The existential, universal, and strict universal operators are denoted ∃r(C), ∀r(C), and ∃∀r(C), respectively.
- Scaling operators: Existential scaling adds ∃r(C) when a source object's related-object set intersects the target concept extent, producing an extended context and updated lattice.For example, remedies receive an attribute for cp_8 when they contain at least one plant in cp_8's extent.
- Scaling operators: Strict universal scaling adds ∃∀r(C) only when a source object has at least one related object and all related objects belong to the target concept extent.Its incidence condition requires both r(o) ≠ ∅ and r(o) ⊆ Extent(C).
3. Relational Concept Analysis based on AOC-posets
RCA-AOC applies relational scaling to AOC-posets rather than full concept lattices, retaining only concepts that introduce objects or attributes. This reduces the represented structure and supports relational pattern extraction, but changes how iterative construction proceeds.
- AOC-posets: RCA-AOC restricts each concept lattice to concepts introducing at least one object or attribute.The resulting AOC-poset is a suborder of the corresponding concept lattice.
- Scaling operators: Existential scaling adds a relational attribute when an object is related to at least one object in a target concept’s extent.For remedy3, the operator adds attributes for each pointed plant concept containing at least one ingredient in its extent.
- Scaling operators: Strict universal scaling adds a relational attribute only when all related objects belong to the target concept’s extent and the relation is nonempty.Remedy3 receives the attribute for cp_6 but not cp_2 because cp_2 excludes some plants it contains.
- Iterative process: RCA-AOC constructs a sequence in which each next context uses the original context and the preceding step’s AOC-poset concepts.Unlike classical RCA, it does not use the preceding step’s context and full lattice concepts.
- Iterative process: Simple instances may reach a fixpoint, but cycles between objects can cause convergence problems in more complex datasets.A fixpoint is reached when subsequent steps produce no new concepts.
- Output patterns: Patterns derived from AOC-posets are included in corresponding lattice-based patterns, while redundancy removal is more straightforward.The paper states that the resulting patterns should be the same after redundant concepts are removed.
4. Convergence issues in RCA-AOC
RCA-AOC can diverge because relational attributes refer to concepts that may disappear from the next AOC-poset. The paper illustrates this mechanism in existential-scaling examples and a UML refactoring case, where alternating dependencies create infinite loops.
- Convergence: Convergence means reaching a stable solution after finitely many steps, detected when successive concept-posets have equal extent sets.The same criterion applies to RCA lattices and RCA-AOC posets.
- Convergence: Lattice-based RCA guarantees convergence because relational attributes use concepts from the complete lattice at each step.This also allows the final relational attributes to be interpreted using only the final-step lattices.
- Concrete divergence: In RCA-AOC, a concept can disappear while its relational attribute remains relevant to constructing concepts at a later step.In the UML example, cc_17 disappears at step 2 but is used to build cpr_22.
- Concrete divergence: At step 3, cpr_22 disappears because cc_17 is absent from step 2, while cpr_22 had been used to construct cc_23.The resulting configurations alternate indefinitely because equivalent AOC-posets recur across steps.
- Concrete divergence: The UML example shows that alternating AOC-posets can still suggest useful refactorings, including a generalized property and new superclass candidates.The proposed model introduces adminId:String and candidate superclasses FinancialStructure and AdminAsset.
- Divergence mechanism: In another example, two concepts appear alternately because each is created using the other at the previous step, producing an infinite loop.The step sequence repeats equivalently, with step 3 matching step 1 and step 4 matching step 2.
- Divergence mechanism: Inter-dependencies among concepts appearing at different steps can prevent the configurations needed for convergence.The paper identifies such dependencies as the source of divergence in the example.
5. Approaches to Ensuring RCA-AOC Convergence
The paper addresses RCA-AOC’s lost convergence guarantee by identifying sufficient structural conditions, a dataset transformation, and a convergent attribute-keeping variant. The proposed variant preserves AOC-posets and terminates, but sacrifices step-to-step structure inclusion and may create dangling attributes.
- Convergence conditions: Convergence follows when the dependency graph has no circuits, because successor fixpoints can be propagated recursively to predecessor contexts.A context whose successors admit concept-poset fixpoints also admits a fixpoint.
- Convergence conditions: Adding an attribute to a context of identified objects cannot remove concepts from its associated concept-poset.This yields monotonic poset growth when the relevant successors grow monotonically.
- Convergence conditions: Contexts on circuits can still converge when a successor-closed set contains only sinks or contexts of identified objects.Under these conditions, every context in the set grows monotonically and reaches a concept-poset fixpoint.
- Dataset transformation: A dataset transformation ensures convergence by detecting circuits and sinks, then adding identifiers to circuit contexts and their reachable nonsink successors.Contexts outside the transformed region converge when all their successors admit fixpoints.
- Convergent variant: RCA-AOC-conv accumulates relational attributes across steps instead of removing them, guaranteeing convergence while retaining the AOC-poset structure.When concepts disappear, attributes built on them remain as dangling attributes with incidence fixed at creation.
- Convergent variant: The attribute-keeping variant may lose step-to-step structure inclusion and produce attributes referring to concepts absent from final concept-posets.Keeping disappearing concepts would avoid dangling attributes but could expand the structure toward the full lattice and would not generally preserve AOC-posets.
6. Related work
Related work positions AOC-posets as compact FCA structures used across reasoning, linguistic classification, and software engineering. RCA extends FCA to relational conceptual modeling and has been applied to UML analysis, design-defect detection, and model transformation.
- AOC-posets: AOC-posets originated as pruned lattices for software engineering and retain concepts introducing objects or attributes rather than the full lattice.Subsequent work developed algorithms and tools for constructing AOC-posets.
- AOC-posets: AOC-posets have supported non-monotonic reasoning, domain theory, linguistic classification, class-hierarchy refactoring, and feature-tree extraction.Several software-engineering applications specifically use the attribute-concept component.
- RCA foundations: RCA originated from knowledge-representation problems in software engineering, databases, and ontology-based settings, including the discovery of concepts latent in conceptual models.Its formalizations compute linked concept lattices iteratively from relational data using multiple scaling operators.
- RCA variants: RCA variants add navigation control over dataset structure, scaling operators, and conceptual structures, with these features implemented in RCAexplore.More recent work also uses LLM-based approaches to support interpretation of RCA results.
- RCA applications: RCA has been applied to UML and use-case analysis, design-defect detection, and learning model transformations from examples.These applications exploit relations among model elements, methods, attributes, and transformations.
7. Conclusion
The paper examines convergence when RCA uses AOC-posets instead of concept lattices, identifying divergence mechanisms and proposing a convergent variant. RCA-AOC-conv guarantees convergence by retaining relational attributes, including attributes referring to concepts absent from the final structures.
- 7. Conclusion: AOC-posets compact RCA representations but generally lose the convergence guarantee of lattice-based RCA.The paper also notes that introducer concepts may be sufficient for some applications.
- 7. Conclusion: Three divergence examples involve existential and strict universal scaling, including a UML class-model refactoring task.
- 7. Conclusion: The paper identifies data and process properties that prevent divergence and discusses conditions for recovering convergence.
- 7. Conclusion: RCA-AOC-conv converges by never removing relational attributes, though some may refer to concepts absent from the final structures.
- 7. Conclusion: Future work targets practical divergence detection and automatic repair of problematic datasets.
A. Proof of Lemma 4
The proof analyzes how adding an attribute changes an AOC-poset by classifying concepts according to their extents and simplified intents. In contexts of identified objects, concept removal cannot occur, so the AOC-poset can only grow.
- A. Proof of Lemma 4: Adding an attribute creates an attribute-concept whose extent is the set g of objects owning that attribute.This concept belongs to the new AOC-poset because its simplified intent contains the added attribute.
- A. Proof of Lemma 4: Concepts with non-empty simplified intents retain equivalent concepts after attribute addition, while some may gain the new attribute.
- A. Proof of Lemma 4: Only cases 3c and 4c can remove a concept; all other cases preserve an equivalent concept or add a new one.
- A. Proof of Lemma 4: In contexts of identified objects, cases 3c and 4c are impossible because object-concepts have singleton extents.Adding one attribute preserves the identified-objects property.
- A. Proof of Lemma 4: Therefore, adding an attribute cannot remove an AOC-poset concept in a context of identified objects, and the poset can only grow.
B. Algorithm RCA-AOC-conv
RCA-AOC-conv iteratively extends contexts and recomputes concept-posets while retaining previously created relational attributes. This prevents the oscillation seen in RCA-AOC and eventually reaches equivalent successive posets.
- B. Algorithm RCA-AOC-conv: Algorithm 1 takes a relational context family and scaling function, and returns a family of concept-posets.
- B. Algorithm RCA-AOC-conv: The process stops when every extended context is unchanged between consecutive steps.
- B. Algorithm RCA-AOC-conv: Convergence follows because relational attributes are never duplicated or removed, making the increasing sequence of extended contexts stationary.Attributes referring to removed concepts are retained as dangling attributes.
- B. Algorithm RCA-AOC-conv: The implementation incrementally generates attributes for newly created concepts and recomputes object-concepts for objects owning new attributes.
- B. Algorithm RCA-AOC-conv: In the example, RCA-AOC-conv resolves mutual dependency by adding attributes to existing concepts, whereas RCA-AOC loops with period two.The convergent process stops at step 5; the ordinary process alternates between structures at steps 3–6.
- B. Algorithm RCA-AOC-conv: Skipping object-concept recomputation would still converge but would not create C_K1_10.