  In this paper, we aim at recovering an undirected weighted graph of $N$
vertices from the knowledge of a perturbed version of the eigenspaces of its
adjacency matrix $W$. For instance, this situation arises for stationary
signals on graphs or for Markov chains observed at random times. Our approach
is based on minimizing a cost function given by the Frobenius norm of the
commutator $\mathsf{A} \mathsf{B}-\mathsf{B} \mathsf{A}$ between symmetric
matrices $\mathsf{A}$ and $\mathsf{B}$.
  In the Erd\H{o}s-R\'enyi model with no self-loops, we show that
identifiability (i.e., the ability to reconstruct $W$ from the knowledge of its
eigenspaces) follows a sharp phase transition on the expected number of edges
with threshold function $N\log N/2$.
  Given an estimation of the eigenspaces based on a $n$-sample, we provide
support selection procedures from theoretical and practical point of views. In
particular, when deleting an edge from the active support, our study unveils
that our test statistic is the order of $\mathcal O(1/n)$ when we overestimate
the true support and lower bounded by a positive constant when the estimated
support is smaller than the true support. This feature leads to a powerful
practical support estimation procedure. Simulated and real life numerical
experiments assert our new methodology.
