The Structure-Mapping Engine

Brian Falkenhainer, Kenneth D. Forbus, Dedre GentnerAAAI 1986

Abstract

The Structure-Mapping Engine (SME) is a landmark cognitive simulation program that models how humans perform analogical reasoning. Developed to implement Dedre Gentner's Structure-Mapping Theory, SME treats analogy as a purely structural alignment of relational networks rather than a search for surface-level similarities. By utilizing syntactic rules to identify deep, systematic correspondences between disparate domains—such as water flow and heat flow—SME demonstrates that meaningful comparisons can be generated efficiently without extensive domain-specific pragmatic knowledge. This paper summarizes the engine's architecture, its application to physical system analogies, and its implications for cognitive science.

Introduction

Analogy is a cornerstone of human cognition, yet modeling it in AI has historically been difficult. Early attempts often fell into two traps: they were either computationally expensive, requiring massive backtracking, or they relied too heavily on "pragmatics"—specific domain knowledge about the goals of the analogy.

The authors sought to bridge the gap between psychological theory and computational implementation. They wanted to test Structure-Mapping Theory, which posits that analogy is about mapping the relations between objects (e.g., "A causes B") rather than the attributes of the objects themselves (e.g., "A is red"). The challenge was to build a flexible, efficient "tool kit" that could simulate this human-like processing without needing to "understand" the meaning of the domains it was comparing.

The Structure-Mapping Engine

The authors introduced the Structure-Mapping Engine (SME), which operates in three distinct stages:

  1. Local Match Construction: The system looks at two descriptions (the "base" and the "target") and creates "match hypotheses" for every pair of predicates or entities that could match based on their roles.
  2. Global Match Construction (Gmaps): SME aggregates these local hypotheses into "Gmaps"—maximal, consistent sets of pairings. It uses a clever "upward propagation" technique to ensure that if a relation is matched, its arguments are also matched consistently, avoiding the need for expensive search-tree backtracking.
  3. Syntactic Evaluation: Each Gmap is scored using a "systematicity" metric. SME prefers mappings that involve higher-order relations (like CAUSE or IMPLIES) because they indicate a deeply connected system of knowledge rather than a collection of isolated facts. This scoring is handled via a simplified version of the Dempster-Shafer formalism for evidence combination.
Structural representation of the water flow domain used by SME.

Case Study: Water Flow and Heat Flow

The paper uses description groups—formalized representations of physical systems written in predicate calculus—to test the engine. A primary example is the comparison between water flow and heat flow.

Physical systems for the water flow (left) and heat flow (right) analogy.

In this example, SME correctly identified that PRESSURE in the water domain corresponds to TEMPERATURE in the heat domain. It correctly generated "candidate inferences" (predictions) about heat flow based on its knowledge of water, despite the physical differences between a vial of water and an ice cube. The system found that "water" maps to "heat" not because they are similar substances, but because they play the same role in the flow equation.

Key Insights and Results

  • The Systematicity Principle: SME looks for deep matches. A mapping that includes a "cause-and-effect" chain is weighted much more heavily than one that just matches object colors.
  • Syntactic Sufficiency: Perhaps the most controversial insight is that you don't need to know the purpose of an analogy to find the best structural match. SME produces "intuitively plausible" analogies using only the structure of the data.
  • Efficiency: The algorithm is remarkably fast for its era. It completed the complex water-to-heat flow match in just 0.7 seconds on a Symbolics 3640 Lisp machine.
  • Flexibility: By changing the "match rules," the authors could simulate different types of comparisons, such as "mere-appearance" matches (which children often prefer) versus "true analogies" (preferred by adults).

Limitations and Future Work

The 1986 version of SME had limitations, such as struggling with commutative predicates (like SUM(A, B)) and an inability to "invent" new entities in the target domain to fill gaps. Future work aimed to investigate the "developmental shift" in children—why they initially focus on surface features before moving to relational structures—and whether this is an algorithmic change or a result of acquiring more higher-order knowledge.

Summary updated

BibTeX
@inproceedings{falkenhainer1986structure,
  author = {Brian Falkenhainer and Kenneth D. Forbus and Dedre Gentner},
  title = {{The Structure-Mapping Engine}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1986},
}
Figure