Calculus on finite weighted graphs

In mathematics, calculus on finite weighted graphs is a discrete calculus for functions whose domain is the vertex set of a graph with a finite number of vertices and weights associated to the edges. This involves formulating discrete operators on graphs which are analogous to differential operators in calculus, such as graph Laplacians (or discrete Laplace operators) as discrete versions of the Laplacian, and using these operators to formulate differential equations, difference equations, or variational models on graphs which can be interpreted as discrete versions of partial differential equations or continuum variational models. Such equations and models are important tools to mathematically model, analyze, and process discrete information in many different research fields, e.g., image processing, machine learning, and network analysis.

In applications, finite weighted graphs represent a finite number of entities by the graph's vertices, any pairwise relationships between these entities by graph edges, and the significance of a relationship by an edge weight function. Differential equations or difference equations on such graphs can be employed to leverage the graph's structure for tasks such as image segmentation (where the vertices represent pixels and the weighted edges encode pixel similarity based on comparisons of Moore neighborhoods or larger windows), data clustering, data classification, or community detection in a social network (where the vertices represent users of the network, the edges represent links between users, and the weight function indicates the strength of interactions between users).

The main advantage of finite weighted graphs is that by not being restricted to highly regular structures such as discrete regular grids, lattice graphs, or meshes, they can be applied to represent abstract data with irregular interrelationships.

If a finite weighted graph is geometrically embedded in a Euclidean space, i.e., the graph vertices represent points of this space, then it can be interpreted as a discrete approximation of a related nonlocal operator in the continuum setting.

Basic definitions

A finite weighted graph

G

{\displaystyle G}

is defined as a triple

G

=

(

V

,

E

,

w

)

{\displaystyle G=(V,E,w)}

for which

V

=

{

x

1

,

…

,

x

n

}

,

n

∈

N

{\displaystyle V=\{x_{1},\dots ,x_{n}\},n\in \mathbb {N} }

, is a finite set of indices denoted as graph vertices or nodes,

E

⊂

V

×

V

{\displaystyle E\subset V\times V}

is a finite set of (directed) graph edges connecting a subset of vertices,

w

:

E

→

R

{\displaystyle w\colon E\rightarrow \mathbb {R} }

is an edge weight function defined on the edges of the graph.

In a directed graph, each edge

(

x

i

,

x

j

)

∈

E

{\displaystyle (x_{i},x_{j})\in E}

has a start node

x

i

∈

V

{\displaystyle x_{i}\in V}

and an end node

x

j

∈

V

{\displaystyle x_{j}\in V}

. In an undirected graph for every edge

(

x

i

,

x

j

)

{\displaystyle (x_{i},x_{j})}

there exists an edge

(

x

j

,

x

i

)

{\displaystyle (x_{j},x_{i})}

and the weight function is required to be symmetric, i.e.,

w

(

x

i

,

x

j

)

=

w

(

x

j

,

x

i

)

{\displaystyle w(x_{i},x_{j})=w(x_{j},x_{i})}

.[1] On the remainder of this page, the graphs will be assumed to be undirected, unless specifically stated otherwise.