STAT 542: Multivariate Analysis Spring 2021

Lecture 2: Graphs and Networks

Instructor: Yen-Chi Chen

2.1 Introduction

Graphical models and networks models are important topics in the modern statistical and machine learning
research. Both methods use the graphs a lot but they are quiet different ideas. In graphical models, graphs
are not our data but are tools to determine relationship among entries of a random vector. In network
models, the graph are the data (i.e., we observe the network) and we want to make inference with this type
of data (known as network data).

2.2 Undirected graphs

A graphical model uses a graph to represent the conditional independence between a set of RVs. We start
with the concepts of graphical models and later we will discuss how this model is constructed. Suppose that
X⊥ ⊥ Y |Z then we have

pXY Z (x, y, z) = p(x, y|z)p(z) = p(x|z)p(y|z)p(z) = g(x, z)h(y, z)

for some functions g and h. We then use the following graph to represent it their relation:

X Z Y

The edge X − Z is drawn because the density factorization has a factor, namely g(x, z), that depends on
both x and z. Similarly, the edge Z − Y is drawn because of factor h(y, z).
Note that there is no edge between X − Y . The only path from X to Y passes through Z. Later we will see
that in the graphical model, this implies conditional independence of X and Y given Z.
The above is the basic definition of a graphical model. We now discuss how this model is constructed. The
graphical model relies on two properties: graph factorization (how the distribution of a random variable is
associated with a graph) and Markov properties (how the graph represents conditional independence).

2.2.1 Graph factorization and clique decomposition

A graph G and a random vector X may or may not have any relationship. The notion of graph factorization
connects the joint PDF/PMF of X using a graph G.
Formally, a graph G = (V, E) is a pair consisting of a (finite) vertex set V and an edge set E ⊂ V × V . Here,
we consider undirected graphs where an edge v − w is represented by the fact that (v, w) and (w, v) are both
in E. We assume no self-loops, so (v, v) ∈
/ E for all v ∈ V .

2-1
2-2 Lecture 2: Graphs and Networks

Example 1: If V = {1, 2, 3, 4} and

E = {(1, 2), (2, 1), (2, 3), (3, 2), (2, 4), (4, 2), (3, 4), (4, 3)}

then the picture is

1 2 3

A non-empty subset of nodes A ⊆ V is complete if there is an edge v − w between any pair of nodes v, w ∈ A.
Complete sets are also called cliques. Sometimes, clique refers to an inclusion-maximal complete set. In this
case, we often call it a maximal clique. We denote the family of all complete sets/maximal cliques as C(G).
In the above example, complete sets/cliques are

{1}, {2}, {3}, {4}, {1, 2}, {2, 3}, {2, 4}, {3, 4}, {2, 3, 4}.

And maximal clinques are {1, 2}, {2, 3, 4}.

Definition 2.1 Let X = (X1 , · · · , Xd ) be a random vector and G = (V, E) be a graph where V = {V1 , · · · , Vd }
is the node set. We say that X that factorizes over/with respect to a graph G if there exists (potential)
functions {ψC ≥ 0 : C ∈ C(G)} such that
1 Y
p(x1 , · · · , xd ) = ψC (xC )
Z
C∈C(G)
RQ
and Z = C∈C(G) ψC (xC )dx1 , · · · dxd is known as the partition function.

Note that we call the distribution of X a Gibbs distribution with respect to G if

 
1 Y 1 X
p(x1 , · · · , xd ) = ψC (xC ) = exp  log ψC (xC )
Z Z
C∈C(G) C∈C(G)

for some positive functions {ψC > 0 : C ∈ C(G)}.

Example 2: If the following graph is a graphical model of random variables X = (X1 , X2 , X3 , X4 ):

4 3

1 2

then
pX (x1 , x2 , x3 , x4 ) = ψ12 (x1 , x2 )ψ23 (x2 , x3 )ψ34 (x3 , x4 )ψ14 (x1 , x4 ).

Definition 2.1 defines the meaning of graph factorization that connects the distribution of a random vector
X to a graph G. However, it does not imply anything about the conditional independence. The graph
factorization and conditional independence are associated via the Markov properties of graphs.
Lecture 2: Graphs and Networks 2-3

2.2.2 Markov properties

There are three Markov properties that associates the graph factorization to the notion of conditional inde-
pendence. We start with the most common type of Markov properties–global Markov property.
The global Markov property relies on the notion of path and separation of a graph. A path in G is a
sequence of distinct nodes v0 , v1 , . . . , vd s.t. there is an edge between any two consecutive nodes, vi−1 − vi
for i = 1, . . . , n. Let A, B, C ⊂ V be subsets of nodes. Then C separates A and B if every path from a
node v ∈ A to a node w ∈ B intersects C. For instance, in example 1, X2 separates X1 and (X3 , X4 ) and in
example 2, (X2 , X4 ) separates X1 and X3 .

Definition 2.2 (Global Markov Property) A probability distribution P for a random vector X = (X1 , · · · , Xd )
satisfies the global Markov property with respect to a graph G if for any disjoint vertex subsets A, B, and C
such that C separates A and B, then the random variables XA are conditionally independent of XB given
XC .

It is very easy to see that the graph factorization in definition (2.1) implies the global Markov property as
stated in the following theorem.

Theorem 2.3 (Global Markov theory) Suppose the distribution of X = (Xv : v ∈ V ) factorizes over
G = (V, E). Let A, B, C ⊂ V be subsets of nodes. Then

C separates A and B =⇒ XA ⊥
⊥ XB | XC .

A distribution that satisfies the global Markov property is said to be a Markov random field or Markov
network with respect to the graph. A more general type of Markov property is the local Markov property,
which is defined as follows.

