Timezone: »
Scalable Causal Discovery with Score Matching
Francesco Montagna · Nicoletta Noceti · Lorenzo Rosasco · Kun Zhang · Francesco Locatello
Event URL: https://openreview.net/forum?id=v56PHv_W2A »
This paper demonstrates how to discover the whole causal graph from the second derivative of the log-likelihood in observational non-linear additive Gaussian noise models. Leveraging scalable machine learning approaches to approximate the score function $\nabla \operatorname{log}p(\mathbf{X})$, we extend the work of Rolland et al., 2022, that only recovers the topological order from the score and requires an expensive pruning step to discover the edges.Our analysis leads to DAS, a practical algorithm that reduces the complexity of the pruning by a factor proportional to the graph size. In practice, DAS achieves competitive accuracy with current state-of-the-art while being over an order of magnitude faster. Overall, our approach enables principled and scalable causal discovery, significantly lowering the compute bar.
This paper demonstrates how to discover the whole causal graph from the second derivative of the log-likelihood in observational non-linear additive Gaussian noise models. Leveraging scalable machine learning approaches to approximate the score function $\nabla \operatorname{log}p(\mathbf{X})$, we extend the work of Rolland et al., 2022, that only recovers the topological order from the score and requires an expensive pruning step to discover the edges.Our analysis leads to DAS, a practical algorithm that reduces the complexity of the pruning by a factor proportional to the graph size. In practice, DAS achieves competitive accuracy with current state-of-the-art while being over an order of magnitude faster. Overall, our approach enables principled and scalable causal discovery, significantly lowering the compute bar.
Author Information
Francesco Montagna (University of Genoa)

