CS224W-Machine Learning with Graph-Link Prediction and Causality

The 3 rungs of the ladder of causation

Rung 1: Associational

• Traditional graph machine learning tasks
  • Assume $X \nVDash Y$
  • Task: Predict output $Y$ form input $X$
  • Data: samples of $(X,Y)$

Background: Inverse Transform Sampling

• Data generation algorithm:
  • Let $U_X \sim \text{Uniform}(0,1)$ be a random uniform value in the interval $[0,1]$
  • Then,

  $$X:=F^{-1}_X (U_X)$$

  • Exponential distribution example: $P(X \leq x) = F_X(x) = 1-e^{-\lambda x}$ with inverse $x = F^{-1}_X (U_X) = -\frac{1}{\lambda} \ln (1-U_X)$

  

Rung 2: Interventional (cont)

Imagine two hypothetical data generators for

do $(X=x)$ changes $f_x$ to a constant in data generation

Rung 3: Counterfactual

Imagine two hypothetical data generators for

Now assume we know $X=x'$, $Y=y'$. This knowledge changes distribution of $U_x$ and $U_y$

Casual DAG

• Representing causal dependencies using graphs (example in the extra notes)
  • $S = \text{Kidney stone size}$
  • $T = \text{Treatment type}$
  • $Y = \text{Treatment outcome}$

  $$\begin{align*} S &= F_S^{-1}(U_{stone\ size})\\ T &= F_T^{-1}(S,U_{treatment})\\ Y&=F_C^{-1}(T,S,U_{outcome}) \end{align*}$$

  where $U_{stone \ size}, U_{treatment},U_{outcome} \in [0,1]$ are independent variables.

The above data generation can be described by an execution graph, called the causal Directed Acyclic Graph (DAG):

Causality Challenge: Identifiability

Link prediction for decision-making interventions (e.g., search & recommendations) tends to be causal

Importance of Causality in Decision-making

Zillow House Offer Example

Biomedical Experiment Causal Graph

Other Applications of Causality in Graph Learning

(Out-of-distribution Graph Tasks)

Consider an out-of-distribution graph classification task

• Training data: $(G^{tr},Y^{tr})$

• Test data: Predict $Y^{te}$ given $G^{te}$,under $P(Y^{tr}|G^{tr}) = P(Y^{te}|G^{te})$ and $supp(G^{tr}) \neq supp (G^{te})$

• where $supp(G):=\{\forall G: P(G)>0\}$

Differences between In-distribution and Out-of-distribution tasks

Out-of-distribution tasks are a mix of associational and counterfactual tasks

• Out-of-distribution tasks are associational

Data: $(X^{tr},Y^{tr})$

Task: Predict $Y ^{te}$ given $X^{te}$ under $P(Y^{tr} | X^{tr}) = P(Y^{te}| X^{te})$

• But the learning is counterfactual
  • Without examples from graphs in test $G^{te}$
  • The classifier must build a correct predictor for unseen graph sizes

  $$Y(N=n)|N=n^{tr},G=g^{tr},Y=y^{tr}$$

Why is Graph ODD Learning a Counterfactual Task?

Example:

A Causal Mechanism for Graph Sizes

• Graph fromation process (Graphon):
  • Graph label $Y$ is a function of the graph model $W$ & some random noise
  • Graph size $N^{tr}(N^{te})$ is a function of “environment” $E^{tr}(E^{te})$ only
  • Train (test) graphs are generated by $W$ and $E^{tr} (E^{te})$ with same random noises.

  

Link Prediction

Temporal Graph Representation Learning is Observational

• Equivalence between two temporal graph representation learning frameworks:
  • Time-and-graph representations
  • Time-then-graph representations

• In general, time-and-graph and time-then-graph are equally expressive

• Using Message Passing GNNs (MP-GNNs), time-then-graph are more expressive than time-and-graph

Time-then-graph more expressive than Time-and-graph (when using MP-GNNs)

Causality & Link Prediction

Link Prediction as an exposure

Task: Link Creation outcome

Causal Identifiability

Graph Formation Process Key to Understand Effect of Exposures

Graph Formation Processes

Latent Factor Graph Formation