  Binary classification problems can be naturally modeled as bipartite graphs,
where we attempt to classify right nodes based on their left adjacencies. We
consider the case of labeled bipartite graphs in which some labels and edges
are not trustworthy. Our goal is to reduce noise by identifying and fixing
these labels and edges.
  We first propose a geometric technique for generating random graph instances
with untrustworthy labels and analyze the resulting graph properties. We focus
on generating graphs which reflect real-world data, where degree and label
frequencies follow power law distributions.
  We review several algorithms for the problem of detection and correction,
proposing novel extensions and making observations specific to the bipartite
case. These algorithms range from math programming algorithms to discrete
combinatorial algorithms to Bayesian approximation algorithms to machine
learning algorithms.
  We compare the performance of all these algorithms using several metrics and,
based on our observations, identify the relative strengths and weaknesses of
each individual algorithm.
