Chapter 8 - Granger - Causality - Among - Graphs - 4

Chapter 1
Granger Causality Among Graphs
Lucas Ribeiro da Silva
Abstract Causality is a key concept when we try to evaluate graphs in a temporal

perspective, in this chapter we introduce a classical and well consolidated method
for time-series causality, known as Granger Causality, and then we translate this
method for graphs time series based in random graph models and spectral analysis
to determine whether one model forecasts another.
1.1 Classical Vector Autoregressive Model
1.1.1 Univariate Vector Autoregressive Model
In time-series analysis one assumption that one can make is that given a time-series
𝑌 a possible estimator for value of 𝑌 at the time-step 𝑡, denoted by 𝑦 𝑡 , is by analysing
the values at previous steps {𝑦 𝑡 −1 , 𝑦 𝑡 −2 , ..., 𝑦 𝑡 −𝑛 } transformed by some function 𝑓 (.),
we can write this problem in the following form:
𝑦ˆ𝑡 = 𝑓 (𝑦 𝑡 −1 , 𝑦 𝑡 −2 , ..., 𝑦 𝑛 ) (1.1)

This process is known as Vector Autoregressive Model (VAR)
Ideally 𝑦ˆ𝑡 = 𝑦 𝑡 when 𝑓 (.) is perfectly fitted for every 𝑡 of some arbitrary set 𝑁,
since this perfect transformation is not practically feasible, we define 𝑦ˆ𝑡 as:
𝑦ˆ𝑡 = 𝑦 𝑡 + 𝑒𝑟𝑟𝑜𝑟 𝑡 (1.2)

Such that 𝑒𝑟𝑟𝑜𝑟 𝑡 is uncorrelated with some 𝑒𝑟𝑟𝑜𝑟 𝑠 when estimating 𝑦 𝑠 for 𝑡¬𝑠.
In broad terms 𝑓 (.) can be any function and the number of time-steps 𝑛 belongs
to N, for simplicity, in this chapter, we will limit the use of VAR model such that
Lucas Ribeiro da Silva

Name, Address of Institute, e-mail: lucasgiachini@gmail.com
3
4 Lucas Ribeiro da Silva
𝑓 (.) is linear and 𝑛 is a finite number. Using these bounds we can write the equation
1.1 in the following form:
𝑦 𝑡 = 𝛼1 𝑦 𝑡 −1 + 𝛼2 𝑦 𝑡 −2 + ... + 𝛼𝑛 𝑦 𝑛 + 𝑒𝑟𝑟𝑜𝑟 (1.3)
1.1.2 Multivariate Vector Autoregressive Model
In the last section (1.1.1) we assume the prediction of one time-series, if multiple
time-series is considered we can rewrite the equation 1.3 considering K time-series:
𝑦 𝑘,𝑡 = 𝛼 𝑘,1 𝑦 𝑘,𝑡 −1 + 𝛼 𝑘,2 𝑦 𝑘,𝑡 −2 + ... + 𝛼 𝑘,𝑛 𝑦 𝑘,𝑛 + 𝑒𝑟𝑟𝑜𝑟 𝑘 , 𝑘 = 1, ..., 𝐾 (1.4)
We can write these K time-series in a vector formulation, let,

𝑇
yt = 𝑦 1𝑡 . . . 𝑦 𝐾𝑡 (1.5)
 𝛼11,𝑖 . . . 𝛼1𝐾 ,𝑖 
 
Ai =  ... . . . ..  (1.6)

 . 
𝛼𝐾1,𝑖 . . . 𝛼𝐾 𝐾 ,𝑖 
 
𝑇
errort = 𝑒𝑟𝑟𝑜𝑟 1𝑡 . . . 𝑒𝑟𝑟𝑜𝑟 𝐾𝑡 (1.7)
Then the equation 1.4 can be formulated as
yt = A1 yt−1 + A2 yt−2 + ... + An yt−n + errort (1.8)

