Home | About | Journals | Submit | Contact Us | Français |

**|**Wiley-Blackwell Online Open**|**PMC5324709

Formats

Article sections

- Abstract
- 1. Introduction
- 2. Definitions
- 3. Random walks and
- 4. Random walks and
- 5. Random walk related to the full Hodge Laplacian
- 6. Walks on triangle complexes and random walks for semi‐supervised learning
- 7. Discussion
- Acknowledgements
- References

Authors

Related links

Random Structures & Algorithms

Random Struct Algorithms. 2016 September; 49(2): 379–405.

Published online 2016 March 7. doi: 10.1002/rsa.20645

PMCID: PMC5324709

Sayan Mukherjee, Email: ude.ciu@negrebj.

Received 2013 October 29; Revised 2015 February 25; Accepted 2015 December 11.

Copyright © 2016 The Authors Random Structures & Algorithms Published by Wiley Periodicals, Inc.

This is an open access article under the terms of the Creative Commons Attribution‐NonCommercial‐NoDerivs License, which permits use and distribution in any medium, provided the original work is properly cited, the use is non‐commercial and no modifications or adaptations are made.

In this paper, we introduce a class of random walks with absorbing states on simplicial complexes. Given a simplicial complex of dimension *d*, a random walk with an absorbing state is defined which relates to the spectrum of the *k*‐dimensional Laplacian for 1≤*k*≤*d*. We study an example of random walks on simplicial complexes in the context of a semi‐supervised learning problem. Specifically, we consider a label propagation algorithm on oriented edges, which applies to a generalization of the partially labelled classification problem on graphs. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 379–405, 2016

The relation between spectral graph theory and random walks on graphs is well studied and has both theoretical and practical implications 2, 13, 14, 16. Consider an unweighted and undirected graph *G*=(*V, E*). A random walk on the graph *G* is defined via a Markov chain on the set of vertices, with transition probability matrix *P*=I – *D*
^{−1}
*W* where *W* is the graph adjacency matrix, and *D* is a diagonal matrix with *D*
_{ii} the degree of vertex *i*. The graph Laplacian is defined as Δ=*D* – *W* so *P*=*D*
^{−1}Δ. Connections between spectral properties of the graph Laplacian and properties of random walks are well understood 13, the mixing time of a random walk on a graph is one connection. A key observation is that the stationary distribution of a random walk on a graph is related to the harmonics of the graph Laplacian 13. Expander graphs are another important example that highlights the relationship between random walks and spectral graph theory 2, 7, 13.

Graphs are common objects on which stochastic processes are defined, however they are limited in their ability to represent interactions between more than two objects. Simplicial complexes provide a language to describe such high‐order interactions. In this paper we will define stochastic processes on simplicial complexes and examine what properties of random walks on graphs extend to random walks on simplicial complexes. The idea of extending results of random walks on graphs to random walks on simplicial complexes have only recently been explored 6, 17, 19, 20. There has also been recent activity studying the related problem of extending the notion of expander graphs to simplicial complexes and finding isoperimetric inequalities for simplicial complexes 8, 15, 17, 18, 21. In contrast, the understanding of quasirandom properties of hypergraphs is relatively well developed 4, 5, 10, 12.

The main objective of this paper is to define random walks on simplicial complexes by a Markov chain and relate the stationary distribution of the chain to harmonics of the Hodge Laplacian. The extension of the graph Laplacian to simplcial complexes goes back to the work of Eckmann 9 where higher‐order combinatorial or Hodge Laplacians were defined. The spectrum of the *k*‐th order Hodge Laplacian provides information on whether the *k*‐th (co)homology class is trivial. The size of the spectral gap can be considered a “measure” of how far the complex is from having nontrivial (co)homology. In this paper we will show that the stationary distribution of the random walk on the simplicial complex captures nontrivial *k*‐th (co)homology classes.

The main differences between random walks on graphs and random walks on simplicial complexes are as follows:

- Detection of higher‐order homology groups: The topological properties studied on graphs are usually limited to connected components and cycles–these are the zeroth and first homology groups,
*H*_{0}and*H*_{1}respectively. In the case of simplicial complexes we can examine higher dimensional analogs of cycles, represented by the higher homology groups*H*_{2},*H*_{3}respectively. Understanding the relationship between random walks on simplicial complexes and their homology is one of our aims. - The role of orientation: In order to study simplicial homology each simplex in a complex is required to have an orientation, an ordering on its vertices that can be either positive or negative. Conceptually, the biggest difference form the graph case is that for random walks on simplicial complexes a Markov chain needs to be defined on each orientation and the two chains need to be coupled.
- Defining neighbors: In a graph there is only one logical way to define neighboring vertices–if they are connected by an edge. Two simplexes in a simplicial complex can be connected in various ways, see Fig. Fig.1.1. In this paper we focus on the case where two
*k*‐simplexes are considered to be neighbors if they share a common (*k*– 1)‐dimensional face. In 17 two*k*‐simplexes are considered neighbors if they are faces of a common (*k*+1)‐dimensional simplex (a coface). These different definitions of neighborhoods yield random walks with different properties.

A strong motivation for studying random walks on simplicial complexes is a desire to capture geometry as well as topology. Consider two objects: (a) a solid three dimensional disc and (b) the same disc with a small hole punctured in the middle. Generate a graph *G*
_{s} from a random sample of the solid disc and a graph *G*
_{p} from a random sample of the punctured disc. If the puncture is small the spectra of the graph Laplacian of *G*
_{s} and the graph Laplacian *G*
_{p} will be very similar. In contrast if one generates a simplicial complex or triangulation of the solid and punctured disc, *T*
_{s} and *T*
_{p} respectively, the spectra of higher‐order Hodge Laplacians will not be the same since the inner boundary of the disc with a hole will be detected by the Hodge Laplacian.

The two operators needed to define the Hodge Laplacian are the boundary map and the coboundary map. Here we provide an intuition for these maps and describe how they relate to the different walks shown in Fig. Fig.1.1. A rigorous formulation will be provided in Section 2.3. The boundary operator
_{k} maps *k*‐dimensional complexes to (*k* – 1) dimensional simplices, for example
_{1} maps edges to vertices and
_{2} maps triangles to edges. The coboundary operator *δ*
_{k} goes in the opposite direction, it defines a map from lower‐dimensional complexes to higher‐dimensional complexes. The *k*‐th Hodge Laplacian for dimension *k*>0 is composed of two components

$${\Delta}_{k}={\partial}_{k+1}{\delta}^{k}+{\delta}^{k-1}{\partial}_{k}.$$

These two components will correspond to the two definitions of random walks displayed in Figure Figure1.1. One can define a random walk between triangles that share an edge, Fig. Fig.1b,1b, this corresponds to *δ*
^{1}
_{2} since each move in the walk can be thought of as a composition of moving from a triangle to an edge and back to a triangle. One can also define a random walk between edges that share a triangle, Fig. Fig.1a,1a, this corresponds to
_{2}
*δ*
^{1} since each move in the walk can be thought of as a composition of moving from an edge to a triangle back to an edge. One can also define a walk that combines both types of walks. Walks corresponding to
_{k+1}
*δ*
^{k} were introduced by Parzanchevski and Rosenthal 17. In this paper we will introduce walks corresponding to *δ*
^{k–1}
_{k} as well as walks that relate to the Hodge Laplacian.

The following example motivates the walk in Fig. Fig.1B.1B. Consider the 2‐dimensional simplicial complex formed by a hollow tetrahedron (or any triangulation of the 2‐sphere). We know that the complex has nontrivial 2‐dimensional homology since there is a void. However, this homology cannot be detected by the random walk defined in 17, because there are no tetrahedrons that can be used by the walk to move between the triangles. In general, the walk defined in 17 can detect homology from dimension 0 to co‐dimension 1, but never co‐dimension 0. Hence, a new walk which can travel from triangles to triangles through edges is needed to detect the void.

In addition to the two types of random walks explored in this paper and in 17, a recent paper by Rosenthal 19 considers a notion of branching processes on simplicial complexes. We will return to a discussion of the similarities and differences of these Markov processes in Section 7.

In Section 2 we state the notation used in this paper and define chains, cochains, and the Hodge Laplacian. In Section 3 we define a random walk from a *k*‐simplex to another *k*‐simplex through a (*k* – 1)‐dimensional face. We then relate the stationary distribution of the walk to the harmonics of the *δ*
^{k–1}
_{k} component of the Hodge Laplacian and provide mixing times. In Section 4 we define a random walk from a *k*‐simplex to another *k*‐simplex through a (*k*+1)‐dimensional coface and relate the stationary distribution to the harmonics of the
_{k+1}
*δ*
^{k} component of the Hodge Laplacian. The results in this section can be considered a restatement of the results in 17. In Section 5 we define a walk that captures the harmonics of the entire Hodge Laplacian. In Section 6 we provide some examples of random walks to illustrate some of our ideas and present a novel machine learning algorithm based on random walks on simplicial complexes.

In this section we define the notion of a simplicial complex *X*, the chain and cochain complexes associated to it, and the *k*‐Laplacian.

By a simplicial complex we mean an abstract finite simplicial complex. Simplicial complexes generalize the notion of a graph to higher dimensions. Given a set of vertices *V*, any nonempty subset *σ* *V* of the form *σ*={*v*
_{0}, *v*
_{1},…,*v*
_{j}} is called a *j*‐dimensional simplex, or *j*‐simplex. A simplicial complex *X* is a finite collection of simplexes of various dimensions such that *X* is closed under inclusion, i.e., *τ* *σ* and *σ* *X* implies *τ* *X*. While we will not need it for this paper, one can include the empty set in *X* as well (thought of as a (–1)‐simplex). Given a simplicial complex *X*, denote the set of *j*‐simplexes of *X* as *X*
^{j}. We say that *X* is *d*‐dimensional or that *X* is a *d*‐complex if ${X}^{d}\ne \varnothing $ but ${X}^{d+1}=\varnothing $. Graphs are 1‐dimensional simplicial complexes. We will assume throughout that *X* is a *d*‐complex for some fixed *d*≥1.

If $\sigma \in {X}^{j},\hspace{0.17em}\tau \in {X}^{j-1}$, and $\tau \subset \sigma $, then we call *τ* a *face* of *σ* and *σ* a *coface* of *τ*. Every *j*‐simplex *σ* for *j*≥1 has exactly *j*+1 faces but may have any number of cofaces. Given *σ* *X*
^{j} we define $\mathrm{deg}(\sigma )$ (called the *degree* of *σ*) to be the number of cofaces of *σ*. Two simplexes are *upper adjacent* if they share a coface and *lower adjacent* if they share a face. The number of simplexes upper adjacent to a *j*‐simplex *σ* is $(j+1)\xb7\mathrm{deg}(\sigma )$ while the number of simplexes lower adjacent to *σ* is $\sum _{\tau \subset \sigma}(\mathrm{deg}(}\tau )-1)$ where the sum is over all faces *τ* of *σ*.

Orientation plays a major role in the geometry of a simplicial complex. For *j*>0, an orientation of a *j*‐simplex *σ* is an equivalence class of orderings of its vertices, where two orderings are equivalent if they differ by an even permutation. Notationally, an orientation is denoted by placing one of its orderings in square brackets, as in [*v*
_{0},…,*v*
_{j}]. Every *j*‐simplex *σ* has two orientations which we think of as negatives of each other. We abbreviate these two orientations as *σ*
_{+} and ${\sigma}_{-}=-{\sigma}_{+}$ (which orientation *σ*
_{+} corresponds to is chosen arbitrarily). For any *j*≥1, we will use ${X}_{+}^{j}=\{{\sigma}_{+}:\sigma \in {X}^{j}\}$ to denote a choice of positive orientation *σ*
_{+} for each *j*‐simplex *σ*. The set of all oriented *j*‐simplexes will be denoted by ${X}_{\pm}^{j}$, so that ${X}_{\pm}^{j}=\{{\sigma}_{\pm}:{\sigma}_{+}\in {X}_{+}^{j}\}$ and $\left|{X}_{\pm}^{j}\right|=2\left|{X}^{j}\right|$ for any choice of orientation ${X}_{+}^{j}$.