Definition 2.4 (Local Markov Property) A probability distribution P for a random vector X = (X1 , · · · , Xd )
satisfies the local Markov property with respect to a graph G if the conditional distribution of a variable given
all its neighbor is independent of any other vertices. Namely, let N (j) = {Xi : Eij = 1} be the neighbors of
Xj . Then the local Markov property means that

P (Xj |X−j ) = P (Xj |XN (j) ),

where X−j = {Xi : i 6= j}.

A more general definition is the pairwise Markov property.

Definition 2.5 (Pairwise Markov Property) A probability distribution P for a random vector X =
(X1 , · · · , Xd ) satisfies the pairwise Markov property with respect to a graph G if for any two non-adjacent
vertices Xi and Xj (i.e., Eij = 0),
Xi ⊥⊥ Xj |XV \{i,j} .

Proposition 2.6 (Equivalence of Markov properties) For any undirected graph G and any distribu-
tion P , we have

Global Markov Property ⇒ Local Markov Property ⇒ Pairwise Markov Property.

2-4 Lecture 2: Graphs and Networks

The proof is very straight forward so we omit it.

Example: local Markov property but no global Markov property. Define binary random variables
X1 , · · · , X5 such that P (X1 = 1) = P (X5 = 1) = 12 and X2 = X1 and X4 = X5 and X3 = X2 X4 . You
can easily verify that the random vector satisfies the local Markov property. However, the global Markov
property is violated. To see this, consider the case of X3 = 0 and it is easy to see that P (x2 , x4 |X3 = 0) = 31
when (x2 , x4 ) = (1, 0), (0, 1), (0, 0). However, the marginal probability P (X2 = 0|X3 = 0) = P (X4 = 0|X3 =
0) = 32 . Thus,

1 4
P (X2 = 0, X4 = 0|X3 = 0) = 6= P (X2 = 0|X3 = 0) × P (X4 = 0|X3 = 0) =
3 9
so the global Markov property does not hold.
Example: pairwise Markov property but no local Markov property. Define binary random variables
X1 , X2 , X3 and X1 = X2 = X3 with P (X1 = 1) = 12 . The random vector X = (X1 , X2 , X3 ) has a very
degenerated PMF. Consider a graph G such that there is only one edge E23 = 1. Then you can easily
verify that X satisfies the pairwise Markov property with respect to G but not the local Markov property
(specifically, P (X1 = 1|X2 = 0, X3 = 0) = 0 6= P (X1 = 1) = 21 ). This example also shows a fact about the
Markov properties– the same distribution may satisfy a Markov property on different graphs! In the above
example, the same pairwise Markov property holds for another graph G0 with only a single edge E12 0
= 1 or
00 00
a graph G with only a single edge E13 = 1.
A good news is that when the PDF/PMF is positive, the three Markov properties are equivalent.

Proposition 2.7 For a distribution P with a PDF/PMF p that is positive, then the three Markov properties
are equivalent.

The above proposition relies on the intersection lemma from

Pearl, J., & Paz, A. (1985). Graphoids: A graph-based logic for reasoning about relevance
relations. University of California (Los Angeles). Computer Science Department.

Lemma 2.8 (Intersection lemma; Pearl, J., & Paz (1985)) Suppose that for any subsets A, B, C, D ⊂
V we have
XA ⊥⊥ XB |XC∪D , XA ⊥ ⊥ XC |XB∪D ⇒ XA ⊥⊥ XB∪C |XD .
Then the three Markov properties are equivalent.

Proof:[Proof of Proposition 2.7]

Without loss of generality, we consider three variable cases: X = (X1 , X2 , X3 ). To use Lemma 2.8, we need
to show that
X1 ⊥⊥ X2 |X3 , X1 ⊥ ⊥ X3 |X2 ⇒ X1 ⊥ ⊥ {X2 , X3 }.

Assume the two conditional independence in the left-hand side of the above equation. Then we have

p(x1 , x2 , x3 ) = f13 (x1 , x3 )f23 (x2 , x3 ) = g12 (x1 , x2 )g23 (x2 , x3 )

for some functions f13 , f23 , g12 , g23 . Thus,

f13 (x1 , x3 )f23 (x2 , x3 ) f23 (x2 , x3 )

g12 (x1 , x2 ) = = f13 (x1 , x3 ) .
g23 (x2 , x3 ) g23 (x2 , x3 )
Lecture 2: Graphs and Networks 2-5

An interesting implication from the above equation is that the left-hand side does not depend on x3 so this
holds for any x3 . WLOG, we choose x3 = 0 and this leads to
f23 (x2 , 0)
g12 (x1 , x2 ) = f13 (x1 , 0) = h(x1 )k(x2 ).
g23 (x2 , 0)
Putting this back to the joint PDF/PMF, we obtain
p(x1 , x2 , x3 ) = g12 (x1 , x2 )g23 (x2 , x3 ) = h(x1 )k(x2 )g23 (x2 , x3 ),
which implies X1 ⊥
⊥ {X2 , X3 }. So by Lemma 2.8, the three Markov properties are equivalent.

2.2.3 Hammersley-Clifford theorem

Theorem 2.3 shows that if the distribution of a random vector X factorizes over a graph, then it satisfies
the global Markov property. However, the reverse direction is unclear to us. Specifically, we want to know

if a random vector satisfies the global Markov property with respect to a graph, can it always be
factorized with respect to the graph?

The following theorem, known as the Hammersley-Clifford (or Hammersley-Clifford-Besag) theorem, provides
a positive answer to this question.

Theorem 2.9 (Hammersley-Clifford (1971)) Suppose that G = (V, E) is a graph and X1 , · · · , Xd are
random variables that take on a finite number of values. If P (x) > 0 is strictly positive and satisfies the local
Markov property with respect to G, then it factors with respect to G.

The following paper is the original paper that states this theorem:

Hammersley, J. M., & Clifford, P. (1971). Markov fields on finite graphs and lattices.

