Home Page

Papers

Submissions

News

Editorial Board

Announcements

Proceedings

Open Source Software

Search

Statistics

Login

Contact Us



RSS Feed

Reconstructing Undirected Graphs from Eigenspaces

Yohann De Castro, Thibault Espinasse, Paul Rochet; 18(51):1−24, 2017.

Abstract

We aim at recovering the weighted adjacency matrix $\mathsf{W}$ of an undirected graph from a perturbed version of its eigenspaces. This situation arises for instance when working with stationary signals on graphs or Markov chains observed at random times. Our approach relies on minimizing a cost function based on the Frobenius norm of the commutator $\mathsf{A} \mathsf{B}-\mathsf{B} \mathsf{A}$ between symmetric matrices $\mathsf{A}$ and $\mathsf{B}$. We describe a particular framework in which we have access to an estimation of the eigenspaces and provide support selection procedures from theoretical and practical points of view. In the Erdős-Rényi model on $N$ vertices with no self-loops, we show that identifiability (i.e., the ability to reconstruct $\mathsf{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$. Simulated and real life numerical experiments assert our methodology.

[abs][pdf][bib]       
© JMLR 2017. (edit)