Learning Graphs from Linear Measurements: Fundamental Trade-offs and Applications
share
We consider a specific graph learning task: reconstructing a symmetric matrix that represents an underlying graph using linear measurements. We study fundamental trade-offs between the number of measurements (sample complexity), the complexity of the graph class, and the probability of error by first deriving a necessary condition (fundamental limit) on the number of measurements. Then, by considering a two-stage recovery scheme, we give a sufficient condition for recovery. Furthermore, assuming the measurements are Gaussian IID, we prove upper and lower bounds on the (worst-case) sample complexity. In the special cases of the uniform distribution on trees with n nodes and the Erdos-Renyi (n,p) class, the fundamental trade-offs are tight up to multiplicative factors. Applying the Kirchhoff's matrix tree theorem, our results are extended to the scenario when part of the topology information is known a priori. In addition, we design and implement a polynomial-time (in n) algorithm based on the two-stage recovery scheme. Simulations for several canonical graph classes and IEEE power system test cases demonstrate the effectiveness of the proposed algorithm for accurate topology and parameter recovery.
READ FULL TEXT