{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T16:12:42Z","timestamp":1772554362351,"version":"3.50.1"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2019,9,20]],"date-time":"2019-09-20T00:00:00Z","timestamp":1568937600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100008838","name":"Shanghai Municipal Commission of Economy and Informatization","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100008838","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Special Fund for Shanghai Industrial Transformation and Upgrading","award":["18XI-05"],"award-info":[{"award-number":["18XI-05"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["U1636205 and 61772367"],"award-info":[{"award-number":["U1636205 and 61772367"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Intell. Syst. Technol."],"published-print":{"date-parts":[[2019,9,30]]},"abstract":"\n We investigate the relationship between conditional independence (CI)\n x<\/jats:italic>\n \u2aeb\n y<\/jats:italic>\n |\n Z<\/jats:italic>\n and the independence of two residuals\n x<\/jats:italic>\n \u2212E(\n x<\/jats:italic>\n |\n Z<\/jats:italic>\n )\u2aeb\n y<\/jats:italic>\n \u2212E(\n y<\/jats:italic>\n |\n Z<\/jats:italic>\n ), where\n x<\/jats:italic>\n and\n y<\/jats:italic>\n are two random variables and\n Z<\/jats:italic>\n is a set of random variables. We show that if\n x<\/jats:italic>\n ,\n y<\/jats:italic>\n , and\n Z<\/jats:italic>\n are generated by following linear structural equation models and all external influences follow joint Gaussian distribution, then\n x<\/jats:italic>\n \u2aeb\n y<\/jats:italic>\n |\n Z<\/jats:italic>\n if and only if\n x<\/jats:italic>\n \u2212E(\n x<\/jats:italic>\n |\n Z<\/jats:italic>\n )\u2aeb\n y<\/jats:italic>\n \u2212E(\n y<\/jats:italic>\n |\n Z<\/jats:italic>\n ). That is, the test of\n x<\/jats:italic>\n \u2aeb\n y<\/jats:italic>\n |\n Z<\/jats:italic>\n can be relaxed to a simpler unconditional independence test of\n x<\/jats:italic>\n \u2212E(\n x<\/jats:italic>\n |\n Z<\/jats:italic>\n )\u2aeb\n y<\/jats:italic>\n \u2212E(\n y<\/jats:italic>\n |\n Z<\/jats:italic>\n ). Furthermore, testing\n x<\/jats:italic>\n \u2212E(\n x<\/jats:italic>\n |\n Z<\/jats:italic>\n )\u2aeb\n y<\/jats:italic>\n \u2212E(\n y<\/jats:italic>\n |\n Z<\/jats:italic>\n ) can be simplified by testing\n x<\/jats:italic>\n \u2212E(\n x<\/jats:italic>\n |\n Z<\/jats:italic>\n )\u2aeb\n y<\/jats:italic>\n or\n y<\/jats:italic>\n \u2212E(\n y<\/jats:italic>\n |\n Z<\/jats:italic>\n )\u2aeb\n x<\/jats:italic>\n . On the other side, if all these external influences follow non-Gaussian distributions and the model satisfies structural faithfulness condition, then we have\n x<\/jats:italic>\n \u2aeb\n y<\/jats:italic>\n |\n Z<\/jats:italic>\n \u21d4\n x<\/jats:italic>\n \u2212E(\n x<\/jats:italic>\n |\n Z<\/jats:italic>\n )\u2aeb\n y<\/jats:italic>\n \u2212E(\n y<\/jats:italic>\n |\n Z<\/jats:italic>\n ).\n <\/jats:p>\n \n We apply the results above to the causal discovery problem, where the causal directions are generally determined by a set of\n V<\/jats:italic>\n -structures and their consistent propagations, so CI test-based methods can return a set of Markov equivalence classes. We show that in the linear non-Gaussian context, in many cases\n x<\/jats:italic>\n \u2212E(\n x<\/jats:italic>\n |\n Z<\/jats:italic>\n )\u2aeb\n z<\/jats:italic>\n or\n y<\/jats:italic>\n \u2212E(\n y<\/jats:italic>\n |\n Z<\/jats:italic>\n )\u2aeb\n z<\/jats:italic>\n (\u2200\n z<\/jats:italic>\n \u2208\n Z<\/jats:italic>\n and\n Z<\/jats:italic>\n is a minimal\n d<\/jats:italic>\n -separator) is satisfied when\n x<\/jats:italic>\n \u2212E(\n x<\/jats:italic>\n |\n Z<\/jats:italic>\n )\u2aeb\n y<\/jats:italic>\n \u2212E(\n y<\/jats:italic>\n |\n Z<\/jats:italic>\n ), which implies\n z<\/jats:italic>\n causes\n x<\/jats:italic>\n (or\n y<\/jats:italic>\n ) if\n z<\/jats:italic>\n directly connects to\n x<\/jats:italic>\n (or\n y<\/jats:italic>\n ). Therefore, we conclude that CIs have useful information for distinguishing Markov equivalence classes.\n <\/jats:p>\n In summary, comparing with the existing discretization-based and kernel-based CI testing methods, the proposed method provides a simpler way to measure CI, which needs only one unconditional independence test and two regression operations. When being applied to causal discovery, it can find more causal relationships, which is extensively validated by experiments.<\/jats:p>","DOI":"10.1145\/3325708","type":"journal-article","created":{"date-parts":[[2019,9,20]],"date-time":"2019-09-20T13:37:15Z","timestamp":1568986635000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Measuring Conditional Independence by Independent Residuals for Causal Discovery"],"prefix":"10.1145","volume":"10","author":[{"given":"Hao","family":"Zhang","sequence":"first","affiliation":[{"name":"Shanghai Key Lab of Intelligent Information Processing, and School of Computer Science, Fudan University, Yangpu District, Shanghai, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1949-2768","authenticated-orcid":false,"given":"Shuigeng","family":"Zhou","sequence":"additional","affiliation":[{"name":"Shanghai Key Lab of Intelligent Information Processing, and School of Computer Science, Fudan University, China; Shanghai Institute of Intelligent Electronics 8 Systems, Fudan University, China, Yangpu District, Shanghai, China"}]},{"given":"Jihong","family":"Guan","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Technology, Tongji University, Shanghai, China"}]},{"given":"Jun (Luke)","family":"Huan","sequence":"additional","affiliation":[{"name":"Big Data Lab, Baidu Research, Haidian District, Beijing, China"}]}],"member":"320","published-online":{"date-parts":[[2019,9,20]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-842X.2004.00360.x"},{"key":"e_1_2_1_2_1","unstructured":"Wicher Pieter Bergsma. 2004. Testing Conditional Independence for Continuous Random Variables. Eurandom. Wicher Pieter Bergsma. 2004. Testing Conditional Independence for Continuous Random Variables. Eurandom."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the International Conference on Machine Learning. 208--216","author":"Cai Ruichu","year":"2013"},{"key":"e_1_2_1_4_1","first-page":"150","article-title":"Learning equivalence classes of Bayesian-network structures","volume":"2","author":"Chickering David Maxwell","year":"2002","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.2307\/1401511"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/67.3.581"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence. 132--141","author":"Doran Gary","year":"2014"},{"key":"e_1_2_1_8_1","volume-title":"A projection based conditional dependence measure with applications to high-dimensional undirected graphical models. Arxiv Preprint Arxiv:1501.01617","author":"Fan Jianqing","year":"2015"},{"key":"e_1_2_1_9_1","first-page":"22","article-title":"Gaussian processes for independence tests with non-iid data in causal inference","volume":"7","author":"Flaxman Seth R.","year":"2016","journal-title":"Trans. Intell.Syst. Technol."},{"key":"e_1_2_1_10_1","first-page":"167","article-title":"Kernel measures of conditional dependence","volume":"20","author":"Fukumizu Kenji","year":"2007","journal-title":"Adv. Neur. Inf. Process. Syst."},{"key":"e_1_2_1_11_1","volume-title":"Smola","author":"Gretton Arthur","year":"2006"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.neuroimage.2015.10.062"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.knosys.2017.01.029"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence. Morgan Kaufmann Publishers Inc., 403--410","author":"Meek Christopher","year":"1995"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Judea Pearl. 2009. Causality. Cambridge University Press. Judea Pearl. 2009. Causality. Cambridge University Press.","DOI":"10.1017\/CBO9780511803161"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2011.71"},{"key":"e_1_2_1_17_1","volume-title":"A scalable conditional independence test for nonlinear, non-gaussian data. Arxiv Preprint Arxiv:1401.5031","author":"Ramsey Joseph D.","year":"2014"},{"key":"e_1_2_1_18_1","volume-title":"Shah and Jonas Peters","author":"Rajen","year":"2018"},{"key":"e_1_2_1_19_1","first-page":"2003","article-title":"A linear non-gaussian acyclic model for causal discovery","author":"Shimizu Shohei","year":"2006","journal-title":"J. Mach. Learn. Res. 7"},{"key":"e_1_2_1_20_1","first-page":"1225","article-title":"DirectLiNGAM: A direct method for learning a linear non-Gaussian structural equation model","author":"Shimizu Shohei","year":"2011","journal-title":"J. Mach. Learn. Res. 12"},{"key":"e_1_2_1_21_1","first-page":"217","article-title":"On a property of the normal distribution","volume":"89","author":"Skitovich V. P.","year":"1953","journal-title":"DAN SSSR"},{"key":"e_1_2_1_22_1","volume-title":"Prediction, and Search","author":"Spirtes Peter"},{"key":"e_1_2_1_23_1","volume-title":"Applied Informatics","author":"Spirtes Peter"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1515\/jci-2018-0017"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0266466608080341"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence. 2029--2036","author":"Zhang Hao","year":"2018"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence. 1250--1256","author":"Zhang Hao","year":"2018"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence. AUAI Press, 647--655","author":"Zhang Kun","year":"2009"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00599-2_25"},{"key":"e_1_2_1_30_1","unstructured":"K. Zhang J. Peters D. Janzing and B. Sch\u00f6lkopf. 2011. Kernel-based Conditional Independence Test and Application in Causal Discovery. AUAI Press Corvallis OR 804--813. K. Zhang J. Peters D. Janzing and B. Sch\u00f6lkopf. 2011. Kernel-based Conditional Independence Test and Application in Causal Discovery. AUAI Press Corvallis OR 804--813."}],"container-title":["ACM Transactions on Intelligent Systems and Technology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3325708","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3325708","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:22Z","timestamp":1750204462000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3325708"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,20]]},"references-count":30,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2019,9,30]]}},"alternative-id":["10.1145\/3325708"],"URL":"https:\/\/doi.org\/10.1145\/3325708","relation":{},"ISSN":["2157-6904","2157-6912"],"issn-type":[{"value":"2157-6904","type":"print"},{"value":"2157-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,9,20]]},"assertion":[{"value":"2018-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-09-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}