Let $\mathcal{X}$ be a reversible Markov chain with transition matrix
$\bm{P}$, and $\bm{\pi}>0$ one of its stationary distributions. Furthermore,
let $\bm{Y}_{R}$ be a set of right eigenvectors of $\bm{P}$ and $\bm{Y}_{L}$
its dual basis, both of which obeying the orthogonality relations of Theorem
4.2.6. Then, if $\bm{r}_{\omega}$ and $\bm{l}_{\omega}$ are right and left
eigenvectors of the same eigenvalue $\lambda_{\omega}$, they are related via
$\bm{l}_{\omega}=\bm{\Pi}\bm{r}_{\omega}$ (proof: see Appendix A).

Theorem 4.2.6 is particularly important for practical reasons. Firstly, the
diagonalizability of $\bm{P}$ implies a full set of linearly independent
eigenvectors. Linearly independent feature spaces are often desirable from a
computational perspective since they (i) reduce the overall redundancy, (ii)
can express any function in $\mathbb{R}^{N}$, and (iii) ensure that certain
matrix operations are well-defined. Furthermore, as already explained in
Section 2, having a diagonalizable transition matrix means that evolving a
Markov chain becomes computationally cheaper. Secondly, since $\bm{P}$ is a
real matrix with real eigenvalues, we can always choose an eigenbasis
consisting only of real valued vectors. This property is useful because real
spaces are often more intuitive to deal with than complex spaces. Furthermore,
in many applications of Markov chains the underlying vector space is required
to be real, either due to the semantic nature of the problem, or because the
algorithm being used is not suited to complex spaces.

While a linearly independent set of eigenvectors is useful, having a basis
that is pairwise orthogonal w.r.t. the standard Euclidean product offers
further analytical and numerical benefits. From Theorem 4.2.6, it is clear
that this is not the case for transition matrices of reversible Markov chains.
However, the matrix $\bm{K}$ is a normalized symmetric version of $\bm{P}$,
and from the proof of Theorem 4.2.6 we know that the eigenvalues of these two
matrices are the same and their eigenvectors are related simply by a
multiplication of $\bm{\Pi}^{\pm\frac{1}{2}}$. Thus, they contain similar
information regarding the relationship between pairs of states in
$\mathcal{S}$, and so $\bm{K}$ can be used as a surrogate for $\bm{P}$ in
situations where orthogonal eigenvectors are required.

When using the matrix $\bm{K}$, it is sometimes useful to express it purely in
terms related to a graph $G$. Starting with Equation 102, this can be done by
swapping stationary probabilities for degree vertices:

$\displaystyle\bm{K}$
$\displaystyle{=}\bm{D}^{\frac{1}{2}}z^{-\frac{1}{2}}\bm{P}z^{\frac{1}{2}}\bm{D}^{-\frac{1}{2}}$
(103) $\displaystyle=\hskip 8.5pt\bm{D}^{\frac{1}{2}}\bm{PD}^{-\frac{1}{2}}$
(104) $\displaystyle{=}\hskip
5.0pt\bm{D}^{-\frac{1}{2}}\bm{WD}^{-\frac{1}{2}}$ (105)

This expression appears in the next section, where we use $\bm{K}$ to define a
positive semi-definite matrix which has the same eigenvectors.

Collectively, the results of this section demonstrate that transition matrices
of reversible chains satisfy similar properties to symmetric matrices, but
subject to a different type of normalization. This alternative normalization
is important for the next section, and in order to make our analyses more
concise we end this section by defining the following two coordinate
transformations:

######  Definition 4.2.8 (Left and right coordinate transformations).

Let $G$ be an undirected graph with $N$ vertices and degree matrix $\bm{D}$.
If $\bm{x}\in\mathbb{R}^{N}$ is a vector defined over these vertices, we
define the following related vectors:

$\displaystyle\bm{x}_{L}$ $\displaystyle=\bm{D}^{\frac{1}{2}}\bm{x}$ (106)
$\displaystyle\bm{x}_{R}$ $\displaystyle=\bm{D}^{-\frac{1}{2}}\bm{x}$ (107)

which we call the left and right coordinate transformations of $\bm{x}$,
respectively.

####  4.2.2 Normalized Graph Laplacian

A symmetric matrix $\bm{A}\in\mathbb{R}^{N\times N}$ is positive semi-definite
if $\bm{x}^{T}\bm{A}\bm{x}\geq 0\;\forall\bm{x}\in\mathbb{R}^{N}$, or
equivalently if all its eigenvalues are non-negative. Such matrices have a
number of numerical properties that make them useful for solving optimization
problems, and because of this they often appear in computational applications.
The matrix $\bm{K}$ is not positive-semidefinite, since it has the same
eigenvalues as $\bm{P}$ (which can be negative). However, it is
straightforward to define a variant of $\bm{K}$ which does have this property,
while also having the same eigenvectors as $\bm{K}$:

######  Definition 4.2.9.

For an undirected graph $G$ with weight matrix $\bm{W}$, the normalized graph
Laplacian is given by:

$\displaystyle\bm{\mathcal{L}}$ $\displaystyle\hskip 0.5pt:=\hskip
3.5pt\bm{\mathbbm{1}}-\bm{K}$ (108)
$\displaystyle\overset{(\ref{eq:Kmat-P})}{=}\bm{\mathbbm{1}}-\bm{D}^{\frac{1}{2}}\bm{PD}^{-\frac{1}{2}}$
(109)
$\displaystyle\overset{(\ref{eq:Kmat-W})}{=}\bm{\mathbbm{1}}-\bm{D}^{-\frac{1}{2}}\bm{WD}^{-\frac{1}{2}}$
(110)

with elements equal to:

$\mathcal{L}_{ij}=\left\\{\begin{array}[]{ll}1-\frac{W_{ii}}{d_{i}}&\mbox{if
}i=j\\\ \\\ -\frac{W_{ij}}{\sqrt{d_{i}d_{j}}}&\mbox{if i $\neq$ j and
$(v_{i},v_{j})\in E$}\\\ \\\ 0&\mbox{otherwise}\end{array}\right.$ (111)

and for which the following properties hold:

  * •

$\bm{\mathcal{L}}$ is symmetric and positive semi-definite, with eigenvalues
in the interval $[0,2]$.

  * •

$\lambda=0$ is guaranteed to be an eigenvalue and its multiplicity is equal to
the number of connected components in $G$.

  * •

If $C$ is a connected component of $G$, then there is an eigenvector
$\bm{y}_{C}$ with eigenvalue $\lambda=0$ whose entries are
$d_{i}^{\frac{1}{2}}$ for $v_{i}\in C$ and $0$ otherwise, or equivalently
$\bm{y}_{C}=\bm{D}^{\frac{1}{2}}\bm{1}_{C}=\bm{1}_{C,L}$ where $\bm{1}_{C}$ is
an indicator vector for vertices in $C$.

  * •

Therefore, for fully connected graphs
$\bm{y}=\bm{D}^{\frac{1}{2}}\bm{1}=\bm{1}_{L}$ is the unique eigenvector with
$\lambda=0$, where $\bm{1}$ is a vector of ones.

There exist other types of graph Laplacians for undirected graphs, such as the
unnormalized Laplacian $\bm{L}:=\bm{D}-\bm{W}$, and the random walk Laplacian
$\bm{L}_{\text{RW}}:=\mathbbm{1}-\bm{D}^{-1}\bm{W}$. Many useful properties of
a graph $G$ can be obtained from graph Laplacians, and they form the basis of
spectral graph theory [51]. Due to its close relationship to $\bm{P}$, in this
tutorial we predominantly focus $\bm{\mathcal{L}}$. In the case of $\bm{L}$,
there is a weaker connection to $\bm{P}$ which we only discuss briefly.
Furthermore, to avoid redundancy we do not discuss $\bm{L}_{\text{RW}}$ at
all, since it is the same as $-\bm{P}$ but shifted by the identity. For a
concise review of each of these objects, see [55].

As the name suggests, graph Laplacians are analogues of the Laplace operator.
In particular, a number of studies have found links between graph Laplacians
and a variant of the Laplace operator on manifolds, known as the Laplace-
Beltrami operator [56, 57]. Broadly speaking, Laplace operators measure how
much the value of a function at a point varies from its local average, which
is informally related to the notion of mean curvature [58]. Furthermore, the
eigenvalues of this operator are non-negative real numbers and are related to
how much the corresponding eigenfunctions vary over the domain of the function
[59]. All of these properties have analogues in the case of
$\bm{\mathcal{L}}$, which justifies the term given to this object. To see
this, we start with the following result [7]:

######  Theorem 4.2.10.

Let $G$ be an undirected graph $G$ with weight matrix $\bm{W}$ and normalized
Laplacian $\bm{\mathcal{L}}$. Then for any vector $\bm{x}$ defining values on
the vertices of $G$:

$\displaystyle\bm{x}^{T}\bm{\mathcal{L}}\bm{x}$
$\displaystyle=\frac{1}{2}\sum_{i,j=1}^{N}W_{ij}\bigg{(}\frac{x_{i}}{d_{i}^{\frac{1}{2}}}-\frac{x_{j}}{d_{j}^{\frac{1}{2}}}\bigg{)}^{2}$
(112)

which is guaranteed to produce a real non-negative number since
$\bm{\mathcal{L}}$ is positive semi-definite (proof: see Appendix A).

In Equation 112, the quadratic term measures the difference between the
entries of a vector that is related to $\bm{x}$ by normalization with
$\bm{D}^{-\frac{1}{2}}$, i.e. the vector $\bm{x}_{R}$. Since this is minimized
when the entries of this vector are similar for pairs of vertices with large
edge weight $W_{ij}$, it can be interpreted to describe the smoothness of
$\bm{x}_{R}$ with respect to the connectivity of $G$. Furthermore, since this
measure describes the smoothness of $\bm{x}_{R}$ as opposed to that of
$\bm{x}$, it is useful for dealing with graphs that have a very heterogeneous
degree structure.

If we evaluate the left-hand side of Theorem 4.2.10 using a normalized
eigenvector $\bm{y}_{\omega}$ of $\bm{\mathcal{L}}$, we get:

$\displaystyle\bm{y}_{\omega}^{T}\bm{\mathcal{L}}\bm{y}_{\omega}$
$\displaystyle=\lambda_{\omega}\langle\bm{y}_{\omega},\bm{y}_{\omega}\rangle$
(113) $\displaystyle=\lambda_{\omega}$ (114)

meaning that $\lambda_{\omega}$ describes precisely this notion of smoothness
for $\bm{y}_{\omega}$. Now assume that we have an orthonormal set of
eigenvectors of $\bm{\mathcal{L}}$. From 4.2.9, we know that the corresponding
eigenvalues are real numbers in the interval $[0,2]$, and that there is
guaranteed to be at least one eigenvalue $\lambda=0$. Thus, they can be
ordered as follows:

$0=\lambda_{1}\leq\lambda_{2}\leq\cdots\leq\lambda_{N}\leq 2$ (115)

Putting these findings together, we can say that given an orthonormal set of
eigenvectors of $\bm{\mathcal{L}}$, there is a natural way to order them based
on their smoothness across $G$, according to Equation 112. For example, taking
an eigenvector with $\lambda=0$ (4.2.9) and plugging it into Equation 112
indeed yields zero. These are therefore the eigenvectors of $\bm{\mathcal{L}}$
that have the lowest smoothness score in Equation 112. Similarly, the
eigenvectors of $\bm{\mathcal{L}}$ with second-smallest eigenvalue are those
that, subject to orthonormality, score the second lowest in Equation 112.

As indicated by Equation 115, we can apply this ordering to all eigenvalues of
$\bm{\mathcal{L}}$, meaning that the resulting set of eigenvectors gets
progressively less smooth, or equivalently more oscillatory, as
$\lambda_{\omega}$ increases. Since this basis is orthonormal, it can express
any signal $\bm{x}\in\mathbb{R}^{N}$ on $G$, with the resulting components
describing the projection of $\bm{x}$ onto each of these oscillatory modes.
Due to its correspondence with Fourier analysis, this decomposition has been
referred to as the Graph Fourier Transform of $\bm{x}$ [60]. Moreover, a
useful result in spectral graph theory is that a basis of eigenvectors
corresponding to the $k$ leading eigenvalues of $\bm{\mathcal{L}}$ is one
which, subject to orthonormality, has the lowest possible total score in
Equation 112. In other words, if $\bm{Y}\in\mathbb{R}^{N\times k}$ represents
such a basis of right eigenvectors, it solves the following optimization
problem [3, 4, 55]:

minimize $\displaystyle\text{tr}(\bm{Y}^{T}\bm{\mathcal{L}}\bm{Y})$ (116)
subject to $\displaystyle\bm{Y^{T}}\bm{Y}=\mathbbm{1}$ (117)

This property underlies several Laplacian-based methods in unsupervised
learning [17, 19], where typically the eigenvectors of $\bm{\mathcal{L}}$ with
the smallest eigenvalues are those that capture the most important information
relating to the learning objective, and so discarding eigenvectors with higher
eigenvalues can provide a description of a data set that has lower
dimensionality, while also being more interpretable.

These observations can be related to the random walk on $G$. Since
$\bm{\mathcal{L}}$ shares an eigenbasis with $\bm{K}$, and the eigenbasis of
$\bm{K}$ is related to that of $\bm{P}$ by Theorem 4.2.5, we can relate the
eigenvectors of $\bm{\mathcal{L}}$ to those of $\bm{P}$ as follows:

######  Proposition 4.2.11.

If $\bm{y}_{\omega}$ is an eigenvector of $\bm{\mathcal{L}}$ with eigenvalue
$\lambda_{\omega}$, then
$\bm{l}_{\omega}=\bm{D}^{\frac{1}{2}}\bm{y}_{\omega}=\bm{y}_{\omega,L}$ and
$\bm{r}_{\omega}=\bm{D}^{-\frac{1}{2}}\bm{y}_{\omega}=\bm{y}_{\omega,R}$ are
left and right eigenvectors of $\bm{P}$, respectively, with eigenvalue
$1-\lambda_{\omega}$.

Because of this, the eigenvectors of $\bm{P}$ have a similar form to those of
$\bm{\mathcal{L}}$, but subject to the coordinate transformations of 4.2.8.
Therefore, they can also be interpreted using the notion of smoothness, with
$\lambda=1$ in some sense being the smoothest case.

To illustrate the relationship between the eigenvectors of $\bm{\mathcal{L}}$
and $\bm{P}$, we consider a simple Markov chain consisting of a linear
arrangement of $100$ states, where only nearest neighbor transitions are
allowed (Figure 16(a)). Transitions to the left and right occur with
probability 0.48 and 0.52, respectively, and the self loops at $s_{1}$ and
$s_{100}$ mean that staying fixed is allowed in these states. Take a moment to
verify that this chain is both ergodic and reversible (hint: in the latter
case, try Theorem 2.6.5). Once we know the stationary probabilities $\pi_{i}$
of this chain, we can calculate the corresponding matrices $\bm{K}$ and
$\bm{\mathcal{L}}$ by using Equation 102 and then Equation 108. In Figure
16(b), we plot the left and right eigenvector of $\bm{P}$ with $\lambda=1$,
which are the stationary distribution $\bm{\pi}$ and
$\bm{\eta}=(1,1,...,1)^{T}$, respectively. The stationary probabilities are
larger for states near the right end of the chain by virtue of the tendency
for rightward transitions in this chain. Additionally, we plot the
corresponding eigenvector of $\bm{\mathcal{L}}$ with $\lambda=0$, which is
$\bm{y}=(\pi_{1}^{\frac{1}{2}},\pi_{2}^{\frac{1}{2}},...,\pi_{100}^{\frac{1}{2}})^{T}$.
This vector is in some sense an intermediary between $\bm{\pi}$ and
$\bm{\eta}$ since, in agreement with 4.2.11,
$\bm{\pi}=\bm{\Pi}^{\frac{1}{2}}\bm{y}=\bm{D}^{\frac{1}{2}}\bm{y}=\bm{y}_{L}$
and
$\bm{\eta}=\bm{\Pi}^{-\frac{1}{2}}\bm{y}=\bm{D}^{-\frac{1}{2}}\bm{y}=\bm{y}_{R}$
(as indicated by the black arrows in Figure 16(b)).

(a)

(b)

(c)

(d)

(e)

Figure 16: (a) A Markov chain with $N=100$ states arranged in a line, with
left and right transitions happening with probability $0.48$ and $0.52$,
respectively. (b) The eigenvector of $\bm{\mathcal{L}}$ with $\lambda=0$
(blue), as well as the left (red) and right (green) eigenvectors of $\bm{P}$
for this model. (c) The next four eigenvectors of $\bm{\mathcal{L}}$, with the
corresponding eigenvectors indicated in the legend, as well as similar plots
for the next four left (d) and right (e) eigenvectors of $\bm{P}$. All
eigenvalues are rounded to 4dp.

In Figure 16(c), we show four more eigenvectors of $\bm{\mathcal{L}}$ having
eigenvalues closest to $0$. In agreement with our foregoing discussion, the
eigenvectors get less smooth as $\lambda$ increases, becoming more oscillatory
and resembling trigonometric functions over the state space. In Figure 16(d,
e), we do the same for the left and right eigenvectors of $\bm{P}$,
respectively. The smoothness of these eigenvectors also depends on the size of
$\lambda$, however this time we are interested in those with eigenvalues
closest to $1$, and the smoothness decreases as $\lambda$ decreases.
Furthermore, in comparison to Figure 16(c) these eigenvectors have an
additional weighting effect across the state space. The left eigenvectors have
larger amplitudes for states on the right-hand side, which is intuitive since
these states have higher stationary probabilities $\pi_{i}$, and the
eigenvectors can be obtained from those of $\bm{\mathcal{L}}$ by the left
coordinate transformation of 4.2.8. For the right eigenvectors, the weighting
is the opposite, with states on the left-hand side having larger amplitudes.
This is explained by an equivalent argument, except that this time we apply
the right coordinate transformation to the eigenvectors of $\bm{\mathcal{L}}$.
It should be noted that for the purpose of visualization, all eigenvectors in
Figure 16(c-e) are normalized to have Euclidean norm $1$, even though for the
eigenvectors of $\bm{P}$ this is not the natural normalization (Theorem
4.2.6).

(a)

(b)

(c)

(d)

(e)

Figure 17: (a) A modified version of the chain in Figure 16(a), whereby the
transition probabilities of $0.48$ and $0.52$ are perturbed by random numbers
$\xi_{i}\in[-0.1,0.1]$. (c-e) The equivalent of the plots in Figure 16(c-e),
where again all eigenvalues are rounded to 4dp.

The example chain in Figure 16(a) is somewhat artificial since the transition
probabilities are homogeneous, which is why the stationary distribution in
Figure 16(b) is such appears to be so smooth visually. This in turn means that
the underlying graph $G$ has a degree structure that varies somewhat smoothly
from left to right, which is partly responsible for the other eigenfunctions
also being so smooth. To see how this generalizes as we make the transition
probabilities less homogeneous, we consider a modified chain which we show in
Figure 17(a). In this model, left transitions from a state $s_{i}$ happen with
probability $0.52+\xi_{i}$ and right transitions with probability
$0.48-\xi_{i}$, where $\xi_{i}$ is a number sampled from a uniform
distribution on the interval $[-0.1,0.1]$. Therefore, this chain is like the
previous example, but with a random perturbation at each state. In Figure
17(b-e), we show the corresponding versions of Figure 16(b-e). As one can see,
the eigenvectors of $\bm{\mathcal{L}}$ as well as the left eigenvectors of
$\bm{P}$ have similar shapes to the previous case, but they appear more rugged
due to the inhomogoneity of the transition probabilities. Given that the
perturbations made to the previous model are small in size, this is an
illustration of the fact that these sets of eigenvectors are very sensitive to
local information. Rather interestingly, the same is not true for the right
eigenvectors of $\bm{P}$: in Figure 17(b) the right eigenvector with
$\lambda=1$ is the same as in the previous example, and in Figure 17(e) the
other right eigenvectors are partially distorted but still appear somewhat
smooth visually. This can be understood in the following way. Since the right
eigenvectors of $\bm{P}$ are the right transformations of the eigenvectors of
$\bm{\mathcal{L}}$, we can reformulate the optimization problem in Equations
116 and 117 in terms of the basis $\bm{Y}_{R}=\bm{D}^{-\frac{1}{2}}\bm{Y}$:

minimize
$\displaystyle\text{tr}(\bm{Y}_{R}^{T}\bm{D}^{\frac{1}{2}}\bm{\mathcal{L}}\bm{D}^{\frac{1}{2}}\bm{Y}_{R})=\text{tr}(\bm{Y}_{R}^{T}\bm{L}\bm{Y}_{R})$
(118) subject to
$\displaystyle\bm{Y}_{R}^{T}\bm{D}^{\frac{1}{2}}\bm{D}^{\frac{1}{2}}\bm{Y}_{R}=\bm{Y}_{R}^{T}\bm{D}\bm{Y}_{R}=\mathbbm{1}$
(119)

where we have used the fact that
$\bm{D}^{\frac{1}{2}}\bm{\mathcal{L}}\bm{D}^{\frac{1}{2}}=\bm{D}^{\frac{1}{2}}(\bm{\mathbbm{1}}-\bm{D}^{-\frac{1}{2}}\bm{WD}^{-\frac{1}{2}})\bm{D}^{\frac{1}{2}}=\bm{D}-\bm{W}=\bm{L}$.
Therefore, for right eigenvectors of $\bm{P}$, the relevant smoothness measure
is related to $\bm{L}$ as opposed to $\bm{\mathcal{L}}$. Furthermore, writing
Equation 112 in terms of $\bm{L}$ and $\bm{x}_{R}$ gives:

$\bm{x}_{R}^{T}\bm{L}\bm{x}_{R}=\frac{1}{2}\sum_{i,j=1}^{N}W_{ij}(x_{R,i}-x_{R,j})^{2}$
(120)

which we can interpret to mean that the vectors which optimize this measure,
i.e. the right eigenvectors of $\bm{P}$ with eigenvalue close to $1$, have
entries that are close for vertices with large $W_{ij}$. In the context of the
example in Figure 17, this means that such eigenvectors have similar values
for neighboring vertices, and a quick check reveals that this is indeed the
case in Figure 17(d). Conversely, for the eigenvectors in Figure 17(b,c) the
values on average vary more between neighbouring vertices.

Lastly, we note that the ordering of eigenvalues used in this section is
somewhat different to that in Section 2.3. In the current section, the
eigenvalues of $\bm{\mathcal{L}}$ are ordered from $0$ up to $2$, which
corresponds to the eigenvalues of $\bm{P}$ being ordered from $1$ to $-1$. To
reflect our interpretation, we call this ordering by smoothness. In Section 2,
however, the eigenvalues of a transition matrix are ordered by their absolute
value, which describes how long the contribution from the corresponding
eigenvector persists as the chain evolves. We therefore call this choice
ordering by persistence. The suitability of either of these types of ordering
depends on the problem domain in which a Markov chain is being used. For
example, in the case of spectral clustering they correspond to distinct
objectives, as demonstrated in [12].

This concludes our treatment of random walks on undirected graphs. As a
summary of the results given, in Table 2 we compare the mathematical
properties and relationships of $\bm{\mathcal{L}}$, $\bm{K}$ and $\bm{P}$. The
material presented in this section is particularly important for applications
in machine learning and data mining in which the data set can be formulated as
a graph. In particular, it underlies work that has been done on problems such
as spectral clustering [8, 9, 10, 11, 12], manifold learning/graph embedding
[15, 16], graph-based classification [20, 21, 22], and value function
approximation in reinforcement learning [24, 25, 29, 27, 28]. In the next
section we consider how, if at all, the material presented in this section
generalizes to directed graphs.

| $\bm{P}$ | $\bm{K}$ | $\bm{\mathcal{L}}$
---|---|---|---
Relationship to $\bm{W}$ | $\bm{D}^{-1}\bm{W}$ | $\bm{D}^{-\frac{1}{2}}\bm{WD}^{-\frac{1}{2}}$ | $\bm{\mathbbm{1}}-\bm{D}^{-\frac{1}{2}}\bm{WD}^{-\frac{1}{2}}$
Diagonalizable | ✓ | ✓ | ✓
Symmetric | ✗ | ✓ | ✓
Positive semi-definite | ✗ | ✗ | ✓
Eigenvalues | $\lambda_{\omega}\in[-1,1]$ | $\lambda_{\omega}\in[-1,1]$ | $\lambda_{\omega}\in[0,2]$
Eigenvectors | lin. indep. | orthogonal | orthogonal
Left eigenvectors | $\bm{y}_{\omega,L}$ | $\bm{y}_{\omega}$ | $\bm{y}_{\omega}$
Right eigenvectors | $\bm{y}_{\omega,R}$ | $\bm{y}_{\omega}$ | $\bm{y}_{\omega}$
Table 2: A summary of the properties established for the three matrices
associated to random walks on undirected graphs: $\bm{P}$, $\bm{K}$, and
$\bm{\mathcal{L}}$.

###  4.3 Random walks on directed graphs

Broadening our consideration to directed graphs is necessary if we want to
describe non-reversible Markov chains. However, since many of the guarantees
established in Section 4.2 do not hold for directed graphs, this case is a lot
harder to treat analytically. In Section 4.3.1 we explore the main challenges
that occur when applying spectral graph theory to the transition matrices of
non-reversible Markov chains, and in Section 4.3.2 we describe methods for
circumventing these issues. Finally, in Section 4.3.3 we define a
generalization of $\bm{\mathcal{L}}$ to directed graphs, and in Section 4.3.4
we present a method for enforcing ergodicity on random walks of directed
graphs.

####  4.3.1 Key difficulties

Since many of the guarantees established in Section 4.2 do not hold for
directed graphs, they are a lot harder to treat analytically. Perhaps most
importantly, the transition matrices of non-reversible chains are neither
guaranteed to be diagonalizable, nor to have real eigenvalues [61], which can
be observed even for simple cases such as those shown in Figure 18(a-c). There
are nonetheless some cases for which both properties hold [61] (as shown by
the example in Figure 18(d)), but it is still not fully understood to what
degree, if at all, the transition structure of a non-reversible chain
determines either the diagonalizability of $\bm{P}$ or whether its eigenvalues
are real/complex.888Although some studies have considered complex eigenspaces
in specific settings [62, 63, 64, 34]. When $\bm{P}$ is non-diagonalizable, it
does not have a set of $N$ linearly independent eigenvectors, which can cause
numerical issues since in this case some matrix operations are computationally
more expensive or not well-defined. Moreover, if the eigenvalues of $\bm{P}$
are complex, then so are its eigenvectors. As in the real case, we can choose
to order these eigenvectors based on persistence, or smoothness. In the former
case, the generalization is somewhat straightforward since $|\lambda|$ still
describes how long each eigenvector typically persists. In the latter case,
however, the question of how to generalize the concept of smoothness to
complex eigenvectors is non-trivial, and is still an actively researched topic
in the literature [65, 66]. These factors make analyzing the transition
matrices of non-reversible Markov chains more challenging than in the
reversible case.

$\bm{P}=\left(\begin{array}[]{ccccc}0&0.4&0.6&0&0\\\ 0&0&0&0&1\\\ 0&0&0&0&1\\\
0&0&0.8&0&0.2\\\ 0.25&0&0&0.75&0\end{array}\right)$

(a) Non-diagonalizble with complex eigenvalues

$\bm{P}=\left(\begin{array}[]{ccc}0.1&0.3&0.6\\\ 0.7&0&0.3\\\
0.5&0.5&0\end{array}\right)$

(b) Diagonalizable with complex eigenvalues

$\bm{P}=\left(\begin{array}[]{cccc}0.25&0.625&0.125\\\ 0.125&0.25&0.625\\\
0.125&0.125&0.75\end{array}\right)$

(c) Non-diagonalizable with real eigenvalues

$\bm{P}=\left(\begin{array}[]{cccc}0.6&0&0.4&0\\\ 0.25&0.5&0&0.25\\\
0.25&0&0.5&0.25\\\ 0&0.5&0&0.5\end{array}\right)$

(d) Diagonalizable with real eigenvalues

Figure 18: (a-d) Four irreducible non-reversible Markov chains (top), that
have transition (bottom) with different properties.

####  4.3.2 Alternative methods

One general technique for treating a non-diagonalizable matrix $\bm{X}$ is to
add a perturbation so that it becomes diagonalizable. This is based on the
notion that diagonalizable matrices densely fill the set of all matrices [67],
meaning that it is always possible to find some nearby matrix
$\bm{X}^{\prime}$ that is diagonalizable. In one study, a method along these
lines was developed for dealing with non-diagonalizable transition matrices
[68]. In particular, for a starting transition matrix $\bm{P}$, a perturbation
matrix $\bm{E}$ is found such that $\bm{P}^{\prime}=\bm{P}+\bm{E}$ preserves a
number of the spectral properties of $\bm{P}$ and is diagonalizable. However,
two limitations of this method are (i) that it has computational complexity
$\mathcal{O}(N^{8})$ for $N\times N$ matrices, and (ii) the resulting
transition matrix can still have complex eigenvalues.

Other lines of work have attempted to circumvent these issues by using
alternative matrix decompositions, with a prominent example being the real
Schur decomposition [31, 34, 61, 69, 70].999It should be noted that most of
these studies primarily consider non-reversible chains that are ergodic. This
decomposition provides a set of real orthogonal basis vectors, known as Schur
vectors, that spans the eigenspaces of $\bm{X}$ [67]. This basis is not unique
and corresponds to some ordering of the eigenvalues of $\bm{X}$, with the
first $k$ Schur vectors spanning the eigenspaces of the first $k$ eigenvectors
in this ordering. Therefore, given some Schur decomposition of $\bm{X}$, if
$U_{k}=(\bm{u}_{1},\bm{u}_{2},...,\bm{u}_{k})$ is the set of first $k$ Schur
vectors, then for any linear combination
$\tilde{\bm{u}}=\sum_{\gamma=1}^{k}c_{\gamma}\bm{u}_{\gamma}$ it is guaranteed
that $\bm{X}\tilde{\bm{u}}\in\text{span}(U_{k})$. For this reason, $U_{k}$ is
said to be an invariant subspace of $\bm{X}$ [67], and when $k<<N$ it provides
a low dimensional description of the transformation that $\bm{X}$ represents.
The real Schur decomposition is therefore a useful alternative to the
eigendecomposition. However, in order that the basis captures the most
important information about $\bm{X}$, a reordering algorithm is needed to
specify which eigenspaces of $\bm{X}$ it should span, and various methods for
this have been developed [71, 72, 73, 74, 75]. Furthermore, it is worth
emphasizing that in contrast to the eigendecomposition, the real Schur
decomposition is guaranteed to exist for any real square matrix $\bm{X}$,
meaning that it sidesteps the issues of non-diagonalizability and complex
feature spaces that can occur with transition matrices of non-reversible
Markov chains. In the field of machine learning, the real Schur decomposition
of transition matrices has been used as a tool for clustering [69] as well as
for building state representations in reinforcement learning [70].

####  4.3.3 Directed Normalized Graph Laplacian

In Section 4.2.2, the normalized graph Laplacian $\bm{\mathcal{L}}$ was
introduced as a way to get a more precise description of the left and right
eigenvectors belonging to transition matrices of reversible Markov chains.
Generalizing $\bm{\mathcal{L}}$ to directed graphs is challenging since two of
its defining features are that it is symmetric and positive semi-definite,
neither of which can be satisfied by Equation 110 if $\bm{W}$ is non-
symmetric. However, various definitions for directed graphs exist, and while
some loosen the constraint that $\bm{\mathcal{L}}$ should be positive semi-
definite [76, 77, 78, 79], others strictly enforce this via a type of
symmetrization [80]. We here focus on the latter type, and demonstrate
connections that this has to some of the material in Section 2.

Perhaps the simplest method along these lines is to symmetrize the weight
matrix $\bm{W}$ of a directed graph $G$ to get an alternative weight matrix
$\bm{W}_{\text{sym}}$, e.g. $\bm{W}_{\text{sym}}=\bm{W}+\bm{W}^{T}$ or
$\bm{W}_{\text{sym}}=\bm{W}^{T}\bm{W}$, and then use the regular definition of
the normalized Laplacian using this new matrix, i.e.
$\bm{D}^{-\frac{1}{2}}\bm{W}_{\text{sym}}\bm{D}^{-\frac{1}{2}}$. Since
$\bm{W}_{\text{sym}}$ describes an undirected graph, the resulting object can
be interpreted in the same way as Section 4.2.2. However, a major drawback of
this approach is that the graphs described by $\bm{W}$ and
$\bm{W}_{\text{sym}}$ can have very different structural properties. For
instance, there is no guarantee that the random walks on these two graphs have
stationary distributions that bear any resemblance to one another. Indeed,
various studies in machine learning have indicated that symmetrizing $\bm{W}$
leads to a significant erasure of structural information from a directed graph
[81, 82, 13, 26].

A more principled approach was given in [80], in which the directed normalized
graph Laplacian is defined as:

$\bm{\mathcal{L}}_{\text{dir}}:=\bm{\mathbbm{1}}-\frac{\bm{\Pi}^{\frac{1}{2}}\bm{P\Pi}^{-\frac{1}{2}}+\bm{\Pi}^{-\frac{1}{2}}\bm{P}^{T}\bm{\Pi}^{\frac{1}{2}}}{2}$
(121)

where $\bm{P}$ and $\bm{\Pi}$ are defined as usual. In the original paper,
restrictions are placed on the underlying graph so that $\bm{P}$ is ergodic.
Among other things, this means that the stationary probabilities are all non-
zero, which is needed for $\bm{\Pi}^{-\frac{1}{2}}$ to be well-defined. In the
next section, we present a method for enforcing this property for any directed
graph $G$, but for now we simply assume that $\bm{\pi}>0$. Equation 121 can be
simplified as follows:

$\displaystyle\bm{\mathcal{L}}_{\text{dir}}$
$\displaystyle=\bm{\mathbbm{1}}-\frac{\bm{\Pi}^{\frac{1}{2}}\bm{P\Pi}^{-\frac{1}{2}}+\bm{\Pi}^{\frac{1}{2}}(\bm{\Pi}^{-1}\bm{P}^{T}\bm{\Pi})\bm{\Pi}^{-\frac{1}{2}}}{2}$
(122)
$\displaystyle=\bm{\mathbbm{1}}-\bm{\Pi}^{\frac{1}{2}}\underbrace{\bigg{(}\frac{\bm{P}+\bm{\Pi}^{-1}\bm{P}^{T}\bm{\Pi}}{2}\bigg{)}}_{=\bm{P}_{\text{A}}}\bm{\Pi}^{-\frac{1}{2}}$
(123)

where $\bm{P}_{\text{A}}$ is the additive reversibilization of the random walk
(2.6.6). Thus, by comparing Equation 123 to Equation 109, we see that
$\bm{\mathcal{L}}_{\text{dir}}$ is a variant of $\bm{\mathcal{L}}$ but where
$\bm{P}$ has been exchanged for $\bm{P}_{\text{A}}$. Thus, this corresponds to
a symmetrization of the stationary flow between states (Equation 80). While
this transformation still destroys some information about the underlying graph
$G$, it has been observed empirically that this effect is less severe in
comparison to methods that symmetrize $\bm{W}$ itself [81, 82, 13, 26]. For
example, note that $\bm{P}$ and $\bm{P}_{\text{A}}$ describe random walks that
have the same stationary distributions (2.6.6).

The only time that symmetrizing $\bm{W}$ and using $\bm{P}_{\text{A}}$ yields
the same result is in the special case of a balanced directed graph. In this
case, $\bm{\Pi}^{\frac{1}{2}}=z^{-\frac{1}{2}}\bm{D}^{\frac{1}{2}}$ (4.1.4),
which allows us to simplify Equation 123:

$\displaystyle\bm{\mathcal{L}}_{\text{dir}}$
$\displaystyle=\bm{\mathbbm{1}}-z^{-\frac{1}{2}}\bm{D}^{\frac{1}{2}}\bigg{(}\frac{\bm{D}^{-1}\bm{W}+\bm{D}^{-1}(\bm{D}^{-1}\bm{W})^{T}\bm{D}}{2}\bigg{)}z^{\frac{1}{2}}\bm{D}^{-\frac{1}{2}}$
(124)
$\displaystyle=\bm{\mathbbm{1}}-\bm{D}^{\frac{1}{2}}\bigg{(}\frac{\bm{D}^{-1}\bm{W}+\bm{D}^{-1}\bm{W}^{T}\bm{D}^{-1}\bm{D}}{2}\bigg{)}\bm{D}^{-\frac{1}{2}}$
(125)
$\displaystyle=\bm{\mathbbm{1}}-\bm{D}^{\frac{1}{2}}\bigg{(}\frac{\bm{D}^{-1}\bm{W}+\bm{D}^{-1}\bm{W}^{T}}{2}\bigg{)}\bm{D}^{-\frac{1}{2}}$
(126)
$\displaystyle=\bm{\mathbbm{1}}-\bm{D}^{-\frac{1}{2}}\bigg{(}\frac{\bm{W}+\bm{W}^{T}}{2}\bigg{)}\bm{D}^{-\frac{1}{2}}$
(127)

meaning that $\bm{\mathcal{L}}_{\text{dir}}$ is equivalent to an additive
symmetrization of $\bm{W}$. However, in most practical applications directed
graphs are not balanced, and it is in these cases that using
$\bm{P}_{\text{A}}$ preserves more information about a directed graph than
simply symmetrizing $\bm{W}$.

The directed normalized Laplacian has been used in various contexts of machine
learning as a way to generalize methods that are restricted to undirected
graphs. It has been applied to problems such as spectral clustering [13, 14],
graph embedding [83, 84], graph-based classification [23], and value function
approximation in reinforcement learning [26]. In most of these applications,
ergodicity is enforced on the random walk described by $\bm{P}$, and in the
next section we introduce the standard method for doing this.

####  4.3.4 Random surfer model

As explained in Section 2.5, ergodic Markov chains have the useful property
that they are guaranteed to converge to a unique stationary distribution, and
various reasons were given for why this is desirable in a general context. For
directed graphs, it is a particularly beneficial property, since without it a
random walk can get trapped in a small cluster of states, or even a single
absorbing state. Because of this, sometimes ergodicity is enforced for random
walks on directed graphs [85, 23, 14, 13, 26]. We remind readers that one
effect this has is that $\bm{\pi}>0$, meaning that the directed normalized
Laplacian is well-defined.

The typical method used for enforcing ergodicity can be thought of as a
variation on the random walk process. Given a directed graph $G$ with weight
matrix $\bm{W}$, at each time step there are two possible outcomes: either a
regular random walk is performed with probability $\alpha$, or the process
teleports randomly to any vertex with probability $1-\alpha$. This is known as
a random surfer model or teleporting random walk, and it appeared for the
first time in the PageRank algorithm [85]. If $\bm{P}$ and
$\bm{P}_{\text{tel}}$ represent the transition probabilities of the two
possible outcomes at each time point, then the overall process is described by
the following transition matrix:

$\bm{P}^{\prime}:=\alpha\bm{P}+(1-\alpha)\bm{P}_{\text{tel}}$ (128)

which is sometimes referred to as a Google matrix [86].

It is worth noting that there exist many variants of the random surfer model
that differ in the assumptions they make about $\bm{P}_{\text{tel}}$ [87]. For
example, teleporting transitions can either be uniformly random, or biased
towards certain vertices through a set of weights. Furthermore, the parameter
$\alpha\in[0,1]$ is known as the damping factor and determines how close the
process is to a regular random walk. Typically, it is set close to $1$, so
that the process still accurately reflects the structure of the underlying
graph $G$.

In the case of uniform teleportation, it is straightforward to specify the
teleportation probabilities since they are all equal to $\frac{1}{N}$.
Therefore, Equation 128 becomes:

$\bm{P}^{\prime}=\alpha\bm{P}+(1-\alpha)\frac{\mathbf{1}}{N}$ (129)

where $\mathbf{1}\in\mathbb{R}^{N\times N}$ denotes a matrix of ones. While
$\bm{P}$ represents the random walk on $G$, we can interpret
$\frac{\mathbf{1}}{N}$ as the transition matrix of a random walk on a graph
$G_{\text{C}}$ that has the same number of vertices as $G$ but where each
vertex $v_{i}$ is connected to all others including itself.101010Sometimes
objects like $G_{\text{C}}$ are referred to as complete graphs or fully
connected networks. However, such terms typically do not include the
possibility of self-loops, which we by definition need since we consider
uniform teleportation. An example is shown in Figure 19, with (a) showing the
starting graph $G$ and (b) showing $G_{\text{C}}$. In (c, d) we show the
transition matrices $\bm{P}$ and $\bm{P}_{\text{tel}}$ of the random walks on
$G$ and $G_{\text{C}}$, respectively. Finally, in (e) we show the transition
matrix of the overall teleporting random walk with $\alpha=0.85$ is shown.

(a)

(b)

$\bm{P}=\left(\begin{array}[]{cccccccc}0&1&0&0&0&0&0&0\\\ 0&0&0&0&0&0&0&1\\\
0&0.4&0&0&0&0&0.6&0\\\ 0&1&0&0&0&0&0&0\\\ 0&0&1&0&0&0&0&0\\\
0&0&0&0&0&0&1&0\\\ 0&0&0&0&0.8&0.2&0&0\\\ 0.6&0&0&0.4&0&0&0&0\\\
\end{array}\right)$

(c)

$\bm{P}_{\text{tel}}=\frac{1}{8}\left(\begin{array}[]{cccccccc}1&1&1&1&1&1&1&1\\\
1&1&1&1&1&1&1&1\\\ 1&1&1&1&1&1&1&1\\\ 1&1&1&1&1&1&1&1\\\ 1&1&1&1&1&1&1&1\\\
1&1&1&1&1&1&1&1\\\ 1&1&1&1&1&1&1&1\\\ 1&1&1&1&1&1&1&1\\\ \end{array}\right)$

(d)

$\bm{P}^{\prime}=\left(\begin{array}[]{cccccccc}0.02&0.87&0.02&0.02&0.02&0.02&0.02&0.02\\\
0.02&0.02&0.02&0.02&0.02&0.02&0.02&0.87\\\
0.02&0.36&0.02&0.02&0.02&0.02&0.53&0.02\\\
0.02&0.87&0.02&0.02&0.02&0.02&0.02&0.02\\\
0.02&0.02&0.87&0.02&0.02&0.02&0.02&0.02\\\
0.02&0.02&0.02&0.02&0.02&0.02&0.87&0.02\\\
0.02&0.02&0.02&0.02&0.7&0.19&0.02&0.02\\\
0.53&0.02&0.02&0.36&0.02&0.02&0.02&0.02\\\ \end{array}\right)$

(e)

Figure 19: (a) a directed graph $G$, (b) the graph $G_{\text{C}}$, (c-d) the
corresponding transition matrices $\bm{P}$ and $\bm{P}_{\text{tel}}$,
respectively, (e) the random surfer transition matrix $\bm{P}^{\prime}$ for
$\alpha=0.85$, with transition probabilities accurate to $2$ decimal places.

Due to the teleportation term $\bm{P}_{\text{tel}}$, from any given state
$s_{i}$ there is always a non-zero probability to access any other state, or
to stay in the same state. By virtue of this, such processes are guaranteed to
be both irreducible and aperiodic, and therefore ergodic.

###  4.4 Summary

This concludes our treatment of random walks. The material presented in this
section forms a useful framework that connects Markov chains and graphs. On
the one hand, describing a Markov chain as a process taking place on a graph
is a useful interpretation since it provides intuition about underlying
relationships between states. Furthermore, it allows one to apply the toolkit
of spectral graph theory to Markov chains. On the other hand, graphs by
themselves represent only static relationships between entities, and
performing a random walk is one way to describe a graph in terms that are
dynamic/temporal. Moreover, the fact that a transition matrix can be easily
exponentiated, i.e $\bm{P}^{k}$, means that a random walk provides information
about a graph $G$ at multiple time scales, which is a property that has been
exploited in the field of manifold learning [15, 16]. As a final note, in the
current section many concepts and results from linear algebra are required,
for which we recommend [35] as a general resource and [31] as a more specific
summary of the application to transition matrices.

##  5 Conclusion

The key motivation of this tutorial is to provide a single introductory text
on the spectral theory of Markov chains. By bringing together concepts and
results from different areas of mathematics, this work is a useful resource
for readers hoping to gain a broad, yet concise, overview of this topic. Since
we only assume minimal exposure to concepts from linear algebra and
probability theory, and since focus is placed on providing intuition rather
than rigorous results, the material of this tutorial is accessible to
researchers and students in a variety of quantitative disciplines. For those
working in fields related to machine learning and data mining, this work is
particularly relevant due to the applications discussed at various points.
Although the material mostly consists of known results, two novel
contributions are the categorization of eigenvalues given in Table 1 and
Figure 3, as well as the notion of random walk sets (4.1.1).

Our presentation involved two different paradigms for interpreting and
analyzing Markov chains. In Section 2 we presented a categorization based on
the transition structure and asymptotic behavior, and in Section 3 we instead
formalized the idea of a Markov chain as a type of graph. In Section 4, we
connected these two perspectives by introducing the idea of a random walk, and
in doing so provided a number of parallels between some categories of Markov
chains and certain types of graphs. In particular, one theme that aligns the
two perspectives is the distinction between reversible/non-reversible Markov
chains on the one hand, and undirected/directed graphs on the other, where in
both cases the former option is easier to treat than the latter. With the
additional use of results from linear algebra, this provided us with an in-
depth description of the eigenvalues and eigenvectors of transition matrices
in the reversible case. Finally, we discussed various attempts that have been
made to generalize spectral methods to the non-reversible case.

##  6 Acknowledgements

We would like to thank Jonathan Hermon for some useful discussions on Markov
chain theory, as well as Josué Tonelli‑Cueto for his insight on the Perron-
Frobenius theorem and various concepts in linear algebra.

##  Appendix A Proofs

###  A.1 2.6.2

###### Proof.

Assume that $\bm{P}$ is the transition matrix of a reducible recurrent Markov
chain with $r$ communicating classes. Therefore, for a suitable indexing of
states in $\mathcal{S}$ the transition matrix of this chain has a block
diagonal form:

$\bm{P}=\left(\begin{array}[]{cccc}\framebox{$\bm{P}_{1}$}&0&\cdots&0\\\
0&\framebox{$\bm{P}_{2}$}&\cdots&0\\\ \vdots&\vdots&\ddots&\vdots\\\
0&0&\cdots&\framebox{$\bm{P}_{r}$}\end{array}\right)$ (130)

where $\bm{P}_{k}$ is a transition matrix composed of the transition
probabilities for states in the $k$-th class. Furthermore, if $\bm{\pi}>0$ is
one of its stationary distributions, it can be written as
$\bm{\pi}=\sum_{k=1}^{r}\alpha_{k}\bm{\pi}_{k}$ where each $\bm{\pi}_{k}$ has
non-zero entries only in the $k$-th class and $\alpha_{k}>0$ (2.4.9). Thus,
given the same indexing of states the matrix $\bm{\Pi}$ and its inverse
$\bm{\Pi}^{-1}$ have the following forms:

$\bm{\Pi}=\left(\begin{array}[]{cccc}\framebox{$\alpha_{1}\bm{\Pi}_{1}$}&0&\cdots&0\\\
0&\framebox{$\alpha_{2}\bm{\Pi}_{2}$}&\cdots&0\\\
\vdots&\vdots&\ddots&\vdots\\\
0&0&\cdots&\framebox{$\alpha_{r}\bm{\Pi}_{r}$}\end{array}\right)\quad\bm{\Pi}^{-1}=\left(\begin{array}[]{cccc}\framebox{$(\alpha_{1}\bm{\Pi}_{1})^{-1}$}&0&\cdots&0\\\
0&\framebox{$(\alpha_{2}\bm{\Pi}_{2})^{-1}$}&\cdots&0\\\
\vdots&\vdots&\ddots&\vdots\\\
0&0&\cdots&\framebox{$(\alpha_{1}\bm{\Pi}_{r})^{-1}$}\end{array}\right)$ (131)

where $\bm{\Pi}_{k}$ is the diagonal block matrix formed from the non-zero
entries of $\bm{\pi}_{k}$. Hence, because $\bm{P}_{\textup{rev}}$ is a product
of three block diagonal matrices, it too has the same form:

$\displaystyle\bm{P}_{\textup{rev}}$
$\displaystyle=\bm{\Pi}^{-1}\bm{P^{T}}\bm{\Pi}$ (132)
$\displaystyle=\left(\begin{array}[]{cccc}\framebox{$\bm{P}_{\textup{rev},1}$}&0&\cdots&0\\\
0&\framebox{$\bm{P}_{\textup{rev},2}$}&\cdots&0\\\
\vdots&\vdots&\ddots&\vdots\\\
0&0&\cdots&\framebox{$\bm{P}_{\textup{rev},r}$}\end{array}\right)$ (137)

where $\bm{P}_{\textup{rev},k}$ contains the transition probabilities of
states in the $k$-th class for the time reversed Markov chain. Furthermore, we
can easily evaluate these block matrices:

$\displaystyle\bm{P}_{\textup{rev},k}$
$\displaystyle=(\alpha_{k}\bm{\Pi}_{k})^{-1}(\bm{P}_{k})^{T}(\alpha_{k}\bm{\Pi}_{k})$
(138)
$\displaystyle=\frac{\alpha_{k}}{\alpha_{k}}(\bm{\Pi}_{k})^{-1}(\bm{P}_{k})^{T}(\bm{\Pi}_{k})$
(139) $\displaystyle=(\bm{\Pi}_{k})^{-1}(\bm{P}_{k})^{T}(\bm{\Pi}_{k})$ (140)

Thus, the matrix $\bm{P}_{\textup{rev}}$ does not depend on the $\alpha_{k}$
terms that parameterize the stationary distribution, meaning that the time
reversed Markov chain the same regardless of which distribution is considered.
∎

###  A.2 2.6.3

###### Proof.

Assume that $\bm{P}$ is the transition matrix of a recurrent Markov chain and
$\bm{\pi}>0$ is one of its stationary distributions. First note that summing
over the $j$-th row or column of the flow matrix $\bm{F}^{\bm{\pi}}$ gives the
same result:

$\displaystyle\sum_{i=1}^{N}(\bm{F}^{\bm{\pi}})_{ji}$
$\displaystyle=\sum_{i=1}^{N}\pi_{j}P_{ji}=\pi_{j}\sum_{i=1}^{N}P_{ji}=\pi_{j}$
(141) $\displaystyle\sum_{i=1}^{N}(\bm{F}^{\bm{\pi}})_{ij}$
$\displaystyle=\sum_{i=1}^{N}\pi_{i}P_{ij}\overset{(\ref{eq:GB2})}{=}\pi_{j}$
(142)

which in vector notation can be written as
$\bm{\pi}^{T}=\bm{1}^{T}\bm{F}^{\bm{\pi}}=\bm{1}^{T}(\bm{F}^{\bm{\pi}})^{T}$,
where the symbol $\bm{1}$ denotes a vector of ones. Using this we see that:

$\displaystyle\bm{\pi}^{T}$ $\displaystyle=\bm{\pi}^{T}\bm{P}$ (144)
$\displaystyle\Longleftrightarrow$ $\displaystyle=\bm{1}^{T}\bm{\Pi}\bm{P}$
(145) $\displaystyle\Longleftrightarrow$
$\displaystyle=\bm{1}^{T}\bm{F}^{\bm{\pi}}$ (146)
$\displaystyle\Longleftrightarrow$
$\displaystyle=\bm{1}^{T}(\bm{F}^{\bm{\pi}})^{T}$ (147)
$\displaystyle\Longleftrightarrow$
$\displaystyle=\bm{1}^{T}\bm{P}^{T}\bm{\Pi}$ (148)
$\displaystyle\Longleftrightarrow$
$\displaystyle=\bm{1}^{T}\bm{\Pi}\bm{\Pi}^{-1}\bm{P}^{T}\bm{\Pi}$ (149)
$\displaystyle\Longleftrightarrow$
$\displaystyle=\bm{\pi}^{T}\bm{\Pi}^{-1}\bm{P}^{T}\bm{\Pi}$ (150)
$\displaystyle\Longleftrightarrow$
$\displaystyle=\bm{\pi}^{T}\bm{P}_{\text{rev}}$ (151)

Therefore, $\bm{\pi}$ is a stationary distribution of $\mathcal{X}$ if and
only if it is a stationary distribution of $\tilde{\mathcal{X}}$. ∎

###  A.3 Theorem 4.1.2

###### Proof.

($\Rightarrow$) Assume that $\bm{P}$ is the transition matrix of a recurrent
Markov chain. Then, for any stationary distribution $\bm{\pi}>0$ the flow
matrix $\bm{F}^{\bm{\pi}}=\bm{\Pi P}$ corresponds to one of the allowed graphs
in $\mathcal{RW}(\mathcal{X})$. Therefore, using the same argument given in
the proof of 2.6.3, the row and column sums of $\bm{F}^{\bm{\pi}}$ are the
same, meaning that this matrix describes a balanced graph.
($\Leftarrow$) We adapt this direction of the proof from [48], where the
unweighted case is considered. Assume that $G$ is a balanced graph with weight
matrix $\bm{W}$, and that $\mathcal{X}$ is the Markov chain realised by a
random walk on this graph. Now consider the distribution
$\bm{\pi}=\frac{1}{z}(d_{1},d_{2},...,d_{N})^{T}$, where
$z=\sum_{j=1}^{N}d_{j}=\text{vol}(G)$ is needed in order for $\bm{\pi}$ to sum
to $1$. We can then easily verify that the equations of global balance hold
for this distribution (Equation 19):

$\sum_{i=1}^{N}\pi_{i}P_{ij}\overset{(\ref{eq:RWmat})}{=}\sum_{i=1}^{N}\pi_{i}\frac{W_{ij}}{d_{i}}=\sum_{i=1}^{N}\frac{d_{i}}{z}\frac{W_{ij}}{d_{i}}=\sum_{i=1}^{N}\frac{W_{ij}}{z}=\frac{1}{z}\underbrace{\sum_{i=1}^{N}W_{ij}}_{=d_{j}^{-}}=\frac{d_{j}}{z}=\pi_{j}$
(152)

and so $\bm{\pi}^{T}\bm{P}=\bm{\pi}^{T}$ which means that $\bm{\pi}$ is a
stationary distribution of the chain. Note that the summation in the fourth
expression defines the in-degree of vertex $v_{j}$, but since the graph $G$ is
balanced we only have one degree $d_{j}$ associated to each vertex. Lastly,
since isolated vertices are not allowed, each degree must be bigger than zero,
meaning similarly that $\pi_{i}>0$ $\forall s_{i}\in\mathcal{S}$. Hence, there
are no transient states, and $\mathcal{X}$ is recurrent. ∎

###  A.4 Theorem 4.1.3

###### Proof.

Assume that $\mathcal{X}$ is a recurrent Markov chain and $G$ is one of the
balanced graphs in $\mathcal{RW}(\mathcal{X})$. Using the same argument from
the second part of the proof of Theorem 4.1.2, the degrees of $G$ are related
to a stationary distribution $\bm{\pi}>0$ of the chain via
$\pi_{i}=\frac{d_{i}}{z}$. From Theorem 2.6.4 we know that $\mathcal{X}$ is
reversible if and only if the flow matrix associated $\bm{\pi}$ is symmetric,
and it is straightforward to show that this equivalent to $G$ being
undirected:

$\displaystyle\bm{F}^{\bm{\pi}}$ $\displaystyle=(\bm{F}^{\bm{\pi}})^{T}$ (153)
$\displaystyle\Longleftrightarrow$ $\displaystyle\bm{\Pi}\bm{P}$
$\displaystyle=\bm{P}^{T}\bm{\Pi}$ (154) $\displaystyle\Longleftrightarrow$
$\displaystyle\bm{\Pi}\bm{D}^{-1}\bm{W}$
$\displaystyle=\bm{W}^{T}\bm{D}^{-1}\bm{\Pi}$ (155)
$\displaystyle\Longleftrightarrow$
$\displaystyle\frac{1}{z}\bm{D}\bm{D}^{-1}\bm{W}$
$\displaystyle=\bm{W}^{T}\bm{D}^{-1}\frac{1}{z}\bm{D}$ (156)
$\displaystyle\Longleftrightarrow$ $\displaystyle\bm{W}$
$\displaystyle=\bm{W}^{T}$ (157)

and since $G$ was chosen arbitrarily, this applies to any balanced graph in
$\mathcal{RW}(\mathcal{X})$. ∎

###  A.5 4.1.4

###### Proof.

See the second part of the proof of Theorem 4.1.2. ∎

###  A.6 Theorem 4.2.4

###### Proof.

($\Rightarrow$) Let $\bm{x},\bm{x}^{\prime}\in\mathbb{R}^{n}$ be two arbitrary
vectors. Then, if $\bm{P}$ is the transition matrix of a reversible chain and
$\bm{\pi}>0$ is one of its stationary distributions, it is guaranteed that
$\bm{\Pi}\bm{P}=\bm{P}^{T}\bm{\Pi}$ (Theorem 2.6.4). Using this, we can show
that $\bm{P}$ satisfies Equation 100:

$\displaystyle\langle\bm{x},\bm{P}\bm{x}^{\prime}\rangle_{\bm{\Pi}}$
$\displaystyle{=}\bm{x}^{T}\bm{\Pi}\bm{P}\bm{x}^{\prime}$ (158)
$\displaystyle=\bm{x}^{T}\bm{P}^{T}\bm{\Pi}\bm{x}^{\prime}$ (159)
$\displaystyle=(\bm{P}\bm{x})^{T}\bm{\Pi}\bm{x}^{\prime}$ (160)
$\displaystyle{=}\langle\bm{P}\bm{x},\bm{x}^{\prime}\rangle_{\bm{\Pi}}$ (161)

($\Leftarrow$) Let $\bm{P}$ be the transition matrix of a reversible Markov
chain, and $\bm{\pi}>0$ one of its stationary distributions. Equation 100 can
be written as:

$\bm{x}^{T}\bm{\Pi}\bm{P}\bm{x}^{\prime}=\bm{x}^{T}\bm{P}^{T}\bm{\Pi}\bm{x}\quad\forall\bm{x},\bm{x}^{\prime}\in\mathbb{R}^{n}$
(162)

If we choose $\bm{x}=\bm{e}_{i}$ to be a vector with $i$-th entry equal to $1$
and zeros elsewhere, this reduces to:

$\displaystyle\sum_{j^{\prime}}\pi_{i}P_{ij^{\prime}}x^{\prime}_{j^{\prime}}$
$\displaystyle=\sum_{j^{\prime\prime}}(\bm{P}^{T})_{ij^{\prime\prime}}\pi_{j^{\prime\prime}}x^{\prime}_{j^{\prime\prime}}$
(163)
$\displaystyle\pi_{i}\sum_{j^{\prime}}P_{ij^{\prime}}x^{\prime}_{j^{\prime}}$
$\displaystyle=\sum_{j^{\prime\prime}}P_{j^{\prime\prime}i}\pi_{j^{\prime\prime}}x^{\prime}_{j^{\prime\prime}}$
(164)

If we then choose $\bm{x}^{\prime}=\bm{e}_{j}$ to be a vector with $j$-th
entry equal to $1$ and zeros elsewhere, we get:

$\pi_{i}P_{ij}=\pi_{j}P_{ji}$ (165)

Since the indices $i$ and $j$ were chosen arbitrarily, Equation 165 between
any pair of states. Therefore, the chain is reversible (Theorem 2.6.4). ∎

###  A.7 Theorem 4.2.5

###### Proof.

Let $\mathcal{X}$ be a reversible Markov chain with transition matrix $\bm{P}$
and a stationary distribution $\bm{\pi}>0$, and let
$\bm{K}=\bm{\Pi}^{\frac{1}{2}}\bm{P}\bm{\Pi}^{-\frac{1}{2}}$. Then the
$(i,j)$-th element of $\bm{K}$ is:

$\displaystyle K_{ij}$ $\displaystyle=\hskip
3.0pt\sqrt{\pi_{i}}P_{ij}\frac{1}{\sqrt{\pi_{j}}}$ (166)
$\displaystyle{=}\sqrt{\pi_{i}}P_{ji}\frac{\pi_{j}}{\pi_{i}}\frac{1}{\sqrt{\pi_{j}}}$
(167) $\displaystyle=\hskip 3.0pt\sqrt{\pi_{j}}P_{ji}\frac{1}{\sqrt{\pi_{i}}}$
(168) $\displaystyle=\hskip 3.0ptK_{ji}$ (169)

meaning that $\bm{K}$ is a symmetric matrix. Note that in the third line we
made use of detailed balance which holds for $\bm{\pi}>0$ if and only if
$\mathcal{X}$ is reversible. Therefore, this concludes both directions of the
proof.

In order to establish the uniqueness of $\bm{K}$, we make use of the fact that
a reversible Markov chain must be recurrent, meaning that any stationary
distribution $\bm{\pi}>0$ is of the form
$\bm{\pi}=\sum_{k=1}^{r}\alpha_{k}\bm{\pi}_{k}$ with $\alpha_{k}>0$ (2.4.9).
Since all entries of $\bm{\pi}$ are greater than zero,
$K_{ij}=\sqrt{\pi_{i}}P_{ij}\frac{1}{\sqrt{\pi_{j}}}\neq 0$ iff $P_{ij}\neq
0$. For a recurrent chain, the latter can only be true for pairs of states in
the same communicating class. If $s_{i}$ and $s_{j}$ belong to the $k$-th
communicating class, then:

$\displaystyle K_{ij}$
$\displaystyle=\sqrt{\pi_{i}}P_{ij}\frac{1}{\sqrt{\pi_{j}}}$ (170)
$\displaystyle=\sqrt{\alpha_{k}\pi_{k,i}}P_{ij}\frac{1}{\sqrt{\alpha_{k}\pi_{k,j}}}$
(171) $\displaystyle=\sqrt{\pi_{k,i}}P_{ij}\frac{1}{\sqrt{\pi_{k,j}}}$ (172)

where $\pi_{k,i}$ denotes the $i$-th component of the stationary distribution
associated to the $k$-th class. Hence, the non-zero entries of $\bm{K}$ do not
depend on the values of $\alpha_{k}$, i.e. they are irrespective of the
stationary distribution used. ∎

###  A.8 Theorem 4.2.6

###### Proof.

Let $\mathcal{X}$ be a reversible Markov chain with transition matrix
$\bm{P}$. The proof of Theorem 4.2.5 establishes that this is equivalent to
$\bm{K}=\bm{\Pi}^{\frac{1}{2}}\bm{P}\bm{\Pi}^{-\frac{1}{2}}$ being symmetric,
where $\bm{\pi}>0$ is a stationary distribution of the chain. By virtue of
Theorem 4.2.2, this in turn is equivalent to the existence of an orthogonal
matrix $\bm{Y}$ for which:

$\displaystyle\bm{D}$ $\displaystyle=\bm{Y}^{T}\bm{K}\bm{Y}$ (173)
$\displaystyle=\bm{Y}^{T}\bm{\Pi}^{\frac{1}{2}}\bm{P}\bm{\Pi}^{-\frac{1}{2}}\bm{Y}$
(174)

Equation 174 says that $\bm{P}$ has the same eigenvalues as $\bm{K}$, which
are real. It also tells us that $\bm{P}$ is diagonalizable by sets of right
and left eigenvectors that are related to the eigenvectors of $\bm{K}$ by
$\bm{\Pi}^{-\frac{1}{2}}$ and $\bm{\Pi}^{\frac{1}{2}}$, respectively. Hence,
if $\bm{y}_{\omega}$ is an eigenvector of $\bm{K}$ with eigenvalue
$\lambda_{\omega}$, then
$\bm{r}_{\omega}=\bm{\Pi}^{-\frac{1}{2}}\bm{y}_{\omega}$ and
$\bm{l}_{\omega}=\bm{\Pi}^{\frac{1}{2}}\bm{y}_{\omega}$ are a pair of
corresponding right and left eigenvectors of $\bm{P}$ with the same
eigenvalue. Using this we see that if $\bm{r}_{\omega}$ and $\bm{r}_{\gamma}$
are a pair of right eigenvectors of $\bm{P}$, then:

$\langle\bm{r}_{\omega},\bm{r}_{\gamma}\rangle_{\bm{\Pi}}=\langle\bm{\Pi}^{-\frac{1}{2}}\bm{y}_{\omega},\bm{\Pi}^{-\frac{1}{2}}\bm{y}_{\gamma}\rangle_{\bm{\Pi}}=\bm{y}_{\omega}^{T}\underbrace{\bm{\Pi}^{-\frac{1}{2}}\bm{\Pi}\bm{\Pi}^{-\frac{1}{2}}}_{=\mathbbm{1}}\bm{y}_{\gamma}=\bm{y}_{\omega}^{T}\bm{y}_{\gamma}=\delta_{\omega\gamma}$
(175)

where we have used the fact that the basis $\bm{Y}$ is orthonormal. Similarly,
if $\bm{l}_{\omega}$ and $\bm{l}_{\gamma}$ are a pair of left eigenvectors of
$\bm{P}$, then:

$\langle\bm{l}_{\omega},\bm{l}_{\gamma}\rangle_{\bm{\Pi}^{-1}}=\langle\bm{\Pi}^{\frac{1}{2}}\bm{y}_{\omega},\bm{\Pi}^{\frac{1}{2}}\bm{y}_{\gamma}\rangle_{\bm{\Pi}^{-1}}=\bm{y}_{\omega}^{T}\underbrace{\bm{\Pi}^{\frac{1}{2}}\bm{\Pi}^{-1}\bm{\Pi}^{\frac{1}{2}}}_{=\mathbbm{1}}\bm{y}_{\gamma}=\delta_{\omega\gamma}$
∎

###  A.9 4.2.7

###### Proof.

From the proof of Theorem 4.2.6, we know that if $\bm{Y}$ is an orthonormal
basis of $\bm{K}$ and $\bm{y}_{\omega}$ is a basis vector with eigenvalue
$\lambda_{\omega}$, then
$\bm{r}_{\omega}=\bm{\Pi}^{-\frac{1}{2}}\bm{y}_{\omega}$ and
$\bm{l}_{\omega}=\bm{\Pi}^{\frac{1}{2}}\bm{y}_{\omega}$ are right end left
eigenvectors of $\bm{P}$, respectively, with the same eigenvalue. Therefore:

$\bm{l}_{\omega}=\bm{\Pi}^{\frac{1}{2}}(\bm{\Pi}^{\frac{1}{2}}\bm{r}_{\omega})=\bm{\Pi}\bm{r}_{\omega}$
(176)

∎

###  A.10 Theorem 4.2.10

###### Proof.

Assume that $\bm{\mathcal{L}}$ is the normalized Laplacian of an undirected
graph $G$ and $\bm{x}\in\mathbb{R}^{N}$. Then:

$\displaystyle\bm{x}^{T}\bm{\mathcal{L}}\bm{x}$
$\displaystyle{=}\bm{x}^{T}\bm{x}-\bm{x}^{T}\bm{D}^{-\frac{1}{2}}\bm{WD}^{-\frac{1}{2}}\bm{x}$
(177)
$\displaystyle=\bigg{(}\sum_{i=1}^{N}x_{i}^{2}\bigg{)}-\bigg{(}\sum_{i,j=1}^{N}W_{ij}\frac{x_{i}x_{j}}{d_{i}^{\frac{1}{2}}d_{j}^{\frac{1}{2}}}\bigg{)}$
(178)
$\displaystyle=\frac{1}{2}\bigg{(}\sum_{i=1}^{N}x_{i}^{2}\bigg{)}+\frac{1}{2}\bigg{(}\sum_{j=1}^{N}x_{j}^{2}\bigg{)}-2\bigg{(}\sum_{i,j=1}^{N}W_{ij}\frac{x_{i}x_{j}}{d_{i}^{\frac{1}{2}}d_{j}^{\frac{1}{2}}}\bigg{)}$
(179)
$\displaystyle=\frac{1}{2}\bigg{(}\sum_{i=1}^{N}x_{i}^{2}\underbrace{\frac{d_{i}}{d_{i}}}_{=1}\bigg{)}+\frac{1}{2}\bigg{(}\sum_{j=1}^{N}x_{j}^{2}\underbrace{\frac{d_{j}}{d_{j}}}_{=1}\bigg{)}-2\bigg{(}\sum_{i,j=1}^{N}W_{ij}\frac{x_{i}x_{j}}{d_{i}^{\frac{1}{2}}d_{j}^{\frac{1}{2}}}\bigg{)}$
(180)
$\displaystyle=\frac{1}{2}\bigg{(}\sum_{i=1}^{N}x_{i}^{2}\frac{\sum_{j=1}^{N}W_{ij}}{d_{i}}\bigg{)}+\frac{1}{2}\bigg{(}\sum_{j=1}^{N}x_{j}^{2}\frac{\sum_{i=1}^{N}W_{ji}}{d_{j}}\bigg{)}-2\bigg{(}\sum_{i,j=1}^{N}W_{ij}\frac{x_{i}x_{j}}{d_{i}^{\frac{1}{2}}d_{j}^{\frac{1}{2}}}\bigg{)}$
(181)
$\displaystyle=\frac{1}{2}\bigg{(}\sum_{i,j=1}^{N}x_{i}^{2}\frac{W_{ij}}{d_{i}}\bigg{)}+\frac{1}{2}\bigg{(}\sum_{i,j=1}^{N}x_{j}^{2}\frac{W_{ji}}{d_{j}}\bigg{)}-2\bigg{(}\sum_{i,j=1}^{N}W_{ij}\frac{x_{i}x_{j}}{d_{i}^{\frac{1}{2}}d_{j}^{\frac{1}{2}}}\bigg{)}$
(182)
$\displaystyle=\frac{1}{2}\sum_{i,j=1}^{N}\bigg{(}x_{i}\bigg{(}\frac{W_{ij}}{d_{i}}\bigg{)}^{\frac{1}{2}}-x_{j}\bigg{(}\frac{W_{ji}}{d_{j}}\bigg{)}^{\frac{1}{2}}\bigg{)}^{2}$
(183)
$\displaystyle=\frac{1}{2}\sum_{i,j=1}^{N}W_{ij}\bigg{(}\frac{x_{i}}{d_{i}^{\frac{1}{2}}}-\frac{x_{j}}{d_{j}^{\frac{1}{2}}}\bigg{)}^{2}\hskip
40.0pt\text{($W_{ij}=W_{ji}$ since $G$ is undirected)}$ (184)

∎

## References

  * [1] E Pardoux.  Markov Processes and Applications: Algorithms, Networks, Genome and Finance.  Wiley/Dunod, Chichester, U.K; Hoboken, NJ, 2010.
  * [2] Charu C. Aggarwal.  Data Mining.  Springer International Publishing, Cham, 2015.
  * [3] Mikhail Belkin and Partha Niyogi.  Laplacian eigenmaps and spectral techniques for embedding and clustering.  In Advances in Neural Information Processing Systems 14, pages 585–591. MIT Press, 2001.
  * [4] Mikhail Belkin and Partha Niyogi.  Laplacian Eigenmaps for Dimensionality Reduction and Data Representation.  Neural Computation, 15(6):1373–1396, June 2003.
  * [5] Y. Weiss.  Segmentation using eigenvectors: A unifying view.  In Proceedings of the Seventh IEEE International Conference on Computer Vision, pages 975–982 vol.2, Kerkyra, Greece, 1999. IEEE.
  * [6] Andrew Y. Ng, Michael I. Jordan, and Yair Weiss.  On spectral clustering: Analysis and an algorithm.  In Proceedings of the 14th International Conference on Neural Information Processing Systems: Natural and Synthetic, NIPS’01, pages 849–856, Cambridge, MA, USA, 2001. MIT Press.
  * [7] Ulrike von Luxburg.  A tutorial on spectral clustering.  Statistics and Computing, 17(4):395–416, December 2007.
  * [8] Marina Meila and Jianbo Shi.  Learning segmentation by random walks.  In T. Leen, T. Dietterich, and V. Tresp, editors, Advances in Neural Information Processing Systems, volume 13. MIT Press, 2000.
  * [9] Marina Meila and Jianbo Shi.  A random walks view of spectral segmentation.  2001\.
  * [10] Naftali Tishby and Noam Slonim.  Data clustering by markovian relaxation and the information bottleneck method.  Advances in Neural Information Processing Systems 13: 2000; Denver, November 2001.
  * [11] Marco Saerens, Francois Fouss, Luh Yen, and Pierre Dupont.  The Principal Components Analysis of a Graph, and Its Relationships to Spectral Clustering.  In Machine Learning: ECML 2004, volume 3201, pages 371–383. Springer Berlin Heidelberg, Berlin, Heidelberg, 2004.
  * [12] Ning Liu.  Markov Chains and Spectral Clustering.  In Performance Evaluation of Computer and Communication Systems. Milestones and Future Challenges, volume 6821, pages 87–98. Springer Berlin Heidelberg, Berlin, Heidelberg, 2011.
  * [13] Marina Meilă and William Pentney.  Clustering by weighted cuts in directed graphs.  In Proceedings of the 2007 SIAM International Conference on Data Mining, pages 135–144. Society for Industrial and Applied Mathematics, April 2007.
  * [14] Jiayuan Huang, Tingshao Zhu, and Dale Schuurmans.  Web Communities Identification from Random Walks.  In Knowledge Discovery in Databases: PKDD 2006, volume 4213, pages 187–198. Springer Berlin Heidelberg, Berlin, Heidelberg, 2006.
  * [15] R. R. Coifman, S. Lafon, A. B. Lee, M. Maggioni, B. Nadler, F. Warner, and S. W. Zucker.  Geometric diffusions as a tool for harmonic analysis and structure definition of data: Diffusion maps.  Proceedings of the National Academy of Sciences, 102(21):7426–7431, May 2005.
  * [16] Ronald R. Coifman and Stéphane Lafon.  Diffusion maps.  Applied and Computational Harmonic Analysis, 21(1):5–30, July 2006\.
  * [17] Benyamin Ghojogh, Ali Ghodsi, Fakhri Karray, and Mark Crowley.  Laplacian-based dimensionality reduction including spectral clustering, laplacian eigenmap, locality preserving projection, graph embedding, and diffusion map: Tutorial and survey, June 2021.
  * [18] Laurenz Wiskott and Terrence J. Sejnowski.  Slow Feature Analysis: Unsupervised Learning of Invariances.  Neural Computation, 14(4):715–770, April 2002.
  * [19] Henning Sprekeler.  On the Relation of Slow Feature Analysis and Laplacian Eigenmaps.  Neural Computation, 23(12):3287–3302, December 2011.
  * [20] Sepandar D. Kamvar, Dan Klein, and Christopher D. Manning.  Spectral learning.  In Proceedings of the 18th International Joint Conference on Artificial Intelligence, IJCAI’03, pages 561–566, San Francisco, CA, USA, 2003. Morgan Kaufmann Publishers Inc.
  * [21] Martin Szummer and Tommi Jaakkola.  Partially labeled classification with markov random walks.  In Proceedings of the 14th International Conference on Neural Information Processing Systems: Natural and Synthetic, NIPS’01, pages 945–952, Cambridge, MA, USA, 2001. MIT Press.
  * [22] Thorsten Joachims.  Transductive learning via spectral graph partitioning.  In Proceedings of the Twentieth International Conference on International Conference on Machine Learning, ICML’03, pages 290–297, Washington, DC, USA, 2003. AAAI Press.
  * [23] Dengyong Zhou, Jiayuan Huang, and Bernhard Schölkopf.  Learning from labeled and unlabeled data on a directed graph.  In Proceedings of the 22nd International Conference on Machine Learning - ICML ’05, pages 1036–1043, Bonn, Germany, 2005\. ACM Press.
  * [24] Sridhar Mahadevan.  Proto-value functions: Developmental reinforcement learning.  In Luc De Raedt and Stefan Wrobel, editors, Machine Learning, Proceedings of the Twenty-Second International Conference (ICML 2005), Bonn, Germany, August 7-11, 2005, volume 119 of ACM International Conference Proceeding Series, pages 553–560. ACM, 2005.
  * [25] Sridhar Mahadevan and Mauro Maggioni.  Proto-value functions: A laplacian framework for learning representation and control in markov decision processes.  Journal of Machine Learning Research, 8:2169–2231, December 2007\.
  * [26] Jeff Johns and Sridhar Mahadevan.  Constructing basis functions from directed graphs for value function approximation.  In Proceedings of the 24th International Conference on Machine Learning - ICML ’07, pages 385–392, Corvalis, Oregon, 2007\. ACM Press.
  * [27] Kimberly L Stachenfeld, Matthew Botvinick, and Samuel J Gershman.  Design principles of the hippocampal cognitive map.  In Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
  * [28] Kimberly L Stachenfeld, Matthew M Botvinick, and Samuel J Gershman.  The hippocampus as a predictive map.  Nature Neuroscience, 20(11):1643–1653, November 2017.
  * [29] Marek Petrik.  An analysis of laplacian methods for value function approximation in MDPs.  In Proceedings of the 20th International Joint Conference on Artifical Intelligence, IJCAI’07, pages 2574–2579, San Francisco, CA, USA, 2007. Morgan Kaufmann Publishers Inc.
  * [30] Yifan Wu, George Tucker, and Ofir Nachum.  The Laplacian in RL: Learning representations with efficient approximations.  In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
  * [31] William J. Stewart.  Introduction to the Numerical Solution of Markov Chains.  Princeton University Press, Princeton, N.J, 1994.
  * [32] Richard S. Sutton and Andrew G. Barto.  Reinforcement Learning: An Introduction.  Adaptive Computation and Machine Learning Series. The MIT Press, Cambridge, Massachusetts, second edition edition, 2018.
  * [33] Peter B. Denton, Stephen J. Parke, Terence Tao, and Xining Zhang.  Eigenvectors from eigenvalues: A survey of a basic identity in linear algebra.  Bulletin of the American Mathematical Society, 59(1):31–58, February 2021.
  * [34] Nataša Djurdjevac Conrad, Marcus Weber, and Christof Schütte.  Finding Dominant Structures of Nonreversible Markov Processes.  Multiscale Modeling & Simulation, 14(4):1319–1340, January 2016\.
  * [35] C. D. Meyer.  Matrix Analysis and Applied Linear Algebra.  Society for Industrial and Applied Mathematics, Philadelphia, 2000\.
  * [36] Matthew Richey.  The Evolution of Markov Chain Monte Carlo Methods.  The American Mathematical Monthly, 117(5):383, 2010.
  * [37] Ursula Porod.  Dynamics of Markov Chains for Undergraduates.  Preprint: https://www.math.northwestern.edu/documents/book-markov-chains.pdf, February 2021\.
  * [38] Pierre Brémaud.  Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues.  Number 31 in Texts in Applied Mathematics. Springer, New York, 1999\.
  * [39] A. Kolmogoroff.  Zur Theorie der Markoffschen Ketten.  Mathematische Annalen, 112(1):155–160, December 1936.
  * [40] A.N. Gorban.  Detailed balance in micro- and macrokinetics and micro-distinguishability of macro-processes.  Results in Physics, 4:142–147, 2014.
  * [41] Da-Quan Jiang, Min Qian, and Min-Ping Qian.  Mathematical Theory of Nonequilibrium Steady States, volume 1833 of Lecture Notes in Mathematics.  Springer Berlin Heidelberg, Berlin, Heidelberg, 2004.
  * [42] Xue-Juan Zhang, Hong Qian, and Min Qian.  Stochastic theory of nonequilibrium steady states and its applications. Part I.  Physics Reports, 510(1-2):1–86, January 2012.
  * [43] Hao Ge, Min Qian, and Hong Qian.  Stochastic theory of nonequilibrium steady states. Part II: Applications in chemical biophysics.  Physics Reports, 510(3):87–118, January 2012.
  * [44] Jakob Witzig, Isabel Beckenbach, Leon Eifler, Konstantin Fackeldey, Ambros Gleixner, Andreas Grever, and Marcus Weber.  Mixed-Integer Programming for Cycle Detection in Nonreversible Markov Processes.  Multiscale Modeling & Simulation, 16(1):248–265, January 2018\.
  * [45] James Allen Fill.  Eigenvalue Bounds on Convergence to Stationarity for Nonreversible Markov Chains, with an Application to the Exclusion Process.  The Annals of Applied Probability, 1(1), February 1991.
  * [46] Peter Dayan.  Improving Generalization for Temporal Difference Learning: The Successor Representation.  Neural Computation, 5(4):613–624, July 1993.
  * [47] Airlie Chapman and Mehran Mesbahi.  Advection on graphs.  In IEEE Conference on Decision and Control and European Control Conference, pages 1461–1466, Orlando, FL, USA, December 2011. IEEE.
  * [48] Cyril Banderier and Robert P. Dobrow.  A Generalized Cover Time for Random Walks on Graphs.  In Formal Power Series and Algebraic Combinatorics, pages 113–124. Springer Berlin Heidelberg, Berlin, Heidelberg, 2000.
  * [49] David Aldous and James Allen Fill.  Reversible markov chains and random walks on graphs.  2002\.
  * [50] Douglas Brent West.  Introduction to Graph Theory.  Prentice Hall, Upper Saddle River, N.J, 2nd ed edition, 2001.
  * [51] Fan R. K. Chung.  Spectral Graph Theory.  Number no. 92 in Regional Conference Series in Mathematics. Published for the Conference Board of the mathematical sciences by the American Mathematical Society, Providence, R.I, 1997.
  * [52] Fayez Gebali.  Periodic Markov Chains, pages 1–39.  Springer US, Boston, MA, 2008.
  * [53] F. Göbel and A.A. Jagers.  Random walks on graphs.  Stochastic Processes and their Applications, 2(4):311–336, October 1974.
  * [54] László Lovász.  Random walks on graphs: A survey, 1993.
  * [55] Laurenz Wiskott and Fabian Schönfeld.  Laplacian Matrix for Dimensionality Reduction and Clustering.  2019\.
  * [56] Mikhail Belkin and Partha Niyogi.  Towards a theoretical foundation for Laplacian-based manifold methods.  Journal of Computer and System Sciences, 74(8):1289–1308, December 2008.
  * [57] M. Hein, J-Y. Audibert, and U. von Luxburg.  Graph laplacians and their convergence on random neighborhood graphs.  Journal of Machine Learning Research, 8:1325–1370, June 2007.
  * [58] Robert C. Reilly.  Mean Curvature, the Laplacian, and Soap Bubbles.  The American Mathematical Monthly, 89(3):180–198, March 1982.
  * [59] D. S. Grebenkov and B.-T. Nguyen.  Geometrical Structure of Laplacian Eigenfunctions.  SIAM Review, 55(4):601–667, January 2013.
  * [60] D. I. Shuman, S. K. Narang, P. Frossard, A. Ortega, and P. Vandergheynst.  The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains.  IEEE Signal Processing Magazine, 30(3):83–98, May 2013.
  * [61] Marcus Weber.  Eigenvalues of non-reversible Markov chains - A case study.  Technical Report 17-13, ZIB, Takustr. 7, 14195 Berlin, 2017.
  * [62] Sean Meyn, Gregory Hagen, George Mathew, and Andrzej Banasuk.  On complex spectra and metastability of Markov models.  In 2008 47th IEEE Conference on Decision and Control, pages 3835–3839, Cancun, Mexico, 2008. IEEE.
  * [63] David Andrieux.  Spectral signature of nonequilibrium conditions, 2011.
  * [64] P. V. Mieghem.  Directed graphs and mysterious complex eigenvalues.  2018\.
  * [65] Harry Sevi, Gabriel Rilling, and Pierre Borgnat.  Harmonic analysis on directed graphs and applications: From Fourier analysis to wavelets, November 2018.
  * [66] Antonio G. Marques, Santiago Segarra, and Gonzalo Mateos.  Signal Processing on Directed Graphs: The Role of Edge Directionality When Processing and Learning From Network Data.  IEEE Signal Processing Magazine, 37(6):99–116, November 2020.
  * [67] Gene H. Golub and Charles F. Van Loan.  Matrix Computations.  Johns Hopkins Studies in the Mathematical Sciences. The Johns Hopkins University Press, Baltimore, fourth edition edition, 2013.
  * [68] P. J. Pauwelyn and M. A. Guerry.  Perturbations of non-diagonalizable stochastic matrices with preservation of spectral properties.  Linear and Multilinear Algebra, pages 1–31, March 2021.
  * [69] K. Fackeldey, A. Sikorski, and M. Weber.  Spectral clustering for non-reversible Markov chains.  Computational and Applied Mathematics, 37(5):6376–6391, November 2018.
  * [70] Dibya Ghosh and Marc G. Bellemare.  Representations for stable off-policy reinforcement learning.  In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 3556–3565. PMLR, July 2020\.
  * [71] K C Ng and Beresford N. Parlett.  Programs to swap diagonal blocks.  1987\.
  * [72] Jack J. Dongarra, Sven Hammarling, and James H. Wilkinson.  Numerical Considerations in Computing Invariant Subspaces.  SIAM Journal on Matrix Analysis and Applications, 13(1):145–161, January 1992.
  * [73] Zhaojun Bai and James W. Demmel.  On swapping diagonal blocks in real Schur form.  Linear Algebra and its Applications, 186:75–95, June 1993.
  * [74] R. Granat, B. Kågström, and D. Kressner.  Parallel eigenvalue reordering in real Schur forms.  Concurrency and Computation: Practice and Experience, 21(9):1225–1250, June 2009.
  * [75] J. H. Brandts.  Matlab code for sorting real Schur forms.  Numerical Linear Algebra with Applications, 9(3):249–261, April 2002.
  * [76] Rafig Agaev and Pavel Chebotarev.  On the spectra of nonsymmetric Laplacian matrices.  Linear Algebra and its Applications, 399:157–168, April 2005.
  * [77] J. S. Caughman and J. J. P. Veerman.  Kernels of Directed Graph Laplacians.  The Electronic Journal of Combinatorics, 13(1):R39, April 2006.
  * [78] Yanhua Li and Zhi-Li Zhang.  Digraph Laplacian and the Degree of Asymmetry.  Internet Mathematics, 8(4):381–401, December 2012.
  * [79] Rahul Singh, Abhishek Chakraborty, and B. S. Manoj.  Graph Fourier transform based on directed Laplacian.  In 2016 International Conference on Signal Processing and Communications (SPCOM), pages 1–5, Bangalore, India, June 2016\. IEEE.
  * [80] Fan Chung.  Laplacians and the Cheeger Inequality for Directed Graphs.  Annals of Combinatorics, 9(1):1–19, April 2005.
  * [81] William Pentney and Marina Meila.  Spectral clustering of biological sequence data.  In Proceedings of the 20th National Conference on Artificial Intelligence - Volume 2, AAAI’05, pages 845–850, Pittsburgh, Pennsylvania, 2005. AAAI Press.
  * [82] Sridhar Mahadevan, Mauro Maggioni, Kimberly Ferguson, and Sarah Osentoski.  Learning representation and control in continuous markov decision processes.  In Proceedings of the 21st National Conference on Artificial Intelligence - Volume 2, AAAI’06, pages 1194–1199, Boston, Massachusetts, 2006. AAAI Press.
  * [83] Mo Chen, Qiong Yang, and Xiaoou Tang.  Directed graph embedding.  IJCAI International Joint Conference on Artificial Intelligence, pages 2707–2712, January 2007.
  * [84] Dominique C. Perrault-Joncas and Marina Meilă.  Directed graph embedding: An algorithm based on continuous limits of laplacian-type operators.  In Proceedings of the 24th International Conference on Neural Information Processing Systems, NIPS’11, pages 990–998, Red Hook, NY, USA, 2011. Curran Associates Inc.
  * [85] Lawrence Page, S. Brin, R. Motwani, and T. Winograd.  The PageRank citation ranking : Bringing order to the web.  In WWW 1999, 1999.
  * [86] Massimo Franceschet.  PageRank: Standing on the shoulders of giants.  Communications of the ACM, 54(6):92–101, June 2011.
  * [87] Pavel Berkhin.  A Survey on PageRank Computing.  Internet Mathematics, 2(1):73–120, January 2005.