  We consider semi-supervised binary classification for applications in which
data points are naturally grouped (e.g., survey responses grouped by state) and
the labeled data is biased (e.g., survey respondents are not representative of
the population). The groups overlap in the feature space and consequently the
input-output patterns are related across the groups. To model the inherent
structure in such data, we assume the partition-projected class-conditional
invariance across groups, defined in terms of the group-agnostic feature space.
We demonstrate that under this assumption, the group carries additional
information about the class, over the group-agnostic features, with provably
improved area under the ROC curve. Further assuming invariance of
partition-projected class-conditional distributions across both labeled and
unlabeled data, we derive a semi-supervised algorithm that explicitly leverages
the structure to learn an optimal, group-aware, probability-calibrated
classifier, despite the bias in the labeled data. Experiments on synthetic and
real data demonstrate the efficacy of our algorithm over suitable baselines and
ablative models, spanning standard supervised and semi-supervised learning
approaches, with and without incorporating the group directly as a feature.
