Learning the meanings of words involves not only forming connections between individual words and concepts but also building a network of connections across objects and words. Previous studies reveal that infants and adults can learn word-referent links across multiple ambiguous training instances by tracking the statistical co-occurrence of labels and objects (Smith & Yu, 2008; Dautriche & Chemla, 2014). We asked whether adults are sensitive to multiple types of statistical structure in these learning instances by manipulating the frequency with which objects co-occurred with each other during training trials. Across several studies (n=150), we find that adults not only learned to disambiguate label referents, but simultaneously formed connections both between the frequently co-occurring objects themselves and between the labels of frequently co-occurring objects. These findings indicate that learners exploit statistical regularities to form multiple types of associations during word learning.