We routinely observe others' choices and use them to guide our own. Whose choices influence us more, and why? Prior work has focused on the effect of perceived similarity between two individuals (self and others), such as the degree of overlap in past choices or explicitly recognizable group affiliations. In the real world, however, any dyadic relationship is part of a more complex social structure involving multiple social groups that are not directly observable. Here we suggest that human learners go beyond dyadic similarities in choice behaviors or explicit group memberships; they infer the structure of social influence by grouping individuals (including themselves) based on choices, and they use these groups to decide whose choices to follow. We propose a computational model that formalizes this idea, and we test the model predictions in a series of behavioral experiments. In Experiment 1, we reproduce a well-established finding that people's choices are more likely to be influenced by someone whose past choices are more similar to their own past choices, as predicted by our model as well as dyadic similarity models. In Experiments 2-5, we test a set of unique predictions of our model by looking at cases where the degree of choice overlap between individuals is equated, but their choices indicate a latent group structure. We then apply our model to prior empirical results on infants' understanding of others' preferences, presenting an alternative account of developmental changes. Finally, we discuss how our model relates to classical findings in the social influence literature and the theoretical implications of our model. Taken together, our findings demonstrate that structure learning is a powerful framework for explaining the influence of social information on decision making in a variety of contexts.