An oriented simplex *σ*
_{+}=[*v*
_{0},…,*v*
_{j}] induces an orientation on the faces of *σ* as ${(-1)}^{i}[{v}_{0},\dots ,{v}_{i-1},{v}_{i+1},\dots ,{v}_{j}]$. Conversely, an oriented face ${(-1)}^{i}[{v}_{0},\dots ,{v}_{i-1},{v}_{i+1},\dots ,{v}_{j}]$ of *σ* induces an orientation *σ*
_{+}=[*v*
_{0},…,*v*
_{j}] on *σ*. Two oriented *j*‐simplexes *σ*
_{+} and $\sigma {\prime}_{+}$ are said to be *similarly oriented*, and we write ${\sigma}_{+}\sim \sigma {\prime}_{+}$, if *σ* and $\sigma \prime $ are distinct, lower adjacent *j*‐simplexes and *σ*
_{+} and $\sigma {\prime}_{+}$ induce the opposite orientation on the common face (if *σ* and $\sigma \prime $ are upper adjacent as well, this is the same as saying that *σ*
_{+} and $\sigma {\prime}_{+}$ induce the same orientation on the common coface). If they induce the same orientation on the common face, then we say they are *dissimilarly oriented* and write ${\sigma}_{-}\sim \sigma {\prime}_{+}$. We say that a *d*‐complex *X* is *orientable* if there is a choice of orientation ${X}_{+}^{d}$ such that for every pair of lower adjacent simplexes $\sigma ,\sigma \prime \in {X}^{d}$, the oriented simplexes ${\sigma}_{+},\sigma {\prime}_{+}\in {X}_{+}^{d}$ are similarly oriented.

Orientation is typically not a property of vertices of a graph and the term oriented graph is taken to mean a directed graph. For *j*=0 there are no distinct orderings, and one can think of each vertex *v* as being positively oriented by default (so, *v*
_{+}=*v*) and having an oppositely‐oriented counterpart ${v}_{-}:=-v$. However, introducing orientation to a graph is not standard. The collection of oriented 0‐simplexes, ${X}_{\pm}^{0}$ does not reduce to the standard graph setting, since graphs are not considered to be oriented. We will discuss orientation in more detail in Section 3. We will see in Section 3 that the random walks we define on simplicial complexes do not reduce to a simple random walk on a graph.

Given a simplicial complex *X*, we can define the chain and cochain complexes of *X* over $\mathbb{R}$. The space of *j*‐chains ${C}_{j}:={C}_{j}(X;\mathbb{R})$ is the vector space of linear combinations of oriented *j*‐simplexes with coefficients in $\mathbb{R}$, with the stipulation that the two orientations of a simplex are negatives of each other in *C*
_{j} (as implied by our notation). Thus, any choice of orientation ${X}_{+}^{j}$ provides a basis for *C*
_{j}. The space of *j*‐cochains ${C}^{j}:={C}^{j}(X;\mathbb{R})$ is then defined to be the vector space dual to *C*
_{j}. These spaces are isomorphic and we will make no distinction between them. Usually, we will work with cochains using the basis elements $\{{\mathbf{1}}_{{\sigma}_{+}}:{\sigma}_{+}\in {X}_{+}^{j}\}$, where ${\mathbf{1}}_{{\sigma}_{+}}:{C}_{j}\to \mathbb{R}$ is defined on a basis element ${\tau}_{+}\in {X}_{+}^{j}$ as

