Abstract
PC algorithm (PC) – named after its authors, Peter and Clark – is an advanced constraint based method for learning causal structures. However, it is a time-consuming algorithm since the number of independence tests is exponential to the number of considered variables. Attempts to parallelise PC have been studied intensively, for example, by distributing the tests to all computing cores in a single computer. However, no effort has been made to speed up PC through parallelising the conditional independence tests into a cluster of computers. In this work, we propose MrPC, a robust and efficient PC algorithm, to accelerate PC to serve causal discovery in distributed systems. Alongside with MrPC, we also propose a novel manner to model non-linear causal relationships in gene regulatory data using kernel functions. We evaluate our method and its variants in the task of building gene regulatory networks. Experimental results on benchmark datasets show that the proposed MrPCgains up to seven times faster than sequential PC implementation. In addition, kernel functions outperform conventional linear causal modelling approach across different datasets.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Colombo, D., Maathuis, M.H.: Order-independent constraint-based causal structure learning. JMLR 15(1), 3741–3782 (2014)
Dean, J., Ghemawat, S.: MapReduce: simplified data processing on large clusters. Commun. ACM 51(1), 107–113 (2008)
Hofmann, T., Schölkopf, B., Smola, A.J.: Kernel methods in machine learning. Ann. Stat. 36(3), 1171–1220 (2008)
Le, T., Hoang, T., Li, J., Liu, L., Liu, H., Hu, S.: A fast PC algorithm for high dimensional causal discovery with multi-core PCs. IEEE/ACM Trans. Comput. Biol. Bioinform. 16(5), 1483–1495 (2019)
Marbach, D., et al.: Wisdom of crowds for robust gene network inference. Nat. Methods 9(8), 796 (2012)
Shimizu, S., Hoyer, P.O., Hyvärinen, A., Kerminen, A.: A linear non-Gaussian acyclic model for causal discovery. JMLR 7, 2003–2030 (2006)
Silverstein, C., Brin, S., Motwani, R., Ullman, J.: Scalable techniques for mining causal structures. Data Min. Knowl. Disc. 4(2–3), 163–192 (2000)
Spirtes, P., Glymour, C.N., Scheines, R., Heckerman, D.: Causation, Prediction, and Search. MIT Press, Cambridge (2000)
Zaharia, M., Chowdhury, M., Franklin, M.J., Shenker, S., Stoica, I.: Spark: cluster computing with working sets. In: Proceedings of the USENIX Conference on Hot Topics in Cloud Computing, pp. 10 (2010)
Zhang, K., Peters, J., Janzing, D., Schölkopf, B.: Kernel-based conditional independence test and application in causal discovery. In: Proceedings of UAI, pp. 804–813 (2011)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Nguyen, T., Nguyen, D.T., Le, T.D., Venkatesh, S. (2020). MrPC: Causal Structure Learning in Distributed Systems. In: Yang, H., Pasupa, K., Leung, A.CS., Kwok, J.T., Chan, J.H., King, I. (eds) Neural Information Processing. ICONIP 2020. Communications in Computer and Information Science, vol 1332. Springer, Cham. https://doi.org/10.1007/978-3-030-63820-7_10
Download citation
DOI: https://doi.org/10.1007/978-3-030-63820-7_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-63819-1
Online ISBN: 978-3-030-63820-7
eBook Packages: Computer ScienceComputer Science (R0)