50 years Univerity of Lübeck

Institute for Theoretical Computer Science

Causality: an algorithmic framework and a computational complexity perspective


Project Description

Project name
Causality: an algorithmic framework and a computational complexity perspective
Leadership
Prof. Dr. Maciej Liskiewicz
Duration and Funding
Started 2016, estimated completion in 2020. Supported by the DFG.
Project staff
Benito Bela van der Zander,
Cooperating partner
Dr. Johannes Textor
Abstract

Establishing cause-effect relationships is a fundamental goal of empirical science, and finding the causes of diseases, economic crises, or other complex phenomena is of great importance for policy-making. Such causal inference typically requires combining observed and interventional data with existing knowledge. The structural approach to causal inference, developed over the past decades by Judea Pearl and others, allows researchers to model complex causal relationships, reason about their implications, and estimate causal effects of interest. In this approach, causal knowledge is encoded using directed or partially directed graphs, which is an intuitive representation that is readable by non-specialists.

The graphical causal modeling approach currently receives substantial attention in Epidemiology, Sociology and other disciplines, but is not yet widely applied. An important barrier to its application is of algorithmic nature: Several key results of structural causality are either not general, i.e. do not apply for certain types of inputs, or are proved non-constructively, such that efficient algorithms to find solutions are lacking. In collaboration with scientists from application areas, we have identified several problems of real-world importance that require more general and/or more efficient solutions. The goal of this proposal is to study those problems from an algorithmic and computational complexity perspective.

Our main focus will be on questions concerning identification and estimation of causal effects, with a secondary focus on learning possible causal structures from data. The graphical language used in structural causal modeling allows us to apply discrete- and graph-algorithmic techniques as well as advanced methods of computational complexity theory. While we expect to obtain some negative outcomes like NP-hardness results, the main goal is to provide effective algorithms, and with our collaborators we aim to feed our positive algorithmic results back into the application areas in the form of working software packages.

Project-Publications

2018

  • Benito van der Zander, Maciej Liskiewicz, Johannes Textor:
    Separators and adjustment sets in causal graphs: Complete criteria and an algorithmic framework.
    Technischer Bericht arXiv:1803.00116 (2018), arXiv preprint, 2018.
    PDF anzeigen

2017

  • Sebastian Berndt, Maciej Liskiewicz, Matthias Lutter, Rüdiger Reischuk:
    Learning Residual Alternating Automata.
    Electronic Colloquium on Computational Complexity (ECCC), 24(46)2017.
    Website anzeigen | Zusammenfassung anzeigen
  • Sebastian Berndt, Maciej Liskiewicz, Matthias Lutter, Rüdiger Reischuk:
    Learning Residual Alternating Automata.
    Proc. 31st AAAI Conference on Artificial Intelligence (AAAI 2017), S. 1749-1755. AAAI Press, 2017.
    Website anzeigen | Zusammenfassung anzeigen
  • Maciej Liskiewicz, Matthias Lutter, Rüdiger Reischuk:
    Proper Learning of k-term DNF Formulas from Satisfying Assignments.
    Electronic Colloquium on Computational Complexity (ECCC), 24(114)2017.
    Website anzeigen | Zusammenfassung anzeigen
  • Martin R. Schuster, Maciej Liskiewicz:
    New Abilities and Limitations of Spectral Graph Bisection.
    Technischer Bericht 1701.01337, arXiv, 2017.
    Website anzeigen | Zusammenfassung anzeigen
  • Martin R. Schuster, Maciej Liskiewicz:
    New Abilities and Limitations of Spectral Graph Bisection.
    In 25th Annual European Symposium on Algorithms, (ESA) 2017, LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017.

2016

  • Johannes Textor, Benito van der Zander, Mark S. Gilthorpe, Maciej Liskiewicz, George T.H. Ellison:
    Robust causal inference using Directed Acyclic Graphs: the R package ’dagitty’.
    International Journal of Epidemiology, 6(45):1887-1894, 2016.
    Website anzeigen
  • Benito Van der Zander, Maciej Liskiewicz:
    On Searching for Generalized Instrumental Variables.
    In Proceedings of the The 19th International Conference on Artificial Intelligence and Statistics (AISTATS'16), S. 1214-1222. JMLR Proceedings, 2016.
    Website anzeigen
  • Benito van der Zander, Maciej Liskiewicz:
    Separators and Adjustment Sets in Markov Equivalent DAGs.
    In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence (AAAI'16), Phoenix, Arizona USA, S. 3315-3321. AAAI Press, 2016.
    Website anzeigen

2015

  • Johannes Textor, Alexander Idelberger, Maciej Liskiewicz:
    On the Faithful DAGs of a Dependency Graph.
    In Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence (UAI'15), S. 882-891. AUAI Press, 2015.
    PDF anzeigen
  • Benito van der Zander, Johannes Textor, Maciej Liskiewicz:
    Efficiently Finding Conditional Instruments for Causal Inference.
    In (IJCAI'15), Proceedings of the 24th International Joint Conference on Artificial Intelligence, Buenos Aires, Argentina, July 25-31, 2015, S. 3243-3249. AAAI Press / International Joint Conferences on Artificial Intelligence, 2015.
    PDF anzeigen

Project-Development

In the context of this project the following software library was developed
DAGitty tool