A Covariance Matching Approach to Graph Topology Identification

1. Problem Statement

Graph Topology Identification (GTI) is the challenge of recovering the hidden underlying structure (graph topology) of a network from observed nodal data.

• Context: In many systems (e.g., brain connectivity, social networks, gene regulatory networks), the direct graph structure is unobservable, but time-series or cross-sectional data from the nodes are available.
• Model: The paper utilizes the Linear Structural Equation Model (SEM), where the observed data vector $\mathbf{x}$ is generated by $\mathbf{x} = \mathbf{S}\mathbf{x} + \mathbf{e}$, with $\mathbf{S}$ being the weighted adjacency matrix (Graph Shift Operator) and $\mathbf{e}$ representing exogenous noise.
• Challenges:
  • Non-convexity: Standard Maximum Likelihood Estimation (MLE) involves a log-determinant term that makes the optimization problem non-convex and difficult to solve globally.
  • Restrictive Assumptions: Existing methods often rely on specific structural constraints, such as the graph being a Directed Acyclic Graph (DAG) or having positive edge weights, limiting their applicability to general networks.
  • Scalability: Many existing approaches struggle with large-scale graphs or require massive sample sizes to achieve accurate recovery.

2. Methodology: The CovMatch Framework

The authors propose CovMatch (Covariance Matching), a framework that bypasses the complexities of log-determinant optimization by directly aligning the empirical sample covariance with the theoretical covariance implied by the graph model.

Core Concept

Instead of maximizing likelihood, CovMatch seeks a graph structure $\mathbf{S}$ such that the theoretical covariance $\boldsymbol{\Sigma}_x$ matches the sample covariance $\mathbf{C}_x$.
Given the SEM relation $\mathbf{x} = (\mathbf{I} - \mathbf{S})^{-1}\mathbf{e}$, the theoretical covariance is $\boldsymbol{\Sigma}_x = \mathbf{H}\boldsymbol{\Sigma}_e\mathbf{H}^\top$, where $\mathbf{H} = (\mathbf{I} - \mathbf{S})^{-1}$.
The goal is to solve:
$$\min_{\hat{\mathbf{H}}} \| \hat{\mathbf{H}}\boldsymbol{\Sigma}_e\hat{\mathbf{H}}^\top - \mathbf{C}_x \|_F^2$$
subject to structural constraints on $\mathbf{S}$ (e.g., sparsity, no self-loops).

Key Reformulation

The authors invert the optimization logic: instead of minimizing the fitting error subject to constraints, they enforce the exact equality $\hat{\mathbf{H}}\boldsymbol{\Sigma}_e\hat{\mathbf{H}}^\top = \mathbf{C}_x$ and minimize a structural penalty function $h(\mathbf{S})$ (e.g., sparsity) over the set of matrices that satisfy this equality.

The approach is split based on graph type:

A. Undirected Graphs

• Decomposition: Uses Eigenvalue Decomposition (EVD). Since $\mathbf{S}$ is symmetric, $\mathbf{H}$ is symmetric.
• Parameterization: The solution is parameterized by the eigenvectors of $\mathbf{C}_x$ and a binary vector $\hat{\mathbf{q}} \in \{-1, 1\}^N$ that resolves sign ambiguities in the eigenvalues.
• Optimization: The problem reduces to a Conic Mixed-Integer Program (CMIP). The objective combines an $\ell_2$ penalty for zero-diagonal (no self-loops) and an $\ell_1$ penalty for sparsity. This can be solved efficiently using modern solvers (branch-and-bound).

B. Directed Graphs

• Decomposition: Uses Singular Value Decomposition (SVD). $\mathbf{H}$ may be non-symmetric.
• Parameterization: The solution is parameterized by the eigenvectors of $\mathbf{C}_x$ and an orthogonal matrix $\hat{\mathbf{V}}$.
• Optimization: The problem becomes finding an orthogonal matrix $\hat{\mathbf{V}}$ that minimizes the structural penalty.
  • Algorithm: The authors propose Riemannian Gradient Descent on the orthogonal group $O(N)$.
  • Escaping Local Minima: To avoid poor local minima, they employ a Basin-Hopping strategy with a multi-threaded candidate set. This involves perturbing the current best solution along geodesics on the manifold and re-optimizing, maintaining a diverse set of candidates to ensure global exploration.

3. Key Contributions

1. Unified Framework: CovMatch provides a single, unified approach for both undirected and general directed graphs (including cyclic and non-positive weighted graphs) without requiring explicit knowledge of acyclicity or positivity.
2. Relaxed Assumptions: Unlike previous methods (e.g., LiNGAM, NOTEARS), CovMatch does not assume the graph is a DAG. It relies solely on the inherent sparsity of the network.
3. Tractable Reformulations:
   • For undirected graphs, the problem is reduced to a CMIP solvable with off-the-shelf solvers.
   • For directed graphs, it is reduced to an orthogonal matrix optimization solvable via Riemannian optimization.
4. Scalability: The method demonstrates the ability to recover large graphs (up to $N=100$ nodes) efficiently, outperforming baselines in accuracy even with moderate sample sizes.

4. Experimental Results

The authors evaluated CovMatch on four settings:

• Undirected Synthetic Graphs:

  • Compared against SpecTemp and SigMatch.
  • Result: CovMatch achieved significantly lower Normalized Squared Error (NSE) than baselines for finite sample sizes ($T=1000$) and approached machine precision as $T \to \infty$. It successfully avoided the over-dense graphs produced by methods lacking explicit sparsity priors.

• DAGs (Directed Acyclic Graphs):

  • Compared against state-of-the-art causal discovery methods NOTEARS and DAGMA.
  • Result: In the asymptotic limit ($T \to \infty$), CovMatch achieved near-zero error, outperforming NOTEARS and DAGMA (which plateaued at $10^{-2}$). Crucially, CovMatch achieved this without enforcing the acyclicity constraint, proving its robustness.

• Cyclic Directed Graphs:

  • Tested on general directed graphs containing cycles.
  • Result: CovMatch successfully recovered the topology with low error, demonstrating its capability to handle non-DAG structures where many existing methods fail.

• Real-World Data (T-cell Protein Expression):

  • Applied to the $N=11$ T-cell dataset (non-Gaussian data handled via copula transformation).
  • Result: The recovered graph was biologically more plausible and contained more correct adjacencies compared to the baseline method from [15].

5. Significance

This paper represents a significant shift in Graph Topology Identification:

• Paradigm Shift: It moves away from complex, non-convex likelihood maximization toward a direct covariance matching strategy that is more robust and easier to constrain.
• Generality: By removing the strict requirement for acyclicity, CovMatch opens the door to learning complex, real-world networks (which are often cyclic) that were previously difficult to model with standard SEM-based tools.
• Practicality: The combination of rigorous mathematical reformulation (CMIP for undirected, Riemannian optimization for directed) and efficient algorithms makes it a viable tool for large-scale network inference in fields like neuroscience, systems biology, and social network analysis.