Orienting Edges
In Planar Graphs & Euler's Formula, we took a
geometric perspective on graphs embedded in surfaces, which revealed the face structure of plane graphs
and led to Euler's formula for connected ones. 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, namely the cycle space, the cut space, and the graph
Laplacian, are all essentially 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. The Laplacian and the Dirichlet energy use each column twice,
so the two sign flips cancel and neither changes at all. The cycle space and the cut space change only
by flipping the sign of the coordinate belonging to the reversed edge, a relabeling that preserves
their dimensions and their combinatorial meaning. The orientation is a bookkeeping device for the
algebra, not a feature of the graph itself. (Physicists call this kind of structural invariance under
arbitrary auxiliary choices gauge freedom, a perspective that becomes central in
geometric deep learning.)
We can already see a shadow of this principle in the permutations counted in
Combinatorics. Reversing an edge swaps its two
endpoints, and this swap is a transposition, an odd permutation, so it introduces 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.
The Incidence Matrix
With an orientation in hand, we can encode the graph in a matrix. This matrix records exactly which
vertex each edge leaves and which it enters. 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, \\
\phantom{+}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 the transpose gives
\(\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, with rows labeled by the
vertices and columns ordered as \(e_1, e_2, e_3\), 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}
\]
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\), a pure 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 with the definition of \(\boldsymbol{B}\), we obtain
\[
\begin{align*}
(\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,
\end{align*}
\]
which gives the stated formula after dropping the zero terms.
Flow conservation at vertex \(v_i\), the condition that nothing is created or destroyed there, 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, which requires flow in to equal flow out
at every internal vertex.
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_{\operatorname{tail}(e_j)} - y_{\operatorname{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_{\operatorname{tail}} + (-1) \cdot y_{\operatorname{head}}
= y_{\operatorname{tail}} - y_{\operatorname{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
\(\boldsymbol{L} = \boldsymbol{B}\boldsymbol{B}^\top\) arises from the same composition, up to a
sign that we make precise there. Apart from a sign convention, \(\boldsymbol{B}^\top\) is the first
of the coboundary maps on which discrete exterior calculus is built.
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 therefore a closed circulation with no
sources or sinks. This is Kirchhoff's law imposed at every vertex simultaneously, with no exempted
source or sink.
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 the vectors that are constant on each connected component. We have already seen that
\(\mathbf{1}\) lies in it, and the full characterization is proved in
Rank of the Incidence Matrix below.
The two null spaces 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\) up to an overall sign. If an edge
oriented from \(u\) to \(v\) is identified with the oriented simplex \([u, v]\), then
\(\partial_1 [u, v] = [v] - [u]\), whereas the corresponding column of \(\boldsymbol{B}\) has \(+1\) at
\(u\) and \(-1\) at \(v\), so \(\partial_1 = -\boldsymbol{B}\). The sign does not affect kernels, so
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 \(y_v = 0\)
otherwise. Then \(\boldsymbol{B}^\top \boldsymbol{y}\) is supported precisely on the edges crossing
between \(S\) and its complement, where it takes the values \(\pm 1\). The result is a signed indicator
of the edge cut separating \(S\) from \(V \setminus S\). Such flows stand opposite to circulations,
since they are created by a global potential function rather than by any genuine topological cycle in
the graph. The orthogonal decomposition below makes this contrast exact.
A note on notation is in order. 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})\). If
\(\operatorname{im}(\boldsymbol{B}^\top) = \{\mathbf{0}\}\), this identity gives
\(\ker(\boldsymbol{B}) = \mathbb{R}^m\), so there is nothing to prove. Otherwise
\(\operatorname{im}(\boldsymbol{B}^\top)\) has an orthogonal basis by the
Gram-Schmidt process,
so the orthogonal decomposition
writes every vector of \(\mathbb{R}^m\) uniquely as the sum of a vector in
\(\operatorname{im}(\boldsymbol{B}^\top)\) and a vector in
\(\operatorname{im}(\boldsymbol{B}^\top)^\perp = \ker(\boldsymbol{B})\). Thus
\(\mathbb{R}^m = \ker(\boldsymbol{B}) \oplus \operatorname{im}(\boldsymbol{B}^\top)\), with
orthogonal summands. 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})\), this reads
\(\dim(Z_1) = m - \operatorname{rank}(\boldsymbol{B})\). The cut space
\(B_1 = \operatorname{im}(\boldsymbol{B}^\top)\) is the column space of \(\boldsymbol{B}^\top\), so
\(\dim(B_1) = \operatorname{rank}(\boldsymbol{B}^\top)\). It remains to determine these two ranks.
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, \quad \dim(B_1) = n - c.
\]
Proof:
The left null space \(\ker(\boldsymbol{B}^\top) \subset \mathbb{R}^n\) of \(\boldsymbol{B}\)
consists of the vectors \(\boldsymbol{y}\) such that
\(\boldsymbol{B}^\top \boldsymbol{y} = \mathbf{0}\). By
Discrete Gradient, this is
equivalent to \(y_{\operatorname{tail}(e_j)} = y_{\operatorname{head}(e_j)}\) for every edge
\(e_j\), that is, \(\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
\(\mathbf{1}_{C_1}, \ldots, \mathbf{1}_{C_c}\) of the \(c\) connected components, which are
linearly independent (their supports are disjoint).
Therefore \(\dim(\ker(\boldsymbol{B}^\top)) = c\), and the rank-nullity theorem
for \(\boldsymbol{B}^\top \in \mathbb{R}^{m \times n}\) reads
\[
\operatorname{rank}(\boldsymbol{B}^\top) + \dim(\ker(\boldsymbol{B}^\top)) = n,
\]
and hence \(\dim(B_1) = \operatorname{rank}(\boldsymbol{B}^\top) = n - c\).
To pass to \(\boldsymbol{B}\) itself, we use the
Orthogonal Decomposition of the Edge Space.
A basis of \(Z_1\) together with a basis of \(B_1\) spans
\(\mathbb{R}^m\), and it is linearly independent because every vector of
\(\mathbb{R}^m\), including \(\mathbf{0}\), splits uniquely into its two
components. Hence \(\dim(Z_1) + \dim(B_1) = m\), so
\(\dim(Z_1) = m - n + c\), and the rank-nullity identity for
\(\boldsymbol{B}\) gives \(\operatorname{rank}(\boldsymbol{B}) = m - \dim(Z_1) = 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, a connected plane
graph with \(n\) vertices, \(m\) edges, and \(F\) faces satisfies \(n - m + F = 2\), so
\(F = 2 - n + m\), and therefore
\[
\dim(Z_1) = m - n + 1 = F - 1.
\]
The cycle space therefore has one dimension for each bounded face of
any planar embedding.
The identity \(\dim(Z_1) = F - 1\) 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. These cycles have exact algebraic
counterparts. Fix a
spanning tree
\(T\), and for a non-tree edge \(e\), traverse \(e\) in its assigned direction and return along the
unique \(T\)-path between its endpoints. The signed indicator of this closed route (\(+1\) on edges
traversed forward, \(-1\) on edges traversed backward, \(0\) elsewhere) is a cycle flow, since at each
vertex of the route one traversed edge arrives and one departs. These \(m - n + 1\)
fundamental cycles are linearly independent, because each is the only one that is
nonzero on its own non-tree edge, so by the dimension count they form a basis of \(Z_1\).
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 the third edge \(e_3 = b \to c\) are traversed in their assigned direction (coefficient
\(+1\)). The second edge \(e_2 = a \to c\) is traversed backwards (as \(c \to a\)), so its
coefficient is \(-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 boundaries of the 3 bounded triangular faces give 3 independent cycle flows, hence a
basis of \(Z_1\) (\(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, which starts with the adjacency structure and constructs a difference
operator. We now arrive at the same matrix from the discrete calculus perspective, which
composes 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\).
The three cases match \(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.
Two completely different starting points thus lead to the same matrix. The first is the combinatorial
definition \(\boldsymbol{D} - \boldsymbol{A}\) from
Graph Laplacians,
and the second is the discrete calculus factorization \(\boldsymbol{B}\boldsymbol{B}^\top\) from the
incidence matrix. The factorization reveals why the Laplacian has the structure it does, since
it exhibits \(\boldsymbol{L}\) as 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\):
\[
\begin{align*}
\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_{\operatorname{tail}(e_j)} - y_{\operatorname{head}(e_j)})^2.
\end{align*}
\]
The Dirichlet energy is simply the squared norm of the discrete gradient of \(\boldsymbol{y}\). It
measures how much \(\boldsymbol{y}\) varies across edges, that is, the total "roughness" of the signal
on the graph.
The Laplacian as Discrete \(\Delta\)
In continuous calculus, the Laplacian of a function \(f\) is the divergence of its gradient,
\(\Delta f = \nabla \cdot (\nabla f)\), and it is the operator at the heart of
the Laplace equation. The
factorization \(\boldsymbol{L} = \boldsymbol{B}\boldsymbol{B}^\top\) is its discrete parallel. Here
\(\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), and their
composition is the graph Laplacian. One sign needs care. The graph Laplacian is positive semidefinite,
since \(\boldsymbol{y}^\top \boldsymbol{L} \boldsymbol{y} = \|\boldsymbol{B}^\top \boldsymbol{y}\|^2 \geq 0\),
whereas integration by parts gives \(\int f \, \Delta f = -\int \|\nabla f\|^2 \leq 0\) for smooth
\(f\) vanishing outside a bounded set. The discrete divergence \(\boldsymbol{B}\) is exactly the
adjoint of the discrete gradient \(\boldsymbol{B}^\top\), whereas the continuous divergence is minus
the adjoint of the gradient, and this minus sign is the whole difference. The graph Laplacian is
therefore the discrete counterpart of \(-\Delta\).
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 = -\boldsymbol{B}\). A simplicial complex is a
higher-dimensional combinatorial object equipped with boundary operators \(\partial_k\) at every
dimension, and the natural generalization of the graph Laplacian to such a complex 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. Its upper term is
\(\partial_1 \partial_1^\top = \boldsymbol{B}\boldsymbol{B}^\top\), and the convention
\(\partial_0 = 0\) makes the lower term \(\partial_0^\top \partial_0\) vanish. We are left with
\(\boldsymbol{L}_0 = \boldsymbol{B}\boldsymbol{B}^\top\), recovering the graph Laplacian exactly. The
absence of 2-simplices matters one level up. For a graph (a purely 1-dimensional complex),
\(\partial_2 = 0\), so the upper term of \(\boldsymbol{L}_1\) vanishes and
\(\boldsymbol{L}_1 = \partial_1^\top \partial_1 = \boldsymbol{B}^\top\boldsymbol{B}\) is an operator
on edge signals.
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.
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.
From Graph Neural Networks to Simplicial Neural Networks
In Graph Signal Processing,
we saw that spectral graph convolutions filter signals in the basis of eigenvectors of
\(\boldsymbol{L}_0\), which form the Graph Fourier basis, and that many GNNs,
such as graph convolutional networks, are built on this idea. Such convolution acts on vertex
signals and is 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
and enable Simplicial Neural Networks (SNNs) that perform message passing along
\(\partial_k\)-defined adjacencies. The incidence matrix \(\boldsymbol{B}\) studied on this page
makes this generalization possible, because, up to sign, it is the \(k = 1\) instance of the
boundary operator around which the entire theory is built.