Why PC algorithm is order dependent? I am studying constraint-based causal discovery algorithms like PC.
From a paper, I learned that PC algorithm is order dependent.
The paper said: "When the PC algorithm is applied to data, it is generally order-dependent, in the sense that its output depends on the order in which the variables are given."
However, I do not understand what's the meaning of 'the order in which the variables are given'? Shouldn't we observe all variable at the same time? How can there be an 'order' in which variables are given?
Besides, can anyone also explain why PC depends on the 'the order in which the variables are given'?
 A: The input for PC:
The vanilla PC algorithm takes as input a set $\frak{I}$ of conditional independence and dependence statements for the nodes of the causal graph that is to be discovered, which need to be obtained before, somehow, usually through domain knowledge and statistical tests. And one has to take into consideration the fact that some of those statements, as they are the results of statistical tests or human judgment, might not be correct.
The PC algorithm:
In the first phase of PC, the algorithm constructs a skeleton (undirected graph) and in the second phase, it tries to orient as many of those edges as possible, resulting in a PDAG for the belonging Markov equivalence class. In this first phase, the algorithm starts with a complete undirected graph. From this complete graph PC removes edges, one at a time, using the fact that if two nodes $X$ and $Y$ are adjacent, there doesn't exist any set that could d-separate them. So it loops through the sizes of possible separation sets $Z$, starting with $\#Z = 0$ and through all pairs of nodes $(X, Y)$ with $X, Y\notin Z$. As soon as it finds a separation $(X\bot Y | Z)$, it removes the edge between $X$ and $Y$, and continues with the testing, but now with the new graph that misses this edge.
The problem with the order:
The above method works fine,  provided all the statements in $\frak I$ are correct. But if this is not the case, and in practice, it usually isn't, it can lead to wrong results. And this depends on the order in which the different d-separations are checked in PC. Imagine that, very early on in the algorithm, a decision to remove an edge has been made based on an incorrect conditional independence statement. But all the following tests will now use the graph with the wrongly removed edge, and even if the rest of the collected (in)dependence statements are correct, all the following decisions will be based on a wrong premise, which leads to further wrong decisions down the line. But if the incorrect conditional independence statement had, because of a fortunate order of how the d-separations are run through, only been used at the end of the algorithm, or maybe not at all, the result would be almost or completely correct.
