Orienting Edges
In Planar Graphs & Euler's Formula,
we studied graphs embedded in surfaces — a geometric perspective that revealed the face
structure and the Euler characteristic \(\chi = V - E + F = 2\). We now shift from geometry
to algebra: by assigning directions to edges, we convert a graph into an object that
linear algebra can act on.
This algebraic encoding will let us decompose the edge space \(\mathbb{R}^E\) into
orthogonal subspaces, recover the
graph Laplacian from first
principles, and lay the foundation for the
boundary operator that drives simplicial homology.
Definition: Orientation of a Graph
Let \(G = (V, E)\) be an undirected simple graph. An orientation of \(G\) is an
assignment, for each edge \(\{u, v\} \in E\), of one of the two possible directions:
either \(u \to v\) or \(v \to u\). The resulting directed graph is called an
oriented graph.
The choice of orientation is entirely arbitrary. Every undirected edge \(\{u, v\}\) has two
possible orientations, and for a graph with \(|E|\) edges there are \(2^{|E|}\) possible
orientations. The central theme of this page is that the algebraic objects we construct —
the cycle space, the cut space, and the graph Laplacian — are all independent of which
orientation we choose.
Choosing a different orientation for an edge merely flips the sign of the corresponding
column in the incidence matrix we are about to define. We will see that every algebraic
quantity built from this matrix — cycle space, cut space, Laplacian, Dirichlet energy — is
constructed so that these sign flips cancel out: opposite-orientation columns produce
opposite-sign contributions that combine to the same result. The orientation is a
bookkeeping device for the algebra, not a feature of the graph itself. (This kind of
structural invariance under arbitrary auxiliary choices is what physicists call
gauge freedom — a perspective that becomes central in geometric deep learning.)
We can already see a shadow of this principle in
Combinatorics: swapping the
orientation of an edge is an odd permutation of its endpoints, introducing a
factor of \(-1\). When we generalize from edges to higher-dimensional simplices in the
sequel on Simplicial Complexes, we will define
oriented simplices by \([a, b] = -[b, a]\), making the sign rule explicit.
For now, the intuition is that orientation is bookkeeping, not geometry.
The Incidence Matrix
With an orientation in hand, we can encode the graph in a matrix. This matrix records
which vertex each edge leaves and which it enters — nothing more and nothing less.
Yet from this simple encoding, the entire theory of flows and potentials on graphs will emerge.
Definition and Structure
Definition: Oriented Incidence Matrix
Let \(G\) be a graph with vertex set \(V = \{v_1, \ldots, v_n\}\) and edge set
\(E = \{e_1, \ldots, e_m\}\), equipped with an orientation. The oriented
incidence matrix is the matrix \(\boldsymbol{B} \in \mathbb{R}^{n \times m}\)
whose \((i, j)\)-entry is
\[
B_{ij} = \begin{cases}
+1 & \text{if edge } e_j \text{ leaves vertex } v_i, \\
-1 & \text{if edge } e_j \text{ enters vertex } v_i, \\
\;\;\,0 & \text{otherwise.}
\end{cases}
\]
Each column of \(\boldsymbol{B}\) contains exactly one \(+1\) and one \(-1\) (and \(n - 2\)
zeros), corresponding to the tail and head of the oriented edge. This immediately gives a
fundamental structural observation.
Proposition: Column Sums of \(\boldsymbol{B}\)
Every column of \(\boldsymbol{B}\) sums to zero. Equivalently, the all-ones vector
\(\mathbf{1} \in \mathbb{R}^n\) satisfies
\[
\mathbf{1}^\top \boldsymbol{B} = \mathbf{0}^\top,
\]
and hence \(\mathbf{1} \in \ker(\boldsymbol{B}^\top)\).
Proof:
For each edge \(e_j\), the column \(\boldsymbol{B}_{:,j}\) has exactly one entry
equal to \(+1\) and one equal to \(-1\), so the sum of entries is \(+1 + (-1) = 0\).
Since \(\mathbf{1}^\top \boldsymbol{B}\) computes column sums, this gives
\(\mathbf{1}^\top \boldsymbol{B} = \mathbf{0}^\top\). Taking transpose:
\(\boldsymbol{B}^\top \mathbf{1} = (\mathbf{1}^\top \boldsymbol{B})^\top = \mathbf{0}\),
so \(\mathbf{1} \in \ker(\boldsymbol{B}^\top)\).
Example: The Triangle Graph \(K_3\)
Example:
Consider \(K_3\) on vertices \(\{a, b, c\}\), with edges oriented as
\(e_1 = a \to b\), \(e_2 = a \to c\), \(e_3 = b \to c\). The oriented incidence
matrix is
\[
\boldsymbol{B} =
\begin{array}{c}
\phantom{-}a \\[2pt] \phantom{-}b \\[2pt] \phantom{-}c
\end{array}
\begin{pmatrix}
+1 & +1 & \phantom{+}0 \\
-1 & \phantom{+}0 & +1 \\
\phantom{+}0 & -1 & -1
\end{pmatrix}
\begin{array}{c}
\leftarrow e_1 \\[2pt] \leftarrow e_2 \\[2pt] \leftarrow e_3
\end{array}
\]
Each column sums to zero, as expected. If we reverse the orientation of \(e_1\) to
\(b \to a\), the first column becomes \((-1, +1, 0)^\top\) — only a sign change.
All subsequent constructions (cycle space, Laplacian) will absorb this sign.
Gradient and Divergence: Two Readings of \(\boldsymbol{B}\)
The incidence matrix encodes two fundamental operations from vector calculus, translated
into the discrete setting of graphs. The interpretation depends on whether we apply
\(\boldsymbol{B}\) or its transpose \(\boldsymbol{B}^\top\).
Proposition: Discrete Divergence (\(\boldsymbol{B}\boldsymbol{x}\))
Let \(\boldsymbol{x} \in \mathbb{R}^m\) assign a scalar value \(x_j\) to each edge \(e_j\)
(interpreted as a flow along the oriented direction). Then
\((\boldsymbol{B}\boldsymbol{x})_i\) computes the net outflow
(divergence) at vertex \(v_i\):
\[
(\boldsymbol{B}\boldsymbol{x})_i = \sum_{\substack{e_j \text{ leaves } v_i}} x_j
\;-\; \sum_{\substack{e_j \text{ enters } v_i}} x_j.
\]
Proof:
Expanding using the matrix definition:
\[
(\boldsymbol{B}\boldsymbol{x})_i = \sum_{j=1}^m B_{ij} \, x_j
= \sum_{e_j \text{ leaves } v_i} (+1)\, x_j
\;+\; \sum_{e_j \text{ enters } v_i} (-1)\, x_j
\;+\; \sum_{e_j \text{ not incident to } v_i} 0 \cdot x_j,
\]
which gives the stated formula after dropping the zero terms.
Flow conservation at vertex \(v_i\) — the condition that nothing is created or destroyed —
is therefore \((\boldsymbol{B}\boldsymbol{x})_i = 0\). This is exactly
Kirchhoff's current law from circuit theory, and it is the algebraic
form of the conservation constraint we encountered in
Network Flow: for every internal vertex,
flow in equals flow out.
Proposition: Discrete Gradient (\(\boldsymbol{B}^\top \boldsymbol{y}\))
Let \(\boldsymbol{y} \in \mathbb{R}^n\) assign a scalar value \(y_i\) to each vertex
\(v_i\) (interpreted as a potential). Then
\((\boldsymbol{B}^\top \boldsymbol{y})_j\) computes the potential difference
along edge \(e_j\):
\[
(\boldsymbol{B}^\top \boldsymbol{y})_j = y_{\text{tail}(e_j)} - y_{\text{head}(e_j)}.
\]
This is the discrete gradient of the vertex potential \(\boldsymbol{y}\).
Proof:
The \(j\)-th row of \(\boldsymbol{B}^\top\) is the transpose of the \(j\)-th column
of \(\boldsymbol{B}\), which has \(+1\) at the tail and \(-1\) at the head of \(e_j\).
Therefore
\((\boldsymbol{B}^\top \boldsymbol{y})_j = (+1) \cdot y_{\text{tail}} + (-1) \cdot y_{\text{head}}
= y_{\text{tail}} - y_{\text{head}}\).
Thus \(\boldsymbol{B}^\top\) maps vertex signals to edge signals by taking differences,
and \(\boldsymbol{B}\) maps edge signals to vertex signals by computing net outflows. These
are the discrete analogues of the gradient operator \(\nabla\) and the divergence operator
\(\nabla \cdot\), respectively.
Discrete Calculus and Musical Isomorphisms
The pair \((\boldsymbol{B}^\top, \boldsymbol{B})\) realizes, on a finite graph, the same algebraic structure that appears
in continuous calculus: the gradient maps 0-forms (functions on vertices) to 1-forms (functions on edges), and the
divergence maps 1-forms back to 0-forms. We encountered the
musical isomorphisms \(\sharp\) and \(\flat\), which
translate between vectors and covectors via the inner product. The continuous Laplacian
\(\Delta f = \nabla \cdot (\nabla f)\) composes divergence with gradient — and below we
will see that the graph Laplacian arises from exactly the same composition:
\(\boldsymbol{L} = \boldsymbol{B}\boldsymbol{B}^\top\). The incidence matrix \(\boldsymbol{B}\) is
the discrete skeleton underlying the full machinery of exterior calculus.
Cycle Space and Cut Space
The incidence matrix encodes the graph, and the fundamental theorem of linear algebra
tells us that any matrix carves its domain into two orthogonal pieces: the kernel and
the row space. Applied to \(\boldsymbol{B} \in \mathbb{R}^{n \times m}\), this
decomposition splits the edge space \(\mathbb{R}^m\) into two subspaces with natural
combinatorial interpretations: cycles and cuts.
The Cycle Space
Definition: Cycle Space
The cycle space (or 1-cycle space) of \(G\) is the
null space of the incidence matrix:
\[
Z_1(G) = \ker(\boldsymbol{B}) = \{\boldsymbol{x} \in \mathbb{R}^m : \boldsymbol{B}\boldsymbol{x} = \mathbf{0}\} \;\subset\; \mathbb{R}^m.
\]
A vector \(\boldsymbol{x} \in Z_1(G)\) is called a cycle flow.
The condition \(\boldsymbol{B}\boldsymbol{x} = \mathbf{0}\) says that the net divergence
at every vertex is zero: the flow \(\boldsymbol{x}\) is a closed circulation
with no sources or sinks. This is flow conservation at every vertex simultaneously —
Kirchhoff's law without exceptions.
Note the distinction between two different null spaces associated with
\(\boldsymbol{B}\). The cycle space \(Z_1 = \ker(\boldsymbol{B}) \subset \mathbb{R}^m\)
lives in the edge space and consists of divergence-free flows. The
left null space \(\ker(\boldsymbol{B}^\top) \subset \mathbb{R}^n\) lives in the
vertex space and consists of vectors constant on each connected component
(as we showed: \(\mathbf{1} \in \ker(\boldsymbol{B}^\top)\)). These are fundamentally
different objects in different ambient spaces.
The notation \(Z_1\) is deliberate. In the sequel on
Homology, we will
define \(Z_k = \ker(\partial_k)\) for the boundary operator \(\partial_k\). The graph
case is \(k = 1\): the incidence matrix \(\boldsymbol{B}\), viewed as a map from
1-chains (\(\mathbb{R}^m\)) to 0-chains (\(\mathbb{R}^n\)), plays the role of
\(\partial_1\), and cycle flows are 1-cycles: \(Z_1 = \ker(\partial_1) = \ker(\boldsymbol{B})\).
The Cut Space
Definition: Cut Space
The cut space of \(G\) is the image of \(\boldsymbol{B}^\top\)
viewed as a map from \(\mathbb{R}^n\) to \(\mathbb{R}^m\):
\[
B_1(G) = \operatorname{im}(\boldsymbol{B}^\top) \;\subset\; \mathbb{R}^m.
\]
A vector \(\boldsymbol{z} \in B_1(G)\) is called a potential flow
(or exact flow).
A potential flow \(\boldsymbol{z} = \boldsymbol{B}^\top \boldsymbol{y}\) is one that
arises as the gradient of some vertex potential \(\boldsymbol{y}\). On each edge, the flow
value is simply the potential difference between the endpoints. The name cut
space comes from the special case where \(\boldsymbol{y}\) is the indicator
vector of a vertex subset \(S \subseteq V\) (with \(y_v = 1\) for \(v \in S\) and \(0\)
otherwise): then \(\boldsymbol{B}^\top \boldsymbol{y}\) is supported precisely on the
edges crossing between \(S\) and its complement, with values \(\pm 1\) — a signed
indicator of the edge cut separating \(S\) from \(V \setminus S\). Such flows are
the "trivial" circulations — they are created by a global potential function, not by any
genuine topological cycle in the graph.
A note on notation: in Intro to Homology,
\(B_k = \operatorname{im}(\partial_{k+1})\) will denote the space of \(k\)-boundaries.
For graphs, \(\operatorname{im}(\partial_2) = \{0\}\) (there are no 2-cells), so the
homological \(B_1\) is trivial and no ambiguity arises. The cut space
\(B_1(G) = \operatorname{im}(\boldsymbol{B}^\top)\) is a distinct concept — it consists of
exact 1-forms (gradients of vertex potentials), which in the language of cohomology are
coboundaries. The notational distinction will sharpen once we encounter
simplicial complexes with non-trivial 2-faces, where \(\operatorname{im}(\partial_2) \neq \{0\}\)
and the two roles of "\(B_1\)" diverge.
Orthogonal Decomposition
Theorem: Orthogonal Decomposition of the Edge Space
The edge space of a graph decomposes as a direct sum of orthogonal subspaces:
\[
\mathbb{R}^m = Z_1(G) \;\oplus\; B_1(G) = \ker(\boldsymbol{B}) \;\oplus\; \operatorname{im}(\boldsymbol{B}^\top).
\]
Proof:
By the fundamental theorem of linear algebra
applied to \(\boldsymbol{B}\) with domain \(\mathbb{R}^m\):
\((\operatorname{Row} \boldsymbol{B})^\perp = \ker(\boldsymbol{B})\). Since
\(\operatorname{Row}(\boldsymbol{B}) = \operatorname{im}(\boldsymbol{B}^\top)\), this
reads \(\operatorname{im}(\boldsymbol{B}^\top)^\perp = \ker(\boldsymbol{B})\). In the
finite-dimensional space \(\mathbb{R}^m\), a subspace and its orthogonal complement
give an orthogonal direct sum decomposition of the ambient space, so
\(\mathbb{R}^m = \ker(\boldsymbol{B}) \oplus \operatorname{im}(\boldsymbol{B}^\top)\).
Substituting \(Z_1(G) = \ker(\boldsymbol{B})\) and
\(B_1(G) = \operatorname{im}(\boldsymbol{B}^\top)\) gives the stated decomposition.
Every edge flow can be uniquely written as the sum of a circulation (divergence-free)
and a potential flow (gradient of a vertex function). This is the graph-theoretic analogue
of the Helmholtz decomposition in vector calculus, which decomposes a
vector field into a divergence-free component (curl of something) and a curl-free component
(gradient of something). On a graph, the cycle space plays the role of divergence-free
fields, and the cut space plays the role of curl-free (= exact) fields.
Dimension Counting
The rank-nullity theorem
applied to \(\boldsymbol{B} \in \mathbb{R}^{n \times m}\) gives
\[
\operatorname{rank}(\boldsymbol{B}) + \dim(\ker(\boldsymbol{B})) = m.
\]
Since the cycle space is \(Z_1 = \ker(\boldsymbol{B})\) and the cut space is
\(B_1 = \operatorname{im}(\boldsymbol{B}^\top)\), and since
\(\operatorname{rank}(\boldsymbol{B}) = \operatorname{rank}(\boldsymbol{B}^\top) = \dim(B_1)\),
we need to determine \(\operatorname{rank}(\boldsymbol{B})\).
Theorem: Rank of the Incidence Matrix
Let \(G\) be a graph with \(n\) vertices, \(m\) edges, and \(c\) connected components. Then
\[
\operatorname{rank}(\boldsymbol{B}) = n - c.
\]
Consequently:
\[
\dim(Z_1) = m - n + c, \qquad \dim(B_1) = n - c.
\]
Proof:
The left null space of \(\boldsymbol{B}\) — i.e.,
\(\ker(\boldsymbol{B}^\top) \subset \mathbb{R}^n\) — consists of vectors
\(\boldsymbol{y}\) such that \(\boldsymbol{B}^\top \boldsymbol{y} = \mathbf{0}\).
By Discrete Gradient,
this is equivalent to \(y_{\text{tail}(e_j)} = y_{\text{head}(e_j)}\) for every edge
\(e_j\), i.e., \(\boldsymbol{y}\) takes the same value at any two vertices joined by
an edge. By induction on path length, \(\boldsymbol{y}\) is then constant along any
path, hence constant on each connected component. The space of such vectors is
spanned by the indicator vectors \(\boldsymbol{1}_{C_1}, \ldots, \boldsymbol{1}_{C_c}\)
of the \(c\) connected components, which are linearly independent (their supports
are disjoint). Therefore
\(\dim(\ker(\boldsymbol{B}^\top)) = c\), and by the rank-nullity theorem applied
to \(\boldsymbol{B}^\top \in \mathbb{R}^{m \times n}\):
\[
\operatorname{rank}(\boldsymbol{B}^\top) + \dim(\ker(\boldsymbol{B}^\top)) = n,
\]
giving \(\operatorname{rank}(\boldsymbol{B}) = n - c\). The dimension formulas follow
from \(\dim(Z_1) = m - \operatorname{rank}(\boldsymbol{B}) = m - n + c\)
and \(\dim(B_1) = \operatorname{rank}(\boldsymbol{B}) = n - c\).
Connection to Euler's Formula
For a connected planar graph (\(c = 1\)), the dimension of the cycle space is
\[
\dim(Z_1) = m - n + 1.
\]
By Euler's formula,
\(V - E + F = 2\), so \(F = 2 - V + E = 2 - n + m\), and therefore
\[
\dim(Z_1) = m - n + 1 = F - 1.
\]
The dimension of the cycle space equals the number of bounded faces in
any planar embedding.
This is the algebraic content of Euler's formula. The proof of Euler's formula added
non-tree edges one at a time, each creating a new face and a new independent cycle. We now see that this correspondence is exact: the
non-tree edges form a basis for \(Z_1\), and each basis vector corresponds to a face boundary.
Example: \(K_3\)
For \(K_3\), we have \(n = 3\), \(m = 3\), \(c = 1\). Then
\(\dim(Z_1) = 3 - 3 + 1 = 1\). The single independent cycle is
\(\boldsymbol{x} = (1, -1, 1)^\top\) (using the orientation from our earlier example),
representing the cycle \(a \to b \to c \to a\). The first edge \(e_1 = a \to b\)
and third edge \(e_3 = b \to c\) are traversed in their assigned direction (coefficient
\(+1\)), while the second edge \(e_2 = a \to c\) is traversed backwards (as
\(c \to a\)), giving coefficient \(-1\).
Verification: \(\boldsymbol{B}\boldsymbol{x} =
\begin{pmatrix} +1 & +1 & 0 \\ -1 & 0 & +1 \\ 0 & -1 & -1 \end{pmatrix}
\begin{pmatrix} 1 \\ -1 \\ 1 \end{pmatrix} =
\begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix}\). ✓
Example: \(K_4\)
For \(K_4\), we have \(n = 4\), \(m = 6\), \(c = 1\). Then
\(\dim(Z_1) = 6 - 4 + 1 = 3\), and \(\dim(B_1) = 4 - 1 = 3\). The edge
space \(\mathbb{R}^6\) splits evenly: 3 dimensions of cycles and 3 dimensions
of cuts. In a planar embedding, \(K_4\) has \(F = 4\) faces, and the
3 independent cycles correspond to the 3 bounded triangular faces (\(F - 1 = 3\)).
The Graph Laplacian Revisited
In Graph Laplacians,
the Laplacian was defined as \(\boldsymbol{L} = \boldsymbol{D} - \boldsymbol{A}\),
where \(\boldsymbol{D}\) is the degree matrix and \(\boldsymbol{A}\) the adjacency matrix.
This was the matrix perspective: start with the adjacency structure and construct
a difference operator. We now arrive at the same matrix from the discrete calculus
perspective: compose the gradient with the divergence.
\(\boldsymbol{L} = \boldsymbol{B}\boldsymbol{B}^\top\): Two Roads to One Matrix
Theorem: Laplacian as \(\boldsymbol{B}\boldsymbol{B}^\top\)
Let \(\boldsymbol{B}\) be the oriented incidence matrix of a graph \(G\). Then the
(unnormalized) graph Laplacian satisfies
\[
\boldsymbol{L} = \boldsymbol{B}\boldsymbol{B}^\top = \boldsymbol{D} - \boldsymbol{A},
\]
regardless of which orientation was chosen for \(G\).
Proof:
We compute \((\boldsymbol{B}\boldsymbol{B}^\top)_{ij}\) by summing over edges:
\[
(\boldsymbol{B}\boldsymbol{B}^\top)_{ij} = \sum_{k=1}^{m} B_{ik} \, B_{jk}.
\]
Case \(i = j\): For each edge \(e_k\) incident to \(v_i\), we have
\(B_{ik} = \pm 1\) (depending on direction), so \(B_{ik}^2 = 1\). For edges not
incident to \(v_i\), \(B_{ik} = 0\). Thus
\((\boldsymbol{B}\boldsymbol{B}^\top)_{ii} = \deg(v_i)\).
Case \(i \neq j\), \(\{v_i, v_j\} \in E\): Let \(e_k\) be the edge
connecting \(v_i\) and \(v_j\). One of them is the tail (\(+1\)) and the other is the
head (\(-1\)), so \(B_{ik} \cdot B_{jk} = (+1)(-1) = -1\). For all other edges, at
least one of \(B_{ik}, B_{jk}\) is zero. Thus
\((\boldsymbol{B}\boldsymbol{B}^\top)_{ij} = -1\).
Case \(i \neq j\), \(\{v_i, v_j\} \notin E\): No edge is simultaneously
incident to both \(v_i\) and \(v_j\), so all terms vanish:
\((\boldsymbol{B}\boldsymbol{B}^\top)_{ij} = 0\).
This matches \(L_{ij} = D_{ij} - A_{ij}\) entry by entry. Orientation
independence follows because reversing the orientation of any edge \(e_k\) negates
both \(B_{ik}\) and \(B_{jk}\) simultaneously, leaving their product unchanged.
This is a satisfying convergence: two completely different starting points — the
combinatorial definition \(\boldsymbol{D} - \boldsymbol{A}\) from
Graph Laplacians,
and the discrete calculus factorization \(\boldsymbol{B}\boldsymbol{B}^\top\) from the
incidence matrix — lead to the same matrix. The factorization reveals
why the Laplacian has the structure it does: it is the composition
\(\text{divergence} \circ \text{gradient}\).
Dirichlet Energy Revisited
The factorization \(\boldsymbol{L} = \boldsymbol{B}\boldsymbol{B}^\top\) also clarifies the
Dirichlet energy
from a new perspective. For a vertex signal \(\boldsymbol{y} \in \mathbb{R}^n\):
\[
\boldsymbol{y}^\top \boldsymbol{L} \boldsymbol{y}
= \boldsymbol{y}^\top \boldsymbol{B}\boldsymbol{B}^\top \boldsymbol{y}
= \|\boldsymbol{B}^\top \boldsymbol{y}\|^2
= \sum_{e_j \in E} (y_{\text{tail}(e_j)} - y_{\text{head}(e_j)})^2.
\]
The Dirichlet energy is simply the squared norm of the discrete gradient of
\(\boldsymbol{y}\). It measures how much \(\boldsymbol{y}\) varies across edges — the
total "roughness" of the signal on the graph.
The Laplacian as Discrete \(\Delta\)
In continuous calculus, the Laplacian of a function \(f\) is
\(\Delta f = \nabla \cdot (\nabla f)\) — the divergence of the gradient. The
factorization \(\boldsymbol{L} = \boldsymbol{B}\boldsymbol{B}^\top\) is the exact
discrete parallel: \(\boldsymbol{B}^\top\) is the discrete gradient (mapping vertex
potentials to edge differences) and \(\boldsymbol{B}\) is the discrete divergence
(mapping edge flows to vertex net outflows). Their composition is the discrete Laplacian.
The Hodge Laplacian
The graph Laplacian is a special case of a much larger structure. In the graph setting,
we have a single boundary operator \(\partial_1\) (the incidence matrix
\(\boldsymbol{B}\), viewed as a map from 1-chains to 0-chains), and the Laplacian is
\(\boldsymbol{L}_0 = \partial_1 \partial_1^\top\). The natural generalization to a
simplicial complex — a higher-dimensional combinatorial object equipped
with boundary operators \(\partial_k\) at every dimension — is the following.
Definition: Hodge Laplacian
Let \(K\) be a simplicial complex with boundary operators
\(\partial_k : C_k(K) \to C_{k-1}(K)\), where each chain space \(C_k(K)\) carries
the inner product for which the oriented \(k\)-simplices form an orthonormal basis
(so \(\partial_k^\top\) is the matrix adjoint of \(\partial_k\)). Adopt the
convention \(\partial_0 = 0\) (the trivial map out of \(C_0\)) and
\(\partial_{k+1} = 0\) whenever \(K\) has no \((k+1)\)-simplices. The
\(k\)-th Hodge Laplacian is the operator
\(\boldsymbol{L}_k : C_k(K) \to C_k(K)\) defined by
\[
\boldsymbol{L}_k
\;=\; \partial_{k+1}\partial_{k+1}^\top
\;+\; \partial_k^\top \partial_k.
\]
The two summands are the upper Laplacian
\(L_k^{\mathrm{up}} = \partial_{k+1}\partial_{k+1}^\top\) and the
lower Laplacian \(L_k^{\mathrm{down}} = \partial_k^\top \partial_k\).
The graph Laplacian
is the \(k = 0\) case. For a graph
(a purely 1-dimensional complex), there are no 2-simplices, so \(\partial_2 = 0\) and
the upper term vanishes. The convention \(\partial_0 = 0\) makes
\(\partial_0^\top \partial_0 = 0\) as well, so the lower term vanishes. We are left with
\(\boldsymbol{L}_0 = \partial_1 \partial_1^\top = \boldsymbol{B}\boldsymbol{B}^\top\),
recovering the graph Laplacian exactly.
The structural meaning of the upper/lower decomposition, and the role of the
Hodge Laplacian in higher-dimensional spectral theory, will be developed in the sequel —
once simplicial complexes and their boundary operators are constructed as first-class
objects.
Similarly, the condition \(\partial^2 = 0\) — the cornerstone of homology theory — holds
vacuously in the graph case: with the convention \(\partial_0 = 0\), the composition
\(\partial_0 \circ \partial_1 = 0\) is automatic. In the simplicial setting, the
composition \(\partial_{k-1} \circ \partial_k = 0\) for \(k \geq 2\) becomes a non-trivial
sign-cancellation result with deep consequences. This is the story that lies ahead.
From Graph Neural Networks to Simplicial Neural Networks
In Graph Signal Processing, we
saw that GNN message passing operates on the eigenfunctions of \(\boldsymbol{L}_0\) — the Graph Fourier basis.
This is spectral convolution on vertices, governed by the 0-th Laplacian. But many real-world signals live
on edges (traffic flow on road networks, current in circuits) or even on triangles (flux through mesh faces).
The higher-order Hodge Laplacians \(\boldsymbol{L}_k\) extend spectral analysis to these settings, enabling
Simplicial Neural Networks (SNNs) that perform message passing along \(\partial_k\)-defined adjacencies.
The incidence matrix \(\boldsymbol{B}\) we studied here is the discrete structure that makes this generalization possible:
it is the \(k = 1\) instance of the boundary operator around which the entire theory is built.