Social navigation—such as anticipating where gossip may spread, or identifying which acquaintances can help land a job—relies on knowing how people are connected within their larger social communities. Problematically, for most social networks, the space of possible relationships is too vast to observe and memorize. Indeed, people's knowledge of these social relations is well known to be biased and error-prone. Here, we reveal that these biased representations reflect a fundamental computation that abstracts over individual relationships to enable principled inferences about unseen relationships. We propose a theory of network representation that explains how people learn inferential cognitive maps of social relations from direct observation, what kinds of knowledge structures emerge as a consequence, and why it can be beneficial to encode systematic biases into social cognitive maps. Leveraging simulations, laboratory experiments, and “field data” from a real-world network, we find that people abstract observations of direct relations (e.g., friends) into inferences of multistep relations (e.g., friends-of-friends). This multistep abstraction mechanism enables people to discover and represent complex social network structure, affording adaptive inferences across a variety of contexts, including friendship, trust, and advice-giving. Moreover, this multistep abstraction mechanism unifies a variety of otherwise puzzling empirical observations about social behavior. Our proposal generalizes the theory of cognitive maps to the fundamental computational problem of social inference, presenting a powerful framework for understanding the workings of a predictive mind operating within a complex social world.