Is there any matrix completion algorithm which can be used to to reconstruct a graph using only a small number of its edges?
There are many algorithms to recover and complete an unknown matrix which has available only several sampled entries. As far as I know, many of these algorithms work for low rank matrix which is not true about graph adjacency matrix. Like SVT.
Unfortunately many of the natural graph types represented as matrices turn out to be high rank (e.g. trees, cycles and grids). In this sense the problem is not a matrix completion problem as stated e.g. in A SINGULAR VALUE THRESHOLDING ALGORITHM FOR MATRIX COMPLETION from Cai, Candes and Shen.
That means, without the contraint of low rankness, the problem is from the prospective of linear algebra ill posed and cannot be solved.