Inverse Graph Learning over Optimization Networks

Vincenzo Matta, Augusto Santos, Ali H. SayedarXiv 2019 · arXiv

Introduction: The Challenge of Partial Observability

In complex systems ranging from neuroscience to social media, we often observe the outputs of a system—such as neural firing patterns or traffic flows—without having access to the underlying architecture that governs these interactions. While the "direct problem" of how a known graph affects decentralized processing is well-studied, this paper addresses the "dual problem": topology inference.

The primary challenge is partial observability. In massive networks, we may only be able to probe a small fraction of nodes. These observed nodes are continuously influenced by the "invisible" remainder of the network, creating structured interference. The central question is whether the information leaked through these partial signals is sufficient to reconstruct the local topology without prior knowledge of the system's global parameters.

Conceptual framework of the direct and dual problems in graph learning.

Methodology: Estimating Topology from Dynamics

The research focuses on networks governed by discrete-time linear dynamical systems, specifically first-order Vector AutoRegressive (VAR) models. In these models, a node's state at time $i$ is a weighted sum of its neighbors' states at time $i-1$, plus local noise.

The paper analyzes three primary matrix estimators for reconstructing the graph:

  1. Granger Estimator: Utilizes linear prediction to identify the best-fit weights based on classical Granger causality.
  2. One-Lag Estimator: Leverages the cross-covariance between current signals and signals from the previous time step.
  3. Residual Estimator: Analyzes differences between consecutive time samples to filter out specific noise components.

To validate these estimators, the authors employ an asymptotic analysis using Erdős-Rényi (ER) random graphs, allowing the network size $N$ to approach infinity to study the "thermodynamic" properties of the system.

Theoretical Framework: Connectivity Regimes and Degree Concentration

A critical insight of this work is that graph reconstruction is not solely dependent on sparsity. The authors identify that in "dense" or "intermediate-sparse" regimes, node degrees tend to concentrate around a mean. This uniform degree concentration allows the interference from unobserved latent nodes to become predictable, enabling it to be effectively bypassed or canceled out during the estimation process.

Connectivity regimes in Erdős-Rényi graphs across different network sizes.

The study categorizes connectivity into three main regimes:

  • Log-sparse regime: Where the average degree $D_{av}$ grows logarithmically with $N$.
  • Intermediate-sparse regime: Where $D_{av}$ grows faster than $\log N$ but slower than $N$.
  • Dense regime: Where $D_{av}$ is proportional to $N$.

Key Results and Consistency

The authors establish conditions for Universal Strong Consistency, a gold standard where connected and disconnected node pairs naturally form distinct clusters in the data. This allows for a data-driven thresholding approach that does not require knowledge of the underlying physics.

Key findings include:

  • Estimator Performance: While the Granger estimator is effective under high observability, the Residual estimator demonstrates superior robustness in specific partial-observability scenarios.
  • Sample Complexity: Successful recovery generally requires a sample size on the order of $O(D_{av}^2 \log S)$, where $S$ is the number of probed nodes.
  • Phase Transitions: Exact reconstruction remains possible even in "low-observability" regimes where the fraction of probed nodes vanishes as the network grows, provided the connectivity conditions are met.

Limitations and Future Directions

While providing a robust theoretical framework, the current study relies on linear VAR models and Erdős-Rényi graph assumptions. Real-world systems often exhibit non-linear dynamics and scale-free (power-law) degree distributions, which may present different challenges for degree concentration.

Future work will focus on extending these results to higher-order dynamics, directed/asymmetric graphs, and improving sample efficiency for high-dimensional settings. The results suggest a "divide and conquer" strategy for global graph reconstruction by sequentially probing and stitching together small, overlapping patches.

Summary updated

BibTeX
@misc{matta2019inverse,
  author = {Vincenzo Matta and Augusto Santos and Ali H. Sayed},
  title = {{Inverse Graph Learning over Optimization Networks}},
  year = {2019},
  eprint = {1912.08465},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1912.08465},
}
Figure