Generalization as diffusion: human function learning on graphs

From social networks to public transportation, graph structures are a ubiquitous feature of life. Yet little is known about how humans learn functions on graphs, where relationships are defined by the connectivity structure. We adapt a Bayesian framework for function learning to graph structures, and propose that people perform generalization by diffusing observed function values across the graph. We test the predictions of this model by asking participants to make predictions about passenger volume in a virtual subway network. The model captures both generalization and confidence judgments, and is a quantitatively superior account relative to several heuristic models. Our work suggests that people exploit graph structure to make generalizations about functions in complex discrete spaces.