Note that they do not publish this paper in a journal article but you can still find the original manuscript
online.
A formal paper that includes this theorem (and improves the proof and mentioned the generalization to
continuous random vector) is the following paper:

Besag, J. (1974). Spatial interaction and the statistical analysis of lattice systems. Journal of
the Royal Statistical Society: Series B (Methodological), 36(2), 192-225.

Although the Hammersley-Clifford theorem only proves the case for discrete random variables, the result
an be generalized to continuous random variables as well. The Hammersley-Clifford theorem together with
Proposition 2.7 imply the following conclusion:

For a random vector X with a positive PDF/PMF, then

satisfying Markov Properties ⇔ factorizing with respect to G.

Thus, Theorem 2.3 together with the Hammersley-Clifford theorem provide the foundation of graphical
model that we can interchangably use graph factorization and conditional independence. This is why the
Hammersley-Clifford theorem is sometimes referred to as the fundamental theorem of graphical models.
2-6 Lecture 2: Graphs and Networks

2.2.4 Gaussian graphical model

Consider the problem of a Gaussian random vector X = (X1 , X2 , · · · , Xp ) ∈ Rp with a mean vector µ and
a covariance matrix Σ. Assume that Σ is positive definite, then the joint PDF can be written as
 
1 1
pX (x) = p exp − (x − µ)T Σ−1 (x − µ) ,
(2π)p det(Σ) 2

where x = (x1 , · · · , xp ).
In this model, there are two parameters µ and Σ. What does the conditional independence X1 ⊥
⊥ X2 |X3 , · · · , Xp
tell us about the underlying parameters?
Using the graph factorization, we can factorize pX into

pX (x) = g(x1 , x3 , x4 , · · · , xp )h(x2 , x3 , · · · , xp ).

Therefore,
1
log pX (x) = g̃(x1 , x3 , x4 , · · · , xp ) + h̃(x2 , x3 , · · · , xp ) = − (x − µ)T Σ−1 (x − µ) + C0 ,
2
where C0 is a constant with respect to x.
Because
p
X
−1
T
(xi − µi )(xj − µj ) Σ−1


(x − µ) Σ (x − µ) = ij
,
i,j=1

we conclude that Σ−1 12 = 0. Namely, for a Gaussian random vector, if we see the (i, j)-th element of the

inverse covariance matrix (also known as the precision matrix) is 0, we have the conditional independence
of Xi and Xj given the other elements.

2.2.5 Log-linear model

The log-linear model is a parametrization for the PMF of multinomials. Suppose that each Xj ∈ {0, 1, 2, · · · , mj −
1} for each j = 1, · · · , d and X = (X1 , · · · , Xd ) is the random vector of interest. Recall that G = (V, E) is
the graph such that V = {1, · · · , d}. The log-linear model expands the log PMF of X as
X
log p(x) = ψA (xA ), (2.1)
A⊂V

with the constraint that if a variable j ∈ A with xj = 0, ψA (xA ) = 0. Equation (2.1) is known as the log-
linear expansion of p(x). Although ψA (xA ) behaves like a function,Q it is a set of several parameters since the
variable(s) xA only takes discrete values. In fact, there are only j∈A (mj − 1) number of possible values of
ψA so it is often referred to as the parameter of a log-linear model. You can interpret the parameter/function
ψA as the (joint) interaction effect of variables in A.
A graphical log-linear model with respect to a graph G is the log-linear model such that ψA (xA ) is not
zero if and only if A is a clique. Moreover, a hierarchical log-linear model is a log-linear model such that
if ψA (xA ) = 0 implies ψB (xB ) = 0 for all B ⊃ A. Namely, a hierarchical log-linear model has a nested
structure that if a parameter ψA = 0, any parameter that is a superset of A must be 0. You can interpret
a hierarchical log-linear model as the model that any higher-order interaction exists only if all lower-order
interactions exist.
Lecture 2: Graphs and Networks 2-7

Lemma 2.10 A graphical log-linear model is hierarchical log-linear model but not vice versa.

Proof:
Suppose that for a graphical model of G with ψA = 0, this implies that A is not a clique in G. Thus, any
set B ⊃ A will not be a clique in G so the model is hierarchical.
Now consider a three variable log-linear model with

log p(x) = ψ1 (x1 ) + ψ2 (x2 ) + ψ3 (x3 ) + ψ12 (x1 , x2 ) + ψ13 (x1 , x3 ) + ψ23 (x2 , x3 ).

Clearly, this is a hierarchical model but not a graphical model (it will requires ψ123 (x1 , x2 , x3 ) 6= 0).

With the above lemma, we conclude that

graphical model ⇒ hierarchical model ⇒ log-linear (multinomial) model.

Ising model. The Ising model is a special case of hierarchical log-linear models. It is a hierarchical model
with binary variables with only pairwise interactions. Specifically, the Ising model is the case where
d
X X
log p(x) = θ i xi + θj,k xj xk . (2.2)
i=1 (j,k)∈E

Since the Ising model only contains pairwise interaction, it can be viewed as a discrete analogue of the
Gaussian graphical model. The Ising model is related to the logistic regression. By the local Markov
property, a random variable Xi only depends on its neighborhoods so the conditional probability
P
exp(θi + (i,j)∈E θi,j xj )
P (Xi = 1|X−i ) = P (Xi = 1|Xj , (i, j) ∈ E) = P ,
1 + exp(θi + (i,j)∈E θi,j xj )

where X−i is the collection of all variables except Xi .

Potts model. The Potts model is a generalized Ising model that allows variables to have m distinct
outcomes, i.e., Xi ∈ {0, 1, 2, · · · , m − 1} and the pairwise interaction contributes only if the two variables
are in the same ‘state’. Specifically, the joint PMF in the Potts model can be factorized as
d
X X
log p(x) = θ i xi + θj,k δ(xj , xk ), (2.3)
i=1 (j,k)∈E

