In
mathematics, calculus on finite weighted graphs is a
discrete calculus
Discrete calculus or the calculus of discrete functions, is the mathematical study of ''incremental'' change, in the same way that geometry is the study of shape and algebra is the study of generalizations of arithmetic operations. The word ''ca ...
for functions whose
domain
Domain may refer to:
Mathematics
*Domain of a function, the set of input values for which the (total) function is defined
** Domain of definition of a partial function
**Natural domain of a partial function
**Domain of holomorphy of a function
*Do ...
is the vertex set of a
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
with a finite number of
vertices and weights associated to the
edges
Edge or EDGE may refer to:
Technology Computing
* Edge computing, a network load-balancing system
* Edge device, an entry point to a computer network
* Adobe Edge, a graphical development application
* Microsoft Edge, a web browser developed by ...
. This involves formulating discrete
operators
Operator may refer to:
Mathematics
* A symbol indicating a mathematical operation
* Logical operator or logical connective in mathematical logic
* Operator (mathematics), mapping that acts on elements of a space to produce elements of another sp ...
on graphs which are analogous to differential operators in
calculus
Calculus, originally called infinitesimal calculus or "the calculus of infinitesimals", is the mathematics, mathematical study of continuous change, in the same way that geometry is the study of shape, and algebra is the study of generalizati ...
, such as
graph Laplacians (or
discrete Laplace operator
In mathematics, the discrete Laplace operator is an analog of the continuous Laplace operator, defined so that it has meaning on a graph or a discrete grid. For the case of a finite-dimensional graph (having a finite number of edges and vertices) ...
s) as discrete versions of the
Laplacian
In mathematics, the Laplace operator or Laplacian is a differential operator given by the divergence of the gradient of a scalar function on Euclidean space. It is usually denoted by the symbols \nabla\cdot\nabla, \nabla^2 (where \nabla is ...
, and using these operators to formulate
differential equation
In mathematics, a differential equation is an equation that relates one or more unknown functions and their derivatives. In applications, the functions generally represent physical quantities, the derivatives represent their rates of change, a ...
s,
difference equations
In mathematics, a recurrence relation is an equation according to which the nth term of a sequence of numbers is equal to some combination of the previous terms. Often, only k previous terms of the sequence appear in the equation, for a parameter ...
, or
variational models on graphs which can be interpreted as discrete versions of
partial differential equations
In mathematics, a partial differential equation (PDE) is an equation which imposes relations between the various partial derivatives of a multivariable function.
The function is often thought of as an "unknown" to be solved for, similarly to ...
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
An image is a visual representation of something. It can be two-dimensional, three-dimensional, or somehow otherwise feed into the visual system to convey information. An image can be an artifact, such as a photograph or other two-dimension ...
,
machine learning
Machine learning (ML) is a field of inquiry devoted to understanding and building methods that 'learn', that is, methods that leverage data to improve performance on some set of tasks. It is seen as a part of artificial intelligence.
Machine ...
, and
network analysis Network analysis can refer to:
* Network theory, the analysis of relations through mathematical graphs
** Social network analysis, network theory applied to social relations
* Network analysis (electrical circuits)
A network, in the context of e ...
.
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
In digital image processing and computer vision, image segmentation is the process of partitioning a digital image into multiple image segments, also known as image regions or image objects ( sets of pixels). The goal of segmentation is to simpl ...
(where the vertices represent
pixel
In digital imaging, a pixel (abbreviated px), pel, or picture element is the smallest addressable element in a raster image, or the smallest point in an all points addressable display device.
In most digital display devices, pixels are the s ...
s and the weighted edges encode pixel similarity based on comparisons of
Moore neighborhood
In cellular automata, the Moore neighborhood is defined on a two-dimensional square lattice and is composed of a central cell and the eight cells that surround it.
Name
The neighborhood is named after Edward F. Moore, a pioneer of cellular a ...
s or larger windows),
data clustering
Cluster analysis or clustering is the task of grouping a set of objects in such a way that objects in the same group (called a cluster) are more similar (in some sense) to each other than to those in other groups (clusters). It is a main task of ...
,
data classification, or
community
A community is a social unit (a group of living things) with commonality such as place, norms, religion, values, customs, or identity. Communities may share a sense of place situated in a given geographical area (e.g. a country, villag ...
detection in a
social network
A social network is a social structure made up of a set of social actors (such as individuals or organizations), sets of dyadic ties, and other social interactions between actors. The social network perspective provides a set of methods for ...
(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 grid
A regular grid is a tessellation of ''n''-dimensional Euclidean space by congruent parallelotopes (e.g. bricks).
Its opposite is irregular grid.
Grids of this type appear on graph paper and may be used in finite element analysis, finite volu ...
s,
lattice graph
In graph theory, a lattice graph, mesh graph, or grid graph is a graph whose drawing, embedded in some Euclidean space , forms a regular tiling. This implies that the group of bijective transformations that send the graph to itself is a lat ...
s, 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 mathematics, a nonlocal operator is a mapping which maps functions on a topological space to functions, in such a way that the value of the output function at a given point cannot be determined solely from the values of the input function in ...
in the continuum setting.
Basic definitions
A finite weighted graph
is defined as a triple
for which
*
, is a finite set of indices denoted as graph vertices or nodes,
*
is a finite set of (directed) graph edges connecting a subset of vertices,
*
is an edge weight function defined on the edges of the graph.
In a
directed graph
In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs.
Definition
In formal terms, a directed graph is an ordered pai ...
, each edge
has a start node
and an end node
. In an
undirected graph
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...
for every edge
there exists an edge
and the weight function is required to be symmetric, i.e.,
. On the remainder of this page, the graphs will be assumed to be undirected, unless specifically stated otherwise. Many of the ideas presented on this page can be generalized to directed graphs.
The ''edge weight function''
associates to every edge
a real value
. For both mathematical and application specific reasons, the weight function on the edges is often required to be strictly positive and on this page it will be assumed to be so unless specifically stated otherwise. Generalizations of many of the ideas presented on this page to include negatively weighted edges are possible. Sometimes an extension of the domain of the edge weight function to
is considered (with the resulting function still being called the ''edge weight function'') by setting
whenever
.
In applications each ''graph vertex''
usually represents a single entity in the given data, e.g., elements of a finite data set, pixels in an image, or users in a social network. A ''graph edge'' represents a relationship between two entities, e.g. pairwise interactions or similarity based on comparisons of geometric neighborhoods (for example of pixels in images) or of another feature, with the edge weight encoding the strength of this relationship. Most commonly used weight functions are normalized to map to values between 0 and 1, i.e.,
.
In the following it is assumed that the considered graphs are
Connected graph, connected without
self-loops or
multiple edges
In graph theory, multiple edges (also called parallel edges or a multi-edge), are, in an undirected graph, two or more edges that are incident to the same two vertices, or in a directed graph, two or more edges with both the same tail vertex a ...
between vertices. These assumptions are mostly harmless as in many applications each
connected component of a disconnected graph can be treated as a graph in its own right, each appearance of
(which would be nonzero in the presence of self-loops) appears in the presence of another factor which disappears when
(see
the section on differential graph operators below), and edge weights can encode similar information as multiple edges could.
Neighborhood
A node
is a neighbor of the node
if there exists an edge
.
In terms of notation this relationship can be abbreviated by
, which should be read as "
is a neighbor of
".
Otherwise, if
is not a neighbor of
one writes
.
The
neighborhood of a vertex
is simply the set of neighbors
.
The
degree
Degree may refer to:
As a unit of measurement
* Degree (angle), a unit of angle measurement
** Degree of geographical latitude
** Degree of geographical longitude
* Degree symbol (°), a notation used in science, engineering, and mathemati ...
of a vertex
is the weighted size of its neighborhood:
:
Note that in the special case where
on
(i.e. the graph is
unweighted) we have
.
Space of real vertex functions
Let
be the space of (real) vertex functions.
Since
is a finite set, any vertex function
can be represented as a
-dimensional vector
(where
) and hence the space of vertex functions
can be identified with an
-dimensional Hilbert space:
. The inner product of
is defined as:
:
Furthermore, for any vertex function
the
-norm and
-norm of
are defined as:
:
The
-norm is induced by the inner product.
In applications vertex functions are useful to label the vertices of the nodes. For example, in graph-based data clustering, each node represents a data point and a vertex function is used to identify cluster membership of the nodes.
Space of real edge functions
Analogously to real vertex functions, one can introduce the space of real edge functions
. As any edge function
is defined on a finite set of edges
, it can be represented as a
-dimensional vector
, where
. Hence, the space of edge functions
can be identified as a
-dimensional Hilbert space, i.e.,
.
One special case of an edge function is the ''normalized edge weight function''
introduced above in the
#Basic definitions, section on basic definitions. Similar to that function, any edge function
can be trivially extended to
by setting
if
. The space of those extended edge functions is still denoted by
and can be identified with
, where now
.
The inner product of
is defined as:
:
Additionally, for any edge function
the
-norm and
-norm of
are defined as:
:
The
-norm is induced by the inner product.
If one extends the edge set
in a way such that
than it becomes clear that
because
. This means that each edge function can be identified with a linear matrix operator.
Differential graph operators
An important ingredient in the calculus on finite weighted graphs is the mimicking of standard differential operators from the continuum setting in the discrete setting of finite weighted graphs.
This allows one to translate well-studied tools from mathematics, such as partial differential equations and variational methods, and make them usable in applications which can best be modeled by a graph.
The fundamental concept which makes this translation possible is the graph gradient, a first-order difference operator on graphs. Based on this one can derive higher-order difference operators, e.g., the graph Laplacian.
First-order differential operators
Weighted differences
Let
be a finite weighted graph and let
be a vertex function.
Then the weighted difference (or weighted graph derivative) of
along a directed edge
is
:
For any weighted difference the following properties hold:
*
*
*
Weighted gradient
Based on the notion of weighted differences one defines the weighted gradient operator on graphs
as
:
This is a
linear operator
In mathematics, and more specifically in linear algebra, a linear map (also called a linear mapping, linear transformation, vector space homomorphism, or in some contexts linear function) is a Map (mathematics), mapping V \to W between two vect ...
.
To measure the ''local variation'' of a vertex function
in a vertex
one can restrict the gradient
of
to all directed edges starting in
and using the
-norm of this edge function, i.e.,
:
Weighted divergence
The
adjoint operator
In mathematics, specifically in operator theory, each linear operator A on a Euclidean vector space defines a Hermitian adjoint (or adjoint) operator A^* on that space according to the rule
:\langle Ax,y \rangle = \langle x,A^*y \rangle,
wher ...
of the weighted gradient operator is a linear operator defined by
:
For undirected graphs with a symmetric weight function
the adjoint operator
of a function
at a vertex
has the following form:
:
One can then define the weighted divergence operator on graphs via the adjoint operator as
. The divergence on a graph measures the net outflow of an edge function in each vertex of the graph.
Second-order differential operators
Graph Laplace operator
The weighted graph Laplacian
is a well-studied operator in the graph setting. Mimicking the relationship
of the Laplace operator in the continuum setting, the weighted graph Laplacian can be derived for any vertex
as:
:
Note that one has to assume that the graph
is undirected and has a symmetric weight function
for this representation.
Graph p-Laplace operators
The continuous
-Laplace operator is a second-order differential operator that can be well-translated to finite weighted graphs.
It allows the translation of various partial differential equations, e.g., the heat equation, to the graph setting.
Based on the first-order partial difference operators on graphs one can formally derive a family of weighted graph
-Laplace operators
for
by minimization of the discrete
-Dirichlet energy functional
:
The necessary optimality conditions for a minimizer of the energy functional
lead to the following definition of the graph
-Laplacian:
:
Note that the graph Laplace operator is a special case of the graph
-Laplace operator for
, i.e.,
:
Applications
Calculus on finite weighted graphs is used in a wide range of applications from different fields such as image processing, machine learning, and network analysis.
A non-exhaustive list of tasks in which finite weighted graphs have been employed is:
*
image denoising
Noise reduction is the process of removing noise from a signal. Noise reduction techniques exist for audio and images. Noise reduction algorithms may distort the signal to some degree. Noise rejection is the ability of a circuit to isolate an und ...
*
image segmentation
In digital image processing and computer vision, image segmentation is the process of partitioning a digital image into multiple image segments, also known as image regions or image objects ( sets of pixels). The goal of segmentation is to simpl ...
*
image inpainting
*
tomographic reconstruction
Tomographic reconstruction is a type of multidimensional inverse problem where the challenge is to yield an estimate of a specific system from a finite number of projection (linear algebra), projections. The mathematical basis for tomographic imag ...
*
inverse problem
An inverse problem in science is the process of calculating from a set of observations the causal factors that produced them: for example, calculating an image in X-ray computed tomography, source reconstruction in acoustics, or calculating th ...
s
*
data clustering
Cluster analysis or clustering is the task of grouping a set of objects in such a way that objects in the same group (called a cluster) are more similar (in some sense) to each other than to those in other groups (clusters). It is a main task of ...
*
point cloud
Point or points may refer to:
Places
* Point, Lewis, a peninsula in the Outer Hebrides, Scotland
* Point, Texas, a city in Rains County, Texas, United States
* Point, the NE tip and a ferry terminal of Lismore, Inner Hebrides, Scotland
* Point ...
compression
*
hand-written digit recognition
See also
*
Phase field models on graphs
Phase-field models on graphs are a discrete analogue to phase-field models, defined on a graph. They are used in image analysis (for feature identification) and for the segmentation of social networks.
Graph Ginzburg–Landau functional
For a g ...
Notes
:1.Note that a slightly different definition of ''undirected graph'' is also in use, which considers an undirected edge to be a
two-set
In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example,
:\
is a finite set with five elements. Th ...
(set with two distinct elements)
instead of a pair of
ordered pair
In mathematics, an ordered pair (''a'', ''b'') is a pair of objects. The order in which the objects appear in the pair is significant: the ordered pair (''a'', ''b'') is different from the ordered pair (''b'', ''a'') unless ''a'' = ''b''. (In co ...
s
and
. Here the latter description is needed, as it is required to allow edge functions in
(see
the section about the space of edge functions) to take different values on
and
.
References
Calculus
Graph theory