CS Paper Radar

Convergence issues in Relational Concept Analysis based on AOC-posets

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

cs.LG cs.AI ·submitted 2026-08-30 10:09 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Formal Concept Analysis with Three Types of Negation

cs.AI ·2026-08-29 ·Zhenghua Pan
unusual similarity 0.60
Abstract · 30 pages, 9 figures, 8 table, 25 conferences

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).

0.36

DIADA: Automatic Data Composition in Data Lakes

cs.DB ·2026-10-01 ·Marc Maynou, Albert Martin, Sergi Nadal, Anna Queralt, Oscar Romero
similarity 0.57
Abstract

Data lakes contain a plethora of attributes scattered across many tables that, when combined, provide enhanced assets for data analysis. Nonetheless, deciding which attributes belong together in meaningful relations remains a manual, per-task effort. Merging by joinability alone provides no guarantees regarding attribute relevance, while selecting features against a single target discards attributes useful to other tasks. To address this gap, we introduce the data composition problem: organizing a fragmented, heterogeneous lake into meaningful relations, agnostic of any particular analytical task so that the resulting organization can serve as a common foundation for diverse downstream analyses. We propose DIADA, a composition system that employs multivariate dependence as the criterion for assessing the meaningfulness of a relation and approximates it by hypothesizing independence among attributes and identifying those sets that violate this hypothesis. To do so, we map the attributes to a predicate space, forming a lattice under inclusion and mining those predicate sets that exhibit dependence among their constituents. We contribute a dedicated and scalable algorithm to effectively explore this space, outscaling classical algorithms for mining relationships, thus discovering dependencies that would otherwise be impractical to identify. We demonstrate that applying a single data composition process benefits diverse potential downstream tasks. This is the result of providing a subset of low-noise, statistically relevant attributes that increases the confidence that detected patterns are grounded in real relationships, thus preventing common modeling issues in large-scale environments.

0.29

Towards a universal language of concepts: A survey

cs.AI cs.PLcs.SC ·2026-09-03 ·Aishni Parab
survey similarity 0.54
Abstract · Originally completed as an M.S. capstone project at UCLA in 2022

Humans can learn and generalize novel concepts from sparse data because they express knowledge in rich structural formats. In this paper, we propose that programs are a strong candidate for universal representation of concepts. We review computational models of concept learning that use programs as their concept representation and evaluate their contribution toward a universal representational language.

0.23

An Analysis of Decision Problems for Relational Pattern Languages under Various Constraints

cs.FL cs.CC ·2026-10-05 ·Klaus Jansen, Dirk Nowotka, Lis Pirotton, Corinna Wambsganz, Max Wiedenhöft
publishedunusual similarity 0.53
Abstract · In Proceedings AFL 2026, arXiv:2608.23071. A full version of this paper, containing all proofs, can be found at arXiv:2512.07476

Patterns are words with terminals and variables. The language of a pattern is the set of words obtained by uniformly substituting all variables with words that contain only terminals. In their original definition, patterns only allow for multiple distinct occurrences of some variables to be related by the equality relation, represented by using the same variable multiple times. In an extended notion, called relational patterns and relational pattern languages, variables may be related by arbitrary other relations, achieved by using regular patterns and relating individual variables independently from the patterns structure separately. We extend the ongoing investigation of the main decision problems for patterns (namely, the equivalence problem, the inclusion problem, and the membership problem) to relational pattern languages under a wide range of relevant individual relations, providing a comprehensive foundation in all three research directions.

0.61

Arrow Operations in Categories of Lattice-valued Relations

cs.DM math.CT ·2026-08-17 ·Fatemeh Jowkar, Michael Winter
similarity 0.52
Abstract

Arrow allegories provide a convenient abstract framework to work with lattice-valued relations, or more precisely, relations that use the elements of a given Heyting algebra as truth values. One characteristic of arrow allegories is that all relations of the given arrow allegory use the same Heyting algebra ${\mathcal H}$. In this paper we want to extend this approach to allegories where relations between different objects may use different lattices of truth values and even further to relations that use a different lattice of truth values for every pair in the relation. Therefore, we define three concrete allegories, $\mathrm{Rel}({\mathcal H})$, $\mathrm{Rel}^u({\mathcal H})$ and ${\mathcal H}{\rm-Rel}$, where the allegory listed later is a full suballegory of the previous ones. These three allegories capture the three different situations mentioned above. In particular, ${\mathcal H}{\rm-Rel}$ is the standard example of an arrow category. We investigate these allegories and provide suitable categorical definitions for these structures.