where δ(a, b) = I(a = b). The Potts model is motivated by statistical mechanics in which each variable Xi
is a particle and a particle has m different states. In a stable scenario, two adjacent particles (particles are
variables Xi ’s) will avoid being in the same state. So the distribution can be modeled using the Potts model
with a negative θj,k .

2.3 Directed acyclic graphs

A graph where the edges are directional is called a directed graph. In statistics and machine learning, we
often focus on one particular directed graph called directed acyclic graphs (DAGs). A DAG is a directed
graph that has no directed loops (i.e., arrows do not form a loop). Directed graphical models are often viewed
2-8 Lecture 2: Graphs and Networks

X1 X1
X4 X4

X2 X2

X5 X5
X3 X3
Figure 2.1: Left: An example of a DAG with 5 variables. Right: The corresponding UG.

as a generative model. To illustrate the idea, consider 5 random variables X1 , · · · , X5 with the following
generative models:

X1 ∼ p1 (x1 )
X2 ∼ p2 (x2 )
X3 ∼ p3 (x3 )
X4 |X1 , X2 ∼ p4 (x4 |X1 , X2 )
X5 |X1 , X3 , X4 ∼ p5 (x5 |X1 , X3 , X4 ).

Then we can summarize this model using the left panel of Figure 2.1.
Formally, a random vector X factorized with respect to a DAG G if the joint density
d
Y
p(x1 , · · · , xd ) = p(xj |PAxj ),
j=1

where PAxj = {xk : there is an directed arrow/edge from Xk to Xj in G} is called the parent nodes of Xj
in the DAG.
Because of the popularity of DAG in the probability generative model, a DAG is also called a Bayesian
network. Note that a Bayesian network has nothing to do with Bayesian inference or Bayesian statistics; it
is just a graphical model that relied on Bayes rule to describe a probability distribution.
The DAG in the left panel of Figure 2.1 implies that the joint density can be written as

p(x1 , · · · , x5 ) = p(x5 |x1 , x3 , x4 )p(x4 |x1 , x2 )p(x3 )p(x2 )p(x1 ) = ψ1,3,4,5 (x1 , x3 , x4 , x5 )ψ1,2,4 (x1 , x2 , x4 )

so the corresponding undirected graphical model is the right panel of Figure 2.1 that has two maximal cliques
(1, 3, 4, 5) and (1, 2, 4).
More generally, we can always convert a DAG into an UG using the idea of moralizing. If there is an arrow
from note Xi to node Xj , we call Xi a parent (node) of Xj and Xj a child (node) of Xi . Note that every
node may have multiple parents and children.

Definition 2.11 The moral graph M of a DAG G is an undirected graph where there is an edge between
two vertices Xi and Xj if one of the following conditions met:
Lecture 2: Graphs and Networks 2-9

X2 X2 X2

X1 X3 X1 X3 X1 X3

Figure 2.2: Left and middle: Two DAGs. Right: The moral graph from both DAGs in the left two panels.

X2 X2

X1 X3 X1 X3

Figure 2.3: Left: A DAG that is similar to the left panel as Figure 2.2 but we reverse only one arrow’s
direction. Right: The moral graph from the DAG in the left panel.

• There is an edge between Xi and Xj in G.

• Xi and Xj are the parents of the same child node.

Informally, the moralized graph can be constructed by ‘marrying the parents’–we connect all parents of each
child node (and remove arrows) to form the corresponding undirected graph. Two different DAGs may have
the same moralized graph, as illustrated in Figure 2.2. Also, the arrow direction matters in the construction
of moral graph; Figure 2.3 shows an example that we only reverse one arrow’s direction in the DAG of the
left panel in Figure 2.2 and the resulting moral graph is different.

2.3.1 Hierarchical Bayes

A Bayesian hierarchical model is scenario that DAGs are often applied to. To illustrate the idea, we consider
the following example. Suppose that we have n individuals participating in an exam and their scores can
be summarizes using univaraite random variables X1 , · · · , Xn . We all know that scores are measurements

µ1 µ2 µ3 ··· µn

X1 X2 X3 ··· Xn

Figure 2.4: A DAG summarizing the relation among random variables X1 , · · · , Xn , µ1 , · · · , µn , θ described
in Section 2.3.1.
2-10 Lecture 2: Graphs and Networks

X2 X2

X1 X3 X1 X3

Figure 2.5: Two DAGs.

(with noises) of the individual’s capability so we can view each random variable as
Xi |µi ∼ N (µi , σ 2 ),
where µi can be interpreted as the individual’s actual performance on the exam. Suppose that these n
individuals are randomly chosen from a population. To model the randomness of the selection, we assume
that
µ1 , · · · , µn ∼ N (θ, τ 2 ),
where θ reflects the average performance of the sampled population. To account for our uncertainty about θ,
we may introduce a prior π(θ) over it. Under this model specification, all random quantities can be written
as the DAG in Figure 2.4.

2.3.2 Causal graph

The DAG is also used frequently in causal inference. The arrow is interpreted as a causal relation. For
instance, if we have a DAG X1 → X2 → X3 , then we mean that X1 causes X2 and X2 causes X3 . The
above graph also implies that conditioning on X2 , X1 and X3 are independent. In the causal relation, this
means that if we controlled X2 , then X1 does not causal any change in X3 . So the conditional independence
becomes an elegant mathematical tool to discuss causal relation.
Here is another example to illustrate how DAGs provide useful insights on causal relation. Consider the left
DAG in Figure 2.5–

• Causal interpretation: X2 causes both X1 and X3 . Thus, if X2 is unobserved, then X1 and X3 are
associated (in this case, X2 is a confounder ). On the other hand, if X2 is controlled, then X1 and X3
are independent.
• Graphical model interpretation: The generative model is
p(x1 , x2 , x3 ) = p(x1 |x2 )p(x3 |x2 )p(x2 ).
Thus, the marginal density
Z Z
p(x1 , x3 ) = p(x1 , x2 , x3 )dx2 = p(x1 |x2 )p(x3 |x2 )p(x2 )dx2 = g(x1 , x3 )

