Fast analogy engine improves aligning complex relational structures
SMTB: Fast Structure-Mapping with Tight Bounds
Artificial Intelligence
Summary
Comparing complex systems based on their structure rather than surface details is hard and often slow. The authors developed a method called SMTB that finds these structural similarities up to 15 times faster and works better with complicated nested structures than the previous standard. Unlike the older method, SMTB doesn’t focus only on certain types of relationships, making it more flexible for different kinds of data. This new approach helps avoid errors that older methods might make in tricky situations. The authors tested SMTB on thousands of examples and showed its advantages clearly.
What this means in practice
- •For cognitive system developers: Build faster analogy-based reasoning features that work well on complex and nested data representations.
- •For knowledge graph engineers: Improve matching of large relational graphs for tasks like data integration and semantic alignment.
Authors
Daniel Weitekamp, Christopher MacLellan
Abstract
Structure-mapping forms analogies by aligning systems of relationally connected elements based on shared structure instead of surface features. We introduce a new structure-mapping algorithm: Structure-Mapping with Tight Bounds (SMTB) that is 5--15x faster than the structure-mapping engine (SME) and about 50\% better at finding mappings in large nested domains. SMTB is part of the broader Cognitive Rule Engine (CRE) project, a flexible multi-language-compatible framework with an accessible Python interface to state-of-the-art C++ implementations of core algorithms commonly used in cognitive systems such as pattern matching, planning, and structure-mapping. CRE and SMTB are designed to work with a wide range of representation choices. Unlike SME, which biases higher-order correspondences in tree-like predicate logic, SMTB maximizes relational connectivity without privileging higher-order relations. This allows SMTB to work just as well over arbitrary relational graphs as it does in tree-like domains of nested predicate logic. We discuss situations where privileging "higher-orderness" in structure-mapping can cause issues, and illustrate how SMTB avoids failure modes that SME would encounter in these situations. We also provide an evaluation comparing SMTB to SME v4 over 5845 domain pairs from the SME corpus.