[ CogSci Summaries home | UP | email ]

Falkenhainer, B., K. D. Forbus, D. Gentner (1990). The Structure mapping engine: algorithm and examples. Artificial Intelligence (41) pp1-63.

  author =       "Brian Falkenhainer and Kenneth D. Forbus and Dedre
  title =        "The Structure-Mapping Engine: Algorithm and Examples",
  journal =      "Artificial Intelligence",
  volume =       "41",
  pages =        "1--63",
  year =         "1990",

Author of the summary: Jim Davies, 1999, jim@jimdavies.org

Cite this paper for:

note: page numbers are taken from a preprint version of this paper, not the one published in AI. Sorry!


Analogy is bringing knowledge of previous experiences to bear on new situations. Defined this broadly, analogy is a fundamental cognitive process and is of great interest to cognitive scientists.

How does analogy work? Does all analogy use the same functions? How do you determine the quality of an analogue? How many ways can you sensible find analogies between two things?


This paper describes the Structure-Mapping Engine (SME) which is based on Gentner's Structure-Mapping Theory of analogy. The theory has been well supported by human subject experiments. The SME works out many computational details of the theory and makes some predictions of its own.

Structure-Mapping Theory

The order of a representation: objects are order 0. The order of a predicate is 1 plus the maximum order of its arguments. This conception of order tells how deep the structure is below an item. How is the mapping made? Isolated object descriptions are discarded such as red(wagon), which means the wagon is red. Relations between objects are mapped. High level mappings occur with a systematicity bias, which means that high order relational similarities are preferred. Systematicity has been empirically validated with empirical studies.

Kinds of similarity:(these correspond to the different sets of match rules typically used in SME.)

Structure-mapping has three stages:
  1. access: retrieval of a similar analogue.
  2. mapping: finding the right coorespondences. Produces a set of candidate inferences. Match rules determine how this is done.
  3. evaluation and use: determining the quality of the match.
SME models the mapping stage.

The Structure-Mapping Engine

SME constructs all possible mappings (each is called a global mapping or Gmap), each with a score for finding the best mapping each with candidate inferences. A Gmap is any consistent set of match hypotheses formed between the target and base Dgroup.

The knowledge is represented with the following constructs:

One of the match rules for literal similarity is: "If the match hypothesis concerns two facts, then create a match hypothesis between any corresponding arguments that are both functions or entities."

With the exception of functions, predicates must match identically.

For two facts to match, all of their descendants must match perfectly (for the literal similarity case). The structural evaluation score is based on the rules and also uses a belief maintainance system that takes weights of mappings into consideration. The evidence for a Gmap is the sum of the evidence for its match hypotheses. (p22) No normalization is done, because normalizing doing so prevents one from comparing Gmaps with different base domains. You still cannot usefully compare Gmaps with different bases and different targets.

An Emap is a map between primitive entities.

Algorithm complexity

local match construction: O(Nb * Nt) in theory, O(N) in practice

conflict calculation: between O(N) and O(N^2)

Emaps and NoGood set: O(# match rules)

Gmap merge: O(# partial matches)

finding candidate inferences: O(N^3)

score computation: O(# match rules)


SME has been applied to the solar-system/atom analogy, heat flow/water flow (in which temperature and diameter are suggested to be analogous an a candidate inference), and analogy of stories.

some hypotheses of SME: That symantic relational overlap determines the inferential soundness of the match and that the surface similarity determines the accessability. Psychological studies supported both. (p32)


A story was the base of the analogy. Two stories were potential analogues: one with different content but with the same structure, and one with the same content (names of things, etc) but with the same structure. It was predicted that the analogical match rules would prefer the deep analogue and the mere similarity rules would prefer the surface story.


The hypotheses were supported. These results also match with human subject data, which show a difference in these stories with respect to accessability and evaluation of match soundness. (p34).

Comparisons with other work

Holyoak's analogy theory makes a match based on the goal of a problem solver. The limitations are that it has no notion of soundness, so the search space explodes. Also, a system should be able to use analogy for more than problem solving.

Winston's matcher does a heuristic search for a single best match. SME produces fewer entity pairings.

Kline's RELAX system focuses on matching relations rather than entities. This program is able to match items with very different syntax, but does not prune the search very well.

Some inductive generalization programs address the partial matching problem. It may appear that many to one mappings are necessary, but the SME view is that though this may happen in artistic methphor, it does not happen with explanatory, predictive analogies. Multiple mappings may sometimes be useful, we suggest multiple analogies between the same base and target.

main claims and contributions of paper

SME is flexible and efficient enough to be of interest to AI as well as for cognitive modelers.

SME has been applied to over 40 examples of analogy. It posits there are 3 distinct ways to map. These may (in part) coorespond to developmental changes in analogical strategy. Different kinds of analogy can be reproduced with these methods.

scope of work and limitations

SME should be looked at as one module of a larger cognitive framework. What SME does is it takes two concepts and finds the best analogy between them. It makes no claims about retrieval of good concepts (though the related project MAC/FAC does) or what to do with the analogy created (though the larger system PHINEAS does). Key to understanding what SME does and does not do relies on the understanding that given two concepts one can make multiple mappings between them. There are many ways to make an analogy between a river and time, for example, and SME choose among them.

One limitation I see is that in spite of the empirical evidence for structure mapping, the theory doesn't fit at all with spreading activation theories (and experiments?) of memory. Since what the objects actually are does not affect analogy (except in mere appearance matching), where do the robust priming effects we can see come from? Why are they seperate?

Related Information

Gentner, D. (1983). Structure-mapping: A theoretical framework for analogy. Cognitive Science, 7, pp 155-170.

Forbus, K. D., Ferguson, R. W., & Gentner, D. (1994). Incremental Structure Mapping. Proceedings of the Sixteenth Annual Conference of the Cognitive Science Society.

Ferguson, R. W., and K.D. Forbus. Understanding illustrations of physical laws by integrating differences in visual and textual representations.

AAAI Fall Symposium on Computational Models for Integrating Language and Vision. 1995.

http://www.qrg.ils.nwu.edu/ideas/smeidea.htm A webpage on structure mapping.

Summary author's notes:

Back to the Cognitive Science Summaries homepage
Cognitive Science Summaries Webmaster:
JimDavies (jim@jimdavies.org)
Last modified: Thu Apr 29 12:41:46 EDT 1999