for some function g. Thus, X1 and X3 are marginally dependent. However, p(x1 , x3 |x2 ) = p(x1 |x2 )p(x3 |x2 )
so X1 and X3 are conditionally independent.

Now we consider the right DAG in Figure 2.5–

• Causal interpretation: Both X1 and X3 causes X2 but they are independent causes. However, if X2
is observed, then X1 and X3 will be associated. Note that X2 in this case will be called a collidor.
Lecture 2: Graphs and Networks 2-11

• Graphical model interpretation: The generative model is

p(x1 , x2 , x3 ) = p(x2 |x1 , x3 )p(x1 )p(x3 ) ⇒ p(x1 , x3 ) = p(x1 )p(x3 )

so X1 and X3 are marginally independent. And the conditional density

p(x1 , x2 , x3 ) p(x2 |x1 , x3 )p(x1 )p(x3 )

p(x1 , x3 |x2 ) = =
p(x2 ) p(x2 )

cannot be factorized into the product of g1 (x1 , x2 ) and g2 (x2 , x3 ) so X1 and X3 are conditionally
dependent given X2 .

Therefore, the probabilistic structure implied by a DAG and the causal interpretation of variables have an
elegant correspondence. This is why DAGs are very popular in causal inference.

2.4 Statistical network models

I would recommend the following lecture notes if you are interested in learning more about network models
in Statistics:

CMU 36-720, Statistical Network Models (by C. Shalizi): [Link]

networks/16-1/
UW CSSS-STAT 567 Statistical Analysis of Social Networks (by P. Hoff): [Link]
[Link]/people/pdhoff/courses/567/

In Statistics, networks models are often used to model a network data. Unlike the graphical model problems,
in handling the network data, we directly observe a network. Studies on statistical network models attempt
to use network data to make scientific inference. There are several scenarios that a network data can be
used in statistical inference, for instance

• Random networks. We may view the network as random quantities (called random networks) and
study the distribution that generate a random network.

• Community detection. We want to find communities (nodes are highly interconnected) within a
network–these communities are often represent certain groups of nodes.

• Networks as covariates. In some scenarios, we may use the network as a covariate in a regres-
sion/classification task.

• Sampling a network data. In many realistic situation, we may not observe the complete network
data but only a fraction of it. Different sampling scheme in this case leads to a different estimator of
the properties of the entire network.

2.4.1 Random networks

A statistical network model is a probability model that describes the generating process of a random graph.
Often the model describes the probability structure of a random undirected and unweighted graph although
many model can be generalized to directed graphs as well. In a network model, the nodes are often assumed
to be fixed and non-random and the edges are randomly formed (although this is not strict–there are network
2-12 Lecture 2: Graphs and Networks

models that nodes can be randomly generated). One of the most famous network model is the Erdos-Renyi
graph, which states that any pair of note has equal probability to form an edge. A generalized version of the
Erdos-Renyi graph is the stochastic block model where we assume that all nodes can be partitioned into K
unknown groups and pairs of nodes has different probability forming an edge depending on if they belong to
the same group or not. We will briefly review and discuss some famous network models. For undirected and
unweighted random networks, the probability model is equivalent to an n × n random matrix with Bernoulli
random variable in every entry. So the random network is a special case of a random matrix. Let G = (V, E)
be a random graph and kV k = n is the number of vertices and we may use the edge/adjacency matrix
E ∈ {0, 1}n×n to denote the edges with Eij = 1 means that there exists an edge between node i and node j.
Erdös-Rényi model. The Erdös-Rényi model is a very simple stochastic model for generating a random
graph. There are two variants of the Erdös-Rényi model.

• ER(n, p) model. This variant is the model that the Erdös-Rényi model is the most commonly referred
to as. It generates a random graph that every possible edge has an independent probability of p to
form.
Namely, P (Eij = 1) = p and {Eij : i ≥ j} are IID. Essentially, its randomness can be described
by n2 independent Bernoulli random variables. This models has several interesting properties on the
asymptotic behavior of n and p, for instance,

1. If np < 1, then the graph will almost surely has no connected components with a size larger than
O(log n).
2. If np = 1, then the graph will almost surely has the largest connected component with a size at
the order of O(n2/3 ).
3. If np → c > 1, then the graph will almost surely has a giant connected component and no other
connected component has size larger than O(log n).
(1−) log n
4. If p < n for some fixed number  > 0, then the graph will almost surely be disconnected.
(1+) log n
5. If p > n for some fixed number  > 0, then the graph will almost surely be (fullly)
connected.

The above results are summarized from the following famous paper by Erdös and Rényi:

Erdös, Paul, and Alfréd Rényi . “On the evolution of random graphs.” Publ. Math. Inst.
Hung. Acad. Sci 5, no. 1 (1960): 17-60.

• ER(n, m) model. This variant creates a random graph with a fixed amount of edges. Here, n stands
for the number of vertices and m stands for the total number of edges. The ER(n, m) model generates
a random graph such that any graph with m edges has an equal probability being selected.

In most cases, the Erdös-Rényi model refers to the first variant. A simple statistical estimator of p is
1 X
pb = n

Eij ,
2 i6=j

the fraction of existing edges. However, there is a very sad news about this model–most of the observed
networks are not from Erdös-Rényi model. The first three properties partition the possible range of n, p into
three categories and from this model, it is unlikely that the graph will have multiple ‘stars’ (stars refer to
the vertices that have high degrees, i.e., many other nodes connecting to them). Many realistic networks
such as the social networks often contain several stars.
Stochastic block model (SBM). A popular alternative to the Erdös-Rényi model is the stochastic block
model. The idea is very simple. Suppose that there is a partition of the vertices that forms K groups of
Lecture 2: Graphs and Networks 2-13

