  With the increased use of machine learning systems for decision making,
questions about the fairness properties of such systems start to take center
stage. Most existing work on algorithmic fairness assume complete observation
of features at prediction time, as is the case for popular notions like
statistical parity and equal opportunity. However, this is not sufficient for
models that can make predictions with partial observation as we could miss
patterns of bias and incorrectly certify a model to be fair. To address this, a
recently introduced notion of fairness asks whether the model exhibits any
discrimination pattern, in which an individual characterized by (partial)
feature observations, receives vastly different decisions merely by disclosing
one or more sensitive attributes such as gender and race. By explicitly
accounting for partial observations, this provides a much more fine-grained
notion of fairness.
  In this paper, we propose an algorithm to search for discrimination patterns
in a general class of probabilistic models, namely probabilistic circuits.
Previously, such algorithms were limited to naive Bayes classifiers which make
strong independence assumptions; by contrast, probabilistic circuits provide a
unifying framework for a wide range of tractable probabilistic models and can
even be compiled from certain classes of Bayesian networks and probabilistic
programs, making our method much more broadly applicable. Furthermore, for an
unfair model, it may be useful to quickly find discrimination patterns and
distill them for better interpretability. As such, we also propose a
sampling-based approach to more efficiently mine discrimination patterns, and
introduce new classes of patterns such as minimal, maximal, and Pareto optimal
patterns that can effectively summarize exponentially many discrimination
patterns
