If we take gold-standard edges as positive examples, and non-gold-standard edges as negative examples, the goal of the training problem can be viewed as finding a large separating margin between the scores of positive and negative examples.
it is infeasible to generate the full space of negative examples, which is factorial in the size of input.