vertices. The SBM places an equal probability for forming a within-group edge and another equal probability
for forming a between-group edge. And every edge is formed independently from each other. This probability
model has K(K + 1)/2 parameters and the parameters form a symmetric K × K matrix θ such that the
diagonal describes the probability of forming a within-group edge in each group and the off-diagonal parts are
the probability of forming a between-group edge that corresponds to the two groups. Let gi ∈ {1, 2, · · · , K}
denotes the group that the node i belongs to. Then the stochastic block model can be written as

P (Eij = 1) = θgi ,gj .

If we rearrange the vertices such that vertices are ordered with respect to the index of the nodes, you can
easily see that the probability matrix P (Eij = 1) forms a block-diagonal structure. Often the label of
which group that a vertex belongs to is unknown and the parameters are also unknown. To estimate the
parameter, we can estimate the parameters by the MLE but the likelihood function is often non-convex
so finding the MLE is computationally challenging. Often people use approximation approach to find a
surrogate of the MLE. One common approximation is the the variational approximation (also known as the
variational inference/variational Bayes). See the following papers for more details:

1. Bickel, Peter, et al. “Asymptotic normality of maximum likelihood and its variational approx-
imation for stochastic blockmodels.” The Annals of Statistics 41.4 (2013): 1922-1943.
2. Celisse, Alain, Jean-Jacques Daudin, and Laurent Pierre. “Consistency of maximum-likelihood
and variational estimators in the stochastic block model.” Electronic Journal of Statistics 6
(2012): 1847-1899.

Another approach to estimate the parameter is via the spectral clustering algorithm. The idea is due to
the fact that spectral clustering is a relaxation of the optimal graph cut problem and the optimal graph
cut is a good approximation to the partition that forms the group structures in SBM. Thus, the spectral
clustering gives a partition of the graph and after forming the partition, we can simply use the average
within/between-group edge proportion as an estimator of the parameter. See the following for more details:

Rohe, Karl, Sourav Chatterjee, and Bin Yu. “Spectral clustering and the high-dimensional
stochastic blockmodel.” The Annals of Statistics 39, no. 4 (2011): 1878-1915.

Random dot product graph (RDPG). Random dot product graph assumes

P (Eij = 1) = XiT Xj

with Xi , Xj are supported on the ball Sd = {x ∈ Rd : kxk = 1} and X1 , · · · , Xn are assumed to be IID from
an unknown distribution F over Sd and denote X ∈ Rn×d be the matrix of X1 , · · · , Xn . Interestingly, under
RDPG, there exists a simple approach to recover the latent position up to rotations called the Adjacency
spectral embedding (ASE). Given an observed edge matrix E, let Ωd ∈ Rd×d be the diagonal matrix consists
of the top d eigenvalues and Ud ∈ Rn×d be the corresponding eigenvector matrix. Define a matrix X b =
1/2 n×d
Ud Ωd ∈ R . Then Xb is a consistent estimator of the latent position matrix X in the sense that there
exists an orthogonal matrix Q ∈ Rn×n such that

bi − Xi k ≤ C log n
max kQX
i n
with a probability of at least 1 − Cn−2 . This result is from the following paper:

Lyzinski, Vince, et al. “Perfect clustering for stochastic blockmodel graphs via adjacency spectral
embedding.” Electronic journal of statistics 8.2 (2014): 2905-2922.
2-14 Lecture 2: Graphs and Networks

For a recent review/survey on RDPG, please see

Athreya, Avanti, et al. “Statistical inference on random dot product graphs: a survey.” The
Journal of Machine Learning Research 18.1 (2017): 8393-8484.

Latent space model. Both SBM and RDPG are latent space models. The latent space model assumes
that there is a latent space S ⊂ Rd such that every node Vi has a latent position Xi ∈ S. And the probability
of forming an edge between node i and j depends on their relative position in the latent space. Namely,

P (Eij = 1) = µ(Xi , Xj ).

A simple choice is µ(x, y) = log odds(α + kx − yk), namely,

P (Eij = 1) = log odds(α + kXi − Xj k) = log odds(α + Aij ),

where α is a parameter. The estimation of the parameter α and the matrix Aij are often done by the ML
procedure but this could be computationally challenging. Note that we can only recover Aij rather than the
exact location Xi and Xj because the model will be translational and rotational invariant with respect to
Xi ’s. For latent space model for networks, I would recommend the first paper on this topic:

Hoff, Peter D., Adrian E. Raftery, and Mark S. Handcock. “Latent space approaches to social
network analysis.” Journal of the american Statistical association 97.460 (2002): 1090-1098.

Exponential family Random Graph Model (ERGM). The ERGM utilizes the exponential family in
statistics to model the generating probability of a specific graph. It does not assume any independence
between pairs of edges so it is a very flexible and powerful model. Recall that to describe the probability
model of the network, we only need to specify the randomness of edges or the edge matrix E. The ERGM
models the probability of the random matrix E as
d
!
X
θ` T` (e) = exp θT T (e) ,


P (E = e; θ) ∝ exp
`=1

where e ∈ {0, 1}n×n is a realization of the edge matrix and T (e) = (T1 (e), · · · , Td (e)) are the sufficient
statistics of the model and θ = (θ1 , · · · , θd ) is the parameter. Sometimes, we will introduce the partition
function Z(θ) and write the above model as
1
exp θT T (e) ,


P (E = e; θ) =
Z(θ)

where X
exp θT T (e) .


Z(θ) =
e

The Erdös-Rényi model is a special case of ERGM. To see this, note that from Erdös-Rényi model,
 
Yn X X
P (E = e) = peij (1 − p)1−Eij = exp  eij log p + (1 − eij ) log(1 − p)
i,j=1 i,j i,j
 
 
X p
= exp n2 log(1 − p) + eij log .
i,j
1−p
Lecture 2: Graphs and Networks 2-15

P
So a sufficient statistic is T (e) = i,j eij , the total number of edges.
In ERGM, all we need is to estimate the parameter θ. In a usual exponential family, this is often done by
the MLE. Given a random adjacency matrix E, you can actually show that the MLE of θ` satisfies

