Learning Graphs from Linear Measurements: Fundamental Trade-offs and Applications

Tongxin Li, Lucien Werner, Steven H. Low

Abstract

We consider the task of reconstructing a symmetric matrix representing an underlying graph from linear measurements. By introducing a novel sparsity characterization that accommodates high-degree nodes, we investigate the fundamental trade-offs between measurement count, graph complexity, and error probability. We propose a three-stage recovery scheme and a corresponding polynomial-time heuristic algorithm. Our results demonstrate that leveraging matrix symmetry allows for the recovery of "hub" nodes that typically frustrate standard compressed sensing techniques. Simulations on synthetic ensembles and IEEE power system test cases confirm the effectiveness and robustness of this approach for parameter reconstruction in practical applications like electric grids.

Introduction

In fields ranging from social network analysis to infrastructure management, the ability to "learn" the structure of a graph from indirect data is critical. This paper addresses the problem of reconstructing a symmetric matrix $Y$, which represents a graph, from a linear system defined by $A = BY + Z$, where $B$ is a measurement matrix and $Z$ represents noise.

A significant challenge in this domain is the presence of high-degree nodes, or "hubs." Traditional compressed sensing relies on the assumption of uniform sparsity—the idea that most entries in a vector are zero. However, in many real-world networks, a few nodes are connected to a large portion of the network. These hubs result in dense columns within the matrix $Y$, causing standard algorithms like Basis Pursuit to fail. This research explores how the inherent symmetry of graph matrices can be used as a "superpower" to recover these dense components.

Theoretical Framework: $(\mu, K, \rho)$-Sparsity

To better model real-world networks, the authors introduce a flexible definition of sparsity termed $(\mu, K, \rho)$-sparsity. Unlike standard models that assume every node has a low degree, this characterization allows for $K$ high-degree nodes. This more accurately reflects the power-law distributions found in the internet or power grids. Under this framework, the paper proves that for common graph classes like Erdős-Rényi graphs or trees, the number of measurements required for recovery scales logarithmically or near-linearly with the number of nodes, even when hubs are present.

The Three-Stage Recovery Scheme

The core contribution is a recovery strategy that exploits the fact that $Y_{ij}$ must equal $Y_{ji}$. This symmetry means that even if a hub's column is too dense to recover directly, its connections are mirrored in the columns of its neighbors. If those neighbors are sparse, the hub's structure can be inferred indirectly.

  1. Independent $\ell_1$-minimization: The algorithm first attempts to recover each column of the matrix independently using standard sparse recovery. This successfully captures the "low-degree" (sparse) columns.
  2. Consistency-Checking: The algorithm checks the recovered columns against each other. If $Y_{ij}$ from column $j$ matches $Y_{ji}$ from column $i$, those entries are deemed verified.
  3. Resolving Unknown Entries: For the high-degree nodes that failed step one, the algorithm uses the verified entries from step two and the original linear equations to solve for the remaining dense sub-matrix.

To make this computationally feasible for large-scale networks, the authors implemented a Heuristic Algorithm. This version iteratively ranks columns based on a "symmetry score," fixing the most consistent entries and reducing the problem's dimensionality over time.

Experimental Results and Applications

The researchers evaluated their approach using synthetic star and chain graphs (scaled from 5 to 300 nodes) and real-world-inspired IEEE Power System benchmarks (5 to 200 nodes). To simulate realistic power grid conditions, they used aggregate load profiles from the Bonneville Power Administration (BPA) to generate time-varying data.

Key Findings:

  • Superiority over Basis Pursuit: In star graph simulations, the iterative heuristic significantly outperformed standard Basis Pursuit. While the baseline struggled as hubs became denser, the proposed method maintained high accuracy.
  • Efficiency in Power Grids: On IEEE test cases, the algorithm reconstructed admittance matrices—the structural "DNA" of the grid—using a fraction of the samples required by non-sparse methods. In a 30-bus system, the inclusion of symmetry and structural constraints reduced the required sample size by approximately 66%.
  • Noise Robustness: The algorithm demonstrated resilience to Additive White Gaussian Noise (AWGN). As the number of measurements $m$ increased, the Frobenius norm error of the reconstructed matrix dropped sharply, confirming the algorithm's stability in noisy environments.

Conclusion

By integrating symmetry constraints directly into the recovery process, this research provides a robust framework for learning graphs with complex degree distributions. While the theoretical three-stage scheme offers strong guarantees, the heuristic algorithm provides a practical path for large-scale applications. Future work may extend this to non-linear measurement models, such as full AC power flow equations, or to dynamic graphs where topology changes in real-time, such as during power line outages.

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 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 Erdos-Renyi (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.
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},
}
Figure