Graph reconstruction using covariance-based methods

Nurgazy Sulaimanov, Heinz KoepplEURASIP J. Bioinform. Syst. Biol 2016 · DOI

TL;DR

This paper explores the relationship between covariance and concentration graphs for reconstructing biological interaction networks. It provides a practical guide for researchers by comparing various methods and offering insights into their performance, especially in high-dimensional settings where the number of variables exceeds samples.

What Problem Does This Paper Address?

Inferring biological networks (like gene regulatory or protein-protein interactions) from high-throughput omics data is a major challenge. Traditional statistical methods struggle when the number of measured variables (genes/proteins) is much larger than the number of samples (experiments). This "small n, large p" scenario is common because experiments are costly. The paper aims to clarify how different graph reconstruction methods, specifically those based on covariance and partial correlation (which relate to concentration matrices), perform and how their underlying principles connect, helping researchers choose the right tools.

Methods

The paper delves into two main types of graphs:

  • Covariance graphs: Edges are determined by non-zero entries in the covariance matrix. These graphs can include indirect dependencies.
  • Concentration graphs: Edges are determined by non-zero entries in the inverse covariance matrix (concentration matrix). These graphs are assumed to represent direct dependencies and are often linked to Gaussian Markov Random Fields.

The authors explore the relationship between these two graph types through:

  • Neumann series and transitive closure: Mathematical tools used to understand how indirect dependencies in covariance graphs arise from direct dependencies in concentration graphs.
  • Network deconvolution: A method to recover direct interactions from observed (covariance) matrices, building on concepts like the Neumann series.
  • Comparison of existing methods: The paper evaluates several popular methods for graph reconstruction, categorized into correlation-based (thresholded covariance, covariance Lasso) and partial correlation-based (nodewise regression Lasso, graphical Lasso, adaptive Lasso).

Datasets

The study primarily uses synthetic datasets generated from various graph topologies (chain, cluster, scale-free, hub graphs) to control experimental conditions and evaluate method performance. These synthetic datasets are generated using a workflow that starts with an adjacency matrix and produces a positive definite matrix, then a correlation matrix, and finally, synthetic data. The paper does not introduce new benchmark datasets.

Key Insights and Ideas

  • Covariance vs. Concentration: Understanding the distinction is crucial. Covariance graphs can be "dense" due to indirect effects, while concentration graphs aim for direct interactions.
  • Transitive Closure Link: The paper mathematically links covariance graphs to the transitive closure of concentration graphs, explaining how indirect edges emerge.
  • Network Deconvolution Potential: Methods like network deconvolution aim to "undo" indirect effects to reveal direct interactions, but their effectiveness can be sensitive to parameters and graph structure.
  • Method Performance Varies: No single method universally outperforms others. Performance depends heavily on graph topology, correlation strength, and whether the underlying graph is known.
  • Nodewise Regression Lasso Strength: In many scenarios, especially when controlling for false positives, the nodewise regression Lasso (and its adaptive version) shows superior performance compared to other methods.

Key Results

  • Analytical Relationship: The paper provides analytical derivations for the relationship between covariance and concentration graphs, particularly for star graphs.
  • Synthetic Data Evaluation: When comparing methods on synthetic data (p > n setting), the nodewise regression Lasso consistently performed well, especially in controlling false positives.
  • Correlation Strength Impact: Increasing the correlation strength in the data generally improves the performance of all tested methods, but some methods saturate earlier than others.
  • Adaptive Lasso Effectiveness: The adaptive Lasso, when using cross-validation for penalty selection, showed good performance on chain graphs but struggled with graphs containing many "hub" nodes (highly connected nodes).

Limitations and Future Work

  • p < n Assumption: Some methods discussed (like network deconvolution) are strictly applicable only when the number of samples exceeds the number of variables (p < n). The paper focuses on the more challenging p > n scenario but acknowledges this limitation.
  • Parameter Selection: Choosing optimal parameters (thresholds, penalty terms) remains a significant challenge, especially in real-world applications where the true graph is unknown. Cross-validation is a common approach, but its effectiveness can vary.
  • Graph Topology Dependence: The performance of methods is highly dependent on the underlying graph structure. Graphs with many hub nodes are particularly difficult to infer accurately.
  • Future Work: The authors suggest extending the analytical findings about transitive closure to other graph types and further investigating the role of scaling parameters in network deconvolution. They also highlight the need for methods that can handle complex graph structures and unknown parameters effectively.

Summary updated

BibTeX
@article{sulaimanov2016graph,
  author = {Nurgazy Sulaimanov and Heinz Koeppl},
  title = {{Graph reconstruction using covariance-based methods}},
  journal = {EURASIP J. Bioinform. Syst. Biol.},
  year = {2016},
  doi = {10.1186/s13637-016-0052-y},
}
Figure