There are various definitions of the discrete Laplacian for graphs, differing by sign and scale factor (sometimes one averages over the neighboring vertices, other times one just sums; this makes no difference for a regular graph). The traditional definition of the graph Laplacian, given below, corresponds to the negative continuous Laplacian on a domain with a free boundary.
Let
G
=
(
V
,
E
)
be a graph with vertices
V
and edges
E
. Let
ϕ
:
V
→
R
be a function of the vertices taking values in a ring. Then, the discrete Laplacian
Δ
acting on
ϕ
is defined by
(
Δ
ϕ
)
(
v
)
=
∑
w
:
d
(
w
,
v
)
=
1
[
ϕ
(
v
)
−
ϕ
(
w
)
]
where
d
(
w
,
v
)
is the graph distance between vertices w and v. Thus, this sum is over the nearest neighbors of the vertex v. For a graph with a finite number of edges and vertices, this definition is identical to that of the Laplacian matrix. That is,
ϕ
can be written as a column vector; and so
Δ
ϕ
is the product of the column vector and the Laplacian matrix, while
(
Δ
ϕ
)
(
v
)
is just the v'th entry of the product vector.
If the graph has weighted edges, that is, a weighting function
γ
:
E
→
R
is given, then the definition can be generalized to
(
Δ
γ
ϕ
)
(
v
)
=
∑
w
:
d
(
w
,
v
)
=
1
γ
w
v
[
ϕ
(
v
)
−
ϕ
(
w
)
]
where
γ
w
v
is the weight value on the edge
w
v
∈
E
.
Closely related to the discrete Laplacian is the averaging operator:
(
M
ϕ
)
(
v
)
=
1
deg
v
∑
w
:
d
(
w
,
v
)
=
1
ϕ
(
w
)
.
In addition to considering the connectivity of nodes and edges in a graph, mesh laplace operators take into account the geometry of a surface (e.g. the angles at the nodes). For triangle meshes, for example, different discretizations exist, some of them are an extension of the graph operator, while other approaches are based on the finite element method (see below) and allow for higher order approximations. An overview on some mesh operators and a comparison is given in.
Approximations of the Laplacian, obtained by the finitedifference method or by the finiteelement method, can also be called discrete Laplacians. For example, the Laplacian in two dimensions can be approximated using the fivepoint stencil finitedifference method, resulting in
Δ
f
(
x
,
y
)
≈
f
(
x
−
h
,
y
)
+
f
(
x
+
h
,
y
)
+
f
(
x
,
y
−
h
)
+
f
(
x
,
y
+
h
)
−
4
f
(
x
,
y
)
h
2
,
where the grid size is h in both dimensions, so that the fivepoint stencil of a point (x, y) in the grid is
{
(
x
−
h
,
y
)
,
(
x
,
y
)
,
(
x
+
h
,
y
)
,
(
x
,
y
−
h
)
,
(
x
,
y
+
h
)
}
.
If the grid size h = 1, the result is the negative discrete Laplacian on the graph, which is the square lattice grid. There are no constraints here on the values of the function f(x, y) on the boundary of the lattice grid, thus this is the case of the homogeneous Neumann boundary condition, i.e., free boundary. Other types of boundary conditions, e.g., the homogeneous Dirichlet boundary condition, where f(x, y) = 0 on the boundary of the grid, are rarely used for graph Laplacians, but are common in other applications.
Multidimensional discrete Laplacians on rectangular cuboid regular grids have very special properties, e.g., they are Kronecker sums of onedimensional discrete Laplacians, see Kronecker sum of discrete Laplacians, in which case all its eigenvalues and eigenvectors can be explicitly calculated.
In this approach, the domain is discretized into smaller elements, often triangles or tetrahedra, but other elements such as rectangles or cuboids are possible. The solution space is then approximated using so called formfunctions of a predefined degree. The differential equation containing the Laplace operator is then transformed into a variational formulation, and a system of equations is constructed (linear or eigenvalue problems). The resulting matrices are usually very sparse and can be solved with iterative methods.
Discrete Laplace operator is often used in image processing e.g. in edge detection and motion estimation applications. The discrete Laplacian is defined as the sum of the second derivatives Laplace operator#Coordinate expressions and calculated as sum of differences over the nearest neighbours of the central pixel.
For one, two and threedimensional signals, the discrete Laplacian can be given as convolution with the following kernels:
1D filter:
D
→
x
2
=
[
1
−
2
1
]
,
2D filter:
D
x
y
2
=
[
0
1
0
1
−
4
1
0
1
0
]
.
D
x
y
2
corresponds to the finitedifference formula seen previously. Other approximations include the diagonals:
2D filter:
D
x
y
2
=
[
0.25
0.5
0.25
0.5
−
3
0.5
0.25
0.5
0.25
]
,
3D filter:
D
x
y
z
2
is given by: first plane =
[
0
0
0
0
1
0
0
0
0
]
; second plane =
[
0
1
0
1
−
6
1
0
1
0
]
; third plane =
[
0
0
0
0
1
0
0
0
0
]
.
nD filter: For the element
a
x
1
,
x
2
,
…
,
x
n
of the kernel
D
x
1
,
x
2
,
…
,
x
n
2
,
a
x
1
,
x
2
,
…
,
x
n
=
{
−
2
n
if
s
=
n
,
1
if
s
=
n
−
1
,
0
otherwise,
where
x_{i} is the position (either
−1,
0 or
1) of the element in the kernel in the
ith direction, and
s is the number of directions
i for which
x_{i} = 0.
Note that the nD version, which is based on the graph generalization of the Laplacian, assumes all neighbors to be at an equal distance, and hence leads to the following 2D filter with diagonals included, rather than the version above:
2D filter:
D
x
y
2
=
[
1
1
1
1
−
8
1
1
1
1
]
.
These kernels are deduced by using discrete differential quotients.
In can be shown that the following discrete approximation of the twodimensional Laplacian operator as a convex combination of difference operators
∇
γ
2
=
(
1
−
γ
)
∇
5
2
+
γ
∇
×
2
=
(
1
−
γ
)
[
0
1
0
1
−
4
1
0
1
0
]
+
γ
[
1
/
2
0
1
/
2
0
−
2
0
1
/
2
0
1
/
2
]
for γ ∈ [0, 1] is compatible with discrete scalespace properties, where specifically the value γ = 1/3 gives the best approximation of rotational symmetry. Regarding threedimensional signals, it is shown that the Laplacian operator can be approximated by the twoparameter family of difference operators
∇
γ
1
,
γ
2
2
=
(
1
−
γ
1
−
γ
2
)
∇
7
2
+
γ
1
∇
+
3
2
+
γ
2
∇
×
3
2
)
,
where
(
∇
7
2
f
)
0
,
0
,
0
=
f
−
1
,
0
,
0
+
f
+
1
,
0
,
0
+
f
0
,
−
1
,
0
+
f
0
,
+
1
,
0
+
f
0
,
0
,
−
1
+
f
0
,
0
,
+
1
−
6
f
0
,
0
,
0
,
(
∇
+
3
2
f
)
0
,
0
,
0
=
1
4
(
f
−
1
,
−
1
,
0
+
f
−
1
,
+
1
,
0
+
f
+
1
,
−
1
,
0
+
f
+
1
,
+
1
,
0
+
f
−
1
,
0
,
−
1
+
f
−
1
,
0
,
+
1
+
f
+
1
,
0
,
−
1
+
f
+
1
,
0
,
+
1
+
f
0
,
−
1
,
−
1
+
f
0
,
−
1
,
+
1
+
f
0
,
+
1
,
−
1
+
f
0
,
+
1
,
+
1
−
12
f
0
,
0
,
0
)
,
(
∇
×
3
2
f
)
0
,
0
,
0
=
1
4
(
f
−
1
,
−
1
,
−
1
+
f
−
1
,
−
1
,
+
1
+
f
−
1
,
+
1
,
−
1
+
f
−
1
,
+
1
,
+
1
+
f
+
1
,
−
1
,
−
1
+
f
+
1
,
−
1
,
+
1
+
f
+
1
,
+
1
,
−
1
+
f
+
1
,
+
1
,
+
1
−
8
f
0
,
0
,
0
)
.
The spectrum of the discrete Laplacian is of key interest; since it is a selfadjoint operator, it has a real spectrum. For the convention
Δ
=
I
−
M
, the spectrum lies within
[
0
,
2
]
(as the averaging operator has spectral values in
[
−
1
,
1
]
). The smallest nonzero eigenvalue is denoted
λ
1
and is called the spectral gap. There is also the notion of the spectral radius, commonly taken as the largest eigenvalue.
The eigenvectors don't depend on the convention above (for regular graphs), and are the same as for the averaging operator (as they differ by adding a multiple of the identity), though the eigenvalues differ according to the convention.
For operators that approximate the underlying continuous Laplacian the eigenvalues are a sequence of positive real numbers. The first eigenvalue is zero, if the domain has a boundary and the Neumann boundary condition is used, or if the shape contains no boundary (e.g. the sphere).
If the graph is an infinite square lattice grid, then this definition of the Laplacian can be shown to correspond to the continuous Laplacian in the limit of an infinitely fine grid. Thus, for example, on a onedimensional grid we have
∂
2
F
∂
x
2
=
lim
ϵ
→
0
[
F
(
x
+
ϵ
)
−
F
(
x
)
]
+
[
F
(
x
−
ϵ
)
−
F
(
x
)
]
ϵ
2
.
This definition of the Laplacian is commonly used in numerical analysis and in image processing. In image processing, it is considered to be a type of digital filter, more specifically an edge filter, called the Laplace filter.
Let
P
:
V
→
R
be a potential function defined on the graph. Note that P can be considered to be a multiplicative operator acting diagonally on
ϕ
(
P
ϕ
)
(
v
)
=
P
(
v
)
ϕ
(
v
)
.
Then
H
=
Δ
+
P
is the discrete Schrödinger operator, an analog of the continuous Schrödinger operator.
If the number of edges meeting at a vertex is uniformly bounded, and the potential is bounded, then H is bounded and selfadjoint.
The spectral properties of this Hamiltonian can be studied with Stone's theorem; this is a consequence of the duality between posets and Boolean algebras.
On regular lattices, the operator typically has both travelingwave as well as Anderson localization solutions, depending on whether the potential is periodic or random.
The Green's function of the discrete Schrödinger operator is given in the resolvent formalism by
G
(
v
,
w
;
λ
)
=
⟨
δ
v