These representations, 1.4 and 1.8, will be the base equation to represent our
time-series throughout the chapter.
1.2 Classical Granger Causality
In classical Granger causality we use the auto regressive model equation defined
above to determine if a time series temporarily correlates with another, Granger’s
main ideia is that, if there is a causality relation between two time series then the
caused time series should improve its predictions if is considered the information of
the cause time series.
The mathematical formulation is the following:
Let 𝑡 be time steps and 𝑋 and 𝑌 stationary time series, we can estimate 𝑌𝑡 through
a VAR model such as equation 1.4:
1 Granger Causality Among Graphs 5
𝑦 𝑡 = 𝑦 𝑡 −1 + 𝑦 𝑡 −2 + ... + 𝑦 𝑡 −𝑛 + 𝑥 𝑡 −1 + 𝑥 𝑡 −2 + ... + 𝑥 𝑡 − 𝑝 + 𝑒𝑟𝑟𝑜𝑟 𝑡 ,𝑦 (1.9)
Given 𝑛 steps of the 𝑌 and 𝑝 steps of the 𝑋 time series we say that X Granger
causes Y if we can fit a VAR model as:
𝑦 𝑡 = 𝑦 𝑡 −1 + 𝑦 𝑡 −2 + ... + 𝑦 𝑡 −𝑛 + 𝑥 𝑡 −1 + 𝑥 𝑡 −2 + ... + 𝑥 𝑡 − 𝑝 + 𝑒𝑟𝑟𝑜𝑟 𝑡 ,𝑥 𝑦 (1.10)
Such that 𝑒𝑟𝑟𝑜𝑟 𝑡 , 𝑥 𝑦 < 𝑒𝑟𝑟𝑜𝑟 𝑡 ,𝑦
1.3 Granger Causality for Graphs
To use the concept of Granger Causality in Graphs we must define a numeric repre-
sentation of a graph at a given time 𝑡, such as betweenness, closeness, eigenvectors,
degree and so on. Ribeiro, et al [1] propose the use of the spectral radius (highest
eigenvalue) of the Graph as a representation that best captures the features of random
graphs models to check for Granger causality and that is the property we are going
to adopt in this chapter as coefficients to the VAR model.
In that way, given a random model graph G with a spectral radius 𝐺 (.) we define
a random variable Θ which we can draw samples 𝜃˜ as parameters for 𝐺 . To analyse
the graph time series of length 𝑇 we calculate the spectral radius 𝐺 ( 𝜃) ˜ for each
time step resulting in a set of parameters 𝜃˜ = {𝜃 1 , 𝜃 2 , 𝜃 3 , ..., 𝜃 𝑇 } and the respective
spectral radius 𝐺˜ ( 𝜃) ˜ = {𝐺 (𝜃 1 ), 𝐺 (𝜃 2 ), 𝐺 (𝜃 3 ), ..., 𝐺 (𝜃 𝑇 )}
For example, let 𝐺 1𝑡 and 𝐺 2𝑡 be a time series of Erdös-Rényi random graphs
with length 𝑇 and parameters 𝜃 1𝑡 and 𝜃 2𝑡 drown from the random variables Θ1
and Θ2 , we calculate the respective spectral radius at each time step 𝐺 [˜1] ( 𝜃˜1 ) =
{𝐺 1 (𝜃 11 ), 𝐺 1 (𝜃 12 ), 𝐺 1 (𝜃 13 ), ..., 𝐺 1 (𝜃 1𝑇 )} and 𝐺˜2 ( 𝜃˜2 ) = {𝐺 2 (𝜃 21 ), 𝐺 2 (𝜃 22 ), 𝐺 2 (𝜃 23 ), ..., 𝐺 2 (𝜃 2𝑇 )}
and then we can calculate the Granger causality between 𝐺 1 and 𝐺 2 based on sam-
ples of 𝐺˜1 ( 𝜃˜1 ) and 𝐺˜2 ( 𝜃˜2 ), applying a statistical test on the graph time series (more
on that on section 1.4)
1.4 Statistical Tests for Granger Causality
Here we present the Wald Test and the Bootstrap Procedure to evaluate if given two
time series 𝐴 and 𝐵 one Granger causes another (Reject 𝐻0 ) or not (Accept 𝐻0 ),
through a hypothesis test.
Let 𝛽 be the matrix of autoregressive coefficients of the VAR model and C is a
matrix of contrasts, we can write the hypothesis test as:
(
𝐻0 : C𝛽 = 0
(1.11)
𝐻1 : C𝛽¬0
6 Lucas Ribeiro da Silva
Which means that we reject 𝐻0 if there is Granger causality among time series or
accept 𝐻0 otherwise.
1.4.1 Wald Test
As proposed in [1], to test if a 𝑦 𝑖,𝑡 Granger causes 𝑦 𝑗,𝑡 , we can look into the
coefficients of the VAR and test if it have zero constraints, that is the proposal of the
Wald test.
First we define a c matrix of dimension (1 × 𝑘) with one in 𝑖th position and zero
otherwise and 0 a matrix of zeros of dimension (1 × 𝑘), then we can define our
matrix of contrasts as:
𝑐
 0 0
...
0 𝑐 0
...
C = . (1.12)

.. .. 
 .. . . 
 
0 0 . . . 𝑐 

Let be 𝛽ˆ𝑗 be vector of coefficients for the VAR model of 𝑦 𝑗,𝑡 of dimension (𝑘 𝑝×1)
and Σ̂ 𝑗, 𝑗 be the 𝑗th column of the 𝑗th row of the covariance matrix Σ̂, then we can
define the Wald test as:
(C 𝛽ˆ𝑗 ) ′ (C(Z′ Z) −1 C′ ) −1 (C 𝛽ˆ𝑗 )

𝑊= (1.13)
Σ̂ 𝑗, 𝑗
Under the null hypotheses (𝐻0 ), 𝑊 will follow a 𝜒2 distribution with 𝑟𝑎𝑛𝑘 (C)
degrees of freedom.
1.4.2 Bootstrap Procedure
The bootstrap procedure is used mainly when the time series number of steps is short
and the Wald’s assumption of the number of time steps going to infinite does not
hold true. Then [1] suggests the use of bootstrap with the exactly following steps:
1. Fit the VAR model.

2. Estimate the VAR model coefficients and residuals.
3. Resample with replacement the residuals obtained in step 2.
4. To test the Granger causality from graph 𝑦 𝑖,𝑡 to graph 𝑦 𝑗,𝑡 , estimate the Wald’s
test statistic 𝑊 and then construct the model under the null hypothesis.
5. Resample the residuals obtained in step 2 and use the model specified in step 4
to simulate a bootstrap multivariate time series.
6. Estimate the coefficients 𝑎 𝑙∗
𝑖, 𝑗 of the bootstrap time series obtained in step 5 and
calculate Wald’s test statistic 𝑊 ∗ .
1 Granger Causality Among Graphs 7
7. Go to step 3 until you obtain the desired number of bootstraps.

8. Estimate the 𝑝-value by calculating the fraction of replicates of 𝑊∗ on the boot-
strap dataset, which is at least as large as the observed statistic 𝑊 on the original
dataset.

Chapter 8 - Granger - Causality - Among - Graphs - 4

Uploaded by

Copyright:

Available Formats

Chapter 8 - Granger - Causality - Among - Graphs - 4

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Chapter 8 - Granger - Causality - Among - Graphs - 4

Uploaded by

Copyright:

Available Formats

Chapter 1

Granger Causality Among Graphs

Lucas Ribeiro da Silva

Abstract Causality is a key concept when we try to evaluate graphs in a temporal

1.1 Classical Vector Autoregressive Model

1.1.1 Univariate Vector Autoregressive Model

𝑦ˆ𝑡 = 𝑓 (𝑦 𝑡 −1 , 𝑦 𝑡 −2 , ..., 𝑦 𝑛 ) (1.1)

𝑦ˆ𝑡 = 𝑦 𝑡 + 𝑒𝑟𝑟𝑜𝑟 𝑡 (1.2)

Lucas Ribeiro da Silva

𝑦 𝑡 = 𝛼1 𝑦 𝑡 −1 + 𝛼2 𝑦 𝑡 −2 + ... + 𝛼𝑛 𝑦 𝑛 + 𝑒𝑟𝑟𝑜𝑟 (1.3)

1.1.2 Multivariate Vector Autoregressive Model

We can write these K time-series in a vector formulation, let,

yt = A1 yt−1 + A2 yt−2 + ... + An yt−n + errort (1.8)

1.2 Classical Granger Causality

𝑦 𝑡 = 𝑦 𝑡 −1 + 𝑦 𝑡 −2 + ... + 𝑦 𝑡 −𝑛 + 𝑥 𝑡 −1 + 𝑥 𝑡 −2 + ... + 𝑥 𝑡 − 𝑝 + 𝑒𝑟𝑟𝑜𝑟 𝑡 ,𝑦 (1.9)

𝑦 𝑡 = 𝑦 𝑡 −1 + 𝑦 𝑡 −2 + ... + 𝑦 𝑡 −𝑛 + 𝑥 𝑡 −1 + 𝑥 𝑡 −2 + ... + 𝑥 𝑡 − 𝑝 + 𝑒𝑟𝑟𝑜𝑟 𝑡 ,𝑥 𝑦 (1.10)

Such that 𝑒𝑟𝑟𝑜𝑟 𝑡 , 𝑥 𝑦 < 𝑒𝑟𝑟𝑜𝑟 𝑡 ,𝑦

1.3 Granger Causality for Graphs

1.4 Statistical Tests for Granger Causality

1.4.1 Wald Test

(C 𝛽ˆ𝑗 ) ′ (C(Z′ Z) −1 C′ ) −1 (C 𝛽ˆ𝑗 )

1.4.2 Bootstrap Procedure

1. Fit the VAR model.

7. Go to step 3 until you obtain the desired number of bootstraps.

You might also like