$${\mathbf{1}}_{{\sigma}_{+}}({\tau}_{+})=\{\begin{array}{cc}1& {\tau}_{+}={\sigma}_{+}\\ 0& \text{else}\end{array}.$$

The boundary map ${\partial}_{j}:{C}_{j}\to {C}_{j-1}$ is the linear map defined on a basis element [*v*
_{0},…,*v*
_{j}] as

$${\partial}_{j}[{v}_{0},\dots ,{v}_{j}]={\displaystyle \sum _{i=0}^{j}{(-1)}^{i}}[{v}_{0},\dots ,{v}_{i-1},{v}_{i+1},\dots ,{v}_{j}].$$

The coboundary map ${\delta}^{j-1}:{C}^{j-1}\to {C}^{j}$ is then defined to be the transpose of the boundary map. In particular, for $f\in {C}^{j-1}$,

$$({\delta}^{j-1}f)([{v}_{0},\dots ,{v}_{j}])={\displaystyle \sum _{i=1}^{j}{(-1)}^{i}}f([{v}_{0},\dots ,{v}_{i-1},{v}_{i+1},\dots ,{v}_{j}]).$$

When there is no confusion, we will denote the boundary and coboundary maps by and *δ*. It holds that =*δδ*=0, so that (*C*
_{j},
_{j}) and (*C*
^{j}, *δ*
^{j}) form chain and cochain complexes respectively.

The homology and cohomology vector spaces of *X* over $\mathbb{R}$ are

$${H}_{j}:={H}_{j}(X;\mathbb{R})=\frac{\text{ker}\hspace{0.17em}{\partial}_{j}}{\text{im}\hspace{0.17em}{\partial}_{j+1}}\hspace{1em}\text{and}\hspace{1em}{\mathrm{H}}^{\mathrm{j}}:{=\mathrm{H}}^{\mathrm{j}}(\mathrm{X};\mathbb{R})=\frac{\text{ker}\hspace{0.17em}{\delta}^{\mathrm{j}}}{\text{im}\hspace{0.17em}{\delta}^{\mathrm{j}-1}}.$$

It is known from the universal coefficient theorem that *H*
^{j} is the vector space dual to *H*
_{j}. Reduced (co)homology can also be used, and it is equivalent to including the nullset as a (–1)‐dimensional simplex in *X*.

The *k*‐Laplacian of *X* is defined to be

$${\Delta}_{k}:={\Delta}_{k}^{\text{up}}+{\Delta}_{k}^{\text{down}}$$

where

$${\Delta}_{k}^{\text{up}}={\partial}_{k+1}{\delta}^{k}\hspace{1em}\text{and}\hspace{1em}{\Delta}_{\mathrm{k}}^{\text{down}}={\delta}^{\mathrm{k}-1}{\partial}_{\mathrm{k}}.$$

The Laplacian is a symmetric positive semi‐definite matrix, as is each part ${\Delta}_{k}^{\text{up}}$ and ${\Delta}_{k}^{\text{down}}$. From Hodge theory, it is known that

$$\text{ker}\hspace{0.17em}{\Delta}_{k}\cong {H}^{k}\cong {H}_{k}$$

and the space of cochains decomposes as

$${C}^{k}=\text{im}\hspace{0.17em}{\partial}_{k+1}\oplus \text{ker}\hspace{0.17em}{\Delta}_{k}\oplus \text{im}\hspace{0.17em}{\delta}^{k-1}$$

where the orthogonal direct sum is with respect to the “usual” inner product

$$\u3008f,g\u3009={\displaystyle \sum _{{\sigma}_{+}\in {X}_{+}^{k}}f}({\sigma}_{+})g({\sigma}_{+}).$$

For much of this paper we will focus on the ${\Delta}_{j}^{\text{down}}$ half of the Laplacian. Trivially, $\text{im}\hspace{0.17em}{\partial}_{j+1}\subseteq \text{ker}\hspace{0.17em}{\Delta}_{j}^{\text{down}}$ and the smallest nontrivial eigenvalue of ${\Delta}_{k}^{\text{down}}$ is therefore given by

$${\lambda}_{k}=\underset{\begin{array}{c}f\in {C}^{k}\\ f\perp \text{im}\hspace{0.17em}\partial \end{array}}{\mathrm{min}}\frac{{\Vert {\partial}_{k}f\Vert}_{2}^{2}}{{\Vert f\Vert}_{2}^{2}},$$

where ${\Vert f\Vert}_{2}:=\sqrt{\u3008f,f\u3009}$ denotes the Euclidean norm on *C*
^{k}. A cochain *f* that achieves the minimum is an eigenvector of *λ*
_{k}. It is easy to see that any such *f* is also an eigenvector of Δ_{k} with eigenvalue *λ*
_{k} and that, therefore, *λ*
_{k} relates to homology:

$${\lambda}_{k}=0\iff \text{ker}\hspace{0.17em}{\Delta}_{k}\ne 0\iff {H}^{k}\ne 0.$$

Remark 2.1

Given a choice of orientation ${X}_{+}^{k},\hspace{0.17em}{\Delta}_{k}^{\text{down}}$ can be written as a matrix with rows and columns indexed by ${X}_{+}^{k}$, the entries of which are given by

$${({\Delta}_{k}^{\text{down}})}_{\sigma {\prime}_{+},{\sigma}_{+}}=\{\begin{array}{cc}k+1& \sigma {\prime}_{+}={\sigma}_{+}\\ 1& \sigma {\prime}_{-}\sim {\sigma}_{+}\\ -1& \sigma {\prime}_{+}\sim {\sigma}_{+}\\ 0& \text{otherwise}.\end{array}$$

Changing the choice of orientation ${X}_{+}^{k}$ amounts to a change of basis for ${\Delta}_{k}^{\text{down}}$. If the row and column indexed by *σ*
_{+} are instead indexed by *σ*
_{–,} all the entries in them switch sign except the diagonal entry. Alternatively, ${\Delta}_{k}^{\text{down}}$ can be characterized by how it acts on cochains

$${\Delta}_{k}^{\text{down}}f({\tau}_{+})=(k+1)\xb7f({\tau}_{+})+{\displaystyle \sum _{{\sigma}_{-}\sim {\tau}_{+}}f}({\sigma}_{+})-{\displaystyle \sum _{{\sigma}_{+}\sim {\tau}_{+}}f}({\sigma}_{+}).$$

Note that since ${\Delta}_{k}^{\text{down}}f$ is a cochain, ${\Delta}_{k}^{\text{down}}f({\tau}_{-})=-{\Delta}_{k}^{\text{down}}f({\tau}_{+})$.

The remainder of this section states some relevant properties on the behavior of ${\Delta}_{k}^{\text{down}}$.

Definition 2.2

A *d*‐complex *X* is called *k*‐connected (1≤*k*≤*d*) if for every two *k*‐simplexes *σ*, $\sigma \prime $ there exists a chain $\sigma ={\sigma}_{0},{\sigma}_{1},\dots ,{\sigma}_{n}=\sigma \prime $ of *k*‐simplexes such that *σ*
_{i} is lower adjacent to *σ*
_{i+1} for all *i*. For a general *d*‐complex *X*, such chains define equivalence classes of *k*‐simplexes, and the subcomplexes induced by these are called the *k*‐connected components of *X*.

Definition 2.3

A *d*‐complex *X* is called disorientable if there is a choice of orientation ${X}_{+}^{d}$ of its *d*‐simplexes such that all lower adjacent *d*‐simplexes are dissimilarly oriented. In this case, the *d*‐cochain $f={\displaystyle \sum _{{\sigma}_{+}\in {X}_{+}^{d}}{\mathbf{1}}_{{\sigma}_{+}}}$ is called a disorientation.

Remark 2.4

Disorientability was defined in 17 and shown to be a higher‐dimensional analog of bipartiteness for graphs. Note that one can also define *X* to be *k*‐disorientable if the *k*‐skeleton of *X* (the *k*‐complex given by the union $\underset{i\le k}{\cup}{X}^{i}$) is disorientable, but this can only happen when *k*=*d*. For example if *k*<*d* then there exists a (*k*+1)‐simplex ${\sigma}_{+}=[{v}_{0},\dots ,{v}_{k+1}]$. Given any two dissimilarly oriented faces of *σ*
_{+}, say, $[{v}_{1},{v}_{2},\dots ,{v}_{k+1}]$ and $[{v}_{0},{v}_{2},\dots ,{v}_{k}]$, we find that the simplex $\{{v}_{0},{v}_{1},{v}_{3},\dots ,{v}_{k}\}$ cannot be dissimilarly oriented to both of them simultaneously.

The following Lemma is similar to Proposition 2.7 in 17.

Lemma 2.5

*Let X be a d‐complex, 1≤k≤d and*
$M={\mathrm{max}}_{\sigma \in {X}^{k-1}}\mathrm{deg}(\sigma )$.

- $\text{Spec}({\Delta}_{k}^{\text{down}})$
*is the disjoint union of*$\text{Spec}({\Delta}_{k}^{\text{down}}{|}_{{X}_{i}})$*where X*._{i}are the k‐connected components of X *The spectrum of*${\Delta}_{k}^{\text{down}}$*is contained in*$[0,(k+1)M]$.*The kernel of*${\Delta}_{k}^{\text{down}}$*is exactly*$\text{ker}\hspace{0.17em}{\partial}_{k}=\text{im}\hspace{0.17em}{\partial}_{k+1}\oplus \text{ker}\hspace{0.17em}{\Delta}_{k}$.*The upper bound (k+1)M is attained if and only if k=d and X has a d‐connected component that is both disorientable and of constant (d – 1)‐degree*.

Statement (1) follows from the fact that ${\Delta}_{k}^{\text{down}}$ can be written as a block diagonal matrix with each block corresponding to a component *X*
_{i}. Statement (3) is easy to verify.

For statement (2), let *f* be an eigenvector of ${\Delta}_{k}^{\text{down}}$ with eigenvalue *λ*, let ${X}_{+}^{k}$ be a choice of orientation such that $f({\sigma}_{+})\ge 0$ for all ${\sigma}_{+}\in {X}_{+}^{k}$ and suppose $f({\tau}_{+})={\mathrm{max}}_{{\sigma}_{+}\in {X}_{+}^{k}}f({\sigma}_{+})$. Then by Remark 2.1,

$$\begin{array}{l}\lambda f({\tau}_{+})={\Delta}_{k}^{\text{down}}f({\tau}_{+})\\ =(k+1)\xb7f({\tau}_{+})+{\displaystyle \sum _{{\sigma}_{-}\sim {\tau}_{+}}f}({\sigma}_{+})-{\displaystyle \sum _{{\sigma}_{+}\sim {\tau}_{+}}f}({\sigma}_{+})\\ \le (k+1)\xb7f({\tau}_{+})+{\displaystyle \sum _{{\sigma}_{-}\sim {\tau}_{+}}f}({\tau}_{+})+{\displaystyle \sum _{{\sigma}_{+}\sim {\tau}_{+}}f}({\tau}_{+})\\ \le (k+1)\xb7f({\tau}_{+})+(k+1)(M-1)\xb7f({\sigma}_{+})\\ \le (k+1)M\xb7f({\tau}_{+})\end{array}$$

$$$$

$$$$

$$$$

$$$$

where the third inequality results from the fact that any *k*‐simplex is lower adjacent to at most (*k*+1)(*M* – 1) other *k*‐simplexes. Therefore, *λ*≤(*k*+1)*M*.

It now remains to prove statement (4). Looking back at the inequalities, it holds that *λ*=(*k*+1)*M* only if *σ*
_{–} ~ *τ*
_{+} and *f*(*σ*
_{+})=*f*(*τ*
_{+}) whenever *σ* and *τ* are lower adjacent, and the faces of *σ* all have degree *M*. But since *f*(*σ*
_{+})=*f*(*τ*
_{+}), the same reasoning can be applied to *f*(*σ*
_{+}) for all *σ* lower adjacent to *τ* and eventually to all *k*‐simplexes in the same *k*‐connected component *X*
_{i}. Ultimately, this implies that *X*
_{i} has constant (*k* – 1)‐degree and is *k*‐disorientable (and hence *k*=*d*).

To see that this bound is indeed attainable, consider a disorientable *d*‐complex with constant (*d* – 1)‐degree *M* (this includes, for instance, the simplicial complex induced by a single *d*‐simplex). Let ${X}_{+}^{d}$ be a choice of orientation such that all lower adjacent *d*‐simplexes are dissimilarly oriented. Then a disorientation *f* on *X*
^{d} will satisfy

$$\begin{array}{l}{\Delta}_{k}^{\text{down}}f({\tau}_{+})=(k+1)\xb7f({\tau}_{+})+{\displaystyle \sum _{{\sigma}_{-}\sim {\tau}_{+}}f}({\sigma}_{+})-{\displaystyle \sum _{{\sigma}_{+}\sim {\tau}_{+}}f}({\sigma}_{+})\\ =(k+1)\xb7f({\tau}_{+})+{\displaystyle \sum _{{\sigma}_{-}\sim {\tau}_{+}}f}({\sigma}_{+})\\ =(k+1)\xb71+{\displaystyle \sum _{{\sigma}_{-}\sim {\tau}_{+}}1}=(k+1)M\hspace{0.17em}=(k+1)M\xb7f({\tau}_{+})\end{array}$$

$$$$

$$$$

for every *τ*
_{+}.

In this section we will define a random walk on a *d*‐complex. The stationary distribution of the random walk is related to the harmonics of ${\Delta}_{k}^{\text{down}}$ for 1≤*k*≤*d*. The mixing time of the walk is a function of the spectral gap of ${\Delta}_{k}^{\text{down}}$. A notion of maximal degree *M* will appear in our results.

The following random walk is a Markov chain that is related to ${\Delta}_{k}^{\text{down}}$.

Definition 3.1

The state space is the set of oriented complexes as well as a death state $\{\Theta \},\hspace{0.17em}S={X}_{\pm}^{k}\cup \{\Theta \}$.

- Neighbors: two oriented
*k*‐cells*σ*and $\sigma \prime $ are called neighbors, which we denote as $\sigma \downarrow \sigma \prime $ if they share a (*k*– 1) face and have opposite orientation on the shared face. - Transition matrix
*P*: the transition matrix is the time‐homogenous Markov chain on the state space $S={X}_{\pm}^{k}\cup \{\Theta \}$ with transition probabilitieswhere $\overline{\sigma \prime}$ denotes the opposite orientation of $\sigma \prime ,\hspace{0.17em}\sigma \downarrow \sigma \prime $ is the notation for moving to an oriented neighboring cell, and $\sigma \downarrow \overline{\sigma \prime}$ is the notation for moving to a disoriented neighboring cell. The probability of transitioning into a death state is $\beta =1-{\displaystyle \sum _{\sigma \prime \in \hspace{0.17em}\text{Lk}(\sigma )}\text{Prob}}(\sigma \to \sigma \prime )-{\alpha}_{0}$ where Lk($${P}_{\sigma ,\sigma \prime}=\text{Prob}(\sigma \to \sigma \prime )=\{\begin{array}{cc}{\alpha}_{0}& \hspace{0.17em}\text{when}\sigma \ne \Theta \hspace{0.17em}\text{and}\sigma \prime =\sigma \\ {\alpha}_{1}& \hspace{0.17em}\text{when}\sigma \ne \Theta \hspace{0.17em}\text{and}\sigma \downarrow \sigma \prime \\ {\alpha}_{2}& \hspace{0.17em}\text{when}\sigma \ne \Theta \hspace{0.17em}\text{and}\sigma \downarrow \overline{\sigma \prime}\\ \beta & \hspace{0.17em}\text{when}\sigma \ne \Theta \hspace{0.17em}\text{and}\sigma \prime =\Theta \\ 1& \sigma =\sigma \prime =\Theta ,\end{array}$$*σ*) are the set of simplexes that are oriented or disoriented neighbors of*σ*. The transition probabilities are constrained to ensure*P*is a stochastic matrix.

The intuition behind the steps in the transition matrix follows. We first consider the case where there is no death state. In this case with probability *α*
_{0} one stays in the same state. The probability of moving to an oriented neighboring cell is *α*
_{1}. The probability of moving in one step to disoriented neighboring cell is *α*
_{2}. The death state is needed when the total probability, 1 – *β*, of either moving to a new cell or staying at the same cell is less than one. In this case the remaining probability *β* corresponds to moving to an absorption or death state. There is also an interpretation of the Markov chain as two coupled Markov chains. Again for simplicity we consider the case where there is no death state. Consider one Markov chain on the state space ${X}_{+}^{k}$ and another chain on ${X}_{-}^{k}$. The two chains are coupled as follows: at each time step one can either jump to another state in the chain or jump to the corresponding state of opposite orientation in the other chain and proceed in the new chain.

We now specify the parameter values of the transition matrix *P*.

Definition 3.2

We define transition matrix *P* based on Definition 3.1 with parameter values

$${\alpha}_{0}=p,\hspace{1em}{\alpha}_{1}={\alpha}_{2}=\frac{1-p}{(M-1)(k+1)},$$

where *M* is the maximal degree ${\mathrm{max}}_{\sigma \in {X}^{k-1}}\mathrm{deg}(\sigma ),\hspace{0.17em}1\le k\le d$ corresponds to the order of ${\Delta}_{k}^{\text{down}}$, and 0<*p*<1.

We selected this parameter specification for ease of analysis and to impose certain intuitive properties of the walk. The value 0<*p*<1 determines the laziness of the walk, the probability of not changing states. We set the probability of moving to a neighbor as equal to the probability of moving to a disoriented neighbor, *α*
_{1}=*α*
_{2}. One reason for the existence of the death state is that if *α*
_{1}=*α*
_{2} the total transition probability at each state may not sum to one so we use the death state as an absorption state. A natural choice for *α*
_{1} is a uniform probability of transitioning to each of the neighbors of a complex. We set ${\alpha}_{1}=\frac{1-p}{(M-1)(k+1)}$, this would be a uniform transition probability if all complexes had maximal degree *M*, this is the analog of a *M*‐regular graph. We suspect that the qualitative phenomena and insights we derive for the specified walk will transfer to walks defined by other parameters, such as the more natural uniform walk.

In the remainder of this section we will relate the stationary distribution of the stochastic matrix *P* to the geometry of the simplicial complex on which the random walk is defined. Specifically we are interested in relating the stationary distribution to the harmonics of ${\Delta}_{k}^{\text{down}}$. From Hodge theory we know that the relevant geometry is characterized by the space of *k*‐cochains, *f* *C*
^{k}. A *k*‐cochain is antisymmetric under exchange of any pairs of indices which implies the following constraint

$$\left\{f:{X}_{\pm}^{k}\to \mathbb{R}|f(\overline{\sigma})=-f(\sigma ),\hspace{0.17em}\forall \sigma \in {X}_{\pm}^{k}\right\}.$$

Given the transition matrix *P* we can compute the following expected value from a *k*‐cochain at time *t* as

$${\mathbb{E}}_{t}[f]:={\displaystyle \sum _{\sigma \in {X}_{\pm}^{k}}{p}_{t}}(\sigma )f(\sigma )={\displaystyle \sum _{\sigma \in {X}^{k}}({p}_{t}(}\sigma )-{p}_{t}(\overline{\sigma}))f(\sigma ),$$

where *p*
_{t}(*σ*) is the probability vector over states *X*
_{+} at time *t* and ${p}_{t}(\overline{\sigma})$ is the probability vector over states *X*
_{–} at time *t*. We will be interested in the convergence of the following “expectation process”

$${\mathcal{E}}_{t}={p}_{t}(\sigma )-{p}_{t}(\overline{\sigma}).$$

If we consider the random walk as two coupled chains, on *X*
_{+} and *X*
_{–} respectively, the above can be thought of as the difference in the marginal probability vectors of each chain.

In the case of a graph with a stochastic matrix *P*
_{G} one studies the convergence of *p*
_{t} the probability vector over states at time *t* to a stationary distribution *π*. The rate of convergence of the probability vector *p*
_{t} to *π* as well as the stationary distribution *π* are related to harmonics of the graph Laplacian. The graph case has some fundamental differences from the case of simplicial complexes in that graphs are not defined with orientation and the antisymmetric constraint that is required of *k*‐cochains is not relevant.

Note that the orientation of the complexes does not affect the Hodge Laplacian. One can define the following propagation matrix on ${X}_{+}^{k}$ that corresponds to the random walk *P* in Definition 3.2.

Definition 3.3

The *propagation matrix B* of the lower *k*‐walk is defined to be a square matrix indexed by ${X}_{+}^{k}$ with

$${(B)}_{{\sigma}_{+}\to \sigma {\prime}_{+}}=\{\begin{array}{cc}{\alpha}_{0}=p& \sigma {\prime}_{+}={\sigma}_{+}\\ {\alpha}_{1}=-\frac{1-p}{(M-1)(k+1)}& \sigma {\prime}_{+}\downarrow {\sigma}_{+}\\ {\alpha}_{2}=\frac{1-p}{(M-1)(k+1)}& \sigma {\prime}_{+}\downarrow {\overline{\sigma}}_{+}\\ 0& \text{otherwise}.\end{array}$$

There is a natural relation between the propagation matrix and the Markov matrix. We define a matrix *Q* with rows indexed by ${X}_{+}^{k}$ and columns indexed by *S*. The values of the matrix are specified as follows: *Q*
_{ij}=1 if state *i* and state *j* are neighbors, *Q*
_{ij}=–1 if state *i* and state *j* with reverse orientation are neighbors, and *Q*
_{ij}=0 if state *j* is a death state. This matrix has the following property *QP*=*BQ*. We now state some properties of the propagation matrix and its relation to the transition probability matrix *P*.

Proposition 3.4

*The propagation matrix B is given by*

$$B=\frac{p(M-2)+1}{M-1}I-\frac{1-p}{(M-1)(k+1)}\xb7{\Delta}_{k}^{\text{down}}.$$

*In addition, B satisfies QP=BQ and*

$$Q{P}^{t}\nu ={B}^{t}Q\nu .$$

The first claim is a straightforward computation based on Definition 3.3. The second claim is equivalent to the equality *QP*=*BQ*, which we now prove. If $\sigma \prime \in S$ and ${P}_{\sigma \prime}$ is the column of *P* indexed by $\sigma \prime $, then the column of *QP* indexed by $\sigma \prime $ is $Q{P}_{\sigma \prime}$. Using the definition of *Q*, the following holds

$$\begin{array}{l}{(QP)}_{{\sigma}_{+},\sigma \prime}=Q{P}_{\sigma \prime}({\sigma}_{+})\\ ={P}_{\sigma \prime}({\sigma}_{+})-{P}_{\sigma \prime}({\sigma}_{-})\\ ={(P)}_{{\sigma}_{+},\sigma \prime}-{(P)}_{{\sigma}_{-},\sigma \prime}\\ =\{\begin{array}{cc}\pm p& \sigma \prime ={\sigma}_{\pm}\\ \pm \frac{1-p}{(M-1)(k+1)}& s\ne \Theta \text{and}\sigma \prime \downarrow {\sigma}_{\pm}\\ 0& \text{otherwise}.\end{array}\end{array}$$

Similarly, note that ${(BQ)}_{{\sigma}_{+},\sigma \prime}=B(Q{\mathbf{1}}_{\sigma \prime})({\sigma}_{+})$ where ${\mathbf{1}}_{\sigma \prime}$ is the vector assigning 1 to $\sigma \prime \in S$ and 0 to all other elements in *S*. If $\sigma \prime =\Theta ,\hspace{0.17em}Q{\mathbf{1}}_{\sigma \prime}$ is the zero vector. Otherwise, if $\sigma \prime ={\tau}_{\pm}$ then $Q{\mathbf{1}}_{\sigma \prime}=\pm {\mathbf{1}}_{{\tau}_{+}}$ and

$$\begin{array}{l}{(BQ)}_{{\sigma}_{+},\sigma \prime}=\pm B\hspace{0.17em}{\mathbf{1}}_{{\tau}_{+}}({\sigma}_{+})\\ =\pm {(B)}_{{\sigma}_{+},{\tau}_{+}}\\ =\{\begin{array}{cc}\pm p& {\tau}_{+}={\sigma}_{+}\\ \pm \frac{1-p}{(M-1)(k+1)}& {\tau}_{+}\downarrow {\sigma}_{+}\\ \mp \frac{1-p}{(M-1)(k+1)}& {\tau}_{-}\downarrow {\sigma}_{+}\\ 0& \text{else}\end{array}\\ =\{\begin{array}{cc}\pm p& \sigma \prime ={\sigma}_{\pm}\\ \pm \frac{1-p}{(M-1)(k+1)}& \sigma \prime \downarrow {\sigma}_{\pm}\\ 0& \text{otherwise}.\end{array}\end{array}$$

For what follows, we define ${\mathcal{E}}_{t}^{{\tau}_{+}}:={B}^{t}{\mathbf{1}}_{{\tau}_{+}}$ to be the marginal difference of the random walk on *X* starting at *τ*
_{+} at time *t*. Also, let ${X}_{+}^{k}$ be a choice of orientation and denote $M={\mathrm{max}}_{\sigma \in {X}^{k-1}}\mathrm{deg}(\sigma )$.

Corollary 3.5

*The spectrum of B is contained in*$\left[2p-1,\frac{p(M-2)+1}{M-1}\right]$,*with the upper bound acheived by cochains in ker*._{k}and the lower bound acheived if and only if k <=d and there is a disorientable d‐connected component of constant (d – 1)‐degree*If τ has a coface, then*$${\Vert {\mathcal{E}}_{t}^{{\tau}_{+}}\Vert}_{2}\ge {\left(\frac{p(M-2)+1}{M-1}\right)}^{t}\frac{1}{\sqrt{k+2}}.$$*If p ≠ 0,1 then*$${\Vert {\mathcal{E}}_{t}^{{\tau}_{+}}\Vert}_{2}\le \mathrm{max}\left\{{\left|2p-1\right|}^{t},{\left(\frac{p(M-2)+1}{M-1}\right)}^{t}\right\}.$$

Statement (1) is easy to verify using Lemma 2.5 and Proposition 3.4. Statement (3) follows from the inequality ${\Vert Af\Vert}_{2}\le \Vert A\Vert {\Vert f\Vert}_{2}$ where *A* is a matrix, *f* is a vector, and $\Vert A\Vert $ is the spectral norm of *A*.

It remains now to prove statement (2). If *τ* has a coface *σ*, let $f={\partial}_{k+1}{\mathbf{1}}_{{\sigma}_{+}}$ (with *σ*
_{+} being any orientation of *σ*) which implies $f\in \text{ker}\hspace{0.17em}{\partial}_{k}$. Let $f,{f}_{1},\dots ,{f}_{i}$ be an orthogonal basis for *C*
^{k} such that ${f}_{1},\dots ,{f}_{i}$ are eigenvectors of *B*. Then,

$$\begin{array}{l}{\Vert {\mathcal{E}}_{t}^{{\tau}_{+}}\Vert}_{2}={\Vert {B}^{t}{\mathbf{1}}_{{\tau}_{+}}\Vert}_{2}\\ ={\Vert \alpha {B}^{t}f+{\alpha}_{1}{B}^{t}{f}_{1}+\dots +{\alpha}_{i}{B}^{t}{f}_{i}\Vert}_{2}\\ \ge {\Vert \alpha {B}^{t}f\Vert}_{2}\\ =|\alpha |{\left(\frac{p(M-2)+1}{M-1}\right)}^{t}{\Vert f\Vert}_{2}\\ ={\left(\frac{p(M-2)+1}{M-1}\right)}^{t}\left|\u3008\frac{f}{{\Vert f\Vert}_{2}},{\mathbf{1}}_{{\tau}_{+}}\u3009\right|\\ ={\left(\frac{p(M-2)+1}{M-1}\right)}^{t}\frac{\left|f({\tau}_{+})\right|}{{\Vert f\Vert}_{2}}\\ ={\left(\frac{p(M-2)+1}{M-1}\right)}^{t}\frac{1}{\sqrt{k+2}}\end{array}$$

$$$$

$$$$

$$$$

$$$$

$$$$

$$$$

By Corollary 3.5 we know that $\underset{t\to \infty}{\mathrm{lim}}{\mathcal{E}}_{t}=0$ when *p* ≠ 0,1. We rescale *B* to define the normalized propagation matrix

$$\tilde{B}:=\frac{M-1}{p(M-2)+1}B.$$

for which the trivial convergence due to $\left(\frac{p(M-2)+1}{M-1}\right)<1$ is eliminated. We also define the normalized marginal difference ${\tilde{\mathcal{E}}}_{t}^{{\tau}_{+}}:={\tilde{B}}^{t}{\mathbf{1}}_{{\tau}_{+}}.$ The next two theorems show that the homology of *X* can be determined from the limiting behavior of the normalized marginal difference.

Theorem 3.6

*The limit*
${\tilde{\mathcal{E}}}_{\infty}^{{\tau}_{+}}:=\underset{t\to \infty}{\mathrm{lim}}{\tilde{\mathcal{E}}}_{t}^{{\tau}_{+}}$
*of the normalized marginal difference exists for all τ _{+} if and only if*
$\tilde{B}$

Note that by Corollary 3.5, the spectrum of $\tilde{B}$ is upper bounded by 1 and the eigenspace of the eigenvalue 1 is exactly ker
_{k}. Let *f*
_{1},…,*f*
_{i} be an orthogonal basis for *C*
^{k} such that *f*
_{1}, …, *f*
_{i} are eigenvectors of $\tilde{B}$ with eigenvalues *γ*
_{1},…,*γ*
_{i}. Then any ${\mathbf{1}}_{{\tau}_{+}}$ can be written as a linear combination ${\mathbf{1}}_{{\tau}_{+}}={\alpha}_{1}{f}_{1}+\dots +{\alpha}_{i},{f}_{i}$ so that

$${\tilde{\mathcal{E}}}_{\infty}^{{\tau}_{+}}={\tilde{B}}^{t}{\mathbf{1}}_{{\tau}_{+}}={\alpha}_{1}{\gamma}_{1}^{t}{f}_{1}+\dots ,{\alpha}_{i}{\gamma}_{i}^{t}{f}_{i}$$

Since the *f*
_{j} form a basis, ${\tilde{\mathcal{E}}}_{\infty}^{{\tau}_{+}}$ converges if and only if ${\alpha}_{j}{\gamma}_{j}^{t}$ converges for each *j*. In other words, ${\tilde{\mathcal{E}}}_{\infty}^{{\tau}_{+}}$ converges if and only if for every *j, α*
_{j}=0 or *γ*
_{j}>–1. Furthermore, the limit (when it exists) is always

$$\sum _{\{j:{\gamma}_{j}=1\}}{\alpha}_{j}}{f}_{j}={\text{proj}}_{\text{ker}\hspace{0.17em}{\partial}_{k}}{\mathbf{1}}_{{\tau}_{+}$$

Finally, suppose $\tilde{B}$ has an eigenvalue *λ*≤–1. Then there is an eigenvector *f* such that ${\tilde{B}}^{t}f={\lambda}^{t}f$ does not converge. Since the set of cochains $\{{\mathbf{1}}_{{\tau}_{+}}:{\tau}_{+}\in {X}_{\pm}^{k}\}$ spans ${C}^{k}(\mathbb{R})$, *f* can be written as a linear combination of the cochains and therefore ${\tilde{B}}^{t}{\mathbf{1}}_{{\tau}_{+}}$ must not converge for some *τ*
_{+}.

Theorem 3.7

*If*$\frac{M-2}{3M-4}<p<1$*then the limit*${\tilde{\mathcal{E}}}_{\infty}^{{\tau}_{+}}$*exists for all τ*_{+}and$$\mathrm{dim}(\text{span}\{{\text{proj}}_{\text{ker}\hspace{0.17em}{\delta}^{k}}{\tilde{\mathcal{E}}}_{\infty}^{{\tau}_{+}}:{\tau}_{+}\in {X}_{\pm}^{k}\})=\mathrm{dim}({H}_{k}(X))$$*where*${\text{proj}}_{\text{ker}\hspace{0.17em}{\delta}^{k}}$*denotes the projection map onto ker δ*.^{k}*The same holds when*$p=\frac{M-2}{3M-4}$*or k=d or there are no disorientatable d‐connected components of constant (d – 1)‐degree*.*We can say more if*$p\ge \frac{1}{2}$.*In this case*,$${\Vert {\tilde{\mathcal{E}}}_{n}^{{\tau}_{+}}-{\tilde{\mathcal{E}}}_{\infty}^{{\tau}_{+}}\Vert}_{2}=O\left({\left[1-\frac{1-p}{(p(M-2)+1)(k+1)}{\lambda}_{k}\right]}^{t}\right)$$

The proof follows mostly from Theorem 3.6. According to Theorem 3.6, ${\tilde{\mathcal{E}}}_{\infty}^{{\tau}_{+}}$ exists for all *τ*
_{+} if and only if the spectrum of $\tilde{B}$ is contained in (–1, 1]. Using Corollary 3.5 and the definition $\tilde{B}:=\frac{M-1}{p(M-2)+1}B$, we know that the spectrum of $\tilde{B}$ is contained in $\left[(2p-1)\frac{M-1}{p(M-2)+1},1\right]$. Now each of the following statements imply each other

$$\begin{array}{l}(2p-1)\frac{M-1}{p(M-2)+1}>-1,\hspace{1em}\frac{p(M-2)+1}{M-1}>1-2p\\ p\left(\frac{M-2}{M-1}+2\right)>1-\frac{1}{M},\hspace{1em}p>\frac{M-2}{3M-4},\end{array}$$

$$$$

which proves that the spectrum of $\tilde{B}$ is indeed contained in (–1, 1] when $p>\frac{M-2}{3M-4}$. Since the ${\mathbf{1}}_{{\tau}_{+}}$ span all of *C*
^{k}, the ${\tilde{\mathcal{E}}}_{\infty}^{{\tau}_{+}}={\text{proj}}_{\text{ker}\hspace{0.17em}{\partial}_{k}}{\mathbf{1}}_{{\tau}_{+}}$ span all of ker
_{k}, and hence the ${\text{proj}}_{\text{ker}\hspace{0.17em}{\delta}^{k}}{\tilde{\mathcal{E}}}_{\infty}^{{\tau}_{+}}$ span all of ker *δ*
_{k}.

In the case that $p=\frac{M-2}{3M-4}$, the spectrum of $\tilde{B}$ is contained in [–1, 1]. However, as long as –1 is not actually an eigenvalue of $\tilde{B}$, the result still holds. According to Corollary 3.5, –1 is an eigenvalue if and only if *k*=*d* and there is a disorientable *d*‐connected component of constant (*d* – 1)‐degree. The case *p*=1 is trivial ($\tilde{B}=I$) and is not considered.

Finally, if the spectrum of *B* lies in (–1, 1] and *λ* is the eigenvalue of $\tilde{B}$ contained in (–1, 1) with largest absolute value, then

$${\Vert {\tilde{B}}^{t}f-\underset{t\to \infty}{\mathrm{lim}}{\tilde{B}}^{t}f\Vert}_{2}\le {|\lambda |}^{t}{\Vert f\Vert}_{2}$$

for all *f*. To see this, let *f*
_{1},…,*f*
_{i} be an orthonormal basis for *C*
^{k} such that *f*
_{1},…,*f*
_{i} are eigenvectors of $\tilde{B}$ with eigenvalues *γ*
_{1},…,*γ*
_{i}. Then any *f* can be written as a linear combination $f={\alpha}_{1}{f}_{1}+\dots ,+{\alpha}_{i}{f}_{i}$ so that ${\Vert f\Vert}_{2}=\sqrt{{\displaystyle \sum _{j}{\left|{\alpha}_{j}\right|}^{2}}}$ and

$$\begin{array}{l}{\Vert {\tilde{B}}^{t}f-\underset{t\to \infty}{\mathrm{lim}}{\tilde{B}}^{t}f\Vert}_{2}={\Vert {\alpha}_{1}{\gamma}_{1}^{t}{f}_{1}+\dots +{\alpha}_{i}{\gamma}_{i}^{t}{f}_{i}-{\displaystyle \sum _{\{j:{\gamma}_{j}=1\}}{\alpha}_{j}}{f}_{j}\Vert}_{2},\\ ={\Vert {\displaystyle \sum _{\{j:{\gamma}_{j}\ne 1\}}{\alpha}_{j}}{\gamma}_{j}^{t}{f}_{j}\Vert}_{2},\\ \le {|\lambda |}^{t}\xb7{\Vert f\Vert}_{2}.\end{array}$$

$$$$

$$$$

In particular, if $p\ge \frac{1}{2}$ then the spectrum of $\tilde{B}$ is contained in [0,1] and therefore $\lambda =1-\frac{1-p}{(p(M-2)+1)(k+1)}{\lambda}_{k}$.

Note the dependence of the theorem on both the probability *p* of remaining in a state and on *M*. We can think of *M* as the maximum amount of “branching”, where *M*=2 means there is no branching, as in a pseudomanifold of dimension *d*=*k*, and large values of *M* imply a high amount of branching. In particular, the walk must become more and more lazy for larger values of *M* in order to prevent the marginal difference from diverging. However, since $\frac{M-2}{3M-4}<\frac{1}{3}$ for all *M* a lazy probability of at least $\frac{1}{3}$ will always ensure convergence. While there is no explicit dependence on *k* or the dimension *d*, it is easy to see that *M* must always be at least *d* – *k*+1 (for instance, it is not possible for a triangle complex to have maximum vertex degree 1). A natural question is how varying the transition matrix *P* in Definition 3.2 will change the scaling behavior of the walk with respect to *M* and *p*.

We would also like to know whether the normalized marginal difference always converges to 0. Note that if *τ*
_{+} has a coface, then we already know that ${\Vert {\mathcal{E}}_{t}^{{\tau}_{+}}\Vert}_{2}$ stays bounded away from 0 according to Corollary 3.5. However, if *τ* has no coface, then ${\mathbf{1}}_{{\tau}_{+}}$ may be perpendicular to ker
_{k}, allowing ${\Vert {\mathcal{E}}_{t}^{{\tau}_{+}}\Vert}_{2}$ to die in the limit as we see in the following corollary.

Corollary 3.8

*If τ has no coface, H _{k} = 0, and if*
$\frac{M-2}{3M-4}<p<1$

$${\Vert {\mathcal{E}}_{\infty}^{{\tau}_{+}}\Vert}_{2}=0.$$

*The same is true when*
$p=\frac{M-2}{3M-4}$
*and or k = d and there are no disorientable d‐connected components of constant (d – 1)‐degree*,

Under all conditions stated, ${\tilde{\mathcal{E}}}_{\infty}^{{\tau}_{+}}$ converges. If *τ* has no coface, then ${\mathbf{1}}_{{\tau}_{+}}$ is in the orthogonal complement of im
_{k+1}, because all elements of im
_{k+1} are supported on oriented faces of (*k* + 1)‐simplexes. If *H*
_{k} = 0 then ker
_{k} = im
_{k+1} and

$${\Vert {\tilde{\mathcal{E}}}_{\infty}^{{\tau}_{+}}\Vert}_{2}={\text{proj}}_{\text{ker}\hspace{0.17em}{\partial}_{k}}{\mathbf{1}}_{{\tau}_{+}}=0.$$

The random walk described by Parzanchevski and Rosenthal in 17 is the “dual” of the random walk defined in the previous section in that one traverses between simplexes via cofaces rather than faces. We include Rosenthal and Parzanchevski's proposed walk in this section so the paper is self contained and we can compare the walk on ${\Delta}_{k}^{\text{up}}$ with the one in the previous section as well as a walk corresponding to the full Hodge Laplacian. We do not present any new results in this section.

Let *X* be a *d*‐complex, 0 ≤ *k* ≤ *d* – 1, and 0 ≤ *p* < 1.

Definition 4.1

The State space is the set of oriented complexes as well as a death state, $S={X}_{\pm}^{k}\cup \{\Theta \}$.

- Co‐neighbors: two oriented
*k*‐cells are called co‐neighbors, which we denote as $\sigma \uparrow \sigma \prime $ if they share a (*k*+ 1) coface and have opposite orientation on the shared face. - Transition matrix
*P*: the transition matrix is the time‐homogenous Markov chain on the state space $S={X}_{\pm}^{k}\cup \{\Theta \}$ with transition probabilitiesfor all $\sigma ,\sigma \prime \in {X}^{k}$.$${P}_{\sigma ,\sigma \prime}=\text{Prob}(\sigma \to \sigma \prime )=\{\begin{array}{cc}{\alpha}_{0}=p& \hspace{0.17em}\text{when}\sigma \ne \Theta \hspace{0.17em}\text{and}\sigma \prime =\sigma \\ {\alpha}_{1}=\frac{1-p}{k-\mathrm{deg}(\sigma )}& \hspace{0.17em}\text{when}\sigma \ne \Theta \hspace{0.17em}\text{and}\sigma \prime \uparrow \sigma \\ {\alpha}_{2}={\alpha}_{1}& \hspace{0.17em}\text{when}\sigma \ne \Theta \hspace{0.17em}\text{and}\sigma \uparrow \overline{\sigma \prime}\\ \beta =1-p& \hspace{0.17em}\text{when}\mathrm{deg}(\sigma )=0\hspace{0.17em}\text{and}\sigma \prime =\Theta \\ 1& \sigma =\sigma \prime =\Theta ,\end{array}$$

The definition of the walk in 17 is slightly different. There is no death state in 17 because the case of *k* = *d* – 1 was examined and it was assumed that every *k*‐simplex had at least one coface. As in the previous section we can relate the above Markov matrix to ${\Delta}_{k}^{\text{up}}$ and *QP ^{t}ν* is the marginal difference after

There are a few differences between the walk across faces and the walk across cofaces. The norm of the normalized marginal difference for the walk across cofaces starting at a single oriented simplex stays bounded away from 0 (see Proposition 2.8 of 17), whereas this need not hold for the walk across faces (as in Corollary 3.8). This is because in the walk across cofaces every starting point ${\mathbf{1}}_{{\tau}_{+}}$ has some nonzero inner product with an element of $\text{im}\hspace{0.17em}{\delta}^{k-1}\subseteq \text{ker}\hspace{0.17em}{\delta}^{k}$. The second difference is the threshold values for *p* in Theorem 3.7 and Theorem 2.9 of 17. For the walk across faces, homology can be detected for $p>\frac{M-2}{3M-4}$ (where $M={\mathrm{max}}_{\sigma \in {X}^{k-1}}\mathrm{deg}(\sigma )$) whereas for the walk across cofaces the threshold is $p>\frac{k}{3k+2}$. Hence, the walk across cofaces is sensitive to the dimension while the walk across faces is sensitive to the maximum degree. In both cases, $p\ge \frac{1}{3}$ is always sufficient to detect homology and $p\ge \frac{1}{2}$ allows us to put a bound on the rate of convergence.

The existence of random walks across faces and cofaces that respectively correspond to the two parts of the Hodge Laplacian suggests that there may be a random walk for the entire Laplacian, ${\Delta}_{k}={\Delta}_{k}^{\text{up}}+{\Delta}_{k}^{\text{down}}$. In this section, we state results for a random walk that captures both parts of the Hodge Laplacian. One can define a weighted notion of the Hodge Laplacian to weighted Laplacians

$${\mathbf{L}}_{k,W}:={W}_{k}^{-1/2}{\partial}_{k+1}{W}_{k+1}{\delta}^{k}{W}_{k}^{-1/2}+{W}_{k}^{1/2}{\delta}^{k-1}{W}_{k-1}^{-1}{\partial}_{k}{W}_{k}^{1/2}$$

where *W*
_{j} denotes a diagonal matrix with diagonal entries equal to positive weights, one for each *j*‐simplex. In general, one can also define an operator **L**
_{k} that is a generalized notion of the *k*‐th Hodge Laplacian.

Definition 5.1

Let ${X}_{+}^{k}$ be a choice of orientation. A generalized Laplacian matrix is a square matrix *L* such that

- the rows and columns of
*L*are indexed by ${X}_{+}^{k}$, *L*has nonnegative diagonal entries,- whenever
*L*has a zero on the diagonal, all other entries in the same row or column are also zero, *L*is a non‐negative operator.

Definition 5.2

Let ${X}_{+}^{k}$ be a choice of orientation, *L* a generalized Laplacian matrix, and *p* [0, 1]. Given *L* we define a normalization matrix ${D}_{L}^{-1}$ as a diagonal matrix with ${({D}_{L}^{-1})}_{{\sigma}_{+},{\sigma}_{+}}={({L}_{{\sigma}_{+},{\sigma}_{+}})}^{-1}$ if ${L}_{{\sigma}_{+},{\sigma}_{+}}>0$ and ${({D}_{L}^{-1})}_{{\sigma}_{+},{\sigma}_{+}}=0$ otherwise.

We define the *p*‐lazy propagation matrix related to *L* to be

$${A}_{L,p}:=\frac{p(K-1)+1}{K}I-\frac{1-p}{K}\xb7L{D}_{L}^{-1}$$

where $p\in [0,1],\hspace{0.17em}K:={\mathrm{max}}_{{\sigma}_{+}\in {X}_{+}^{k}}{\displaystyle \sum _{\sigma {\prime}_{+}\ne {\sigma}_{+}}\left|{(L{D}_{L}^{-1})}_{\sigma {\prime}_{+},{\sigma}_{+}}\right|}$. The case *K* = 0 is degenerate and is not considered. In addition, we define the normalized *p*‐lazy propagation matrix

$${\tilde{A}}_{L,p}:=I-\frac{1-p}{p(K-1)+1}L{D}_{L}^{-1}\left(=\frac{K}{p(K-1)+1}{A}_{L,p}\right)$$

Note that whenever *K* = 1, ${A}_{L,p}={\tilde{A}}_{L,p}$. In particular, this is true in the graph case when *L* = Δ_{0}.

We will now define the Markov transition matrix in terms of the propagation matrix.

Definition 5.3

Let ${X}_{+}^{k}$ be a choice of orientation, *L* a generalized Laplacian matrix, *p* [0, 1], and let *A*
_{L,p} be defined as above. The state space is $S:={X}_{\pm}^{k}\cup \{\Theta \}$ which is a (2*n* + 1) × (2*n* + 1) matrix where the number of unoriented complexes is *n*. The Markov transition matrix is defined as

$${P}_{L,p}=\left[\begin{array}{cc}\begin{array}{cc}\mathbf{A}& \mathbf{A}\prime \\ \mathbf{A}\prime & \mathbf{A}\end{array}& 0\\ v& 1\end{array}\right],$$

where the first *n* rows and columns correspond to ${X}_{+}^{k}$, the second *n* rows and columns correspond to ${X}_{-}^{k}$, and the last row and column correspond to the death state. The elements of matrix **A** correspond to transition probabilities between simplexes of the same orientation and ${\mathbf{A}}_{ij}={({A}_{L,p})}_{ij}\vee 0$ for *i*, *j* = 1,…,*n*. The elements of matrix $\mathbf{A}\prime $ correspond to transition probabilities between simplexes of the opposite orientation and $\mathbf{A}{\prime}_{ij}={(-{A}_{L,p})}_{ij}\vee 0$ for *i*, *j* = 1,…,*n*. The elements in the column vector *v* are the probabilities of entering the death set from one of the complexes and

$${v}_{i}=1-{\displaystyle \sum _{\sigma \prime \in S\setminus \{\Theta \}}{({P}_{L,p})}_{\sigma \prime ,\sigma}}\text{for}\text{all}\sigma .$$

The row vector $v\prime $ is the transpose of *v*. The 1 in the lower diagonal states implies that one does not leave the death state.

The following lemma shows that *P*
_{L,p} is a left stochastic matrix.

Lemma 5.4

*Let*
${X}_{+}^{k}$
*be a choice of orientation, L a generalized Laplacian, and p [0, 1]. The matrix*
${P}_{L,p}$
*defined above is a left stochastic matrix for an absorbing Markov chain on the state space S (i.e.*, ${({P}_{L})}_{\sigma \prime ,\sigma}=\text{Prob}(\sigma \to \sigma \prime )$) *such that Θ is an absorbing state and Prob(σ → σ) = p for all σ ≠ Θ*.

It is clear by the definition of *P*
_{L,p} that Θ is an absorbing state. To see that Prob(*σ* → *σ*) = *p* for all *s* ≠ Θ, note that

$$\begin{array}{l}{({A}_{L,p})}_{{\sigma}_{+},{\sigma}_{+}}=\frac{p(K-1)+1}{K}-\frac{1-p}{K}\xb71\\ =\frac{p(K-1)+1-1+p}{K}=p\end{array}$$

$$$$

and hence by the definition of *P*
_{L,p},

$${({P}_{L,p})}_{{\sigma}_{-},{\sigma}_{-}}={({P}_{L,p})}_{{\sigma}_{+},{\sigma}_{+}}=p$$

for all *σ*. It is also clear by the definition of *P*
_{L,p} that the entries ${({P}_{L,p})}_{\sigma {\prime}_{-},{\sigma}_{+}}={({P}_{L,p})}_{\sigma {\prime}_{+},{\sigma}_{-}}$ are nonnegative for any $\sigma ,\sigma \prime $. Hence, in order to show that *P*
_{L,p} is left stochastic we need only to prove that $\sum _{\sigma \prime \in S\setminus \{\Theta \}}{({P}_{L,p})}_{\sigma \prime ,\sigma}}\le 1$ for all $\sigma \in S\setminus \{\Theta \}$. By the symmetries inherent in *P*
_{L,p}, the value of the sum is the same for *σ* = *σ*
_{+} as it is for *σ* = *σ*
_{–.} For any *σ* = *σ*
_{+},

$$\begin{array}{l}{\displaystyle \sum _{\sigma \prime \in S\setminus \{\Theta \}}{({P}_{L,p})}_{\sigma \prime ,\sigma}}={\displaystyle \sum _{\sigma {\prime}_{+}\in {X}_{+}^{k}}{({A}_{L,p})}_{\sigma {\prime}_{+},{\sigma}_{+}}}\\ =p+{\displaystyle \sum _{\sigma {\prime}_{+}\in {X}_{+}^{k}\setminus \left\{{\sigma}_{+}\right\}}\left|{({A}_{L,p})}_{\sigma {\prime}_{+},{\sigma}_{+}}\right|}\\ =p+\frac{1-p}{K}{\displaystyle \sum _{\sigma {\prime}_{+}\in {X}_{+}^{k}\setminus \left\{{\sigma}_{+}\right\}}\left|{(L{D}_{L}^{-1})}_{\sigma {\prime}_{+},{\sigma}_{+}}\right|}\\ \le p+(1-p)=1.\end{array}$$

$$$$

$$$$

$$$$

The following theorem relates the Markov transition matrix *P*
_{L,p} to the generalized Hodge Laplacian *L*.

Theorem 5.5

*Let*
${X}_{+}^{k}$
*be a choice of orientation, L a generalized Laplacian matrix, p [0, 1], and let A _{L,p} and P_{L,p} be defined as above. In addition, let Q be defined as in Section*
3.

$${A}_{L,p}Q=Q{P}_{L,p}.$$

*In other words, the evolution of the marginal differences*
$Q{P}_{L,p}^{t}\nu $
*after n steps with initial distribution ν is governed by the propagation matrix*: $Q{P}_{L,p}^{t}\nu ={A}_{L,p}^{t}Q\nu $.

Using the definition of *Q*

$$\begin{array}{l}{(Q{P}_{L,p})}_{{\sigma}_{+},s}={({P}_{L,p})}_{{\sigma}_{+},s}-{({P}_{L,p})}_{{\sigma}_{-},s}\\ =\{\begin{array}{cc}\pm {({A}_{L,p})}_{{\sigma}_{+},\sigma {\prime}_{+}}& s=\sigma {\prime}_{\pm}\\ 0& s=\Theta \end{array}.\end{array}$$

Similarly, note that ${({A}_{L,p}Q)}_{{\sigma}_{+},s}={A}_{L,p}(Q{\mathbf{1}}_{s})({\sigma}_{+})$ where **1**
_{s} is the vector assigning 1 to *s* *S* and 0 to all other elements in *S*. If $s=\Theta ,\hspace{0.17em}Q{\mathbf{1}}_{s}$ is the zero vector. Otherwise, if *s* = *τ*
_{±} then $Q{\mathbf{1}}_{s}=\pm {\mathbf{1}}_{{\tau}_{+}}$. Thus,

$$\begin{array}{l}{({A}_{L,p}Q)}_{{\sigma}_{+},s}=\{\begin{array}{cc}\pm {A}_{L,p}{\mathbf{1}}_{{\tau}_{+}}({\sigma}_{+})& s={\tau}_{\pm}\\ 0& s=\Theta \end{array}\\ =\{\begin{array}{cc}\pm {({A}_{L,p})}_{{\sigma}_{+},{\tau}_{+}}& s={\tau}_{\pm}\\ 0& s=\Theta \end{array}.\end{array}$$

Finally, we conclude with a few results motivating the normalized propagation matrix and showing how the limiting behavior of the marginal difference relates to the kernel and spectrum of *L*.

Theorem 5.6

*Let*
${X}_{+}^{k}$
*be a choice of orientation, L a generalized Laplacian matrix with*
$\text{Spec}(L)\subset [0,\Lambda ]$
*(Λ > 0). Then for*
$\frac{\Lambda -1}{K+\Lambda -1}\le p<1$
*the following statements hold*:

- ${\Vert {A}_{L,p}^{t}Q\nu \Vert}_{2}\to 0$
*for every initial distribution ν*, - ${\tilde{A}}_{L,p}^{t}Q\nu \to {\text{proj}}_{\text{ker}\hspace{0.17em}L}Q\nu $
*for every initial distribution ν, where*${\text{proj}}_{\text{ker}\hspace{0.17em}L}$*denotes the projection map onto the kernel of L*, *If λ is the spectral gap (smallest nonzero eigenvalue) of L then*$${\Vert {\tilde{A}}_{L,p}^{t}Q\nu -{\text{proj}}_{\text{ker}\hspace{0.17em}L}Q\nu \Vert}_{2}=O\left({\left[1-\frac{1-p}{p(K-1)+1}\lambda \right]}^{t}\right).$$

The proof is the same as in the proofs of Corollary 3.5 and Theorem 3.7 and mostly boil down to statements about the spectra of *A*
_{L,p} and ${\tilde{A}}_{L,p}$. Note that since $\frac{\Lambda -1}{K+\Lambda -1}\le p<1,\hspace{0.17em}\text{Spec}({\tilde{A}}_{L,p})\subset [0,1]$ where the eigenspace of the eigenvalue 1 is equal to the kernel of *L*, and the largest eigenvalue of ${\tilde{A}}_{L,p}$ less than 1 is $1-\frac{1-p}{p(K-1)+1}\lambda $.

As an example of the applicability of this framework, ${\tilde{A}}_{L,p}$ is used with *L* = Δ* _{k}* to perform label propagation on edges in the next section.

In this section we provide some examples of random walks on simplicial complexes to provide some intuition. In addition we extend the label propagation algorithm used in machine learning for semi‐supervised learning from graphs to simplicial complexes.

We begin by reviewing local random walks on graphs as defined by Fan Chung in 3. Given a graph *G* = (*V*, *E*) and a designated “boundary” subset $S\subset V$, a $\frac{1}{2}$ ‐lazy random walk on $\overline{S}=V\setminus S$ can be defined to satisfy a Dirichlet boundary condition on *S* (meaning a walker is killed whenever it reaches *S*). The walker starts on a vertex ${v}_{0}\in \overline{S}$ and at each step remains in place with probability $\frac{1}{2}$ or else jumps to one of the adjacent vertices with equal probability. The boundary condition is enforced by declaring that whenever the walker would jump to a vertex in *S*, the walk ends. Thus, the left stochastic matrix *P* for this walk can be written as

$${(P)}_{v\prime ,v\in \overline{S}}=\text{Prob}(v\to v\prime )=\{\begin{array}{cc}\frac{1}{2}& \text{if}v=v\prime \\ \frac{1}{2{d}_{v}}& \text{if}v\sim v\prime \\ 0& \text{else}\end{array}$$

where $v\sim v\prime $ denotes that vertices *v* and $v\prime $ are adjacent and *d _{v}* is the number of edges connected to

$$P=I-\frac{1}{2}{\Delta}_{S}{D}_{S}^{-1}.$$

Hence, the existence and rate of convergence to a stationary distributions can be studied in terms of the spectrum of the local Laplace operator.

Now suppose we are given an orientable 2‐dimensional non‐branching simplicial complex *X* = (*V*, *E*, *T*) where *T* is the set of triangles (subsets of *V* of size 3). Non‐branching means that every edge is contained in at most 2 triangles. We can define a random walk on triangles fundamentally identical to a local walk on a graph which reveals the 2‐dimensional homology of *X*. The $\frac{1}{2}$‐lazy 2‐walk on *T* starts at a triangle *t*
_{0} and at each step remains in place with probability $\frac{1}{2}$ or else jumps to the other side of one of the three edges. If no triangle lies on the other side of the edge, the walk ends. The transition matrix *B* for this walk is given by

$${(B)}_{t\prime ,t}=\text{Prob}(t\to t\prime )=\{\begin{array}{cc}\frac{1}{2}& \text{if}t=t\prime \\ \frac{1}{6}& \text{if}t\sim t\prime \\ 0& \text{else}\end{array}$$

where $t\sim t\prime $ denotes *t* and $t\prime $ share an edge. This is the same transition matrix as *P*, in the case that *d _{v}* = 3 for all $v\in \overline{S}$. In this case, the analog of the set

Then take the “dual graph” *G* = (*V*, *E*) of $\tilde{X}$ by thinking of triangles as vertices (so, $V=\tilde{T}$) and connecting vertices in *G* with an edge if the corresponding triangles in $\tilde{X}$ share an edge. We do not add a vertex for each outer face. Choose the vertices corresponding to the added triangles $\tilde{T}\setminus T$ to be the boundary set *S*. Now the matrix *P* associated to the local random walk on *G* is indistinguishable from the matrix *B* associated to the random walk on *X*. In addition, it can be seen that Δ* _{S}* on

$$B=P=I-\frac{1}{6}{\Delta}_{S}=I-\frac{1}{6}{\Delta}_{2}.$$

See Section 2 for the definition of Δ_{2}, and the appendix of 21 for more on the connection between Δ* _{S}* and Δ

It is a basic fact that the kernel of Δ_{2} corresponds to the 2‐dimensional homology group of *X* over $\mathbb{R}$. Therefore, there exists a stationary distribution for the random walk if and only if *X* has nontrivial homology in dimension 2. Additionally, the rate of convergence to the stationary distribution (if it exists) is governed by the spectral gap of Δ_{2}. In particular, the following statements hold:

- Given a starting triangle
*t*_{0}, the marginal distribution of the random walk after*n*steps is ${\mathcal{E}}_{n}^{{t}_{0}}:={B}^{n}{\mathbf{1}}_{{t}_{0}}$ where ${\mathbf{1}}_{{t}_{0}}$ is the vector assigning a 1 to*t*_{0}and 0 to all other triangles. For any*t*_{0}, the marginal distrubition converges, i.e., ${\mathcal{E}}_{\infty}^{{t}_{0}}:=\underset{n\to \infty}{\mathrm{lim}}{\mathcal{E}}_{n}^{{t}_{0}}$ exists. - The limit ${\mathcal{E}}_{\infty}^{{t}_{0}}$ is equal to 0 for all starting triangles
*t*_{0}if and only if*X*has trivial homology in dimension 2 over $\mathbb{R}$. - The rate of convergence is given bywhere$${\Vert {\mathcal{E}}_{n}^{{t}_{0}}-{\mathcal{E}}_{\infty}^{{t}_{0}}\Vert}_{2}=O\left({\left[1-\frac{1}{6}{\lambda}_{2}\right]}^{n}\right)$$
*λ*_{2}is the smallest nonzero eigenvalue of Δ_{2}.

The example given here is constrained by certain assumptions (orientability and the non‐branching property), which allows for the most direct interpretation with respect to previous work done on graphs.

In machine learning random walks on graphs have been used for semi‐supervised learning. In this section we will generalize a class of algorithms on graphs called “label propagation” algorithms to simplicial complexes, specifically we extend the algorithm described in 23 (for more examples, see 1, 11, 22). The goal of semi‐supervised classification learning is to classify a set of unlabelled objects {*v*
_{1}, …, *v _{u}*}, given a small set of labelled objects $\{{v}_{u+1},\dots ,{v}_{u+\ell}\}$ and a set

$${(P)}_{ij}=\text{Prob}({v}_{j}\to {v}_{i})=\frac{1}{{d}_{j}}$$

where *d _{j}* is the degree of vertex

- For
*t*= 1,…, and*c*= 1,…,*C*:- Set ${f}_{t}^{c}\leftarrow P{f}_{t-1}^{c}$
- Reset ${f}_{t}^{c}({v}_{i})=1$ for all
*v*labelled as_{i}*c*.

- Consider ${f}_{H}^{c}$ as an estimate of the relative confidence that each object is in class
*c*. - For each unlabelled point
*v*,_{i}*i*≤*u*, assign the label$$\underset{c=1,\xa8C}{\mathrm{arg}\hspace{0.17em}\mathrm{max}}\{{f}_{\ell}^{c}({v}_{i})\}.$$

The number of steps is set to be large enough such that ${f}_{\ell}^{c}$ is close to its limit ${f}_{\infty}^{c}:=\underset{\ell \to \infty}{\mathrm{lim}}{f}_{\ell}^{c}$. If *G* is connected, it can be shown that ${f}_{\infty}^{c}$ is independent of the choice of ${f}_{0}^{c}$. Even if *G* is disconnected, the algorithm can be performed on each connected component separately and again the limit ${f}_{\infty}^{c}$ for each component will be independent of the choice of ${f}_{0}^{c}$.

We will now adapt the label propagation algorithm to higher dimensional walks, namely, walks on oriented edges. Given any random walk on the set of oriented edges (and an absorbing death state Θ), its probability transition matrix *P* could be used to propagate labels in the same manner as the above algorithm. However, this will treat and label the two orientations of a single edge separately as though they are unrelated. We will use walks that are related to the 1‐forms and harmonics of the Hodge Laplacian. A major difference with propagation on a goal is that the labels will be oriented. For example, given an oriented edge *e*
_{+} and a class *c*, the propagation algorithm may assign a positive confidence that *e*
_{+} belongs to class *c* or a negative confidence that *e*
_{+} belongs to class *c*, which we view as a positive confidence that *e*
_{+} belongs to class –*c* or, equivalently, that *e*
_{–} belongs to class *c*. This construction applies to systems in which every class has two built‐in orientations or signs, so the class information has a directed sense of “flow”.

For example, imagine water flowing along a triangle complex in two dimensions. Given an oriented edge, the water may flow in the positive or negative direction along the edge. A “negative” flow of water in the direction of *e*
_{+} can be interpreted as a positive flow in the direction of *e*
_{–.} Perhaps the flow along a few edges is observed and one wishes to infer the direction of the flow along all the other edges. Unlike in the graph case, a single class of flow already presents a classification challenge. Alternately, consider multiple streams of water colored according to the *C* classes, in which case we may want to know which stream dominates the flow along each edge and in which direction. In order to make these inferences, it is necessary to make some assumption about how labels should propagate from one edge to the next. When considering water flow, it is intuitive to make the following two assumptions.

**Local Consistency of Motion**. If water is flowing along an oriented edge [*v*,_{i}*v*] in the positive direction, then for every triangle [_{j}*v*,_{i}*v*,_{j}*v*] the water should also tend to flow along [_{k}*v*,_{i}*v*] and [_{k}*v*,_{k}*v*] in the positive directions._{j}**Preservation of Mass**. The total amount of flow into and out of each vertex (along edges connected to the vertex) should be the same.

In fact, either one of these assumptions is sufficient to infer oriented class labels given the observed flow on a few edges. Depending on which assumptions one chooses, different normalized propagation matrices ${\tilde{A}}_{L,p}$ (see Section 5) may be applied. For example, setting the Laplacian matrix *L* to ${\Delta}_{1}^{\text{up}}={\partial}_{2}{\delta}^{1}$ will enforce local consistency of motion without regard to preservation of mass, while $L={\Delta}_{1}^{\text{down}}={\delta}^{0}{\partial}_{1}$ will do the opposite. A reasonable way of preserving both assumptions is by using the full Hodge 1‐Laplacian *L* = Δ_{1}, see Fig. Fig.33 for a visual example of the contrast between walks.

(**A**) An edge labelled on a 2‐complex. (**B**) Label propagation with ${\Delta}_{1}^{\text{up}}$, note the gradient like flows. (**C**) Label propagation with ${\Delta}_{1}^{\text{down}}$, note the short cycles or curl structure. (**D**) Label propagation with Δ_{1}, note the cycle **...**

We now state a simple algorithm, analogous to the one for graphs, that propagates labels on edges to infer a partially‐observed flow. Let *X* be a simplicial complex of dimension *d* ≥ 1 and let ${X}_{+}^{1}=\{{e}_{1},\dots ,{e}_{n}\}$ be a choice of orientation for the set of edges. Without loss of generality, assume that oriented edges ${e}_{u+1},\dots ,{e}_{n=u+\ell}$ have been classified with class *c* (not –*c*). Similar to the graph case, we apply a recursive label propagation process to an initial distribution vector ${f}_{0}^{c}:{X}_{+}^{1}\to \mathbb{R}$ measuring the *a priori* confidence that each oriented edge is in class *c*. See Algorithm 1 for the procedure. The result of the algorithm is a set of estimates of the relative confidence that each edge is in class *c* with some orientation. [Color figure can be viewed in the online issue, which is available at wileyonlinelibrary.com.]

After running the algorithm, an unlabelled edge *e _{i}* is assigned the oriented class $\text{sgn}({f}_{\ell}^{c}({e}_{i}))c$ where $c=\mathrm{arg}\hspace{0.17em}{\mathrm{max}}_{c=1,\xa8C}\left\{\left|{f}_{\ell}^{c}({e}_{i})\right|\right\}$.

We now prove that given enough iterations the algorithm converges and the resulting assigned labels are meaningful. The proof uses the same methods as the one found in 23 for the graph case.

Proposition 6.1### Algorithm 1

#### 1.

*Using the notation of Section*
5, *assume that L is a Laplacian matrix with*
$\text{Spec}(L{D}_{L}^{-1})\subset [0,\Lambda ]$. *Let*
${\tilde{A}}_{L,p}$
*be the normalized p‐lazy propagation matrix as defined in Definition*
5.2. *If*
$\frac{\Lambda -2}{2K+\Lambda -2}<p<1$
*and if no vector in kerL is supported on the set of unclassified edges, then Algorithm*
1
*converges. That is*,

$$\underset{\ell \to \infty}{\mathrm{lim}}{f}_{T}^{c}=:{f}_{\infty}^{c}=\left(\begin{array}{c}{\psi}^{c}\\ {(I-{A}_{4})}^{-1}{A}_{3}{\psi}^{c}\end{array}\right),$$

*where A _{4} and A_{3} are submatrices of*
${\tilde{A}}_{L,p}$

First, note that we are only interested in the convergence of ${f}_{T}^{c}({e}_{i})$ for *e _{i}* not labelled ±

$${f}_{\ell}^{c}=\left(\begin{array}{c}{\psi}^{c}\\ {\widehat{f}}_{\ell}^{c}\end{array}\right)\hspace{1em}\hspace{1em}\text{and}\hspace{1em}\hspace{1em}{\tilde{A}}_{L,p}=\left(\begin{array}{cc}{A}_{1}& {A}_{2}\\ {A}_{3}& {A}_{4}\end{array}\right).$$

The recursive definition of ${f}_{\ell}^{c}$ in Algorithm 1 can now be rewritten as ${\widehat{f}}_{\ell}^{c}={A}_{4}{\widehat{f}}_{\ell -1}^{c}+{A}_{3}{\psi}^{c}$. Solving for ${\widehat{f}}_{\ell}^{c}$ in terms of ${\widehat{f}}_{0}^{c}$ yields

$${\widehat{f}}_{\ell}^{c}={({A}_{4})}^{k}{\widehat{f}}_{0}^{c}+{\displaystyle \sum _{i=0}^{\ell -1}{({A}_{4})}^{i}}{A}_{3}{\psi}^{c}.$$

In order to prove convergence of ${\widehat{f}}_{\ell}^{c}$, it suffices to prove that *A*
_{4} has only eigenvalues strictly less than 1 in absolute value. This ensures that ${({A}_{4})}^{k}{\widehat{f}}_{0}^{c}$ converges to zero (eliminating dependence on the initial distribution) and that $\sum _{i=0}^{k-1}{({A}_{4})}^{i}}{A}_{3}{\psi}^{c$ converges to ${(I-{A}_{4})}^{-1}{A}_{3}{\psi}^{c}$ as *k* → *∞*. We will prove that $\text{Spec}({A}_{4})\subset (-1,1)$ by relating Spec(*A*
_{4}) to $\text{Spec}(L{D}_{L}^{-1})\subset [0,\Lambda ]$ as follows.

First, partition *L* and *D _{L}* in a similar way to ${\tilde{A}}_{L,p}$ as

$$L=\left(\begin{array}{cc}{L}_{1}& {L}_{2}\\ {L}_{3}& {L}_{4}\end{array}\right)\hspace{1em}\hspace{1em}\text{and}\hspace{1em}\hspace{1em}{D}_{L}=\left(\begin{array}{cc}{D}_{1}& 0\\ 0& {D}_{4}\end{array}\right).$$

so that

$${A}_{4}=I-\frac{1-p}{p(K-1)+1}{L}_{4}{D}_{4}^{-1}.$$

Hence Spec(*A*
_{4}) is determined by $\text{Spec}({L}_{4}{D}_{4}^{-1})$, or to be more specific, $\lambda \in \text{Spec}({L}_{4}{D}_{4}^{-1})\iff 1-\frac{1-p}{p(K-1)+1}\lambda \in \text{Spec}({A}_{4})$. Furthermore, note that ${L}_{4}{D}_{4}^{-1}$ and ${D}_{4}^{-1/2}{L}_{4}{D}_{4}^{-1/2}$ are similar matrices that share the same spectrum. It turns out that the spectrum of ${D}_{4}^{-1/2}{L}_{4}{D}_{4}^{-1/2}$ is bounded within the spectrum of ${D}_{L}^{-1/2}L{D}_{L}^{-1/2}$, which in turn is equal to $\text{Spec}(L{D}_{L}^{-1})\subset [0,\Lambda ]$ by similarity. Let *g* be an eigenvector of ${D}_{4}^{-1/2}{L}_{4}{D}_{4}^{-1/2}$ with eigenvalue *λ* and let *g*
_{1},…, *g _{i}* be an orthonormal basis of eigenvectors of ${D}_{L}^{-1/2}L{D}_{L}^{-1/2}$ (such a basis exists since it is a symmetric matrix) with eigenvalues

$$\left(\begin{array}{c}{\mathbf{0}}_{c}\\ g\end{array}\right)={\alpha}_{1}{g}_{1}+\dots +{\alpha}_{i}{g}_{i}$$

for some *α*
_{1},…, *α _{i}*, where

$$\begin{array}{l}{\alpha}_{1}^{2}{\gamma}_{1}+\dots +{\alpha}_{i}^{2}{\gamma}_{i}={\left(\begin{array}{c}{\mathbf{0}}_{c}\\ g\end{array}\right)}^{\ell}{D}_{1}^{-1/2}{L}_{2}{D}_{4}^{-1/2}\left(\begin{array}{c}{\mathbf{0}}_{c}\\ g\end{array}\right)\\ ={\left(\begin{array}{c}{\mathbf{0}}_{c}\\ g\end{array}\right)}^{\ell}\left(\begin{array}{cc}{D}_{1}^{-1/2}{L}_{1}{D}_{1}^{-1/2}& {D}_{1}^{-1/2}{L}_{2}{D}_{4}^{-1/2}\\ {D}_{4}^{-1/2}{L}_{3}{D}_{1}^{-1/2}& {D}_{4}^{-1/2}{L}_{4}{D}_{4}^{-1/2}\end{array}\right)\left(\begin{array}{c}{\mathbf{0}}_{c}\\ g\end{array}\right)\\ ={\left(\begin{array}{c}{\mathbf{0}}_{c}\\ g\end{array}\right)}^{\ell}\left(\begin{array}{c}{D}_{1}^{-1/2}{L}_{2}{D}_{4}^{-1/2}g\\ \lambda g\end{array}\right)\\ =\lambda \left({\alpha}_{1}^{2}+\dots +{\alpha}_{i}^{2}\right)\end{array}$$

Because we assumed that *γ _{j}* [0, Λ] for all

To see that the solution ${\widehat{f}}_{\infty}^{c}={(I-{A}_{4})}^{-1}{A}_{3}{\psi}^{c}$ does not depend on *p*, note that *I* – *A*
_{4} is a submatrix of $\frac{1-p}{p(K-1)+1}L{D}_{L}^{-1}$ so that $\frac{p(K-1)+1}{1-p}(I-{A}_{4})$ does not depend on *p*. Then write ${\widehat{f}}_{\infty}^{c}$ as

$${\widehat{f}}_{\infty}^{c}={\left[\frac{p(K-1)+1}{1-p}(I-{A}_{4})\right]}^{-1}\times \frac{1}{1-p}{A}_{3}{\psi}^{c}$$

and note that $\frac{p(K-1)+1}{1-p}{A}_{3}$ is an *off‐diagonal* submatrix of $\frac{p(K-1)+1}{1-p}I-L{D}_{L}^{-1}$ and therefore does not depend on *p* either.

Note that while the limit ${f}_{\infty}^{c}$ exists, the matrix *I* – *A*
_{4} could be ill‐conditioned. In practice, it may be better to approximate ${f}_{\infty}^{c}$ with ${f}_{t}^{c}$ for large enough *t*. Also, the algorithm will converge faster for smaller values of *p* and if ${\widehat{f}}_{0}^{c}=\mathbf{0}$.

We use two simulations to illustrate how Algorithm 1 works. In the first example, we describe how a single oriented edge of one class is propagated via the different walks. In the second example, we describe the case where to oriented edges with different class labels are propagated.

Figure Figure3A3A shows a simplicial complex in which a single oriented edge *e*
_{1} has been labelled red and all other edges are unlabelled. Figure Figure3B3B displays the result of propagating this single label 1000 steps using Algorithm 1 with $L={\Delta}_{1}^{\text{up}}$, with the parameter *p* = 0.9, and *f*
_{0} equal to the indicator function on *e*
_{1} (edge *e*
_{1} is labelled red). The edges in Fig. Fig.3B3B are oriented according to the sign of *f*
_{1000}. Figures Figures3C3C and and3D3D display the results of propagating the same red edge by $L={\Delta}_{1}^{\text{down}}$ and *L* = Δ_{1} respectively. Propagation by ${\Delta}_{1}^{\text{up}}$ results in gradient like flows while propagation by ${\Delta}_{1}^{\text{down}}$ results in a more curl like structure. Propagation by the walk corresponding to the full Laplacian Δ_{1} results in longer cycles or harmonics as can be seen by the cycle around the boundary of the simplcial complex.

Figure Figure4A4A shows a simplicial complex in which two edges have been labelled with class *c* = 1 (indicated by the red color) and two other edges have been labelled with class *c* = 2 (indicated by the blue color). Figure Figure4B4B displays the result of 1000 iterations of Algorithm 1 with *L* = Δ_{1}, *p* = 0.9, and ${f}_{0}^{c}$ equal to the indicator function on the oriented edges labelled with classes *c* = 1, 2. The orientation of the edges are given by the sign of ${f}_{T}^{c=1}$, if $\left|{f}_{T}^{c=1}\right|>\left|{f}_{T}^{c=2}\right|$, or ${f}_{T}^{c=2}$, if $\left|{f}_{T}^{c=1}\right|<\left|{f}_{T}^{c=2}\right|$. Notice that only a small number of labels are needed to induce large‐scale circular motion. Near the middle, a few blue labels mix in with the red due to the asymmetry of the initial labels.

**(A)A2**‐complex with two different labels on four edges. (**B**) Edge propagation with two classes with Δ_{1}. [Color figure can be viewed in the online issue, which is available at wileyonlinelibrary.com.]

In this paper, we introduced a random walk on simplicial complexes with a stationary distribution that is related to part of the *k*‐th Hodge Laplacian ${\Delta}_{k}^{\text{down}}={\delta}^{k-1}{\partial}_{k}$. We compared our result to the result in 17 which focused on the walk corresponding to part of the *k*‐th Hodge Laplacian ${\Delta}_{k}^{\text{up}}={\partial}_{k+1}{\delta}^{k}$. We also state a walk that corresponds to the full Hodge Laplacian Δ_{k}.

There remain many open questions about random walks on simplicial complexes and the spectral theory of higher order Laplacians. Possible future directions of research include:

- What is the continuum limit for these random walks for a model where the random complex is generated by sampling a manifold.
- Is it possible to use conditioning techniques from stochastic processes such as Doob's
*h*‐transform to analyze these walks? - What applications do these walks have to problems in machine learning and statistics?

SM would like to thank Anil Hirani, Misha Belkin, and Jonathan Mattingly for useful comments. JS would like to thank Kevin McGoff for proofreading and useful comments.

^{†}Supported by NIH (System Biology) (to S.M.) (5P50‐GM081883); AFOSR (to S.M.) (FA9550‐10‐1‐0436); NSF (to S.M.) (CCF‐1049290); NSF (to J.S.) (DMS‐1045153; DMS‐12‐09155).

The copyright line for this article was changed on 14 February 2017 after original online publication.

Sayan Mukherjee, Email: ude.ciu@negrebj.

John Steenbergen, Email: ude.ekud.tats@nayas.

1.
Callut J., Françoisse K., Saerens M., and Dupont P., Semi‐supervised classification from discriminative random walks, Machine learning and knowledge discovery in databases, Springer‐Verlag, Berlin‐Heidelberg‐New York, 2008, pp. 162–177.

2.
Chung F. R. K., Spectral graph theory, American Mathematical Society, Providence, RI, 1997.

3.
Chung F. R. K., Random walks and local cuts in graphs, Linear Algebra Appli Vol. 423 (2007), 22–32.

4.
Chung F. R. K., Quasi‐random hypergraphs revisited, Random Struct Algorithms
40 (2012), 39–48.

5.
Chung F. R. K. and Graham R. L., Quasi‐random hypergraphs, Random Struct Algorithms
1 (1990), 105–124.

6.
Cohen E., Mubyi D., Ralli P., and Tetali P., Inverse expander mixing for hypergraphs, Arxiv preprint arXiv:1407.2285, 2014.

7.
Dodziuk J., Difference equations, isoperimetric inequality and transience of certain random walks, Trans Am Math Soc
284 (1984), 787–794.

8.
Dotterrer D. and Kahle M., Coboundary expanders, J Topol Anal
4 (2012), 499–514.

9.
Eckmann B., Harmonische Funktionen und Randwertaufgaben in einem Komplex, Comment Math Helv
17 (1944), 240–255.

10.
Friedman J. and Wigderson A., On the second eigenvalue of hypergraphs, Combinatorica
15 (1995), 43–65.

11.
Jaakkola T. and Szummer M., Partially labeled classification with M, arkov random walks, Advances in neural information processing systems (NIPS), MIT Press, Cambridge, MA, Vol. 14, 2002, pp. 945–952.

12.
Kahle M., Sharp vanishing thresholds for cohomology of random flag complexes, Ann Math
179 (2014), 1085–1107.

13.
Levin D. A., Peres Y., and Wilmer E. L., Markov chains and mixing times, American Mathematical Society, Providence, RI, 2008.

14.
Lovász L., Random walks on graphs: A survey, In Miklós D., editor; , Sós V. T., editor; and Szőnyi T., editor. , editors, Combinatorics, Paul Erdős is eighty, Vol. 2, János Bolyai Mathematical Society, Budapest‐Hungary, 1996, pp. 353–398.

15.
Lubotzky A., Ramanujan complexes and high dimensional expanders, Japanese Journal of Mathematics
9 (2014), 137–169.

16.
Meilă M. and Shi J., A random walks view of spectral segmentation, In AI and Statistics (AISTATS) 2001, Key West, Florida, 2001.

17.
Parzanchevski O. and Rosenthal R., Simplicial complexes: Spectrum, homology and random walks, arXiv:1211.6775v2, 2012.

18.
Parzanchevski O., Rosenthal R., and Tessler R. J., Isoperimetric inequalities in simplicial complexes, Combinatorica, 1–33.

19.
Rosenthal R., Simplicial branching random walks and their applications, Arxiv preprint arXiv:1412.5406, 2014.

20.
Steenbergen J., Towards a spectral theory for simplicial complexes, PhD thesis, Duke University, Durham, NC, 2013, AAI3605065.

21.
Steenbergen J., Klivans C., and Mukherjee S., A Cheeger‐type inequality on simplicial complexes, Adv Appl Math
56 (2014), 56–77.

22.
Zhou D. and Schölkopf B., Learning from labeled and unlabeled data using random walks, Pattern recognition, Springer, Berlin‐Heidelberg, 2004, pp. 237–244.

23.
Zhu X., Semi‐supervised learning with graphs, PhD thesis, Carnegie Mellon University, Language Technologies Institute, School of Computer Science, Pittsburgh, PA, 2005.

Articles from Wiley-Blackwell Online Open are provided here courtesy of **Wiley-Blackwell, John Wiley & Sons**

PubMed Central Canada is a service of the Canadian Institutes of Health Research (CIHR) working in partnership with the National Research Council's national science library in cooperation with the National Center for Biotechnology Information at the U.S. National Library of Medicine(NCBI/NLM). It includes content provided to the PubMed Central International archive by participating publishers. |