I am a PhD student jointly between University of Genova and Amazon AWS Tuebingen. I am co-supervised by professors Lorenzo Rosasco and Nicoletta Noceti from University of Genoa, and Dr. Francesco Locatello drom Amazon AWS. I am doing a research internship at Amazon AWS Tuebingen until April 2023
Nicoletta Noceti (Università degli Studi di Genova)
Lorenzo Rosasco (University of Genova- MIT - IIT)
Kun Zhang (CMU & MBZUAI)
Francesco Locatello (Amazon)
More from the Same Authors
-
2022 : Tier Balancing: Towards Dynamic Fairness over Underlying Causal Factors »
Zeyu Tang · Yatong Chen · Yang Liu · Kun Zhang -
2023 : Procedural Fairness Through Decoupling Objectionable Data Generating Components »
Zeyu Tang · Jialu Wang · Yang Liu · Peter Spirtes · Kun Zhang -
2023 : Procedural Fairness Through Decoupling Objectionable Data Generating Components »
Zeyu Tang · Jialu Wang · Yang Liu · Peter Spirtes · Kun Zhang -
2023 Poster: On the Identifiability of Sparse ICA without Assuming Non-Gaussianity »
Ignavier Ng · Yujia Zheng · Xinshuai Dong · Kun Zhang -
2023 Poster: Generalizing Nonlinear ICA Beyond Structural Sparsity »
Yujia Zheng · Kun Zhang -
2023 Poster: Counterfactual Generation with Identifiability Guarantees »
Hanqi Yan · Lingjing Kong · Lin Gui · Yuejie Chi · Eric Xing · Yulan He · Kun Zhang -
2023 Poster: Temporally Disentangled Representation Learning under Unknown Nonstationarity »
Xiangchen Song · Weiran Yao · Yewen Fan · Xinshuai Dong · Guangyi Chen · Juan Carlos Niebles · Eric Xing · Kun Zhang -
2023 Poster: Identification of Nonlinear Latent Hierarchical Models »
Lingjing Kong · Biwei Huang · Feng Xie · Eric Xing · Yuejie Chi · Kun Zhang -
2023 Poster: An Optimal Structured Zeroth-order Algorithm for Non-smooth Optimization »
Marco Rando · Cesare Molinari · Lorenzo Rosasco · Silvia Villa -
2023 Oral: Generalizing Nonlinear ICA Beyond Structural Sparsity »
Yujia Zheng · Kun Zhang -
2023 Poster: Assumption violations in causal discovery and the robustness of score matching »
Francesco Montagna · Atalanti Mastakouri · Elias Eulig · Nicoletta Noceti · Lorenzo Rosasco · Dominik Janzing · Bryon Aragam · Francesco Locatello -
2023 Poster: Estimating Koopman operators with sketching to provably learn large scale dynamical systems »
Giacomo Meanti · Antoine Chatalic · Vladimir Kostic · Pietro Novelli · Massimiliano Pontil · Lorenzo Rosasco -
2023 Poster: Subspace Identification for Multi-Source Domain Adaptation »
Zijian Li · Ruichu Cai · Guangyi Chen · Boyang Sun · Zhifeng Hao · Kun Zhang -
2023 Poster: Learning World Models with Identifiable Factorization »
Yuren Liu · Biwei Huang · Zhengmao Zhu · Honglong Tian · Mingming Gong · Yang Yu · Kun Zhang -
2022 Spotlight: Lightning Talks 5B-3 »
Yanze Wu · Jie Xiao · Nianzu Yang · Jieyi Bi · Jian Yao · Yiting Chen · Qizhou Wang · Yangru Huang · Yongqiang Chen · Peixi Peng · Yuxin Hong · Xintao Wang · Feng Liu · Yining Ma · Qibing Ren · Xueyang Fu · Yonggang Zhang · Kaipeng Zeng · Jiahai Wang · GEN LI · Yonggang Zhang · Qitian Wu · Yifan Zhao · Chiyu Wang · Junchi Yan · Feng Wu · Yatao Bian · Xiaosong Jia · Ying Shan · Zhiguang Cao · Zheng-Jun Zha · Guangyao Chen · Tianjun Xiao · Han Yang · Jing Zhang · Jinbiao Chen · MA Kaili · Yonghong Tian · Junchi Yan · Chen Gong · Tong He · Binghui Xie · Yuan Sun · Francesco Locatello · Tongliang Liu · Yeow Meng Chee · David P Wipf · Tongliang Liu · Bo Han · Bo Han · Yanwei Fu · James Cheng · Zheng Zhang -
2022 Spotlight: Self-supervised Amodal Video Object Segmentation »
Jian Yao · Yuxin Hong · Chiyu Wang · Tianjun Xiao · Tong He · Francesco Locatello · David P Wipf · Yanwei Fu · Zheng Zhang -
2022 Spotlight: Latent Hierarchical Causal Structure Discovery with Rank Constraints »
Biwei Huang · Charles Jia Han Low · Feng Xie · Clark Glymour · Kun Zhang -
2022 : Kun Zhang: Causal Principles Meet Deep Learning: Successes and Challenges. »
Kun Zhang -
2022 : Kun Zhang: Causal Principles Meet Deep Learning: Successes and Challenges. »
Kun Zhang -
2022 Workshop: Causal Machine Learning for Real-World Impact »
Nick Pawlowski · Jeroen Berrevoets · Caroline Uhler · Kun Zhang · Mihaela van der Schaar · Cheng Zhang -
2022 Poster: Are Two Heads the Same as One? Identifying Disparate Treatment in Fair Neural Networks »
Michael Lohaus · Matthäus Kleindessner · Krishnaram Kenthapadi · Francesco Locatello · Chris Russell -
2022 Poster: On the Identifiability of Nonlinear ICA: Sparsity and Beyond »
Yujia Zheng · Ignavier Ng · Kun Zhang -
2022 Poster: Independence Testing-Based Approach to Causal Discovery under Measurement Error and Linear Non-Gaussian Models »
Haoyue Dai · Peter Spirtes · Kun Zhang -
2022 Poster: Neural Attentive Circuits »
Martin Weiss · Nasim Rahaman · Francesco Locatello · Chris Pal · Yoshua Bengio · Bernhard Schölkopf · Erran Li Li · Nicolas Ballas -
2022 Poster: Assaying Out-Of-Distribution Generalization in Transfer Learning »
Florian Wenzel · Andrea Dittadi · Peter Gehler · Carl-Johann Simon-Gabriel · Max Horn · Dominik Zietlow · David Kernert · Chris Russell · Thomas Brox · Bernt Schiele · Bernhard Schölkopf · Francesco Locatello -
2022 Poster: Latent Hierarchical Causal Structure Discovery with Rank Constraints »
Biwei Huang · Charles Jia Han Low · Feng Xie · Clark Glymour · Kun Zhang -
2022 Poster: MissDAG: Causal Discovery in the Presence of Missing Data with Continuous Additive Noise Models »
Erdun Gao · Ignavier Ng · Mingming Gong · Li Shen · Wei Huang · Tongliang Liu · Kun Zhang · Howard Bondell -
2022 Poster: Causal Discovery in Linear Latent Variable Models Subject to Measurement Error »
Yuqin Yang · AmirEmad Ghassami · Mohamed Nafea · Negar Kiyavash · Kun Zhang · Ilya Shpitser -
2022 Poster: Unsupervised Image-to-Image Translation with Density Changing Regularization »
Shaoan Xie · Qirong Ho · Kun Zhang -
2022 Poster: Factored Adaptation for Non-Stationary Reinforcement Learning »
Fan Feng · Biwei Huang · Kun Zhang · Sara Magliacane -
2022 Poster: Counterfactual Fairness with Partially Known Causal Graph »
Aoqi Zuo · Susan Wei · Tongliang Liu · Bo Han · Kun Zhang · Mingming Gong -
2022 Poster: Learning Dynamical Systems via Koopman Operator Regression in Reproducing Kernel Hilbert Spaces »
Vladimir Kostic · Pietro Novelli · Andreas Maurer · Carlo Ciliberto · Lorenzo Rosasco · Massimiliano Pontil -
2022 Poster: Self-supervised Amodal Video Object Segmentation »
Jian Yao · Yuxin Hong · Chiyu Wang · Tianjun Xiao · Tong He · Francesco Locatello · David P Wipf · Yanwei Fu · Zheng Zhang -
2022 Poster: Temporally Disentangled Representation Learning »
Weiran Yao · Guangyi Chen · Kun Zhang -
2022 Poster: Truncated Matrix Power Iteration for Differentiable DAG Learning »
Zhen Zhang · Ignavier Ng · Dong Gong · Yuhang Liu · Ehsan Abbasnejad · Mingming Gong · Kun Zhang · Javen Qinfeng Shi -
2020 Workshop: Causal Discovery and Causality-Inspired Machine Learning »
Biwei Huang · Sara Magliacane · Kun Zhang · Danielle Belgrave · Elias Bareinboim · Daniel Malinsky · Thomas Richardson · Christopher Meek · Peter Spirtes · Bernhard Schölkopf -
2020 Poster: Kernel Methods Through the Roof: Handling Billions of Points Efficiently »
Giacomo Meanti · Luigi Carratino · Lorenzo Rosasco · Alessandro Rudi -
2020 Oral: Kernel Methods Through the Roof: Handling Billions of Points Efficiently »
Giacomo Meanti · Luigi Carratino · Lorenzo Rosasco · Alessandro Rudi -
2019 Poster: Implicit Regularization of Accelerated Methods in Hilbert Spaces »
Nicolò Pagliana · Lorenzo Rosasco -
2019 Poster: Beating SGD Saturation with Tail-Averaging and Minibatching »
Nicole Muecke · Gergely Neu · Lorenzo Rosasco -
2018 Poster: On Fast Leverage Score Sampling and Optimal Learning »
Alessandro Rudi · Daniele Calandriello · Luigi Carratino · Lorenzo Rosasco -
2018 Poster: Statistical and Computational Trade-Offs in Kernel K-Means »
Daniele Calandriello · Lorenzo Rosasco -
2018 Poster: Learning with SGD and Random Features »
Luigi Carratino · Alessandro Rudi · Lorenzo Rosasco -
2018 Spotlight: Statistical and Computational Trade-Offs in Kernel K-Means »
Daniele Calandriello · Lorenzo Rosasco -
2018 Spotlight: Learning with SGD and Random Features »
Luigi Carratino · Alessandro Rudi · Lorenzo Rosasco -
2018 Poster: Dirichlet-based Gaussian Processes for Large-scale Calibrated Classification »
Dimitrios Milios · Raffaello Camoriano · Pietro Michiardi · Lorenzo Rosasco · Maurizio Filippone -
2018 Poster: Manifold Structured Prediction »
Alessandro Rudi · Carlo Ciliberto · Gian Maria Marconi · Lorenzo Rosasco -
2017 Poster: Learning Causal Structures Using Regression Invariance »
AmirEmad Ghassami · Saber Salehkaleybar · Negar Kiyavash · Kun Zhang -
2017 Poster: Generalization Properties of Learning with Random Features »
Alessandro Rudi · Lorenzo Rosasco -
2017 Oral: Generalization Properties of Learning with Random Features »
Alessandro Rudi · Lorenzo Rosasco -
2017 Poster: Consistent Multitask Learning with Nonlinear Output Relations »
Carlo Ciliberto · Alessandro Rudi · Lorenzo Rosasco · Massimiliano Pontil -
2017 Poster: FALKON: An Optimal Large Scale Kernel Method »
Alessandro Rudi · Luigi Carratino · Lorenzo Rosasco -
2016 Poster: A Consistent Regularization Approach for Structured Prediction »
Carlo Ciliberto · Lorenzo Rosasco · Alessandro Rudi -
2016 Poster: Optimal Learning for Multi-pass Stochastic Gradient Methods »
Junhong Lin · Lorenzo Rosasco -
2015 Poster: Learning with Incremental Iterative Regularization »
Lorenzo Rosasco · Silvia Villa -
2015 Poster: Less is More: Nyström Computational Regularization »
Alessandro Rudi · Raffaello Camoriano · Lorenzo Rosasco -
2015 Oral: Less is More: Nyström Computational Regularization »
Alessandro Rudi · Raffaello Camoriano · Lorenzo Rosasco -
2013 Workshop: Modern Nonparametric Methods in Machine Learning »
Arthur Gretton · Mladen Kolar · Samory Kpotufe · John Lafferty · Han Liu · Bernhard Schölkopf · Alexander Smola · Rob Nowak · Mikhail Belkin · Lorenzo Rosasco · peter bickel · Yue Zhao -
2013 Poster: On the Sample Complexity of Subspace Learning »
Alessandro Rudi · Guillermo D Canas · Lorenzo Rosasco -
2012 Poster: Learning Manifolds with K-Means and K-Flats »
Guillermo D Canas · Tomaso Poggio · Lorenzo Rosasco -
2012 Poster: Multiclass Learning with Simplex Coding »
Youssef Mroueh · Tomaso Poggio · Lorenzo Rosasco · Jean-Jacques Slotine -
2012 Poster: Learning Probability Measures with respect to Optimal Transport Metrics »
Guillermo D Canas · Lorenzo Rosasco -
2010 Poster: A Primal-Dual Algorithm for Group Sparse Regularization with Overlapping Groups »
Sofia Mosci · Silvia Villa · Alessandro Verri · Lorenzo Rosasco -
2010 Poster: Spectral Regularization for Support Estimation »
Ernesto De Vito · Lorenzo Rosasco · Alessandro Toigo -
2009 Workshop: Kernels for Multiple Outputs and Multi-task Learning: Frequentist and Bayesian Points of View »
Mauricio A Alvarez · Lorenzo Rosasco · Neil D Lawrence -
2009 Poster: On Invariance in Hierarchical Models »
Jake Bouvrie · Lorenzo Rosasco · Tomaso Poggio