Learning Graphs From Linear Measurements: Fundamental Trade-Offs and Applications

You are here

Top Reasons to Join SPS Today!

1. IEEE Signal Processing Magazine
2. Signal Processing Digital Library*
3. Inside Signal Processing Newsletter
4. SPS Resource Center
5. Career advancement & recognition
6. Discounts on conferences and publications
7. Professional networking
8. Communities for students, young professionals, and women
9. Volunteer opportunities
10. Coming soon! PDH/CEU credits
Click here to learn more.

Learning Graphs From Linear Measurements: Fundamental Trade-Offs and Applications

Tongxin Li; Lucien Werner; Steven H. Low

We consider a specific graph learning task: reconstructing a symmetric matrix that represents an underlying graph using linear measurements. We present a sparsity characterization for distributions of random graphs (that are allowed to contain high-degree nodes), based on which we study fundamental trade-offs between the number of measurements, the complexity of the graph class, and the probability of error. We first derive a necessary condition on the number of measurements. Then, by considering a three-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 for both noisy and noiseless recovery. In the special cases of the uniform distribution on trees with n nodes and the Erdős-Rényi (n,p) class, the fundamental trade-offs are tight up to multiplicative factors with noiseless measurements. In addition, for practical applications, we design and implement a polynomial-time (in n ) algorithm based on the three-stage recovery scheme. Experiments show that the heuristic algorithm outperforms basis pursuit on star graphs. We apply the heuristic algorithm to learn admittance matrices in electric grids. Simulations for several canonical graph classes and IEEE power system test cases demonstrate the effectiveness and robustness of the proposed algorithm for parameter reconstruction.

SPS on Twitter

  • NEW SPS WEBINAR: On Tuesday, 13 December, join Dr. Qian Huang for "Deep Learning for All-in-Focus Imaging" - regist… https://t.co/4AVCabulyP
  • Join the SPS Membership Drive on Monday, 12 December, when SPS members, potential members, and the greater signal p… https://t.co/gtbisawJIK
  • The fundraising deadline to meet our 30 unique donations of US$10 or more is tonight — increase your impact for sig… https://t.co/KTzzCKnEMO
  • Happy ! Celebrate this global day of generosity and community action with the IEEE Foundation and… https://t.co/UvaytMFnQ1
  • The SPS Biomedical Imaging and Signal Processing Technical Committee Webinar Series continues on Tuesday, 6 Decembe… https://t.co/SYEEzoxIAK

SPS Videos

Signal Processing in Home Assistants


Multimedia Forensics

Careers in Signal Processing             


Under the Radar