QWO: Speeding Up Permutation-Based Causal Discovery in LiGAMs

We thank the reviewer for acknowledging our method's theoretical guarantees, efficient computational complexity, and of our experimental results.

The format for definitions is not consistent throughout the paper. Some definitions are directly given in the content body (Lines 64-72), while some others are put in a ‘Definition’ framework (Definition 2.1, 3.1, 3.2).

We used the ‘Definition’ framework for the following cases:

• Definition 2.1 $G(B)$

• Definition 3.1 $[\mathcal{G}]$

• Definition 3.2 $\mathcal{B}(X)$

• Definition 3.3 $\mathcal{G}^{\pi}$

• Definition 4.2 Whitening matrix $W$

These notations are either new and crucial for our presentation, or there is no consensus for them in the literature. On the other hand, the notations and definitions provided in lines 64-72 (which is the notations section) are commonly used in various fields, and we did not see the necessity of assigning a separate box for them.

Line 89 and Line 94 both mention that “faithfulness holds”.

We will edit line 89.

In Definition 3.3., how come “there is an edge from $X_{\pi(i)}$ to $X_{\pi(j)}$ if and only if $X_{\pi(i)}$ and $X_{\pi(j)}$ are conditionally independent”?

We thank the reviewer for pointing out this typo. The independency ($\perp \mathrel{\mkern-9mu} \perp$) in Equation (5) should be changed to dependency.

Despite faithfulness, Markov assumption is also required for inferring causal graphs.

When the underlying model is a structural equation model (SEM), which is a more general setting of our problem, the Markov property holds (please refer to Theorem 1.2.5 in [1]). Therefore, Markov property is not technically an assumption. To avoid any confusion, we will mention this in the revised version.

[1] Pearl, Judea. Causality. Cambridge university press, 2009.

We thank the reviewer for their interesting comment regarding incorporating finite-sample uncertainty. We also appreciate the positive feedback on our method's clarity, intuitive design, and superiority in experiments.

Can QWO be extended to incorporate finite-sample uncertainty while retaining (some of) the advantage in the scalability of the method? For instance, could a confidence set over scores be output with the same scalability?

Below, we drive an uncertainty analysis for each edge in $\mathcal{G}^{\pi}$. In our experiments, our method incorporates a point estimate of $W$ using a finite set of samples. This estimation can indeed be noisy, which is the primary source of error for the final estimation. After constructing $q_1, q_2, ..., q_n$, we then proceed to check the orthogonality of vectors $w_1, ..., w_n$ and $q_1, ..., q_n$. We can show that for $i<j$, the dot product of $w_{\pi(i)}$ and $q_{\pi(j)}$ is an estimation for partial correlation $\rho_{X_{\pi(i)}, X_{\pi(j)} |{X_{\{\pi(1), \pi(2), \ldots, \pi(j-1)\}\backslash\{\pi(i)\}}}}.$ To check whether this dot product is zero, we then apply a z-test for this partial correlation. Using results in [1], we can accordingly derive the following confidence interval:

where `Error of estimation' is the distance between our estimated dot product and the actual dot product.

[1] Drton, Mathias, and Michael D. Perlman. "Multiple testing and error control in Gaussian graphical model selection." (2007): 430-449.

QWO is intended primarily for the setting with large $N$ where other methods are too computationally expensive?

Our method has the advantage of being fast with large sample sizes, but it can also be applied in situations with small sample sizes. It is worth noting that there is extensive literature on computing the inverse covariance matrix with a small number of data points. For example, see [2, 3].

[2] Ravikumar, Pradeep, et al. "High-dimensional covariance estimation by minimizing l1-penalized log-determinant divergence." (2011): 935-980.

[3] Friedman, Jerome, Trevor Hastie, and Robert Tibshirani. "Sparse inverse covariance estimation with the graphical lasso." Biostatistics 9.3 (2008): 432-441.

We appreciate the reviewer's comments and are pleased that they found our approach to be a clear and original contribution.

Why comparing PDAGs instead of CPDAGs when computing evaluation metrics?

We thank the reviewer for pointing out this issue/typo. In our experiments, we have indeed compared the CPDAGs (complete PDAG achieved after applying Meek rules). We will correct this typo in the revised version.

GRASP-BIC usually achieves better results then the proposed solution in random graphs.

We acknowledge the reviewer's observation that GRASP-BIC usually archives slightly higher accuracy in random graphs. However, we note that (i) the difference in accuracy is almost negligible, and (ii) the primary goal of our method is to reduce computational complexity, which we have demonstrated both theoretically (by a factor of $O(n^2)$) and empirically. Figure 1 shows that GRASP-BIC was scalable to nearly 50 variables and only in sparse graphs, while our method was easily scalable to over 150 variables, even in denser graphs.

We thank the reviewer for their detailed and thoughtful comments.

Assumptions needed is not spelled out

We agree with the reviewer that permutation-based algorithms aim to relax necessary assumptions, such as faithfulness. However, for our method, the sparsest Markovian representation assumption in [RU18] is indeed sufficient. We did not mention this in the text to keep it simple and avoid exceeding the page limit. Since we have an extra page for the revised version, we will explicitly mention this lesser version of faithfulness. Additionally, for the sake of completeness, we will refer to the exact assumptions in the main results of the paper.

The significance of the proposed method may need a better justification

We acknowledge the reviewer's insights on the matter. While there may be alternative methods based on Cholesky decomposition as the reviewer suggested, our method offers some advantages. For instance, the update step in our method is straightforward and can be easily integrated into existing search methods. Furthermore, we propose a characterization over $\mathcal{B}(X)$ in Theorem 4.3, which is defined for cyclic models as well, paving the way for learning cyclic models. For example, by removing the upper-triangularity constraint in Equation 13, it would be a valid optimization for learning a cyclic graph (though we might need a stronger version of faithfulness to extend this to cyclic models). However, solving the optimization for cyclic models could be a challenging problem, but it is a promising direction for future work.

A more clearer justification for the necessity of speeding up $\mathcal{G}^{\pi}$ construction is needed

We believe there has been a misunderstanding regarding lines 138-141, which we include here for reference:

To solve (9), various approaches have been proposed. Note that the complexity of a brute-force search over all subsets $\mathbf{U}$ is exponential. Instead, the state-of-the-art search methods apply the grow-shrink (GS) algorithm [ARSR+23] on the candidate sets $\mathbf{U}$ to find the parent set of each variable. These methods require computing the score function $S$, $O(n^2)$ times.

Herein, we provide a literature review of the existing methods for constructing $\mathcal{G}^{\pi}$. We start by pointing out that brute force is not a feasible method. Therefore, we mention alternative approaches that involve computing the score function $S$ only $O(n^2)$ number of times. We then introduce different score functions for $S$ in the following paragraph. This gives us the computation complexity of the existing work for constructing $\mathcal{G}^{\pi}$ (please refer to Table 1). Finally, we justify our proposed method by the fact that it gains a speed-up of $O(n^2)$ in comparison to the aforementioned class of approaches.

Some missing references

We appreciate the reviewer for bringing up that paper. It looks very interesting and relevant to our problem. In the revised version, we will include a brief discussion on the similarities and differences between our work and this paper.