PC learns different graphs dependent on the ordering

[theabrusch]

Hi,

Thank you for your great work on this package! I am testing the behaviour of the PC algorithm on simple simulated data. I found that the number of directed edges detected differs based on the ordering of the variables given to the algorithm.

I am running the following code:

import numpy as np
import matplotlib.pyplot as plt
from causallearn.search.ConstraintBased.PC import pc

def simulate_data(n_obs):
    '''
    Simulate data from the following graph

        A       B
         \     /
          v   v
            C
          /   \
         v     v
        D       E
    '''
    A = np.random.normal(size = n_obs)
    B = np.random.normal(size = n_obs)
    C = A + B + np.random.normal(size = n_obs)*0.25
    D = C + np.random.normal(size = n_obs)*0.25
    E = C + np.random.normal(size = n_obs)*0.25
    return np.stack((A,B,C,D,E), axis =1)

# generate data
n = 10000
data = simulate_data(n)

# test different permutations
permutations = [[0,1,2,3,4], [0,1,3,2,4]]

for permutation in permutations:
    graph = pc(data[:,permutation], 0.05, 'fisherz', node_names = np.array(["A","B", "C", "D", "E"])[permutation],  verbose = False)
    graph.draw_pydot_graph(labels=np.array(["A","B", "C", "D", "E"])[permutation])
    plt.show()

When the ordering of variables C and D is permuted, the PC algorithm returns the Graph with an undirected edge from C to D. However, when the ordering is unpermuted, the PC algorithm correctly directs the edge from C to D. This happens, even though the p-values in the CI tests are unchanged for the two permutations. Is this expected behaviour or can you help me fix this?

[chenweiDelight]

Thanks for reporting!

We had fixed this bug. Please try to use the latest version. If there is any problem, please let us know. Thanks again!

[tofuwen]

@chenweiDelight Which PR fixed this bug? Could you link it here?

cc @MarkDana

[chenweiDelight]

Sure. The link is https://github.com/cmu-phil/causal-learn/pull/68/commits/3cfd99ed132ef671654df7ed2b1806aca469da6e.

[tofuwen]

@chenweiDelight hmm, this commit is not pushed yet, right? So the latest version doesn't have this bug fixed?

@MarkDana Any idea why our PC tests didn't capture this bug?

[chenweiDelight]

Yes. I mistakenly thought it had already been pushed.

[theabrusch]

Hi again, Sorry for the long reaction time. I just pulled the latest version (1.3.0) and I am still experiencing the same issue. Do you experience the same problem when running my code or is it working?

[kunwuz]

Hi @theabrusch , sorry for the late reply. Could you please try the latest version (1.3.3) to see if the issue remains?

[jdramsey]

Sorry for the late reply. This is studied problem--see this paper (available as PDF in Google Scholar):

Colombo, D., & Maathuis, M. H. (2014). Order-independent constraint-based causal structure learning. J. Mach. Learn. Res., 15(1), 3741-3782.

[moonlians]

I just installed this and I'm having the same issue with the FCI algorithm... Totally different results based on the ordering.

[kunwuz]

Hi, as @jdramsey mentioned, this is a studied problem for constraint-based methods including FCI. Please let me know if I misunderstood anything.