What are some reasons why the PC algorithm might generate zero edges for a certain dataset? How and why could this happen?
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
The PC algorithm starts with a complete graph (all nodes have edges to all remaining nodes). In the first step all node pairs are tested for conditional independence with conditional independence tests, suspect to a certain threshold. If those tests suggest conditional independence between pairs of nodes the edges are deleted from the complete graph. As far as I am concerned all remaining steps are concerned with directing the edges between nodes.
Therefore, the only (theoretical) solution to your question is that all your variables in the dataset are conditionally independent with respect to the threshold of your CI-test (reasonable/default values of that threshold should lie between 0 and 0.05).
-
$\begingroup$ Let's say I run PC algorithm on 10/15 total variables and I get edges. I then run PC algorithm again on the total data set of 15 variables and the algorithm gives me 0 edges. Why would this happen? Why does adding new variables remove previous association? $\endgroup$– EisenCommented Jul 26, 2022 at 14:51
-
$\begingroup$ The base version of PC is not order dependent. Maybe your variable order and therefore the order in which the conditional independences are checked for are responsible for you not getting any edges. You could try changing the variable order and see if you get edges this way. $\endgroup$ Commented Jul 26, 2022 at 15:02
-
$\begingroup$ I'm using the stable pc algorithm, which takes care of the order issue. Wondering why I'm still getting no edges in some cases. $\endgroup$– EisenCommented Jul 26, 2022 at 15:58
$\begingroup$
$\endgroup$
As @ReelSaemon's answer points out, if the data is suggesting complete independence, you get a completely disconnected graph (no edges).
You asked in the comments to @ReelSaemon's answer, how it can be that adding nodes could turn a graph with edges into an edge-free graph. In general, if $G$ is a Bayesian network and $M$ is a marginalization of $G$, then if $M$ has edges, $G$ must have edges, too. If there is an edge in $M$ between two nodes $x_1$ and $x_2$, there must be an open path between $x_1$ and $x_2$ in $G$.
So there is definitely a contradiction in your results which is due to the probabilistic nature of the problem. Lots of things can go wrong, especially if the independency relations are not very clear and there is not a sufficient amount of data. And since PC is a nontrivial algorithm, it is difficult to investigate its numerical stability.
Having said that, I just want to point out one way in which this phenomenon of "edge removal" in the larger graph $G$ could happen. Let's say there is an edge in the marginalization $M$ between $x_1$ and $x_2$ and when switching to the original graph $G$, this edge becomes a collection of several connections, as shown in this figure:
Now, imagine that for each of those nodes $y_i$, the edges of the path from $x_1$ to $x_2$ via $y_i$ describe only weak dependencies, too weak to be recognized by PC. But in the marginalization $M$, only the combined strength of all the paths is measured. And this combination can get you a strong enough dependence in $G$ between $x_1$ and $x_2$. E.g., the variables $y_i$ could be a collection of weak predictors that, when boosted, get you a strong prediction of both $x_1$ and $x_2$.
The PC algorithm working on $G$ will also recognize the strong connection between $x_1$ and $x_2$ e.g. when testing the unconditional independence between $x_1$ and $x_2$ and it probably rejects independence there, too. But the edge between $x_1$ and $x_2$ will be removed when testing the independence $x_1\perp\kern-5pt\perp x_2\;| (y_1,y_2,y_3,y_4)$.
