Computing the complete lattice of bonds via a close-by-one strategy

This paper fills a major algorithmic gap in FCA by proposing ‘Bond-CbO’, the first algorithm to compute the complete lattice of bonds. We adapt the Close-by-One strategy by defining the necessary theoretical building blocks, such as ‘maximal bonds’ and a bond infimum operator. This provides the first practical method for exploring the entire space of inter-contextual relationships.

Keywords

Lattice of bonds, Close-by-One, CbO, Bond-CbO, Maximal bonds, Infimum, Algorithmic gap

The set of all formal bonds between two contexts forms a complete lattice, yet no algorithm exists to compute this structure in its entirety. This paper fills this significant algorithmic gap by adapting the Close-by-One (CbO) strategy for this purpose. We first formalize the necessary building blocks for a CbO approach: (1) the definition of “maximal” or $\vee$-irreducible bonds, which will serve as the generators of the structure, and (2) a definition for an infimum operation ($\wedge$) on bonds that aligns with the lattice’s meet operator. We then present Bond-CbO, a novel algorithm that uses these components to construct the full lattice of bonds. This work provides the first practical method for exploring the entire space of conceptual relationships between two contexts, opening new possibilities for complex recommender systems and inter-contextual analysis.

Introduction

It is known that the set of all $L$-bonds between two contexts forms a complete lattice. This is a deep structural result, but it has remained purely theoretical. Current methods focus on constructing specific bonds (e.g., rigorous or benevolent) but provide no means to compute the entire space of possible relationships.

The Close-by-One (CbO) algorithm is a powerful strategy for building concept lattices by iteratively generating concepts from a set of join-irreducible elements. We propose to port this entire strategy to the domain of bonds.

To do so, we must solve two foundational problems:

1. What is the bond-analogue of a join-irreducible concept? We call these “maximal bonds.”
2. What is the bond-analogue of the set-theoretic intersection of intents? We need a meet operator for bonds.

This paper provides the solution to both and presents the resulting Bond-CbO algorithm.

Methodology and expected theoretical results

The methodology is a direct analogy to the development of CbO for concept lattices.

Theoretical foundation

• Maximal bonds: We will formally define a “maximal bond” and prove that every bond in the lattice can be expressed as a join of these maximal bonds. They will be the fundamental building blocks our algorithm generates.
• Infimum of bonds: We will define an operator $\wedge$ on two bonds, $\mathbb{B}_1$ and $\mathbb{B}_2$, and prove that $\mathbb{B}_1 \wedge \mathbb{B}_2$ is their greatest lower bound in the lattice of bonds. This is crucial for the CbO canonicity test.

The Bond-CbO algorithm

The algorithm will be a direct adaptation of FastCbO or InClose: 1. Compute the set of all maximal bonds. 2. Build a search tree where nodes are bonds (represented by their context matrix). 3. A child bond is generated from a parent by adding a maximal bond. 4. A canonicity test, using the $\wedge$ operator, ensures that each bond is generated only once.

Work plan

• Months 1-5: Intense theoretical work with Samuel Molina Ruiz to define and prove the properties of maximal bonds and the bond infimum operator.
• Months 6-8: Design and implement the Bond-CbO algorithm.
• Months 9-11: Test the algorithm on small-to-medium contexts to verify correctness and analyze its performance characteristics.
• Month 12: Write the manuscript.

Potential target journals

1. Discrete Applied Mathematics (Q1): An ideal venue for a paper introducing a novel, non-trivial algorithm based on lattice-theoretic principles.
2. Information Sciences (Q1): A strong candidate if the paper also includes a compelling application or use-case for having the entire lattice of bonds.

MVA strategy

• Paper 1 (The MVA):
  • Scope: The complete paper as described. The novelty is immense: the first algorithm to compute a structure that was previously only known to exist theoretically.
  • Goal: To provide a fundamental new algorithmic capability to the FCA community.
  • Target venue: Discrete Applied Mathematics.