Discrete Laplace operator

Content sourced from Wikipedia, licensed under CC BY-SA 3.0.

The discrete Laplace operator is a way to measure how a value at a node in a graph or grid differs from its neighbors. It plays the same role as the continuous Laplacian in smooth spaces, but it works on discrete structures like networks or pixel grids.

How it works on a graph
- Think of a graph with vertices (nodes) V and edges E. Each node has a number assigned to it, call it phi(vertex).
- At a node v, the discrete Laplacian Delta phi(v) is the sum over all neighboring nodes w of phi(w) minus phi(v). In words: you compare the value at v to the values of its neighbors.
- If the graph has edge weights gamma between nodes, you weight each neighbor’s contribution by gamma and still sum the differences phi(neighbor) − phi(v).
- This operation can be written as a matrix product: Delta phi = L phi, where L is the Laplacian matrix. The diagonal entries of L reflect how connected a node is, and the off-diagonal entries connect neighboring nodes (negative values for neighbors).

Intuition: averaging and diffusion
- The Laplacian measures how a node stands out from its surroundings. If a node’s value is already close to the average of its neighbors, Delta phi(v) is small.
- This idea underlies diffusion: if you simulate heat or information spreading on a graph, you often use an equation like phi_t = -k L phi. Over time, values tend to become more uniform within each connected part of the graph.
- On a graph with multiple disconnected pieces, each piece settles to its own average of the initial values.

From graphs to meshes
- On geometric meshes (like a triangle mesh), there are variants that take geometry into account. One common approach uses cotangent weights to better approximate the Laplace-Beltrami operator on a surface.
- In practice, you still end up with a sparse matrix that represents the discrete Laplacian, often written as L = M^{-1}C, where M is a diagonal matrix of areas (or masses) and C contains the weights from the mesh geometry.

Finite differences on grids
- If you view a grid as a graph, you can approximate the Laplacian with the five-point stencil in two dimensions: the value at a grid point is influenced by its four neighbors (up, down, left, right). The standard formula involves adding the neighbor values and subtracting four times the center value, scaled by the grid spacing.
- This is the discrete version of the continuous Laplacian used in numerical methods for solving partial differential equations.

Boundary conditions and practical notes
- Boundary conditions matter. Neumann (no-flux) boundaries let values near the edge float freely, while Dirichlet boundaries fix the boundary values.
- On infinite or very large grids, the discrete Laplacian has a well-understood spectrum (the set of eigenvalues). For the common sign convention, all eigenvalues are non-negative, and in a simple infinite grid the spectrum lies in a fixed interval. The eigenvectors provide natural modes of diffusion.

Applications
- Image processing: the discrete Laplacian acts as an edge detector and is used in smoothing and sharpening when combined with other filters.
- Machine learning: it helps with clustering and semi-supervised learning on data represented as graphs, by exploiting local neighborhood structure.
- Physics and numerical analysis: it models diffusion, heat flow, and other processes on graphs and grids; it also serves as a building block in simulations on meshes.

In short
- The discrete Laplace operator turns local neighbor differences into a global tool for measuring and evolving values on graphs and grids.
- It’s implemented as a sparse matrix, relates directly to how a node compares to its neighbors, and feeds into many practical algorithms in science and engineering.