A logic-based framework for characterizing nexus of similarity within knowledge bases

Similarities play a pivotal role in diverse real-world scenarios, driving extensive research into methodologies for measuring entity similarity and expanding sets of entities with similar ones. Machines are nowadays adept at performing these tasks by taking in some regard relevant interconnected properties shared by entities, which we term nexus of similarity. To the best of our knowledge, however, there lacks a general logic-based framework for ‘characterizing’ nexus of similarity between (tuples of) entities within a given relational knowledge base represented via some arbitrary formalism. Essentially, there is no way to formally express such nexus in a comprehensive and concise manner, making them understandable to both machines and humans. Moreover, the classical notion of expanding a set of entities overlooks the inherent human tendency to naturally generalize entities in a taxonomic way. In light of what was discussed above, we introduce the novel notion of selective knowledge base, denoted by S=(K,ς), designed to enhance any pre-existing relational knowledge base K with a summary selector ς. For any tuple τ of entities, ς selects a relevant portion of the knowledge entailed by K that describes τ. Subsequently, we design a nexus explanation language, called NCF, with an associated semantics. This allows us to delve into the task of explaining and characterizing the nexus of similarity among (tuples of) entities within a selective knowledge base. Then, we introduce the notions of explanation, characterization, canonical characterization, and core characterization, demonstrating that they always exist and are computable. Furthermore, we introduce the notions of essential expansion and expansion graph, formally generalizing the classical notion of linear expansions by showcasing that expansions are naturally taxonomic. We also study key reasoning tasks related to the computation of characterizations and expansions, and analyze their tractability under various computational assumptions. Finally, we contextualize our framework within the existing literature by exploring related technical problems, analyze our design choices in a critical way, and investigate the adaptability and effectiveness of our approach in real-world scenarios.