0.23

ConceptARC at Scale: Studying Conceptual Understanding in Reasoning Models

cs.AI cs.LG ·2026-11-04 ·Philipp Mondorf, Adrien Deliège, Solim LeGris, Claas Beger, Ryan Yi +3 more
benchmarkdataset similarity 0.52
Abstract · 23 pages, 14 figures

Large reasoning models (LRMs) perform well on challenging benchmarks, yet it remains unclear whether they form generalizable abstractions across conceptually related reasoning tasks. The Abstraction and Reasoning Corpus (ARC) provides a controlled testbed for studying abstraction, requiring solvers to infer transformation rules over two-dimensional grids from a small set of examples. While ARC evaluates rule abstraction within individual tasks, different tasks may share higher-level structure despite requiring different transformations$\unicode{x2014}$for example, several tasks may involve reasoning about objects contained within other objects. Benchmarks such as ConceptARC capture this structure by grouping ARC-style tasks into recurring spatial and semantic concepts, but they often contain only a few manually constructed tasks per concept. We introduce ConceptARC at Scale, a generator for creating thousands of ARC-style tasks targeting a specific concept. Using this generator, we construct ConceptARC-100, a dataset of 1,600 new, manually reviewed tasks, with 100 tasks for each of the 16 concepts defined by ConceptARC$\unicode{x2014}$ten times the size of the original benchmark. We evaluate a range of recent LRMs and models trained from scratch on ConceptARC-100 to characterize which concepts they solve reliably and where they struggle. We further analyze the models' internal representations and find clear semantic structure: task representations cluster according to the operations applied to objects, such as recoloring, removal, or translation, even when realized through substantially different rules and scenarios. Together, our results suggest that models form stable abstractions of transformation operations that generalize across diverse tasks.

0.10

SPARROW: Scalable Taxonomy Induction via Structure-Preserving Partitioning and Constraint-Guided Merging

cs.CL ·2026-09-07 ·Yirui Zhang, Yixuan Tang, Yandong Sun, Mong-Li Lee, Anthony Kum Hoe Tung
top venuepositioncode/data similarity 0.51
Abstract · Accepted to EMNLP 2026 Main

Taxonomy induction aims to organize concept sets into coherent hierarchical structures. Recent LLM-based methods can induce taxonomies directly from flat term lists, avoiding the need for corpora, but degrade sharply as concept sets scale up. We argue that this degradation stems not only from context length limitations, but also from structural failures in hierarchical reasoning. To address this, we adopt a divide-and-merge paradigm that partitions concepts into smaller subsets, induces local taxonomies, and merges them into a global hierarchy. However, we identify two structural failure modes inherent to this paradigm: Structural Fragmentation, where partitioning weakens local hierarchical signals, and Parent Displacement, where locally plausible relations are misplaced in the global hierarchy. To address both, we propose SPARROW, a scalable taxonomy induction framework that combines structure-preserving spectral partitioning to retain hierarchical connectivity within each block, and constraint-guided incremental fusion that treats block-level relations as structural constraints rather than ground truth for global placement. Experiments on large-scale benchmarks show that SPARROW consistently achieves the strongest global structural quality across backbones. The code is available at https://github.com/rebeccazyr/SPARROW.

0.46

Merging and Evolution of Data Bases: A Many-Logic Approach

cs.LO cs.DB ·2026-10-29 ·Manuel A. Martins, Abilio Rodrigues
published similarity 0.51
Abstract · In Proceedings NCL'26, arXiv:2610.34489

A new approach to information-based logics using many-logic modal structures (MLMSs) was recently proposed by Martins et al. In such a setting, it is possible to have worlds with different underlying logics within the same frame, all anchored to a base lattice that contains the semantics of each logic as a down-complete sublattice. In this paper, we take the lattice L6, defined by the six-valued semantics of the logic of evidence and truth LET + K , as our base lattice. We also consider four-, three-, and two-valued formal systems associated with down-complete sublattices of L6. These logics are capable of representing paracomplete, paraconsistent, and classical contexts with six, four, three, and two informational scenarios, respectively. As applications of MLMSs, we will discuss the merging and temporal evolution of databases whose underlying logics are two-, three-, four-, and six-valued. We will also investigate inconsistency measures in this context.

0.47