A native CbO algorithm for computing the mixed concept lattice

This idea proposes a new ‘native’ CbO-style algorithm (Mixed-InClose) for computing mixed concept lattices. It operates directly on contexts with positive and negative attributes, using logical pruning to be more efficient than attribute-doubling or projection-based methods.

Keywords

Mixed concept lattice, Native algorithm, InClose, Positive-negative attributes, Simplification logic, Performance, fcaR

Contexts with positive and negative attributes (mixed contexts) provide a richer modeling framework than classical FCA but introduce computational challenges. The standard method for computing the mixed concept lattice involves creating an appended context with twice the number of attributes, which is inefficient. While decomposition methods based on projections exist, a direct, “native” algorithm for mixed lattice construction is still lacking. This paper fills this gap by extending the Close-by-One (CbO) strategy to the mixed attribute setting. We develop a native InClose algorithm that operates directly on the mixed context, incorporating logical constraints (e.g., m \wedge \bar{m} is a contradiction) into the pruning and canonicity testing phases. We prove the correctness of our algorithm and show empirically that it significantly outperforms both the attribute-doubling and the projection-based decomposition approaches.

Introduction

Real-world knowledge often involves not just the presence of properties but also their explicit absence. FCA with mixed attributes captures this by considering both positive (m) and negative (\bar{m}) information. The standard approach to compute the mixed concept lattice, \mathfrak{B}^{\#}(\mathbb{K}), is to construct the lattice of the appended context \mathbb{K} | \bar{\mathbb{K}}, which doubles the attribute set and is computationally expensive.

An alternative, proposed in our prior work , is to compute the positive and negative lattices (\mathfrak{B}(\mathbb{K}) and \mathfrak{B}(\bar{\mathbb{K}})) separately and then combine them. While more efficient than attribute-doubling, this still requires computing two lattices and a complex recombination step. A truly direct, “native” algorithm that builds \mathfrak{B}^{\#}(\mathbb{K}) in one pass is highly desirable.

This paper proposes such an algorithm by adapting the efficient InClose algorithm to the mixed setting. Our contributions are:

1. The first native CbO-style algorithm for computing the mixed concept lattice directly.
2. A novel canonicity test for mixed concepts that leverages logical constraints between positive and negative attributes to enhance pruning.
3. A formal proof of the algorithm’s correctness and an empirical evaluation demonstrating its superiority over existing methods.

Methodology and expected results

The core challenge is to adapt the CbO search tree to handle a vocabulary M \cup \bar{M} while respecting the underlying logic.

Theoretical foundation: Pruning with simplification logic

The search will traverse a tree where branches are labeled with attributes from M \cup \bar{M}. The key innovation is to use rules from Simplification Logic for Mixed Attributes to prune the search. For example, if the current closure in the search already contains an attribute m, then any branch corresponding to its negation \bar{m} can be immediately pruned, as it leads to a contradiction (the bottom concept).

Algorithmic design: Mixed-InClose

We will adapt the InClose algorithm as follows: * Search space: The algorithm will iterate over an ordered list of all mixed attributes M \cup \bar{M}. * Mixed closure operator: It will use the native mixed closure operator (\cdot)^{\Uparrow\Downarrow} incrementally. * Enhanced canonicity test: The test for a new concept generated from attribute y will not only check the standard CbO condition but also verify that it is not logically redundant due to the presence of y’s negation in the closure.

Expected results

The main expected result is a significant performance improvement. By avoiding the attribute doubling of the standard method, we halve the width of the search space at the top level. By incorporating logical pruning, we expect to cut down the search tree depth and breadth much more effectively than running a standard algorithm on the appended context. We will prove that Mixed-InClose is correct and complete, i.e., it finds all and only the mixed formal concepts.

Work plan

• Weeks 1-4: Formalize the Mixed-InClose algorithm and the enhanced canonicity test. Prove its correctness.
• Weeks 5-7: Implement the algorithm, likely as a new major feature in the `fcaR` library. This will involve close collaboration with Prof. Simon Andrews.
• Weeks 8-10: Benchmark Mixed-InClose against (1) the attribute-doubling method and (2) the projection-recombination method.
• Weeks 11-12: Write the manuscript, highlighting the novelty and efficiency of the native approach.

Potential target journals

1. Information Sciences (Q1): A perfect venue for a novel algorithm with strong performance improvements in knowledge representation.
2. Fundamenta Informaticae (Q2): A good choice that values formal methods and correctness proofs in computer science.
3. ICFCA Conference (CORE B): An excellent place to present the algorithm to the core community and get feedback.

Minimum viable article (MVA) strategy

This topic can be published as a strong single paper, but a split is possible to maximize output by separating the binary mixed case from the more complex unknown/partial information case.

• Paper 1 (The MVA - the mixed binary case):
  • Scope: This paper introduces the Mixed-InClose algorithm exactly as described above, for contexts with only positive and negative attributes. It provides the correctness proof and a solid empirical comparison against the two existing methods.
  • Goal: To establish the first native CbO algorithm for mixed contexts as the new state-of-the-art.
  • Target venue: A strong conference like IPMU (where the projection method was presented) followed by a journal submission to Information Sciences.
• Paper 2 (The partial/unknown information case):
  • Scope: This paper extends the algorithm to handle contexts with a third value for “unknown” (\circ) or even a fourth for “contradiction” (\imath), as introduced in. This requires a more sophisticated closure operator and canonicity test, making it a significant new contribution. The evaluation would compare this algorithm’s performance on partial data.
  • Goal: To provide a complete and efficient algorithmic solution for the most general case of FCA with incomplete information.
  • Target venue: A high-impact journal like International Journal of Approximate Reasoning or Fuzzy Sets and Systems.