Abstract
The PC algorithm is a foundational method for model selection in graphical modeling, utilizing conditional independence tests to recover the structure of acyclic directed graphs. While high-dimensional consistency results have been established for the PC algorithm in Gaussian settings using Pearson correlations, real-world data frequently violates normality assumptions. This paper proves that high-dimensional consistency extends to the broader class of Gaussian copula, or nonparanormal, models through the use of rank-based correlation measures. For graphs with bounded degrees, our results match the strength of existing Gaussian-specific proofs. In simulations, the proposed 'Rank PC' algorithm performs comparably to the 'Pearson PC' algorithm on normal data and significantly outperforms it on non-normal Gaussian copula data, without a meaningful increase in computational overhead. Furthermore, Rank PC demonstrates superior robustness to contaminated data compared to other robust estimators.
Introduction
Learning the structure of a Directed Acyclic Graph (DAG) from observational data is a central challenge in causal discovery. The PC algorithm, named after Spirtes and Glymour, has become the standard tool for this task. It operates by performing a series of conditional independence tests to prune edges from a complete undirected graph, eventually orienting the remaining edges into a Completed Partially Directed Acyclic Graph (CPDAG).
In its classic implementation, the PC algorithm assumes the underlying data follows a multivariate normal distribution. Under this assumption, conditional independence is equivalent to zero partial correlation, which is efficiently estimated using Pearson correlation. However, real-world datasets are often characterized by heavy tails, skewness, or outliers. When these Gaussian assumptions are violated, the Pearson-based PC algorithm often fails to recover the true graph structure. This paper introduces the Rank PC (RPC) algorithm, which replaces Pearson correlations with rank-based measures to achieve robustness within the "nonparanormal" framework.
The Rank PC Algorithm
The core innovation of the Rank PC algorithm is the substitution of the standard Pearson correlation matrix with a transformed rank-based correlation matrix. This approach is situated within the nonparanormal (Gaussian copula) model, which assumes that there exists a set of unknown, strictly increasing functions $f = \{f_1, \dots, f_p\}$ such that $f(X) = (f_1(X_1), \dots, f_p(X_p))$ follows a multivariate normal distribution.
Rank-Based Estimators
Instead of calculating correlations on the raw data values, RPC utilizes Spearman’s $\rho$ or Kendall’s $\tau$. These measures are based on the relative ordering of data points, making them invariant to any strictly increasing transformation of the variables. This property allows the algorithm to bypass the need to explicitly estimate the transformation functions $f_v$.
Trigonometric Transformation
To ensure the rank-based measures are comparable to the latent Gaussian correlations required for the PC algorithm's conditional independence tests, the authors apply specific trigonometric transformations:
- For Spearman’s $\rho$: $\hat{R}_{jk} = 2 \sin\left(\frac{\pi}{6}\hat{\rho}^S_{jk}\right)$
- For Kendall’s $\tau$: $\hat{R}_{jk} = \sin\left(\frac{\pi}{2}\hat{\tau}_{jk}\right)$
These transformed estimators provide a consistent estimate of the correlation matrix of the latent Gaussian variables, which can then be plugged into the standard PC algorithm framework.
Theoretical Consistency
The primary theoretical contribution of this work is the proof that Rank PC is high-dimensionally consistent. The authors demonstrate that as the sample size $n$ increases, the probability of correctly identifying the CPDAG approaches 1, even if the number of variables $p$ grows polynomially with $n$. For graphs where the maximum degree is bounded, the consistency requirements for RPC are as robust as those for the standard Pearson-based PC algorithm in the Gaussian case. This suggests that the move to rank-based measures does not require sacrificing theoretical rigor.
Experimental Evaluation
The algorithm was evaluated using extensive synthetic simulations to compare its performance against the standard Pearson PC and other robust variants like $Q_n$-PC.
Performance on Diverse Data Types
- Multivariate Normal Data: RPC performed almost identically to Pearson PC. This indicates that there is no significant "penalty" for using rank-based methods even when the data is perfectly Gaussian.
- Gaussian Copula Data: Using non-normal marginal distributions, RPC achieved a significantly lower Structural Hamming Distance (SHD) than Pearson PC. In these scenarios, Pearson PC often failed to recover any meaningful structure, whereas RPC remained accurate.
- Contaminated Data: To test robustness against extreme outliers, the authors used a mixture of 80% standard normal and 20% Cauchy distributions. RPC outperformed $Q_n$-PC, particularly as the dimensionality $p$ increased, demonstrating its utility even when the data falls outside the nonparanormal family.
Computational Efficiency
While computing a rank-based correlation matrix is slightly more complex than a Pearson matrix—$O(p^2 n \log n)$ versus $O(p^2 n)$—this difference is negligible in practice. The primary computational bottleneck in causal discovery is the graph-searching phase (the conditional independence tests), not the initial correlation estimation. Consequently, RPC offers robustness with almost no increase in total computation time.
Conclusion and Future Work
The Rank PC algorithm provides a powerful, theoretically sound alternative to the standard PC algorithm for high-dimensional causal discovery. By leveraging the invariance of rank-based correlations, it extends the reach of the PC algorithm to non-normal, heavy-tailed, and contaminated datasets without requiring the explicit estimation of marginal transformations.
Future research directions include extending these rank-based methods to algorithms that can account for latent variables (such as the Fast Causal Inference or FCI algorithm) and adapting the framework to handle discrete or mixed data types, as the current nonparanormal model assumes continuous distributions. Additionally, addressing the "faithfulness" assumption—where small but non-zero correlations can lead to structural errors—remains a critical challenge for all PC-based methodologies.
Summary updated