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

Tongxin Li, Lucien Werner, Steven H. Low

TL;DR

This paper tackles the challenge of reconstructing graph-based matrices (like those found in power grids) from limited linear measurements. By introducing a novel three-stage recovery scheme that exploits matrix symmetry, the authors provide a way to learn graphs even when they contain "hubs" (high-degree nodes) that typically cause standard compressed sensing techniques to fail.

What Problem Does This Paper Address?

In fields ranging from social network analysis to electrical engineering, we often need to "learn" the structure of a graph from data. Specifically, the authors look at the problem of reconstructing a symmetric matrix $Y$ (representing the graph) from a linear system $A = BY + Z$, where $B$ is a measurement matrix and $Z$ is noise.

The major hurdle in this sub-field is the presence of high-degree nodes. Standard compressed sensing relies on "sparsity"—the idea that most entries in a vector are zero. However, if a graph has a "hub" (a node connected to almost everyone else), the corresponding column in the matrix is dense, not sparse. Traditional algorithms like Basis Pursuit often fail to recover these dense columns. Furthermore, while many graph matrices are symmetric, standard recovery techniques often treat columns independently, leaving the powerful constraint of symmetry on the table.

Methods

The authors propose a Three-Stage Recovery Scheme and a practical Heuristic Algorithm to bridge the gap between theory and practice.

  1. Independent $\ell_1$-minimization: The algorithm first tries to recover each column of the matrix independently using standard sparse recovery. This successfully captures the "low-degree" (sparse) columns.
  2. Consistency-Checking: This is the "aha!" moment. Because the matrix is symmetric, the entry $Y_{ij}$ must equal $Y_{ji}$. The algorithm checks the recovered columns against each other. If they match, they are deemed "correct."
  3. Resolving Unknown Entries: For the "high-degree" nodes that couldn't be recovered in step one, the algorithm uses the already-verified entries from step two and the original linear equations to solve for the remaining unknown "dense" sub-matrix.

To make this computationally feasible for large networks, they developed a Heuristic Algorithm that iteratively ranks columns based on a "symmetry score," fixing the most consistent ones and reducing the problem's dimension over time.

Datasets

The researchers evaluated their approach using both synthetic and real-world-inspired data:

  • Synthetic Ensembles: Star graphs (one hub, many leaves) and chain graphs, scaled from 5 to 300 nodes.
  • IEEE Power System Test Cases: 17 standard benchmarks ranging from 5 to 200 buses (nodes).
  • Realistic Load Data: To simulate power grid measurements, they used aggregate load profiles from the Bonneville Power Administration (BPA) to generate time-varying voltage and current data via the Matpower simulator.

Key Insights and Ideas

  • Symmetry as a Superpower: The paper demonstrates that symmetry isn't just a property to be satisfied; it's a source of information. A dense column (a hub) is hard to recover directly, but its entries are mirrored in other columns. If those other columns are sparse, we can "sneak in" and learn the hub's connections through its neighbors.
  • $(\mu, K, \rho)$-Sparsity: The authors introduce a more flexible definition of sparsity. Instead of assuming every node has a low degree, they allow for $K$ "high-degree" nodes. This better reflects real-world networks like the internet or power grids, which often follow power-law distributions.
  • Sample Complexity: They prove that for many common graph classes (like Erdős-Rényi or trees), the number of measurements needed scales logarithmically or near-linearly with the number of nodes, even with hubs present.

Key Results

  • Outperforming the Baseline: In star graph simulations, the proposed iterative approach significantly outperformed standard Basis Pursuit. While Basis Pursuit struggled as the hub became denser, the new method maintained high accuracy.
  • Efficiency in Power Grids: On IEEE test cases, the algorithm successfully reconstructed admittance matrices (the "DNA" of a power grid) using a very small number of samples. For example, in a 30-bus system, adding symmetry and structural constraints reduced the required samples by roughly 66% compared to non-sparse recovery.
  • Noise Robustness: The algorithm proved robust to Additive White Gaussian Noise (AWGN). Experiments showed that as the number of measurements $m$ increases, the Frobenius norm error of the reconstructed matrix drops sharply, even in noisy environments.

Limitations and Future Work

While the theoretical three-stage scheme is powerful, its "consistency-check" step can be combinatorially explosive if one tries to check every possible subset of nodes. The heuristic algorithm solves this by being greedy, but it lacks the same ironclad provable guarantees as the theoretical version.

Future research could explore extending this framework to non-linear measurement models (like the full AC power flow equations) or applying it to dynamic graphs where the topology changes over time (e.g., detecting line outages in real-time). Additionally, the authors note that the "high-degree" nodes must still be a relatively small fraction of the total nodes for the recovery to remain efficient.

Summary updated

Abstract

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 tradeoffs 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 Erdos-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 polynomialtime (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.
BibTeX
@article{li2020learning,
  author = {Tongxin Li and Lucien Werner and Steven H. Low},
  title = {{Learning Graphs From Linear Measurements: Fundamental Trade-Offs and Applications}},
  journal = {IEEE Trans. Signal Inf. Process. Over Networks},
  year = {2020},
  url = {https://openreview.net/forum?id=nwsUjJZ5OD},
}

Loading related content...

Figure