The assumption that all "random" edges in the top scoring section of the result set are truly false positives is not technically correct. It would be possible that the reason they are scoring highly is because they are indeed missing edges. As a consequence, the improvement over chance determined by the algorithm is thus, technically, a lower boundary on the performance of the algorithm.