1
H
−
λ

δ
w
⟩
where
δ
w
is understood to be the Kronecker delta function on the graph:
δ
w
(
v
)
=
δ
w
v
; that is, it equals 1 if v=w and 0 otherwise.
For fixed
w
∈
V
and
λ
a complex number, the Green's function considered to be a function of v is the unique solution to
(
H
−
λ
)
G
(
v
,
w
;
λ
)
=
δ
w
(
v
)
.
Certain equations involving the discrete Laplacian only have solutions on the simplylaced Dynkin diagrams (all edges multiplicity 1), and are an example of the ADE classification. Specifically, the only positive solutions to the homogeneous equation:
Δ
ϕ
=
ϕ
,
in words,
"Twice any label is the sum of the labels on adjacent vertices,"
are on the extended (affine) ADE Dynkin diagrams, of which there are 2 infinite families (A and D) and 3 exceptions (E). The resulting numbering is unique up to scale, and if the smallest value is set at 1, the other numbers are integers, ranging up to 6.
The ordinary ADE graphs are the only graphs that admit a positive labeling with the following property:
Twice any label minus two is the sum of the labels on adjacent vertices.
In terms of the Laplacian, the positive solutions to the inhomogeneous equation:
Δ
ϕ
=
ϕ
−
2.
The resulting numbering is unique (scale is specified by the "2"), and consists of integers; for E_{8} they range from 58 to 270, and have been observed as early as 1968.