1 of 66

Accelerating Recursive Partition-Based Causal Structure Learning

¹Department of Computer Science and Engineering, University of Dhaka, Bangladesh

²School of Electrical and Computer Engineering, Purdue University, USA

³Department of Computer Science and Engineering, University of South Carolina, USA

Md Musfiqur Rahman¹

Research Assistant

musfiq14shohan@gmail.com

@musfiq_shohan

Ayman Rasheed¹

Research Assistant

aymanrasheed7

@gmail.com

Md. Mosaddek Khan¹

Assistant Professor

mosaddek@du.ac.bd

Mohammad Ali Javidian²

Postdoctoral Scholar

mjavidia@purdue.edu

@ali_javidian

Pooyan Jamshidi³

Assistant Professor

pjamshid@cse.sc.edu

@PooyanJamshidi

Md. Mamun-Or-Rashid¹

Professor

mamun@cse.du.ac.bd

2 of 66

Correlation does not imply causation!

2

Observational Data

Existing machine learning approaches

3 of 66

Correlation does not imply causation!

3

Observational Data

Existing machine learning approaches

Causal Inference

4 of 66

Correlation does not imply causation!

4

Observational Data

Existing machine learning approaches

Causal Inference

Incorrect decision-making!

5 of 66

Correlation does not imply causation!

5

Observational Data

Existing machine learning approaches

Causal Inference

Incorrect decision-making!

Causal structures/graphs

6 of 66

Causal Graphs and Causal Discovery

Causal graphs: A directed acyclic graph (DAG), G = (V,E)

V= {v₁, v₂, …, v_n} is a set of variables and E is a set of directed edges.
Each edge u → v represents cause and effect relation

6

7 of 66

Causal Graphs and Causal Discovery

Causal graphs: A directed acyclic graph (DAG), G = (V,E)

V= {v₁, v₂, …, v_n} is a set of variables and E is a set of directed edges.
Each edge u → v represents cause and effect relation

Causal discovery: Identifying causal relationships from large quantities of data

A data sample set D
T represents the true graph or ground truth

7

8 of 66

How we infer causal relations.

D-separation

8

9 of 66

How we infer causal relations.

D-separation

9

10 of 66

How we infer causal relations.

D-separation

10

11 of 66

How we infer causal relations.

D-separation

When controlled experiments are not possible.
Applications: 1. Gene regulatory network 2. Medical decision support systems

11

12 of 66

Recursive Causal Discovery is appropriate for large problems.

Constraint-based methods with conditional independence tests
Recursive split-and-merge strategies

12

13 of 66

Recursive Causal Discovery is appropriate for large problems.

Constraint-based methods with conditional independence tests
Recursive split-and-merge strategies

13

14 of 66

Recursive Causal Discovery is appropriate for large problems.

Constraint-based methods with conditional independence tests
Recursive split-and-merge strategies

14

15 of 66

Recursive Causal Discovery is appropriate for large problems.

Constraint-based methods with conditional independence tests
Recursive split-and-merge strategies

15

16 of 66

Recursive Causal Discovery is appropriate for large problems.

Constraint-based methods with conditional independence tests
Recursive split-and-merge strategies

16

17 of 66

Recursive Causal Discovery is appropriate for large problems.

Constraint-based methods with conditional independence tests
Recursive split-and-merge strategies

17

18 of 66

Benchmark algorithms are not perfect. Therefore, they execute refinement steps to remove undesired/redundant edges. But these refinement procedures are very expensive.

18

19 of 66

Existing approaches experience expensive refinement.

SADA

Costly partitioning with violation. Removes the less significant edges.

19

20 of 66

Existing approaches experience expensive refinement.

SADA

Costly partitioning with violation. Removes the less significant edges.

CAPA

Severe execution time overhead due to the third partition.

20

21 of 66

Existing approaches experience expensive refinement.

SADA

Costly partitioning with violation. Removes the less significant edges.

CAPA

Severe execution time overhead due to the third partition.

CP

D-separation violation. CI-tests for every pair of variables.

21

22 of 66

The Dsep-CP algorithm

22

In terms of contributions, Dsep-CP:

Improves the scalability without sacrificing the solution quality

23 of 66

The Dsep-CP algorithm

23

In terms of contributions, Dsep-CP:

Improves the scalability without sacrificing the solution quality
Explores d-separation violation and the graphical analysis for the false edges.

24 of 66

The Dsep-CP algorithm

24

In terms of contributions, Dsep-CP:

Improves the scalability without sacrificing the solution quality
Explores d-separation violation and the graphical analysis for the false edges.
Illustrates a substantial reduction in execution time up to 14% (and 86% reduction in CI-tests during refinement)

25 of 66

Preliminaries for Dsep-CP algorithm

Y-structure

25

26 of 66

Preliminaries for Dsep-CP algorithm

Y-structure
Independence Matrix

26

1⟂5 | {4}

27 of 66

The Dsep-CP Algorithm: The improved recursive learning

Find Causal Partitions (Line 4)

27

28 of 66

The Dsep-CP Algorithm: The improved recursive learning

Find Causal Partitions (Line 4)
Recursive Dsep-CP (Line 9-10)

28

29 of 66

The Dsep-CP Algorithm: The improved recursive learning

Find Causal Partitions (Line 4)
Recursive Dsep-CP (Line 9-10)
Dsep-CP Refinement (Line 12)

29

30 of 66

The Dsep-CP starts with a variable set and observational data

30

31 of 66

Finds efficient causal partitions to split the variable set.

31

32 of 66

Recursively solves the sub-problems with PC algorithm

32

PC algorithm is not always efficient.

33 of 66

Merges the discovered sub-graphs (May include false edges).

33

34 of 66