Homophily is commonly known as the phenomenon whereby “birds of a feather flock together”. A documented but under-appreciated challenge in predicting gender on social networks is the minimal presence of general gender homophily, a critical assumption underlying the success of diffusion-based approaches to gender inference. In this work, we perform a broad study of structural predictors of gender in social networks, contributing a taxonomy of frameworks to categorize and contrast subtly different approaches to gender inference. We show that approaches within these different frameworks achieve dramatically different performance when predicting gender, and provide a novel analysis in terms of the overdispersion of individual homophilic tendencies—identifying individuals we term “gender canaries”—to explain these major deviations between frameworks. These findings provide a new perspective on social network trait inference in general and gender in particular, complicating the already difficult task of protecting anonymity in social networks, and introducing new considerations regarding any study of social network covariates. This is joint work with Kristen M. Altenburger.