T` (E) = EE 0 ∼Pθb (T` (E 0 )).

The left-hand-side is a fixed sufficient statistic and all we need to do is to find the parameter such that the
expected value of the sufficient statistic happens to be the same as the observed sufficient statistic. Although
this seems to be not difficult (in the regular exponential family problem), it is actually a computationally
challenging problem. For any parameter θ, we do not have a closed-form of EE 0 ∼Pθ (T` (E 0 )) so the only way
to compute the expectation is to compute the probability P (E 0 ; θ) for each possible E 0 and then use the fact
X
EE 0 ∼Pθ (T` (E 0 )) = T` (e)P (E = e; θ).
e

The problem of the above summation is that there are too many terms in the summation of e. For a network
n
with n vertices, there are 2( 2 ) possible edges. So it is almost impossible to compute the sum when n is
not small. There are some stochastic approximations or MCMC methods for approximating the MLE. For
instance, the statnet1 is an R package developed at our department to address this issue.
Statistical inference. Recently, there is more and more attentions on making statistical inference with
network models. But in general, it is hard to construct a confidence interval for a parameter of interest
under a network model. And it is not so easy to construct a resampling method such as the bootstrap in the
network models. However, there are some progress on the resampling inference from a network model. One
possible approach is a parametric bootstrap: we assume a parametric model (such as SBMs) and resample
from the fitted parametric model; see, e.g.,

Bickel, Peter, et al. “Asymptotic normality of maximum likelihood and its variational approxi-
mation for stochastic blockmodels.” The Annals of Statistics 41.4 (2013): 1922-1943.

Another approach is to use the latent space model. We resample the fitted latent space positions and
regenerate a new network from the resampled latent space positions. See the following paper for an example:

Levin, Keith, and Elizaveta Levina. “Bootstrapping Networks with Latent Space Structure.”
arXiv preprint arXiv:1907.10821 (2019).

Incorporating covariates. It is possible to incorporate the covariates into the network model. The
ERGMs can easily have some effects from the covariates. For instance, if we have a network representing by
an adjacency matrix E and covariates X ∈ Rn×p for each node, we may use the logistic regression model

Y  exp(Eij (β0 + β T (Xi + Xj ))) 

1
P (E = e|X; β) = .
i6=j
1 + exp(β0 + β1T (Xi + Xj ))

See the following lecture note for more details:

[Link]
1 [Link]
2-16 Lecture 2: Graphs and Networks

2.4.2 Other statistical analysis with networks

Community detection. The goal of community detection is to find communities within a network data.
While there are several definitions of communities, often a community is a collection of nodes such that
nodes share many inter-community connections. In a sense, a community is like a cluster of observations.
The stochastic block model is a common model for modeling communities– nodes within the same block are
in the same community. A recent survey on this topic can be found in

Abbe, Emmanuel. ”Community detection and stochastic block models: recent developments.”
The Journal of Machine Learning Research 18, no. 1 (2017): 6446-6531.

Networks as covariates. The network may be used as a covariate that informs us the dependency among
the response variable. A good news of this use of network is that we no longer have to worry about the
probability model that generates the observed networks. For some work along this direction, please see:

1. Forastiere, Laura, Edoardo M. Airoldi, and Fabrizia Mealli. “Identification and estima-
tion of treatment and interference effects in observational studies on networks.” arXiv preprint
arXiv:1609.06245 (2016).
2. Basse, Guillaume W., and Edoardo M. Airoldi. “Model-assisted design of experiments in the
presence of network-correlated outcomes.” Biometrika 105, no. 4 (2018): 849-858.
3. Basse, Guillaume W., and Edoardo M. Airoldi. “Limitations of design-based causal inference
and A/B testing under arbitrary and network interference.” Sociological Methodology 48, no. 1
(2018): 136-151.

Sampling a network data In many realistic scenarios, we do not observe the entire network but only
a fraction of it. For instance, medical researchers often use ‘coupons’ for participants to recruit other
participants. This generates samples from a network structure (assuming that a participant only gives the
coupon to his/her friends).
Note that sometimes we can design how the network is sampled but sometimes we cannot design the sampling
scheme–we already observed the network. However, even we cannot design the sampling scheme, if we have
information about how the network is sampled, we can construct a corresponding probabilistic model that
helps us understand properties of an estimator.
There are four common types of sampling a network data:

• Node-induced subgraph sampling. We random choose m out of n nodes from the graph and examine if
there are edges within these m sampled nodes. This generates a subgraph G0 ⊂ G. This is the common
scenario that we recruit several participants to join a study and examine their relationships.

• Edge-induced subgraph sampling. Randomly choose a set of edges from G and construct the corre-
sponding subgraph. Note that a node will be included in the sampled subgraph if any of its edge is
sampled. Again, this generates a subgraph G0 ⊂ G.

• Egocentric sampling. Similar to the node-induced approach but whenever we observe a node, we also
observe all its edges along with adjacent nodes. In addition, if any of the adjacent nodes are linked,
we also observe this information. This occurs in questionnaires such as the ones asking

1. Who are your friends?

2. Among your friends, who are friends with each other?
Lecture 2: Graphs and Networks 2-17

• Link-tracing sampling (also known as snowball sampling). Link-tracing sampling is similar to the
egocentric sampling but we repeat this process several times. We perform egocentric sampling on
those who are already recruited and expand the sampled network gradually.

For more details, I would recommend the following lecture note

[Link]

A Properties of Conditional Independence

A.1 Independence Revisited

Recall that two random variables X and Y are independent if

P (X ≤ x, Y ≤ y) = P (X ≤ x)P (Y ≤ y).
In this case, we write it as X ⊥
⊥ Y . Let pX and pY denote the PDF or PMF of X and Y , respectively. Then
independence also implies
pXY (x, y) = pX (x)pY (y) ⇔ pX|Y (x|y) = pX (x).

Consider a special case where both X and Y are categorical variables such that X ∈ {1, 2, · · · , m} and
Y ∈ {1, 2, · · · , n}. We further define
qij = P (X = i, Y = j) qi+ = P (X = i) q+j = P (Y = j).
Then X ⊥
⊥ Y if and only if
qij = qi+ · q+j for all i, j.

Lemma 2.12 Let Q be an m × n matrix such that Qij = qij . Then X ⊥

⊥ Y if and only if the matrix Q has
rank 1.

Proof:
⇒:
This direction is easy to see because qij = qi+ · q+j implies that Q = uv T , where u = (q1+ , q2+ , · · · , qn+ ) and
v = (q+1 , q+2 , · · · , q+m ).
⇐:
If Q has rank 1, there exists vectors u ∈ Rn and b ∈ Rm such that Q = uv T . Because qij ≥ 0, we may choose
every elements of u and v to be non-negative, i.e., uj ≥ 0 and vj ≥ 0 for every i and j.
Since Qij = pij = ui vj ,
X m
X
pi+ = pij = ui vj = ui v+ ,
j=1,··· ,m j=1
Pm
where v+ = j=1 vj > 0. Similarly,
n
X
p+j = u+ vj , u+ = ui .
i=1
2-18 Lecture 2: Graphs and Networks

Therefore, we obtain
pi+ p+j
ui = , vj =
v+ u+
and
pi+ p+j
pij = ui vj = = pi+ p+j
v+ u+
Pm Pn P P
because v+ u+ = j=1 vj i=1 ui = i,j ui vj = i,j pij = 1.

A.2 Conditional Independence

For three RVs X, Y, and Z, we say X, Y are conditional independent given Z if

P (X ≤ x, Y ≤ y|Z = z) = P (X ≤ x|Z = z)P (Y ≤ y|Z = z)

for every x and y and PZ -almost everywhere of z. PZ -almost everywhere of z means that the above equality
holds for all z except for a set of values that has 0 probability. It is a slightly weaker notion than ‘for every
z’. We use the notation
X⊥ ⊥ Y |Z
for denote the case where X, Y are conditional independent given Z.
Note that X ⊥
⊥ Y |Z also implies

P (X ≤ x|Y = y, Z = z) = P (X ≤ x|Z = z)

for every x and PY,Z -almost everywhere of (y, z).

Theorem 2.13 Let pXY Z be the joint PDF/PMF of X, Y, and Z. Then the followings are equivalent:

(i) X ⊥
⊥ Y |Z.

(ii) pXY |Z (x, y|z) = pX|Z (x|z)pY |Z (y|z) a.e.

(iii) pX|Y Z (x|y, z) = pX|Z (x|z) a.e.

pXZ (x,z)pY Z (y,z)
(iv) pXY Z (x, y, z) = pZ (z) a.e.

(v) pXY Z (x, y, z) = g(x, z)h(y, z), where g and h are some (measurable) functions.

(vi) pX|Y Z (x|y, z) = w(x, z), where w is some (measurable) function.

Proof: The equivalence between (i), (ii), (iii), and (iv) are trivial so we focus on case (v) and (vi).
(ii) ⇒ (v):
Because
pXY |Z (x, y|z) = pX|Z (x|z)pY |Z (y|z),
we have
pXY Z (x, y, z) pXZ (x, z) pY Z (y, z)
=
pZ (z) pZ (z) pZ (z)
Lecture 2: Graphs and Networks 2-19

so
pXZ (x, z)pY Z (y, z)
pXY Z (x, y, z) = = h(x, z)g(y, z),
pZ (z)
which proves (v).
(v) ⇒ (vi):
Based on (v), we have
Z Z
pY Z (y, z) = pXY Z (x, y, z)dx = h(y, z) g(x, z)dx = h(y, z)q(z).

Thus,
pXY Z (x, y, z) g(x, z)h(y, z) g(x, z)
pX|Y Z (x|y, z) = = = = w(x, z).
pY Z (y, z) h(y, z)q(z) q(z)

Finally, we show that (vi) ⇒ (iii):

Z Z
pX|Z (x|z) = pXY |Z (x, y|z)dy = pX|Y Z (x|y, z)pY |Z (y|z)dy
Z
= w(x, z) pY |Z (y|z)dy = w(x, z) = pX|Y Z (x|y, z).

Here are five important properties of conditional independence. Let X, Y, Z, W be RVs.

(C1) (symmetry) X ⊥
⊥ Y |Z ⇐⇒ Y ⊥
⊥ X|Z.
(C2) (decomposition) X ⊥ ⊥ Y |Z =⇒ h(X) ⊥⊥ Y |Z for any (measurable) function h.
A special case is: (X, W ) ⊥
⊥ Y |Z =⇒ X ⊥⊥ Y |Z.

(C3) (weak union) X ⊥ ⊥ Y |Z =⇒ X ⊥ ⊥ Y |Z, h(X) for any (measurable) function h.

A special case is: (X, W ) ⊥
⊥ Y |Z =⇒ X ⊥ ⊥ Y |(Z, W )
(C4) (contraction)
X⊥
⊥ Y |Z and X ⊥
⊥ W |(Y, Z) ⇐⇒ X ⊥
⊥ (W, Y )|Z.

(C5) If the joint PDF pXY ZW (x, y, z, w) satisfies fY ZW (y, z, w) > 0 almost everywhere. Then

X⊥
⊥ Y |(W, Z) and X ⊥
⊥ W |(Y, Z) ⇐⇒ X ⊥
⊥ (W, Y )|Z.